Recherche
En recherchant des « fonctions » écrites en code informatique, FunSearch a fait les premières découvertes sur des problèmes ouverts en sciences mathématiques grâce aux LLM.
Les grands modèles linguistiques (LLM) sont des assistants utiles : ils excellent dans la combinaison de concepts et peuvent lire, écrire et coder pour aider les gens à résoudre des problèmes. Mais pourraient-ils découvrir des connaissances entièrement nouvelles ?
Comme il a été démontré que les LLM « hallucinent » des informations factuellement incorrectes, les utiliser pour faire des découvertes vérifiables est un défi. Mais et si nous pouvions exploiter la créativité des LLM en identifiant et en s'appuyant uniquement sur leurs meilleures idées ?
Aujourd'hui, dans un article publié dans Nature, nous présentons FunSearch, une méthode pour rechercher de nouvelles solutions en mathématiques et en informatique. FunSearch fonctionne en associant un LLM pré-formé, dont l'objectif est de fournir des solutions créatives sous forme de code informatique, à un « évaluateur » automatisé qui protège contre les hallucinations et les idées incorrectes. En itérant entre ces deux composants, les solutions initiales « évoluent » vers de nouvelles connaissances. Le système recherche des « fonctions » écrites en code informatique ; d'où le nom FunSearch.
Ce travail représente la première fois qu'une nouvelle découverte est faite pour résoudre des problèmes ouverts en sciences ou en mathématiques à l'aide de LLM. FunSearch a découvert de nouvelles solutions au problème du cap set, un problème ouvert de longue date en mathématiques. De plus, pour démontrer l’utilité pratique de FunSearch, nous l’avons utilisé pour découvrir des algorithmes plus efficaces pour résoudre le problème du « bin-packing », qui a des applications omniprésentes telles que l’amélioration de l’efficacité des centres de données.
Le progrès scientifique a toujours reposé sur la capacité de partager de nouvelles connaissances. Ce qui fait de FunSearch un outil scientifique particulièrement puissant, c'est qu'il produit des programmes qui révèlent comment ses solutions sont construites, plutôt que simplement ce que sont les solutions. Nous espérons que cela pourra inspirer de nouvelles perspectives aux scientifiques qui utilisent FunSearch, initiant ainsi un cycle vertueux d’amélioration et de découverte.
Favoriser la découverte grâce à l'évolution avec des modèles de langage
FunSearch utilise une méthode évolutive alimentée par les LLM, qui promeut et développe les idées les plus performantes. Ces idées sont exprimées sous forme de programmes informatiques, afin qu'elles puissent être exécutées et évaluées automatiquement. Tout d’abord, l’utilisateur rédige une description du problème sous forme de code. Cette description comprend une procédure pour évaluer des programmes, et un programme d'amorçage utilisé pour initialiser un groupe de programmes.
FunSearch est une procédure itérative ; à chaque itération, le système sélectionne certains programmes dans le pool actuel de programmes, qui sont transmis à un LLM. Le LLM s'appuie de manière créative sur ceux-ci et génère de nouveaux programmes, qui sont automatiquement évalués. Les meilleurs sont réajoutés au pool de programmes existants, créant ainsi une boucle d’auto-amélioration. Utilisations de FunSearch PaLM 2 de Googlemais il est compatible avec d'autres LLM formés au code.
Le processus FunSearch. Le LLM se voit présenter une sélection des meilleurs programmes qu'il a générés jusqu'à présent (récupérés de la base de données des programmes) et est invité à en générer un encore meilleur. Les programmes proposés par le LLM sont automatiquement exécutés et évalués. Les meilleurs programmes sont ajoutés à la base de données pour être sélectionnés lors des cycles suivants. L'utilisateur peut à tout moment récupérer les programmes les mieux notés découverts jusqu'à présent.
Découvrir de nouvelles connaissances mathématiques et de nouveaux algorithmes dans différents domaines est une tâche notoirement difficile et largement au-delà de la puissance des systèmes d’IA les plus avancés. Pour résoudre des problèmes aussi difficiles avec FunSearch, nous avons introduit plusieurs composants clés. Au lieu de repartir de zéro, nous commençons le processus évolutif avec une connaissance commune du problème et laissons FunSearch se concentrer sur la recherche des idées les plus critiques pour réaliser de nouvelles découvertes. De plus, notre processus évolutif utilise une stratégie pour améliorer la diversité des idées afin d'éviter la stagnation. Enfin, nous exécutons le processus évolutif en parallèle pour améliorer l'efficacité du système.
Innover en mathématiques
Nous abordons d'abord le problème de réglage du capuchon, un défi ouvert qui contrarie les mathématiciens dans de nombreux domaines de recherche depuis des décennies. Le célèbre mathématicien Terence Tao l'a un jour décrit comme son question ouverte préférée. Nous avons collaboré avec Jordan Ellenberg, professeur de mathématiques à l'Université du Wisconsin-Madison et auteur d'un ouvrage sur avancée importante sur le problème du cap set.
Le problème consiste à trouver le plus grand ensemble de points (appelé ensemble de casquettes) dans une grille de grande dimension, où il n'y a pas trois points sur une ligne. Ce problème est important car il sert de modèle à d'autres problèmes de combinatoire extrême – l'étude de la taille d'une collection de nombres, de graphiques ou d'autres objets. Les approches de calcul par force brute pour résoudre ce problème ne fonctionnent pas : le nombre de possibilités à considérer devient rapidement supérieur au nombre d'atomes dans l'univers.
FunSearch a généré des solutions – sous forme de programmes – qui, dans certains contextes, ont permis de découvrir les plus grands ensembles de capitalisations jamais trouvés. Ceci représente le la plus forte augmentation de la taille des plafonds fixés au cours des 20 dernières années. De plus, FunSearch a surpassé les solveurs informatiques de pointe, car ce problème dépasse largement leurs capacités actuelles.
Figure interactive montrant l'évolution du programme d'amorçage (en haut) vers une nouvelle fonction avec un score plus élevé (en bas). Chaque cercle est un programme dont la taille est proportionnelle à la note qui lui est attribuée. Seuls les ancêtres du programme en bas sont affichés. La fonction correspondante produite par FunSearch pour chaque nœud est affichée à droite (voir le programme complet utilisant cette fonction dans l'article).
Ces résultats démontrent que la technique FunSearch peut nous amener au-delà des résultats établis sur des problèmes combinatoires difficiles, où l'intuition peut être difficile à construire. Nous espérons que cette approche jouera un rôle dans de nouvelles découvertes sur des problèmes théoriques similaires en combinatoire et qu’à l’avenir, elle pourrait ouvrir de nouvelles possibilités dans des domaines tels que la théorie de la communication.
FunSearch privilégie les programmes concis et interprétables par l'homme
Bien que la découverte de nouvelles connaissances mathématiques soit importante en soi, l’approche FunSearch offre un avantage supplémentaire par rapport aux techniques de recherche informatique traditionnelles. En effet, FunSearch n'est pas une boîte noire qui génère simplement des solutions à des problèmes. Au lieu de cela, il génère des programmes qui décrivent comment ces solutions ont été trouvées. Cette approche de démonstration est la façon dont les scientifiques opèrent généralement, avec de nouvelles découvertes ou de nouveaux phénomènes expliqués par le processus utilisé pour les produire.
FunSearch privilégie la recherche de solutions représentées par des programmes très compacts – des solutions avec une faible complexité de Kolmogorov†. Les programmes courts peuvent décrire des objets très volumineux, permettant à FunSearch de s'adapter à de gros problèmes d'aiguille dans une botte de foin. De plus, cela rend les résultats du programme FunSearch plus faciles à comprendre pour les chercheurs. Ellenberg a déclaré : « FunSearch offre un mécanisme complètement nouveau pour développer des stratégies d’attaque. Les solutions générées par FunSearch sont conceptuellement bien plus riches qu'une simple liste de chiffres. Quand je les étudie, j’apprends quelque chose ».
De plus, cette interprétabilité des programmes de FunSearch peut fournir des informations exploitables aux chercheurs. En utilisant FunSearch, nous avons remarqué, par exemple, des symétries intrigantes dans le code de certaines de ses sorties les plus performantes. Cela nous a donné un nouvel aperçu du problème, et nous avons utilisé cet aperçu pour affiner le problème introduit dans FunSearch, aboutissant à des solutions encore meilleures. Nous considérons cela comme un exemple de procédure collaborative entre les humains et FunSearch sur de nombreux problèmes mathématiques.
À gauche : l'inspection du code généré par FunSearch a donné d'autres informations exploitables (points saillants ajoutés par nos soins). À droite : l'ensemble brut « admissible » construit à l'aide du programme (beaucoup plus court) de gauche.
Les solutions générées par FunSearch sont conceptuellement bien plus riches qu'une simple liste de chiffres. Quand je les étudie, j’apprends quelque chose.
Jordan Ellenberg, collaborateur et professeur de mathématiques à l'Université du Wisconsin-Madison
Relever un défi informatique notoirement difficile
Encouragés par notre succès avec le problème théorique de l'ensemble de plafonds, nous avons décidé d'explorer la flexibilité de FunSearch en l'appliquant à un défi pratique important en informatique. Le problème du « conditionnement des bacs » consiste à emballer des articles de différentes tailles dans le plus petit nombre de bacs. Il est au cœur de nombreux problèmes du monde réel, du chargement de conteneurs contenant des éléments à l'allocation des tâches de calcul dans les centres de données pour minimiser les coûts.
Le problème du conditionnement en ligne est généralement résolu à l’aide de règles empiriques algorithmiques (heuristiques) basées sur l’expérience humaine. Mais trouver un ensemble de règles pour chaque situation spécifique – avec des tailles, des délais ou des capacités différents – peut s’avérer difficile. Bien qu'il soit très différent du problème de définition de plafond, la configuration de FunSearch pour ce problème a été facile. FunSearch a fourni un programme automatiquement adapté (s'adaptant aux spécificités des données) qui a surpassé les heuristiques établies : en utilisant moins de casiers pour emballer le même nombre d'éléments.
Exemple illustratif de bin packaging utilisant une heuristique existante – Heuristique la mieux adaptée (à gauche) et utilisant une heuristique découverte par FunSearch (à droite).
Les problèmes combinatoires difficiles tels que l'emballage des bacs en ligne peuvent être résolus à l'aide d'autres approches d'IA, comme les réseaux de neurones et l'apprentissage par renforcement. De telles approches se sont également révélées efficaces, mais leur déploiement peut également nécessiter des ressources importantes. FunSearch, quant à lui, produit un code qui peut être facilement inspecté et déployé, ce qui signifie que ses solutions pourraient potentiellement être intégrées dans une variété de systèmes industriels réels pour apporter des avantages rapides.
Découverte basée sur le LLM pour la science et au-delà
FunSearch démontre que si nous nous protégeons contre les hallucinations des LLM, la puissance de ces modèles peut être exploitée non seulement pour produire de nouvelles découvertes mathématiques, mais également pour révéler des solutions potentiellement efficaces à d'importants problèmes du monde réel.
Nous envisageons que pour de nombreux problèmes scientifiques et industriels – anciens ou nouveaux – la génération d'algorithmes efficaces et personnalisés utilisant des approches basées sur le LLM deviendra une pratique courante.
En effet, ce n'est que le début. FunSearch s'améliorera comme une conséquence naturelle des progrès plus larges des LLM, et nous travaillerons également à élargir ses capacités pour relever une variété de défis scientifiques et techniques urgents de la société.
