Usando grandes modelos para resolver problemas que preocupam os matemáticos há mais de 60 anos, os resultados mais recentes do Google DeepMind foram publicados na Nature.Pushmeet Kohli, um dos autores e vice-presidente de pesquisa do Google DeepMind, disse:Este esquema não estará nos dados de treinamento e nem mesmo será conhecido pelos humanos antes.

Essa tecnologia é chamada FunSearch, onde Fun é a abreviatura de função.

Aproveite grandes modelos para resolver desafios científicos de longa data, gerando novas informações verificáveis ​​e valiosas* que não existiam antes.

Na interpretação da notícia que acompanha o artigo da Nature, o responsável pela DeepMind afirmou que “a forma como utilizamos grandes modelos é como um motor de criatividade”.

Esta é a primeira vez que alguém mostra que sistemas baseados em grandes modelos podem superar a cognição de matemáticos e cientistas da computação.

Não só é novo, como é mais eficaz do que qualquer outra coisa que existe hoje.

Em resposta a esta conquista, alguns internautas lamentaram:

Se isto for verdade, é a descoberta mais importante da humanidade desde o incêndio.

Então, quais problemas o FunSearch resolve?

Encontre melhores soluções para problemas NP-difíceis

DeepMind demonstra especificamente dois tipos de problemas, ambos problemas NP-difíceis.

De acordo com a comunidade acadêmica, não existe e talvez nunca exista um algoritmo que possa encontrar soluções exatas para problemas NP-difíceis em tempo polinomial em todas as circunstâncias.

Diante de tais problemas, os pesquisadores geralmente buscam soluções aproximadas ou algoritmos eficientes e adequados para situações específicas.

Específico do FunSearch, o primeiro tipo de problema NP-difícil que ele resolve é o problema Capset, que é um tipo de problema de conjunto de limite superior. Sua descrição é a seguinte:

Existem n pontos equidistantes em cada dimensão de um espaço n-dimensional (n^n no total, por exemplo, 3 dimensões são 3*3*3). Encontre tantos pontos quanto possível para formar um conjunto. É necessário que quaisquer 3 pontos do conjunto não sejam colineares. Quantos pontos existem no máximo nesse conjunto?

Se parece um pouco difícil de entender, você também pode aprender sobre o antecessor do problema Capset – um jogo de cartas inventado pela geneticista Marsha Falco na década de 1970.

Há um total de 81 cartas neste jogo de cartas. Cada cartão tem de 1 a 3 padrões de cores. As cores, formas e sombras dos padrões no mesmo cartão são exatamente iguais.

Este deck tem um total de 3 cores, 3 formas e 3 tonalidades. Incluindo o número de padrões, há um total de 3*3*3*3=81 cartas. Os jogadores precisam virar algumas cartas para encontrar a combinação especial de 3 cartas.

Se a forma específica desta “combinação especial” for expressa em forma geométrica discreta, obteremos o problema de Capset.

O problema de Capset também nasceu na década de 1970, proposto pelo matemático Ron Graham, da Universidade de Oxford, mas os primeiros resultados importantes só apareceram na década de 1990.

Em 2007, Terence Tao mencionou em uma postagem de blog que este era seu problema de matemática aberto favorito.

Antes do surgimento do FunSearch, o avanço mais significativo no problema de Capset foi proposto pelo matemático americano Jordan Ellenberg e pelo matemático holandês Dion Gijswijt em 2016.

Através do método polinomial, Ellenberg e Gijswijt reduziram o limite supremo da solução deste tipo de problema para 2,756^n quando n>6 (o conjunto máximo pode ser encontrado com precisão quando n≤6).

Além disso, quando n>6, o número mais recente do limite inferior é 2,218^n, proposto por Fred Tyrrell, um estudante de doutorado na Universidade de Bristol em 2022.

Mas este limite inferior só existe em teoria - quando n=8, existem apenas 496 pontos no maior conjunto que os humanos podem construir e, de acordo com a conclusão de Tyrrell, o número de pontos não deve ser inferior a 585,7.

O FunSearch expandiu o tamanho do conjunto para 512 pontos - embora ainda haja uma lacuna em relação ao valor teórico, ainda é considerado o avanço mais significativo nesta questão em 20 anos.

Ao mesmo tempo, o limite inferior do tamanho do conjunto Capset também foi aumentado para 2,2202^n pelo FunSearch.

A segunda categoria são os problemas de boxe online:

Suponha que haja um conjunto de contêineres padrão com capacidade C e uma sequência de n itens (o tamanho dos itens não excede C). Esses itens chegam em uma determinada ordem.

“Online” significa que o operador não pode ver todos os itens com antecedência, mas deve decidir imediatamente em qual contêiner carregar os itens quando eles chegarem.

O objetivo final é manter o número de contêineres utilizados o menor possível.

O problema do binning online atraiu extensas pesquisas desde a década de 1970, e as primeiras remontam ao problema de layout estudado por Gauss em 1831.

Após quase 200 anos de pesquisa, ainda não existe uma teoria madura e um método de cálculo numérico eficaz.

Algoritmos gananciosos tradicionalmente usados ​​incluem FirstFit e BestFit:

FirstFit significa colocar cada item na primeira caixa que possa acomodá-lo. BestFit coloca cada item na caixa que pode acomodá-lo e tem o menor espaço restante na caixa.

FunSearch propôs um novo algoritmo, que reduziu significativamente o número de contêineres usados ​​nos conjuntos de dados de teste OR e Weibull.

Especialmente quando o número de itens no conjunto de teste atinge 100.000, a solução encontrada pelo FunSearch consome apenas 0,03% mais contêineres do que o limite inferior teórico.

(Os dados na tabela abaixo representam a diferença do limite inferior teórico. Quanto menor o número, melhor o desempenho)

Então, como o FunSearch é implementado?

Procure por “programa” em vez de “respostas”

No geral, o fluxo de trabalho do FunSearch é um processo iterativo, e o núcleo é procurar programas que possam resolver o problema, e não a resposta à pergunta em si.

A pesquisa é exatamente o que a DeepMind vem explorando desde o AlphaGo.

O cofundador Shane Legg explicou certa vez em uma entrevista:

De onde veio a chave "Etapa 37" na derrota de Lee Sedol pelo AlphaGo? Não a partir de dados de jogos humanos, mas de uma busca no espaço de probabilidade.

Os grandes modelos atuais apenas imitam e misturam diferentes dados de treinamento. Para gerar verdadeira criatividade e superar a arquitetura atual, ela precisa ser aliada à busca.

Voltando à última conquista do FunSearch, existe uma biblioteca de programas no sistema. A cada iteração, o sistema irá procurar o programa inicial e inserir o modelo grande (PaLM2 é usado para o experimento, outros códigos também são compatíveis, desde que o suportem).

O grande modelo é construído nesta base para gerar novos programas e entregue ao sistema de avaliação automática. O programa com maior pontuação será adicionado à biblioteca de programas, realizando assim uma autocirculação.

Entre eles, o sistema de avaliação gera casos de teste com base nas perguntas do usuário e então determina se a saída do programa candidato está correta.

Dependendo da complexidade, os métodos para determinar a correção incluem a inspeção direta do valor de saída ou a chamada de funções relacionadas.

Ao mesmo tempo, o sistema de avaliação também está equipado com lógica tolerante a falhas para evitar que o tempo limite e outros problemas afetem o processo geral.

Finalmente, o sistema dará uma pontuação geral com base no comportamento do programa candidato nesses casos de teste, fornecendo uma base para a geração de resultados e subsequentes atualizações da biblioteca do programa.

Jordan Ellenberg, da Universidade de Wisconsin-Madison, coautor do artigo, acredita que uma característica importante do FunSearch é que as pessoas podem ver as soluções bem-sucedidas geradas pela IA e aprender com elas, o que é completamente diferente do modelo anterior de caixa preta de IA.

O mais entusiasmante para mim é construir novos modelos de colaboração homem-máquina, que espero utilizar não como um substituto para os matemáticos humanos, mas como um multiplicador de forças.