Diffusion sur arbre syntaxique pour la synthèse de programmes
(tree-diffusion.github.io)- L’article Tree Diffusion, accepté à ICLR 2025, propose un modèle neuronal qui, au lieu de générer un programme token par token, édite itérativement le programme en s’appuyant sur le résultat de son exécution
- L’idée clé est d’apprendre sur un arbre syntaxique construit à partir d’une grammaire hors contexte, en inversant le bruit à la manière de la diffusion appliquée aux images
- Le bruit est ajouté sous forme de mutations aléatoires qui remplacent des nœuds arbitraires de l’arbre syntaxique par d’autres nœuds du même type valide
- Comme le code est corrigé tout en conservant un état grammaticalement valide, l’approche se combine facilement avec la recherche (search) dans l’espace des programmes
- En inverse graphics, elle permet de convertir une image en programme générateur, puis, combinée à la recherche, de déboguer un programme graphique en observant son exécution pour satisfaire la spécification demandée
L’approche de Tree Diffusion
- Tree Diffusion applique la diffusion sur l’arbre syntaxique à la synthèse de programmes
- L’article, la page arXiv ainsi que le code et les poids sont disponibles
- Les grands modèles de langage existants utilisent une approche autorégressive qui génère le code token par token, sans retour d’information sur la sortie du programme pendant la génération
- Les approches qui entraînent directement un LLM à proposer des modifications peuvent être difficiles, car elles nécessitent suffisamment de données d’édition
- Tree Diffusion modifie les programmes à l’aide d’un modèle qui inverse le bruit appliqué aux arbres syntaxiques d’une grammaire hors contexte
Bruit, recherche et cas d’usage
- Le bruit consiste en une mutation aléatoire où l’on choisit un nœud arbitraire dans l’arbre syntaxique, puis on le remplace par un autre nœud du même type valide
- Au lieu de générer un programme séquentiellement depuis zéro, le système le modifie de façon répétée tout en conservant la validité syntaxique
- Cette propriété facilite la combinaison du modèle neuronal avec la recherche dans l’espace des programmes
- Pour les tâches d’inverse graphics, le système apprend à convertir une image d’entrée en programme capable de générer cette image
- Combiné à la recherche, il peut écrire un programme graphique, vérifier le résultat de son exécution, puis le déboguer jusqu’à satisfaire la spécification demandée
- Les auteurs montrent aussi qu’il est capable d’écrire des programmes graphiques à partir de croquis dessinés à la main
1 commentaires
Commentaires Hacker News
Ça ressemble davantage au travail fait avec Racket et la génération d’indices pour les MOOC
Je ne suis pas sûr de l’université, mais j’ai vu une présentation sur la génération d’indices pour les étudiants en transformant des arbres syntaxiques et en analysant les modifications nécessaires pour arriver à la solution cible
C’était probablement une présentation à RacketCon il y a une dizaine d’années, et il serait peut-être possible de combiner ce type de méthodologie avec des approches modernes de machine learning
J’ai retrouvé la présentation : https://invidious.baczek.me/watch?v=ijyFC36kVis
Ces mutations de sous-arbres sont intéressantes, car Koza et Adamı les avaient étudiées assez en profondeur dans les années 90 sous le nom d’algorithmes génétiques
La fonction d’optimisation était simplement un peu différente
L’article contient une référence de 2000 sur des algorithmes génétiques pour générer rapidement des arbres de programmes, mais le travail central semble manquer
J’aimerais que les auteurs lisent cela et explorent les travaux de ces chercheurs
FFX et PGE sont tous deux très rapides
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
https://arxiv.org/pdf/2209.09675
En tant que créateur de PGE, j’ai pensé que l’apprentissage par renforcement et, plus récemment, les techniques de diffusion pourraient aider ce type d’algorithmes
Tous les algorithmes ont besoin de moyens pour mieux guider la recherche, ou pour les faire sortir des optima locaux dans lesquels ils tombent étonnamment vite
La majeure partie de la recherche en programmation génétique/calcul évolutionnaire se concentre sur l’évitement de la convergence prématurée
D’après la description du site, c’est « le manuel d’IA le plus reconnu et le plus utilisé, adopté par plus de 1 500 établissements »
https://aima.cs.berkeley.edu/
Bon, c’était une erreur de ma part
Je possède les deux gros livres de Koza parus en 1992 et 1994, Genetic Programming: On the Programming of Computers by Means of Natural Selection et Genetic Programming II : Automatic Discovery of Reusable Programs
Je n’ai pas lu les deux suivants
À l’époque, les grands problèmes qui bloquaient étaient en partie d’arriver à aller assez vite, et en partie d’obtenir des résultats compréhensibles par des humains
Sur ce dernier point, les grands modèles de langage semblent bien meilleurs
On finissait par passer beaucoup de temps à restructurer et élaguer les arbres pour obtenir des résultats interprétables, si bien que la valeur principale semblait limitée aux cas où il valait la peine de consacrer beaucoup de ressources à trouver des versions mieux optimisées d’algorithmes très petits et denses
Mais la plupart des bases de code ont tellement de fruits bien plus faciles à cueillir qu’on arrive rarement au point où ce genre d’effort en vaut la peine
Conceptuellement, cela dit, j’aime toujours l’idée
[1] https://www.genetic-programming.com/johnkoza.html
https://web.archive.org/web/20021224053225/http://smi-web.st...
https://www.genetic-programming.com/jkpdf/tr1314.pdf
Utiliser les méthodes de Monte-Carlo par chaînes de Markov pour la synthèse de programmes n’est pas vraiment une idée nouvelle
La référence qui me vient immédiatement à l’esprit est le travail de Josh Tenenbaum
WebPPL (langage de programmation probabiliste web) propose aussi de nombreuses démos, comme la synthèse de vaisseaux spatiaux 3D
Je recommande vivement aussi les livres liés à The Design and Implementation of Probabilistic Programming Languages et Probabilistic Models of Cognition
Les articles du MIT Probabilistic Computing Project valent également le détour
[1] Human-level concept learning through probabilistic program induction. https://www.cs.cmu.edu/~rsalakhu/papers/LakeEtAl2015Science....
[2] http://webppl.org/
[3] https://dritchie.github.io/web-procmod/
[4] https://dippl.org/
[5] http://probmods.org/
[6] http://probcomp.csail.mit.edu/
Je ne comprends pas bien la « magie » dont il est question ici
Avec une approche traditionnelle, on générerait une image aléatoire, on calculerait une certaine métrique de distance, puis on minimiserait cette distance avec une méthode d’optimisation comme le recuit simulé
Ici, je comprends qu’on optimise l’écart entre des représentations d’images, mais je ne vois pas comment un changement de tokens dans le programme pourrait être différentiable
L’idée centrale semble être qu’on peut entraîner un modèle de réseau neuronal à proposer des modifications de programme en transformant aléatoirement des nœuds
Quand on exécute ce modèle neuronal, il peut effectuer des modifications syntaxiquement valides selon une grammaire hors contexte, par exemple remplacer uniquement des nombres par des nombres
Je me demande ce que cela donnerait appliqué à l’optimisation de compilateurs/interpréteurs
Serait-il possible de « disséquer » une partie de l’exécution, peut-être au niveau assembleur, pour produire des optimisations spécialisées du code compilé, que les compilateurs modernes ne trouvent pas de façon déterministe, sans changer la sortie ?
Ici, par sortie, j’entends la sortie attendue du programme, pas le binaire généré
Je ne m’attendrais pas à ce qu’un tel outil « découvre » de l’assembleur sans avoir été entraîné sur des résultats de compilation
Le modèle n’a aucune notion de la manière dont le code s’exécute, ni de l’endroit où il s’exécute
Après des décennies de recherche sur les compilateurs et de supercompilateurs en fonctionnement, on est arrivé à un point où il est presque impossible de découvrir de nouvelles optimisations produisant des gains visibles
Les compilateurs d’aujourd’hui sont vraiment bons
Cela dit, la valeur d’une telle approche pourrait être d’optimiser l’intention du code
S’il détermine que le code trie des nombres, il pourrait le remplacer par un algorithme de tri plus rapide ayant les mêmes propriétés fonctionnelles
S’il stocke des données inutilisées, il pourrait cesser de les stocker
Il s’agit de regarder le code à un niveau d’abstraction supérieur à celui du compilateur, en comprenant non seulement ce qu’il fait, mais aussi pourquoi il le fait
J’ai utilisé l’obfuscation pour créer un grand jeu de données à partir d’un petit ensemble de fonctions de référence, puis construit un modèle qui classe du code binaire obfusqué jamais vu vers la fonction connue la plus proche
À l’époque, l’application que j’avais en tête était l’analyse statique de malwares, mais l’optimisation est en fait l’opposé de l’obfuscation
Ce que j’aimerais essayer à l’avenir, c’est un modèle de diffusion qui traite l’obfuscation comme du « bruit » à supprimer
Une chose que j’ai apprise, c’est que les compilateurs optimisants produisent une sortie très régulière
Une fois les adresses normalisées, la taille du « vocabulaire » des blocs de base devient assez réduite, de l’ordre d’environ 2000 tokens
Certaines « phrases » conservent une corrélation avec la sémantique du code source original, quelle que soit la quantité d’obfuscation ajoutée par-dessus
Certaines personnes appliquent aussi des techniques de synthèse à la superoptimisation
Il est donc possible que ce type d’approche s’y applique
Il y avait eu autrefois des discussions sur le fait que GitHub ajouterait des intégrations avec les outils de build courants
Et si l’on pouvait compiler tous les projets sur GitHub qui se compilent avec LLVM, puis faire tourner un modèle de diffusion sur leur représentation intermédiaire ?
La diffusion pourrait-elle aussi fonctionner au niveau binaire ?
Peut-on entraîner un modèle de diffusion qui, à partir d’un prompt, génère le binaire final d’un programme ?
Un arbre syntaxique abstrait serait probablement préférable, mais les binaires semblent au moins très faciles à tester rapidement pour savoir s’ils fonctionnent
Il y aurait beaucoup d’inconvénients, mais si c’est possible, j’ai hâte du jour où l’on pourra dire « crée-moi une appli qui fait ça » et où un modèle de diffusion générera tous les octets de cette appli
Je pose juste la question par curiosité
Cela augmenterait les chances de produire un programme valide
On pourrait générer directement du code machine, et il n’y aurait pas vraiment de raison de passer par une multitude d’étapes intermédiaires comme Python ou JS
J’aimerais aussi voir ça appliqué aux SDF
Tu penses à approximer des fonctions de distance avec des expressions algébriques, et à considérer l’algèbre elle-même comme un « langage de programmation » ?
Le rendu du PDF est extrêmement lent
C’est sans doute parce qu’il contient des commandes pour des figures générées par programmation
Ça donne cette impression d’article académique qui me manque ces temps-ci
https://arxiv.org/pdf/2405.20519
La partie appliquée aux travaux de graphisme inverse me rappelle cet article publié une semaine plus tôt : https://arxiv.org/abs/2405.15306