FunSearch (abreviação de busca no espaço de funções) é um método de inteligência artificial desenvolvido pelo Google DeepMind para descobrir programas de computador que resolvem problemas matemáticos e algorítmicos. Ele combina um grande modelo de linguagem com um avaliador automatizado e um procedimento de busca evolucionária, gerando programas candidatos, pontuando-os e usando programas de alto desempenho para produzir novos candidatos. O sistema foi anunciado em 2023, com um artigo publicado na revista Nature, e foi aplicado a problemas em combinatória extremal e empacotamento de bins online.
FunSearch representa uma mudança na forma como grandes modelos de linguagem são usados para descoberta. Em vez de gerar respostas diretamente, ele enquadra um problema como uma busca sobre programas de computador, permitindo que o modelo proponha código que é então rigorosamente testado. Essa abordagem aproveita as capacidades generativas de modelos como os usados em IA generativa, garantindo que as saídas sejam verificáveis e frequentemente interpretáveis por pesquisadores.
Método
O FunSearch opera gerando e avaliando programas candidatos de forma iterativa. O usuário fornece uma especificação do problema, uma função de avaliação e um esqueleto inicial de programa. A cada etapa, o sistema amostra programas existentes de um banco de dados, favorecendo aqueles com pontuações mais altas, e constrói um prompt para um grande modelo de linguagem pré-treinado. O modelo gera um programa modificado, que é então executado e pontuado pelo avaliador. Programas válidos são adicionados de volta ao banco de dados, permitindo que a busca se baseie em sucessos anteriores.
A busca usa um método evolucionário baseado em ilhas para manter a diversidade entre os programas candidatos, reduzindo o risco de convergir para ótimos locais. Uma vantagem chave, conforme observado no artigo original, é que o FunSearch gera programas que podem ser inspecionados, simplificados e interpretados por pesquisadores, em vez de apenas fornecer uma resposta numérica final ou uma grande lista de objetos.
Formulação Algorítmica
O FunSearch pode ser descrito como uma busca sobre um espaço de fragmentos de programa, tipicamente funções embutidas em um esqueleto fixo. Seja \(\mathcal{F}\) o espaço de funções candidatas e \(S: \mathcal{F} \to \mathbb{R}\) uma pontuação de avaliador obtida executando um solucionador fixo que chama a função candidata. Dada uma função inicial \(f_0\), o FunSearch mantém um banco de dados \(D\) de funções válidas avaliadas. Ele repetidamente amostra funções de alta pontuação de \(D\), usa-as para construir prompts para um grande modelo de linguagem e pede ao modelo para gerar uma nova função candidata \(f'\). A nova função é executada dentro do esqueleto específico do problema e pontuada. Se válida, ela é adicionada a \(D\), permitindo que prompts posteriores se baseiem em candidatos mais fortes.
O objetivo idealizado é encontrar uma função candidata com alta pontuação de avaliador, \(f^* \in \arg\max_{f \in \mathcal{F}} S(f)\), embora na prática o FunSearch retorne a melhor função válida descoberta durante a busca. A implementação original usa um processo evolucionário baseado em ilhas para preservar a diversidade enquanto favorece programas com pontuações mais altas.
Aplicações
Problema do Conjunto Cap
O FunSearch foi demonstrado pela primeira vez no problema do conjunto cap, um problema em combinatória aditiva sobre o maior subconjunto possível de \(\mathbb{Z}_3^n\) sem três pontos em uma linha. Na dimensão 8, o FunSearch encontrou um conjunto cap de tamanho 512, melhorando construções previamente conhecidas. O artigo também relatou limites inferiores melhorados para a capacidade do conjunto cap ao descobrir construções relacionadas a conjuntos admissíveis. O Google DeepMind descreveu o resultado como um exemplo de uso de grandes modelos de linguagem para gerar novo conhecimento verificável em matemática. Uma notícia da Nature relatou que o sistema melhorou os esforços humanos para um problema de combinatória relacionado ao jogo de cartas Set.
Empacotamento de Bins Online
O FunSearch também foi aplicado ao problema de empacotamento de bins online, onde itens devem ser atribuídos a bins conforme chegam. Nesse cenário, o FunSearch evoluiu heurísticas programáticas que decidem qual bin deve receber um novo item. O artigo original relatou que as heurísticas descobertas superaram as linhas de base comuns de first-fit e best-fit em dados simulados e instâncias de benchmark OR-Library.
Software
O Google DeepMind lançou o software FunSearch em um repositório público do GitHub, permitindo que pesquisadores reproduzam os resultados e apliquem o método a outros problemas. O lançamento inclui o código para a busca evolucionária, a interface do avaliador e exemplos para os problemas de conjunto cap e empacotamento de bins. Essa disponibilidade aberta apoia experimentação adicional no campo de aprendizado de máquina e inteligência artificial.
Significância
O FunSearch é notável por sua integração de grandes modelos de linguagem com computação evolucionária, uma direção que ganhou atenção no campo mais amplo de aprendizado profundo. Ao produzir programas interpretáveis, ele oferece um caminho para sistemas de IA que não apenas resolvem problemas, mas também fornecem insights que os humanos podem entender e desenvolver. O método foi discutido no contexto dos esforços mais amplos do Google DeepMind para aplicar IA à descoberta científica, junto com outras iniciativas em IA generativa.
Embora o FunSearch tenha mostrado potencial em tarefas matemáticas e algorítmicas específicas, sua aplicabilidade geral permanece uma área de pesquisa ativa. A dependência de um modelo de linguagem pré-treinado e a necessidade de um avaliador bem definido são restrições que podem limitar seu uso em outros domínios. No entanto, a abordagem inspirou trabalhos adicionais sobre o uso de modelos de linguagem para síntese e otimização de programas, contribuindo para o cenário em evolução da pesquisa em IA.