FunSearch (abréviation de recherche dans l'espace des fonctions) est une méthode d'intelligence artificielle développée par Google DeepMind pour découvrir des programmes informatiques qui résolvent des problèmes mathématiques et algorithmiques. Elle combine un grand modèle de langage avec un évaluateur automatisé et une procédure de recherche évolutive, générant des programmes candidats, les notant, et utilisant les programmes les plus performants pour produire de nouveaux candidats. Le système a été annoncé en 2023, avec un article publié dans la revue Nature, et a été appliqué à des problèmes de combinatoire extrémale et de bin packing en ligne.
FunSearch représente un changement dans la manière dont les grands modèles de langage sont utilisés pour la découverte. Au lieu de générer directement des réponses, il formule un problème comme une recherche sur des programmes informatiques, permettant au modèle de proposer du code qui est ensuite rigoureusement testé. Cette approche exploite les capacités génératives des modèles comme ceux utilisés dans la IA générative tout en garantissant que les sorties sont vérifiables et souvent interprétables par les chercheurs.
Méthode
FunSearch fonctionne en générant et en évaluant itérativement des programmes candidats. L'utilisateur fournit une spécification du problème, une fonction d'évaluation et un squelette de programme initial. À chaque étape, le système échantillonne des programmes existants à partir d'une base de données, en favorisant ceux ayant des scores plus élevés, et construit une invite pour un grand modèle de langage pré-entraîné. Le modèle génère un programme modifié, qui est ensuite exécuté et noté par l'évaluateur. Les programmes valides sont ajoutés à la base de données, permettant à la recherche de s'appuyer sur les succès précédents.
La recherche utilise une méthode évolutive basée sur des îles pour maintenir la diversité parmi les programmes candidats, réduisant le risque de convergence vers des optima locaux. Un avantage clé, comme noté dans l'article original, est que FunSearch produit des programmes qui peuvent être inspectés, simplifiés et interprétés par les chercheurs, plutôt que de fournir uniquement une réponse numérique finale ou une grande liste d'objets.
Formulation algorithmique
FunSearch peut être décrit comme une recherche sur un espace de fragments de programmes, généralement des fonctions intégrées dans un squelette fixe. Soit \(\mathcal{F}\) l'espace des fonctions candidates et \(S: \mathcal{F} \to \mathbb{R}\) un score d'évaluateur obtenu en exécutant un solveur fixe qui appelle la fonction candidate. Étant donné une fonction initiale \(f_0\), FunSearch maintient une base de données \(D\) de fonctions valides et évaluées. Il échantillonne de manière répétée des fonctions à score élevé depuis \(D\), les utilise pour construire des invites pour un grand modèle de langage, et demande au modèle de générer une nouvelle fonction candidate \(f'\). La nouvelle fonction est exécutée dans le squelette spécifique au problème et notée. Si elle est valide, elle est ajoutée à \(D\), permettant aux invites ultérieures de s'appuyer sur des candidats plus forts.
L'objectif idéalisé est de trouver une fonction candidate avec un score d'évaluateur élevé, \(f^* \in \arg\max_{f \in \mathcal{F}} S(f)\), bien qu'en pratique FunSearch renvoie la meilleure fonction valide découverte pendant la recherche. L'implémentation originale utilise un processus évolutif basé sur des îles pour préserver la diversité tout en favorisant les programmes à score plus élevé.
Applications
Problème des ensembles cap
FunSearch a été démontré pour la première fois sur le problème des ensembles cap, un problème de combinatoire additive concernant le plus grand sous-ensemble possible de \(\mathbb{Z}_3^n\) sans trois points alignés. En dimension 8, FunSearch a trouvé un ensemble cap de taille 512, améliorant les constructions précédemment connues. L'article a également rapporté des bornes inférieures améliorées pour la capacité des ensembles cap en découvrant des constructions liées aux ensembles admissibles. Google DeepMind a décrit le résultat comme un exemple d'utilisation de grands modèles de langage pour générer des connaissances nouvelles et vérifiables en mathématiques. Un article de Nature News a rapporté que le système améliorait les efforts humains pour un problème de combinatoire lié au jeu de cartes Set.
Bin packing en ligne
FunSearch a également été appliqué au problème de bin packing en ligne, où les articles doivent être assignés à des conteneurs à mesure qu'ils arrivent. Dans ce contexte, FunSearch a évolué des heuristiques programmatiques qui décident quel conteneur doit recevoir un nouvel article. L'article original a rapporté que les heuristiques découvertes surpassaient les références courantes de first-fit et best-fit sur des données simulées et des instances de référence OR-Library.
Logiciel
Google DeepMind a publié le logiciel FunSearch dans un dépôt GitHub public, permettant aux chercheurs de reproduire les résultats et d'appliquer la méthode à d'autres problèmes. La publication inclut le code pour la recherche évolutive, l'interface d'évaluateur et des exemples pour les problèmes d'ensembles cap et de bin packing. Cette disponibilité ouverte soutient une expérimentation supplémentaire dans le domaine de la apprentissage automatique et de l'intelligence artificielle.
Importance
FunSearch est notable pour son intégration des grands modèles de langage avec le calcul évolutif, une direction qui a gagné en attention dans le domaine plus large du apprentissage profond. En produisant des programmes interprétables, il offre une voie vers des systèmes d'IA qui non seulement résolvent des problèmes, mais fournissent également des insights que les humains peuvent comprendre et sur lesquels ils peuvent s'appuyer. La méthode a été discutée dans le contexte des efforts plus larges de Google DeepMind pour appliquer l'IA à la découverte scientifique, aux côtés d'autres initiatives en IA générative.
Bien que FunSearch ait montré des promesses sur des tâches mathématiques et algorithmiques spécifiques, son applicabilité générale reste un domaine de recherche active. La dépendance à un modèle de langage pré-entraîné et la nécessité d'un évaluateur bien défini sont des contraintes qui peuvent limiter son utilisation dans d'autres domaines. Néanmoins, l'approche a inspiré des travaux supplémentaires sur l'utilisation de modèles de langage pour la synthèse et l'optimisation de programmes, contribuant au paysage évolutif de la recherche en IA.