FunSearch: novas descobertas em matemática e ciências usando LLMs

(deepmind.google)

1 pontos por GN⁺ 2023-12-15 | 1 comentários | Compartilhar no WhatsApp

O FunSearch do Google DeepMind combina um LLM pré-treinado com um avaliador automático para buscar, em forma de código, novas soluções verificáveis para problemas de matemática e ciência da computação
O LLM cria novos programas, o avaliador automático atribui pontuações e, em seguida, programas com pontuação alta voltam ao conjunto, melhorando as soluções por meio de uma iteração evolutiva
No cap set problem, encontrou os maiores cap sets já descobertos até agora em algumas configurações e mostrou desempenho mesmo em escalas difíceis para solucionadores computacionais de ponta existentes
A mesma abordagem também foi aplicada a online bin packing, em que programas ajustados às características dos dados colocaram a mesma quantidade de itens em menos bins do que heurísticas existentes
Como o resultado são programas curtos legíveis por humanos, pesquisadores podem examinar a estrutura das soluções e usá-las em colaboração humano-IA para melhorar a formulação do problema

Ideia básica do FunSearch

FunSearch busca funções escritas em código de computador para encontrar novas soluções em matemática e ciência da computação
O nome vem do fato de pesquisar funções (functions)
Como LLMs podem gerar informações incorretas, o FunSearch combina o LLM, que faz propostas criativas, com um avaliador (evaluator) automático para filtrar ideias erradas
É o primeiro caso de uso de um LLM para produzir novas descobertas em problemas científicos e matemáticos abertos e difíceis

Estrutura de iteração evolutiva

Primeiro, o usuário escreve a descrição do problema em forma de código
- Incluindo o procedimento para avaliar o programa
- E também um programa-semente para inicializar o conjunto de programas
Em cada iteração, parte do conjunto atual de programas é fornecida ao LLM
- O LLM gera novos programas com base nos programas existentes
- Os novos programas passam por execução e avaliação automáticas
- Programas com pontuação alta são adicionados novamente ao banco de dados de programas
O usuário pode obter a qualquer momento o programa de maior pontuação encontrado até então
O FunSearch usou o Google PaLM 2, mas também é compatível com outros LLMs treinados em código
A estrutura de busca também foi reforçada para lidar com problemas combinatórios difíceis
- Começa com conhecimento geral sobre o problema e se concentra nas ideias centrais necessárias para novas descobertas
- Aumenta a diversidade de ideias para evitar estagnação
- Executa o processo evolutivo em paralelo para aumentar a eficiência

Resultados no cap set problem

A primeira aplicação foi o cap set problem, que há décadas desafia matemáticos de várias áreas de pesquisa
O problema consiste em encontrar o tamanho máximo de um cap set, isto é, um conjunto de pontos em uma grade de alta dimensão no qual nenhum trio de pontos esteja na mesma reta
Ele também serve como modelo para outros problemas de combinatória extremal (extremal combinatorics)
Como o número de casos possíveis rapidamente ultrapassa o número de átomos no universo, o cálculo por força bruta não funciona
O FunSearch gerou soluções em forma de programa e encontrou, em algumas configurações, os maiores cap sets já descobertos até hoje
Esse resultado representa o maior aumento no tamanho de cap sets dos últimos 20 anos e mostrou desempenho superior mesmo em regiões de escala além da capacidade atual de solucionadores computacionais de ponta
Isso mostrou que é possível superar resultados anteriores em problemas combinatórios nos quais é difícil construir intuição, e pode abrir caminho para problemas teóricos semelhantes em combinatória e áreas como teoria da comunicação

Programas curtos interpretáveis por humanos

O FunSearch não é uma caixa-preta que apenas devolve uma lista de respostas; ele gera programas que mostram como a solução foi construída
Isso também se conecta ao modo geral como a ciência explica novas descobertas ou fenômenos por meio do processo que os gera
O FunSearch favorece soluções representadas por programas compactos com baixa complexidade de Kolmogorov
- A complexidade de Kolmogorov é o comprimento do menor programa de computador capaz de produzir a solução
- Programas curtos conseguem descrever objetos muito grandes, o que ajuda a escalar para grandes problemas do tipo procurar uma agulha no palheiro
- A saída do programa é mais fácil de entender para pesquisadores
Em alguns códigos de saída com alta pontuação, foram observadas simetrias interessantes, e com base nisso a formulação do problema foi refinada para obter soluções melhores
Jordan Ellenberg disse que o FunSearch oferece “um mecanismo totalmente novo para desenvolver estratégias de ataque” e que as soluções geradas são conceitualmente muito mais ricas do que uma lista de números

Aplicação em online bin packing

O FunSearch também foi aplicado a bin packing, um problema prático de ciência da computação
Bin packing é o problema de colocar itens de tamanhos diferentes no menor número possível de bins
Exemplos de aplicação no mundo real incluem carregamento de contêineres e alocação de tarefas computacionais em datacenters para reduzir custos
O online bin packing costuma ser tratado com heurísticas baseadas na experiência humana
- Pode ser difícil encontrar um conjunto de regras para cada situação específica, com diferentes tamanhos, tempos e capacidades
Mesmo sendo muito diferente do cap set problem, o FunSearch foi configurado com facilidade e criou programas ajustados automaticamente às características dos dados
Os programas gerados colocaram a mesma quantidade de itens em menos bins do que as heurísticas existentes
Outras abordagens de IA, como redes neurais ou aprendizado por reforço, também podem ser eficazes em problemas combinatórios difíceis, mas podem exigir muitos recursos para implantação
Como o FunSearch produz código fácil de inspecionar e implantar, ele pode gerar soluções em um formato que pode ser incorporado a diversos sistemas industriais reais

Atualização e expansão em 2024

Um relatório no arXiv, publicado em dezembro de 2024, mostra que a abordagem do FunSearch pode ser usada para ampliar o desempenho humano em programação competitiva combinatória
Competições tradicionais de programação, como o Codeforces, exigem soluções completas para problemas clássicos de algoritmos dentro de limites de tempo e memória
Competições combinatórias lidam com problemas complexos em que não há uma única resposta correta, mas sim a melhor solução aproximada possível
Essa abordagem pode produzir soluções melhores do que aquelas encontradas por participantes do percentil mais alto
Ela usa uma estrutura colaborativa em que programadores humanos escrevem o backbone do código da solução, e o LLM evolui de forma criativa as funções que o controlam
Com a melhora dos LLMs gerais, deixou de ser necessário um modelo especializado em código, e a abordagem pode ser usada com base no Gemini 1.5 Flash
Além da programação competitiva, o FunSearch também foi usado para encontrar maneiras de otimizar melhor funções em frameworks de otimização bayesiana

Direção das descobertas baseadas em LLM

O FunSearch mostra que, ao incluir mecanismos para conter as alucinações dos LLMs, eles podem ser usados não apenas para novas descobertas matemáticas, mas também para gerar soluções potenciais para problemas importantes do mundo real
Em problemas antigos ou novos da ciência e da indústria, pode se tornar comum gerar algoritmos eficazes e personalizados por meio de abordagens baseadas em LLM
O FunSearch pode melhorar junto com o avanço geral dos LLMs e deve se expandir para ampliar suas capacidades em diversos problemas científicos e de engenharia

1 comentários

GN⁺ 2023-12-15

Opiniões no Hacker News

Fico curioso sobre o quanto os LLMs são necessários aqui
Pelo que parece, o papel do LLM é gerar algo plausível, como uma função Python que siga uma determinada assinatura de tipos
Mas, mesmo sem um LLM, deveria ser possível criar funções Python aleatórias e válidas que satisfaçam uma determinada assinatura de tipos. Seria o mesmo tipo de exercício que [1], só que tendo como alvo uma linguagem muito mais complexa; e talvez uma linguagem restrita fosse até mais fácil de usar. Imagino que abordagens como PushGP [2] também poderiam funcionar
As perguntas são: (1) qual é o valor agregado do LLM aqui, se ele reduz muito o número de avaliações necessárias para convergir e, se sim, como; (2) se outras técnicas de programação genética são menos competitivas no mesmo problema e produzem soluções com menor aptidão; (3) se a programação genética mais tradicional alcançar aptidão semelhante, qual é a diferença de custo computacional incluindo o custo de treinamento do LLM
[1] http://www.davidmontana.net/papers/stgp.pdf
[2] https://faculty.hampshire.edu/lspector/push.html
- O espaço de estados de programas executáveis é muito maior do que o de programas úteis
  Não basta ter macacos e máquinas de escrever; a razão para usar Palm2 aqui é que os candidatos precisam ser plausíveis, não aleatórios. A ideia é não desperdiçar tempo com programas sem sentido
  Além disso, algoritmos genéticos baseados em geração de programas aleatórios têm um problema enorme de cold start. Se a aptidão de todos os candidatos for 0, é bem provável que não haja progresso no início — e talvez nem até o fim
- A função descoberta está aqui: https://github.com/google-deepmind/funsearch/blob/main/cap_s...
  Não sou muito familiarizado com algoritmos genéticos, mas não acho que algo desse nível estaria fora do alcance deles. Dito isso, eu ficaria surpreso se alguém já tivesse tentado bastante isso na prática
  Por outro lado, como se vê no Apêndice A.2 do artigo, uma abordagem genética sem LLM provavelmente exigiria mais projeto manual do que a abordagem com LLM
- Algoritmos genéticos acabam criando muitos programas sem sentido, mesmo com restrições. Com esforço suficiente, provavelmente dá para fazer com que a maioria seja sintaticamente correta, mas só isso
  A diferença que o LLM faz aqui é limitar, em grande parte, o espaço possível de mutações a programas semanticamente plausíveis
  Quanto ao ponto 3, um LLM treinado é útil para muitos propósitos, então, se o custo de treiná-lo do zero for amortizado, ele não é tão grande. Pode haver um custo adicional para ajustar o modelo ao framework FunSearch, mas o custo de fine-tuning é relativamente baixo. Usá-lo nesse framework provavelmente traz vantagem em relação a usar apenas programação genética
- Síntese indutiva de programas ficou praticamente parada por décadas porque o espaço de busca é grande demais. Era difícil ir além de programas muito triviais
  LLMs reduzem bastante o espaço de busca e, claro, muitas vezes o reduzem de forma errada, mas depois é possível aplicar síntese indutiva de programas para refinar e testar. Pelo que se sabe hoje, esse tipo de abordagem é impossível sem LLMs. Mesmo em casos triviais, você acabaria testando bilhões de programas completamente sem sentido
- Eu achava que descida de gradiente estocástica e LLMs convergiam muito mais rápido do que programação genética. Com certeza são muito mais rápidos do que busca aleatória
O contexto importante é que essa descoberta mostrou que um certo número em combinatória não está mais no intervalo conhecido no ano passado, de 2,218 a 2,756, mas agora entre 2,2202 e 2,756
A melhoria veio não tanto de uma prova matemática centrada em lógica, mas da descoberta de sequências específicas com propriedades especiais. Isso não quer dizer que não seja rigoroso
É uma forma interessante e provavelmente útil de gerar exemplos e, na prática, está mais próxima de um algoritmo genético com LLM
Comentário de Subbarao relacionado a “self-play”: https://twitter.com/rao2z/status/1728121216479949048
Segundo o texto, o FunSearch usa um método evolutivo movido por LLM para promover e desenvolver ideias com pontuação alta. Essas ideias têm a forma de programas de computador, então podem ser executadas e avaliadas automaticamente
O usuário escreve a descrição do problema em forma de código. Essa descrição inclui um procedimento para avaliar o programa e um programa semente para inicializar o pool de programas
A cada iteração, o FunSearch seleciona alguns programas do pool atual, o LLM os expande de forma criativa para criar novos programas, e os novos programas são avaliados automaticamente. Os melhores são adicionados de volta ao pool existente, criando um loop de autoaperfeiçoamento
Em buscas na web, pplx.ai e phind.com são usados de forma parecida como avaliadores. Você faz uma pergunta, vê quais referências e links da web eles trazem e então refina a pergunta ou faz perguntas de acompanhamento para puxar materiais mais profundos ou diferentes. Funciona melhor para encontrar joias escondidas do que ficar vasculhando reddit ou Google
Também há muito conteúdo excelente no Tech Twitter, então, agora que o Grok foi aberto a todos, espero que ele seja usado em pesquisa
https://twitter.com/gfodor/status/1735348301812383906
Há quem diga: “Se a DeepMind provou de forma definitiva que redes neurais podem gerar conhecimento realmente novo, então esta é a descoberta mais importante desde o fogo”
Se isso for verdade, fico me perguntando por que nem todo mundo está falando sobre isso. É impressionante que tenham conseguido fazer isso com o PaLM 2, que é menos avançado que o GPT-4 ou o Gemini. O que as próximas gerações de modelos poderão fazer usando esse método deve ser algo enorme
- Aqui, o trabalho pesado está sendo feito por um algoritmo evolutivo
  O LLM basicamente substitui um operador de mutação aleatória e recebe um pedido do tipo “sugira uma modificação razoável para estas 20 linhas de Python”. Parece generoso atribuir à rede neural o mérito pela geração de conhecimento
  Além disso, para além da necessidade de uma estrutura em que “criar é difícil e avaliar é fácil”, isso depende muito da natureza do problema. A parte que se quer evoluir precisa poder ser decomposta em uma única função Python bem curta
- Eu disse “uau!” em voz alta
  Um LLM conseguir descobrir uma nova solução para geometria de alta dimensão, área sem avanço havia 20 anos, vai muito além de simplesmente juntar de forma plausível trechos plagiados dos dados de treinamento
  Isso sugere que há uma profundidade oculta nas capacidades dos LLMs, desde que se descubra como fazer o prompt e a avaliação corretamente
  É um resultado que quebrou bastante as expectativas. Não sabemos que descoberta pode estar escondida por trás do próximo prompt e da próxima seed aleatória
- Redes neurais já eram capazes de gerar “novo conhecimento” há muito tempo
  O mesmo vale para LLMs: https://www.nature.com/articles/s41587-022-01618-2
- Segundo o artigo, atualmente o FunSearch funciona melhor em problemas com as seguintes características
  a) há um avaliador eficiente, b) há feedback de pontuação rico que quantifica o grau de melhoria, ou seja, não é um sinal binário, c) é possível fornecer um esqueleto com uma parte isolada a ser evoluída
  Por exemplo, o problema de gerar provas de teoremas fica fora desse escopo, porque não está claro como fornecer um sinal de pontuação suficientemente rico
- Este exemplo parece relativamente limitado a encontrar novos algoritmos ou funções
  É um ótimo trabalho, mas não parece estar no mesmo nível da descoberta do fogo, nem de muitas coisas que vieram depois, como a eletricidade
Em resumo, dado um template/esqueleto de programa e uma função de fitness, eles geram uma população de programas com um LLM e usam prompts que criam um novo programa a partir de outras k versões; descobriram que k=2 funciona bem. É algo meio biológico. Em seguida, executam os programas sobre as entradas, atribuem pontuações com a função de fitness e usam um modelo de ilhas para a evolução
Em princípio, imagino que o prompt tenha uma aparência parecida com isto
def foo_v1(a, b): ...
def foo_v2(a, b): ...
# Crie uma nova função usando foo_v1 e foo_v2. Você só pode alterar o que está dentro das chaves duplas, como em {{ THIS }}
def foo(a, b): return a + {{}}
Se foram apenas cerca de 1e6 chamadas ao LLM para obter um novo resultado, é um número impressionantemente baixo. Também dizem que a avaliação/pontuação leva alguns minutos
Aqui vale pensar no trade-off entre profundidade e largura. Isso se conecta à latência e à vazão ao pontuar programas individuais e populações. E se fosse usada memoização para todos os programas? Penso se não seria possível manter a função de perda multidimensional, com uma dimensão para cada entrada ou bucket de entradas, de modo a primeiro encontrar populações de programas que se saem bem em regiões diferentes e depois combiná-las
Também fico curioso se havia conhecimento prévio sobre o quão raros são os cap sets. Gostaria de saber se já tinham havido tentativas computacionais anteriores sem sucesso; de qualquer forma, é muito legal
Parafraseando o post do Twitter / X, daqui para frente isso só vai melhorar
Ou seja, as capacidades da IA estão aumentando monotonicamente, e vêm aumentando há décadas; neste caso, a capacidade se autoaperfeiçoa recursivamente. Já vejo, pessoalmente, um ganho de cerca de 20% a 30% na produtividade de programação com autocompletar por IA, refatoração baseada em IA e diffs de code review gerados automaticamente por IA nos comentários
Parece que a IA entrou em uma fase parecida com a da Intel nos anos 90. Para deixar o código 2 vezes mais rápido, bastava esperar a próxima revisão dos CPUs da Intel. Agora, os modelos de IA cumprem esse papel. Se você conecta partes de um fluxo de negócios, como programação, suporte ao cliente e triagem de bugs, a sistemas de LLM, a “melhoria” do sistema passa a ser algo como trocar o nome do modelo
Depois da integração inicial, com esforço mínimo, dá para esperar que, nos próximos anos, “tudo fique magicamente um pouco melhor”
- Do meu ponto de vista, não há nada assim no post do blog nem no artigo linkado
  Em particular, eles não compararam resultados com e sem LLM. Pelo que entendi, o artigo mostra um resultado de programação genética em que um LLM gera funções kernel em Python que provavelmente seguem uma determinada assinatura de tipos. Um LLM não é indispensável para essa tarefa
  Portanto, continua em aberto a questão de se o LLM, especificamente, está fazendo algo especial aqui
Um dos problemas abordados foi o problema do cap set
https://en.m.wikipedia.org/wiki/Cap_set
Esse problema consiste em encontrar, em uma grade de alta dimensão, o maior conjunto de pontos em que três pontos não estejam em uma mesma linha reta, isto é, um cap set. Ele é importante porque serve como modelo para outros problemas de combinatória extremal. A combinatória extremal estuda quão grandes ou pequenas podem ser coleções de números, grafos ou outros objetos. Cálculo por força bruta não funciona nesse problema, porque o número de possibilidades a considerar rapidamente supera o número de átomos no universo
O FunSearch gerou soluções na forma de programas e, em algumas configurações, encontrou o maior cap set já descoberto até agora. Esse foi o maior aumento no tamanho de cap sets nos últimos 20 anos. Além disso, como esse problema cresce para escalas muito além da capacidade dos solvers computacionais de ponta atuais, o FunSearch superou esses solvers
Fico curioso sobre como integrar raciocínio simbólico a LLMs, ou se isso é possível
- É exatamente isso que estamos fazendo. Acho que não só é possível, como é necessário para aplicações que vão além da geração por tentativa e erro
- Também parece haver um certo paralelo com as ideias neuro-simbólicas que o Lab V2 da ASU está explorando
- LEAN
O artigo recente da FunSearch, da DeepMind, destacou o uso de modelos de linguagem grandes pré-treinados para gerar melhorias de código
Curiosamente, embora o LLM principal fosse o Codey, baseado na família de modelos PaLM2, os materiais suplementares também mencionam o StarCoder, um LLM de código aberto
No entanto, o repositório GitHub da FunSearch não inclui essa implementação de LLM. Por exemplo, sampler.py contém o seguinte código
```
class LLM:  
"""Language model that predicts continuation of provided source code."""

def __init__(self, samples_per_prompt: int) -> None:  
self._samples_per_prompt = samples_per_prompt

def _draw_sample(self, prompt: str) -> str:  
"""Returns a predicted continuation of `prompt`."""  
raise NotImplementedError('Must provide a language model.')  
```
Esse código mostra que é necessária uma implementação externa de LLM. Se eles conseguiram usar o StarCoder com sucesso, é surpreendente que não haja um guia de integração ou uma implementação básica para ele ou para um LLM de código aberto semelhante. Se houvesse esse conteúdo, a reprodutibilidade e a acessibilidade da pesquisa teriam melhorado bastante
Independentemente de isso ser ou não novo conhecimento verificável, é um estudo de caso interessante quando pensamos no problema de limitar o acesso à IA por meio do tamanho do modelo ou de outros mecanismos regulatórios
Essas restrições dão uma vantagem injusta a empresas que podem descobrir novos conhecimentos ou leis da natureza e monetizá-los sem compartilhá-los

FunSearch: novas descobertas em matemática e ciências usando LLMs

Ideia básica do FunSearch

Estrutura de iteração evolutiva

Resultados no cap set problem

Programas curtos interpretáveis por humanos

Aplicação em online bin packing

Atualização e expansão em 2024

Direção das descobertas baseadas em LLM

Leituras relacionadas

1 comentários

Opiniões no Hacker News