FunSearch : de nouvelles découvertes en mathématiques et en sciences grâce aux LLM

(deepmind.google)

1 points par GN⁺ 2023-12-15 | 1 commentaires | Partager sur WhatsApp

FunSearch de Google DeepMind combine un LLM préentraîné et un évaluateur automatique pour explorer, sous forme de code, de nouvelles solutions vérifiables à des problèmes de mathématiques et d’informatique
Le LLM génère de nouveaux programmes, l’évaluateur automatique leur attribue un score, puis les programmes les mieux notés sont réinjectés dans le pool afin d’améliorer les solutions par itérations évolutives
Sur le cap set problem, il a trouvé, dans certaines configurations, les plus grands cap sets découverts à ce jour, avec de bonnes performances même à des échelles difficiles à traiter pour les solveurs de calcul de pointe existants
La même approche a aussi été appliquée à l’online bin packing, où des programmes ajustés aux caractéristiques des données placent le même nombre d’objets dans moins de bins que les heuristiques existantes
Comme le résultat prend la forme de programmes courts lisibles par l’humain, les chercheurs peuvent examiner la structure des solutions et s’en servir dans une collaboration humain-IA pour améliorer la formulation des problèmes

L’idée de base de FunSearch

FunSearch explore des fonctions écrites en code informatique pour trouver de nouvelles solutions en mathématiques et en informatique
Son nom vient du fait qu’il explore des fonctions (function)
Comme les LLM peuvent produire des informations erronées, FunSearch associe le LLM, chargé de proposer des idées créatives, à un évaluateur automatique (evaluator) pour écarter les mauvaises idées
Il s’agit du premier exemple où un LLM a permis de produire de nouvelles découvertes sur des problèmes scientifiques et mathématiques ouverts difficiles

Structure des itérations évolutives

L’utilisateur commence par écrire la description du problème sous forme de code
- Elle inclut la procédure d’évaluation du programme
- Elle comprend aussi un programme graine pour initialiser le pool de programmes
À chaque itération, une partie du pool courant de programmes est fournie au LLM
- Le LLM génère un nouveau programme à partir des programmes existants
- Le nouveau programme est ensuite exécuté et évalué automatiquement
- Les programmes obtenant les meilleurs scores sont ajoutés à nouveau à la base de données de programmes
L’utilisateur peut à tout moment récupérer le programme au meilleur score trouvé jusque-là
FunSearch a utilisé Google PaLM 2, mais il est aussi compatible avec d’autres LLM entraînés sur du code
La structure de recherche a également été renforcée pour faire face à des problèmes combinatoires difficiles
- Elle part de connaissances générales sur le problème pour se concentrer sur les idées clés nécessaires à de nouvelles découvertes
- Elle augmente la diversité des idées afin d’éviter la stagnation
- Elle exécute le processus évolutif en parallèle pour gagner en efficacité

Résultats sur le cap set problem

La première application visait le cap set problem, qui occupe des mathématiciens de plusieurs domaines depuis des décennies
Ce problème consiste à trouver la taille maximale d’un ensemble de points dans une grille de grande dimension tel qu’aucun triplet de points ne soit aligné, autrement dit un cap set
Il sert aussi de modèle pour d’autres problèmes en combinatoire extrémale (extremal combinatorics)
Comme le nombre de cas possibles dépasse très vite le nombre d’atomes dans l’univers, le calcul par force brute ne fonctionne pas
FunSearch a généré des solutions sous forme de programmes et a trouvé, dans certaines configurations, les plus grands cap sets découverts à ce jour
Ce résultat correspond à la plus forte progression de la taille des cap sets depuis 20 ans, et il montre de meilleures performances même dans des domaines de taille de problème qui dépassent les capacités actuelles des solveurs de calcul de pointe existants
Cela montre qu’il est possible de dépasser les résultats antérieurs sur des problèmes combinatoires où l’intuition est difficile à construire, avec un potentiel pour d’autres questions théoriques similaires en combinatoire ainsi que pour des domaines comme la théorie des communications

Des programmes courts interprétables par l’humain

FunSearch n’est pas une boîte noire qui se contente de produire une liste de réponses : il génère des programmes qui montrent comment la solution est construite
Cela rejoint la manière générale dont la science explique de nouvelles découvertes ou de nouveaux phénomènes à partir de leur processus de génération
FunSearch privilégie les solutions exprimées sous forme de programmes compacts ayant une faible complexité de Kolmogorov
- La complexité de Kolmogorov est la longueur du plus court programme informatique capable de produire une solution
- Des programmes courts peuvent décrire des objets très grands, ce qui aide à étendre l’approche à de vastes problèmes où l’on cherche une aiguille dans une botte de foin
- La sortie des programmes est plus facile à comprendre pour les chercheurs
Dans certains codes de sortie obtenant de bons scores, des symétries intéressantes ont été observées, ce qui a permis d’affiner la formulation du problème et d’obtenir de meilleures solutions
Jordan Ellenberg a déclaré que FunSearch fournit « un mécanisme entièrement nouveau pour développer des stratégies d’attaque » et que les solutions générées sont conceptuellement bien plus riches qu’une simple liste de nombres

Application à l’online bin packing

FunSearch a aussi été appliqué au bin packing, un problème pratique d’informatique
Le bin packing consiste à placer des objets de tailles différentes dans le plus petit nombre possible de bins
Parmi les cas d’usage concrets, on trouve le chargement de conteneurs ou encore l’affectation de tâches de calcul dans des datacenters afin de réduire les coûts
L’online bin packing est généralement traité à l’aide d’heuristiques fondées sur l’expérience humaine
- Il peut être difficile de trouver un ensemble de règles adapté à chaque situation particulière, selon la taille, le timing et la capacité
Bien que ce problème soit très différent du cap set problem, FunSearch a pu être configuré facilement et a produit des programmes automatiquement ajustés aux caractéristiques des données
Les programmes générés placent le même nombre d’objets dans moins de bins que les heuristiques existantes
D’autres approches IA, comme les réseaux de neurones ou l’apprentissage par renforcement, peuvent aussi être efficaces sur des problèmes combinatoires difficiles, mais leur déploiement peut demander des ressources importantes
Comme FunSearch produit du code facile à inspecter et à déployer, il peut générer des solutions directement exploitables dans divers systèmes industriels réels

Mise à jour 2024 et extension

Un rapport arXiv publié en décembre 2024 montre que l’approche FunSearch peut servir à amplifier les performances humaines en programmation compétitive combinatoire
Les concours de code traditionnels comme Codeforces exigent une solution complète à des problèmes algorithmiques classiques dans des contraintes de temps et de mémoire
Les compétitions combinatoires portent sur des problèmes complexes où il ne s’agit pas de trouver une unique bonne réponse, mais la meilleure solution approchée possible
Cette approche peut produire de meilleures solutions que celles trouvées par des participants situés dans les tout premiers centiles
Elle repose sur une structure collaborative dans laquelle le programmeur humain écrit la backbone du code de la solution, et le LLM fait évoluer de manière créative les fonctions qui la pilotent
Avec l’amélioration des LLM généralistes, il n’est plus nécessaire d’utiliser un modèle spécialisé dans le code, et l’approche peut s’appuyer sur Gemini 1.5 Flash
Au-delà de la programmation compétitive, FunSearch est aussi utilisé pour trouver de meilleures façons d’optimiser des fonctions dans un framework d’optimisation bayésienne

La direction des découvertes fondées sur les LLM

FunSearch montre qu’en mettant en place des garde-fous contre les hallucinations des LLM, on peut les utiliser non seulement pour de nouvelles découvertes mathématiques, mais aussi pour générer des solutions potentielles à d’importants problèmes du monde réel
Sur des problèmes anciens ou nouveaux en science et dans l’industrie, il pourrait devenir courant de générer des algorithmes efficaces et adaptés à chaque contexte grâce à des approches fondées sur les LLM
FunSearch peut continuer à s’améliorer avec les progrès généraux des LLM et devrait s’étendre à un plus large éventail de problèmes scientifiques et d’ingénierie

1 commentaires

GN⁺ 2023-12-15

Avis de Hacker News

Je me demande à quel point le LLM est nécessaire ici
À première vue, le rôle du LLM semble être de générer quelque chose de plausible, comme une fonction Python respectant une signature de type donnée
Mais même sans LLM, on devrait pouvoir créer des fonctions Python aléatoires et correctes qui satisfont une signature de type donnée. C’est le même exercice que [1], mais appliqué à un langage beaucoup plus complexe, et un langage restreint pourrait être plus pratique à utiliser. Des approches comme PushGP [2] ne seraient-elles pas possibles ?
Les questions sont : (1) quelle est la valeur ajoutée du LLM ici, réduit-il fortement le nombre d’évaluations nécessaires à la convergence, et si oui comment ; (2) sur le même problème, d’autres techniques de programmation génétique sont-elles moins compétitives et produisent-elles des solutions de moindre fitness ; (3) si une programmation génétique plus traditionnelle atteint une fitness comparable, quelle est la différence de coût de calcul en incluant le coût d’entraînement du LLM ?
[1] http://www.davidmontana.net/papers/stgp.pdf
[2] https://faculty.hampshire.edu/lspector/push.html
- L’espace d’états des programmes exécutables est bien plus vaste que celui des programmes utiles
  Les singes et les machines à écrire ne suffisent pas ; la raison pour laquelle Palm2 est utilisé ici est que les candidats doivent être plausibles, pas aléatoires. Il s’agit d’éviter de perdre du temps avec des programmes absurdes
  En outre, les algorithmes génétiques fondés sur la génération aléatoire de programmes ont un très gros problème de cold start. Si la fitness de tous les candidats est de 0, il y a de fortes chances qu’il n’y ait aucun progrès au début, et peut-être même jamais
- La fonction découverte est ici : https://github.com/google-deepmind/funsearch/blob/main/cap_s...
  Je ne suis pas très familier avec les algorithmes génétiques, mais je ne pense pas qu’un algorithme génétique soit incapable de trouver quelque chose de ce niveau. Cela dit, je serais surpris si quelqu’un l’avait vraiment tenté de nombreuses fois
  En revanche, comme on le voit dans l’annexe A.2 de l’article, une approche génétique sans LLM nécessiterait sans doute davantage de conception manuelle que l’approche avec LLM
- Les algorithmes génétiques finissent par produire beaucoup de programmes dénués de sens, même avec des contraintes. Avec suffisamment d’efforts, on peut probablement faire en sorte que la plupart soient syntaxiquement corrects, mais cela s’arrête là
  La différence apportée par le LLM ici est qu’il limite globalement l’espace des mutations possibles à des programmes sémantiquement plausibles
  Pour le point 3, un LLM entraîné est utile à énormément de fins, donc si l’on amortit aussi le coût de son entraînement initial, il n’est pas très élevé. Il peut y avoir un coût supplémentaire de fine-tuning pour l’adapter au framework FunSearch, mais le coût du fine-tuning est assez faible. Dans ce framework, l’utiliser a de fortes chances d’être avantageux par rapport à la seule programmation génétique
- La synthèse inductive de programmes était en pratique bloquée depuis des décennies, parce que l’espace de recherche est trop vaste. Il était difficile d’aller au-delà de programmes tout à fait triviaux
  Les LLM réduisent fortement l’espace de recherche et, bien sûr, ils le réduisent souvent de travers, mais on peut ensuite appliquer une synthèse inductive de programmes pour affiner et tester. À ma connaissance, cette approche est actuellement impossible sans LLM, car même dans les cas triviaux, on finit par tester des milliards de programmes totalement absurdes
- Je pensais que la descente de gradient stochastique et les LLM convergeaient beaucoup plus vite que la programmation génétique. En tout cas, c’est clairement beaucoup plus rapide qu’une recherche aléatoire
Le contexte important, c’est que cette découverte a montré qu’un certain nombre en combinatoire ne se situe plus dans l’intervalle 2,218~2,756 connu l’an dernier, mais désormais entre 2,2202~2,756
L’amélioration ne relève pas tant d’une preuve mathématique centrée sur la logique que de la découverte de suites particulières ayant des propriétés spéciales. Cela ne veut pas dire pour autant que ce n’est pas rigoureux
C’est une façon intéressante, et probablement utile, de produire des exemples ; en pratique, cela ressemble beaucoup à un algorithme génétique agrémenté d’un LLM
Commentaire de Subbarao sur le « self-play » : https://twitter.com/rao2z/status/1728121216479949048
D’après le texte, FunSearch utilise une méthode évolutive pilotée par un LLM pour promouvoir et développer les idées qui obtiennent de bons scores. Ces idées prennent la forme de programmes informatiques, ce qui permet de les exécuter et de les évaluer automatiquement
L’utilisateur rédige la description du problème sous forme de code. Cette description inclut une procédure d’évaluation du programme et un programme graine pour initialiser le pool de programmes
À chaque itération, FunSearch sélectionne certains programmes dans le pool courant, le LLM les prolonge de manière créative pour produire de nouveaux programmes, puis ces nouveaux programmes sont évalués automatiquement. Les meilleurs sont réintégrés au pool existant, créant une boucle d’auto-amélioration
Pour la recherche web, j’utilise pplx.ai et phind.com de manière similaire comme évaluateurs. Je pose une question, j’observe quelles références et quels liens web ils récupèrent, puis j’affine la question ou je pose des questions de suivi afin de faire émerger des sources plus approfondies ou différentes. Cela fonctionne mieux que de fouiller Reddit ou Google pour trouver des perles rares
Il y a aussi beaucoup d’excellents contenus sur Tech Twitter ; maintenant que Grok est ouvert à tout le monde, j’espère qu’il sera utilisé pour la recherche
https://twitter.com/gfodor/status/1735348301812383906
Certains disent que « si DeepMind a prouvé de manière définitive que les réseaux de neurones peuvent produire de véritables connaissances nouvelles, c’est la découverte la plus importante depuis le feu »
Si c’est vraiment le cas, je me demande pourquoi tout le monde n’en parle pas. Le fait qu’ils y soient parvenus avec PaLM 2, moins avancé que GPT-4 ou Gemini, est impressionnant. Ce que les prochaines générations de modèles pourront faire en exploitant ce genre de méthode semble énorme
- Ici, le gros du travail est fait par l’algorithme évolutionnaire
  Le LLM remplace un opérateur de mutation aléatoire et reçoit en gros une demande du type « propose une modification raisonnable de ces 20 lignes de Python ». Attribuer la création de connaissances au réseau de neurones me paraît être une appréciation généreuse
  De plus, au-delà du fait qu’il faut une structure où « la création est difficile et l’évaluation facile », cela dépend fortement de la nature du problème. La partie que l’on veut faire évoluer doit pouvoir être décomposée en une seule fonction Python très courte
- J’ai dit « Waouh ! » à voix haute
  Qu’un LLM puisse découvrir une nouvelle solution en géométrie de grande dimension, où il n’y avait pas eu de progrès depuis 20 ans, va bien au-delà du simple assemblage plausible de fragments plagiés de données d’entraînement
  Cela suggère qu’il existe une profondeur cachée dans les capacités des LLM, à condition de trouver comment les prompter et les évaluer correctement
  C’est un résultat qui dépasse largement les attentes. On ne sait pas quelles découvertes se cachent derrière le prochain prompt et la prochaine seed aléatoire
- Les réseaux de neurones pouvaient déjà produire de « nouvelles connaissances » depuis longtemps
  Les LLM aussi : https://www.nature.com/articles/s41587-022-01618-2
- D’après l’article, FunSearch fonctionne actuellement le mieux sur des problèmes présentant les caractéristiques suivantes
  a) il existe un évaluateur efficace, b) il existe un retour de score riche qui quantifie le degré d’amélioration, c’est-à-dire pas un simple signal binaire, c) on peut fournir un squelette contenant une partie isolée à faire évoluer
  Par exemple, la génération de preuves de théorèmes sort de ce cadre, car on ne voit pas clairement comment fournir un signal de score suffisamment riche
- Cet exemple semble relativement limité à la recherche de nouveaux algorithmes ou de nouvelles fonctions
  C’est un excellent travail, mais comparé à la découverte du feu, ou à quantité d’autres choses entre les deux, comme l’électricité, cela ne paraît pas du même ordre
En résumé, étant donné un template/squelette de programme et une fonction de fitness, on génère une population de programmes avec un LLM, en utilisant un prompt qui crée un nouveau programme à partir de k autres versions ; ils ont constaté que k=2 fonctionnait bien. C’est assez biologique. Ensuite, on exécute les programmes sur les entrées et on les note avec la fonction de fitness, puis on utilise un modèle en îles pour l’évolution
Le prompt ressemble probablement, en principe, à quelque chose comme ceci
def foo_v1(a, b): ...
def foo_v2(a, b): ...
# Crée une nouvelle fonction à partir de foo_v1 et foo_v2. Tu ne peux modifier que ce qui se trouve entre doubles accolades, comme {{ THIS }}
def foo(a, b): return a + {{}}
S’il n’a fallu qu’environ 1e6 appels au LLM pour obtenir un nouveau résultat, c’est un nombre assez impressionnant par sa faiblesse. Il est aussi dit que l’évaluation/la notation prend quelques minutes
Il vaut la peine de réfléchir ici au compromis entre profondeur et largeur. C’est lié à la latence et au débit lors de la notation des programmes individuels et des populations. Et si l’on faisait de la mémoïsation pour tous les programmes ? En gardant la fonction de perte multidimensionnelle, avec une dimension par entrée ou par bucket d’entrées, on pourrait peut-être d’abord trouver des populations de programmes performantes dans différentes régions, puis les combiner plus tard
Je me demande aussi s’il existait des connaissances a priori sur la rareté des cap sets. Je me demande s’il y avait déjà eu des tentatives calculatoires restées sans résultat, mais quoi qu’il en soit, c’est chouette
Pour paraphraser le post Twitter / X, à partir de maintenant cela ne fera que s’améliorer
Autrement dit, les capacités de l’IA augmentent de façon monotone, et c’est le cas depuis des décennies ; dans ce cas précis, les capacités s’auto-améliorent récursivement. Je constate déjà, à titre personnel, une hausse d’environ 20 à 30 % de ma productivité en codage grâce à l’autocomplétion par IA, au refactoring assisté par IA et aux diffs de code review générés automatiquement par IA dans les commentaires
J’ai l’impression que l’IA entre dans une phase comparable à Intel dans les années 90. Pour rendre le code deux fois plus rapide, il suffisait d’attendre la prochaine révision des CPU Intel. Désormais, ce sont les modèles d’IA qui jouent ce rôle. Si l’on branche certaines parties des flux métier, comme le codage, le support client ou le tri des bugs, sur des systèmes LLM, « améliorer » le système revient plus ou moins à changer le nom du modèle
Après l’intégration initiale, on peut s’attendre, avec un effort minimal, à ce que « tout s’améliore un peu par magie » pendant les prochaines années
- À mon avis, rien de tel n’apparaît dans le billet de blog ni dans l’article lié
  En particulier, ils n’ont pas comparé les résultats avec et sans LLM. D’après ce que je comprends, cet article montre des résultats de programmation génétique où un LLM génère une fonction noyau Python qui suit probablement une signature de type donnée. Un LLM n’est pas indispensable pour cette tâche
  Il reste donc une question ouverte de savoir si le LLM fait ici quelque chose de particulièrement spécial
L’un des problèmes abordés était le problème des cap sets
https://en.m.wikipedia.org/wiki/Cap_set
Ce problème consiste à trouver, dans une grille de grande dimension, le plus grand ensemble de points dont aucun triplet n’est aligné, c’est-à-dire un cap set. Il est important parce qu’il sert de modèle à d’autres problèmes de combinatoire extrémale. La combinatoire extrémale étudie à quel point des ensembles de nombres, de graphes ou d’autres objets peuvent être grands ou petits. Le calcul par force brute ne fonctionne pas pour ce problème, car le nombre de possibilités à considérer dépasse rapidement le nombre d’atomes dans l’univers
FunSearch a généré des solutions sous forme de programmes et, dans certains réglages, a trouvé les plus grands cap sets découverts à ce jour. C’est la plus forte augmentation de la taille des cap sets depuis 20 ans. De plus, comme ce problème croît à une échelle qui dépasse largement les capacités des solveurs computationnels de pointe actuels, FunSearch les a surpassés
Je me demande comment intégrer le raisonnement symbolique aux LLM, ou même si c’est possible
- C’est précisément ce que nous faisons. Je pense que c’est non seulement possible, mais nécessaire pour les applications qui dépassent la génération par essais et erreurs
- Il semble aussi y avoir un certain parallèle avec les idées neuro-symboliques explorées par le Lab V2 de l’ASU
- LEAN
Le récent article de DeepMind sur FunSearch mettait en avant le fait qu’il utilisait un grand modèle de langage pré-entraîné pour générer des améliorations de code
Fait intéressant, le LLM principal était Codey, basé sur la famille de modèles PaLM2, mais les documents complémentaires mentionnent aussi StarCoder, un LLM open source
Pourtant, le dépôt GitHub de FunSearch n’inclut pas cette implémentation de LLM. Par exemple, sampler.py contient le code suivant
```
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.')  
```
Ce code montre qu’une implémentation externe de LLM est nécessaire. S’ils ont réussi à utiliser StarCoder, il est surprenant qu’il n’y ait pas de guide d’intégration ni d’implémentation de base pour celui-ci, ou pour un LLM open source similaire. Un tel contenu aurait nettement amélioré la reproductibilité et l’accessibilité de la recherche
Que cela constitue ou non une nouvelle connaissance vérifiable, c’est une étude de cas intéressante quand on pense au problème de la restriction de l’accès à l’IA par la taille des modèles ou par d’autres moyens réglementaires
De telles restrictions donnent un avantage injuste aux entreprises capables de découvrir de nouvelles connaissances ou des lois naturelles, puis de les monétiser sans les partager

FunSearch : de nouvelles découvertes en mathématiques et en sciences grâce aux LLM

L’idée de base de FunSearch

Structure des itérations évolutives

Résultats sur le cap set problem

Des programmes courts interprétables par l’humain

Application à l’online bin packing

Mise à jour 2024 et extension

La direction des découvertes fondées sur les LLM

À lire aussi

1 commentaires

Avis de Hacker News