- Das ICLR-2025-Paper Tree Diffusion schlägt ein neuronales Modell vor, das Programme nicht Token für Token erzeugt, sondern sie unter Bezug auf die Ausführungsergebnisse wiederholt editiert
- Der Kern ist, dass auf einem Syntaxbaum, der aus einer beliebigen kontextfreien Grammatik erzeugt wurde, so gelernt wird, dass Rauschen ähnlich wie bei Bild-Diffusion zurückgenommen wird
- Das Rauschen wird als zufällige Mutation hinzugefügt, bei der ein beliebiger Knoten im Syntaxbaum durch einen anderen Knoten desselben korrekten Typs ersetzt wird
- Da der Code unter Beibehaltung eines grammatikalisch gültigen Zustands schrittweise korrigiert wird, lässt sich das leicht mit Suche (search) im Programmraum kombinieren
- Bei inverse graphics können Bilder in Programme zur Erzeugung dieser Bilder umgewandelt werden; in Kombination mit Suche lässt sich anhand der Ausführungsergebnisse ein Grafikprogramm so debuggen, dass es die Anforderungsspezifikation erfüllt
Der Ansatz von Tree Diffusion
- Tree Diffusion ist ein Verfahren, das für die Programmsynthese Diffusion auf Syntaxbäumen anwendet
- Paper, arXiv sowie Code und Gewichte sind veröffentlicht
- Bestehende große Sprachmodelle verwenden für Code eine autoregressive Methode, bei der Token für Token erzeugt wird; dabei gibt es im Generierungsprozess kein Feedback aus den Programmausgaben
- Ansätze, bei denen ein LLM direkt lernt, Bearbeitungen vorzuschlagen, können schwierig sein, weil dafür ausreichend Editierdaten benötigt werden
- Tree Diffusion überarbeitet Programme mit einem Modell, das das auf Syntaxbäume einer kontextfreien Grammatik aufgebrachte Rauschen zurücknimmt
Rauschen, Suche und Anwendungsfälle
- Das Rauschen ist eine zufällige Mutation, bei der nach Auswahl eines beliebigen Knotens im Syntaxbaum dieser durch einen anderen Knoten desselben korrekten Typs ersetzt wird
- Statt Programme von Grund auf sequentiell zu erzeugen, werden sie wiederholt editiert, während die syntaktische Gültigkeit erhalten bleibt
- Dadurch lässt sich das neuronale Modell leicht mit Suche im Programmraum kombinieren
- Bei Aufgaben aus inverse graphics wird gelernt, ein Eingabebild in ein Programm umzuwandeln, das dieses Bild erzeugt
- Ein mit Suche kombiniertes System kann Grafikprogramme schreiben, deren Ausführungsergebnisse prüfen und sie dann so debuggen, dass sie die Anforderungsspezifikation erfüllen
- Es wird auch gezeigt, dass sich für handgezeichnete Skizzen Grafikprogramme erstellen lassen
1 Kommentare
Hacker-News-Meinungen
Klingt eher nach der Arbeit, die mit Racket und der Generierung von Hinweisen für MOOCs gemacht wurde.
Ich bin mir nicht sicher, welche Universität das war, aber ich habe einmal einen Vortrag gesehen, in dem Syntaxbäume verändert und analysiert wurden, wie sie angepasst werden müssten, um zur Ziellösung zu gelangen, um daraus Hinweise für Studierende zu erzeugen.
Das war vermutlich ein RacketCon-Vortrag vor etwa zehn Jahren, und vielleicht ließe sich eine solche Methodik mit modernen Machine-Learning-Ansätzen kombinieren.
Habe den Vortrag gefunden: https://invidious.baczek.me/watch?v=ijyFC36kVis
Solche Teilbaum-Mutationen sind interessant, weil Koza und Adamı sie in den 90ern unter dem Namen genetische Algorithmen recht tiefgehend behandelt haben.
Nur die Optimierungsfunktion war etwas anders.
In dem Paper gibt es eine Referenz aus dem Jahr 2000 zu genetischen Algorithmen für die schnelle Erzeugung von Programmbäumen, aber die zentrale Arbeit scheint zu fehlen.
Ich hoffe, die Autoren lesen das und vertiefen sich in deren Arbeit.
FFX und PGE sind beide sehr schnell.
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
https://arxiv.org/pdf/2209.09675
Als jemand, der PGE entwickelt hat, habe ich schon länger gedacht, dass Reinforcement Learning und, in jüngerer Zeit, Diffusionsverfahren solchen Algorithmen helfen könnten.
Alle Algorithmen brauchen Methoden, die die Suche besser leiten oder sie aus lokalen Optima herausholen, in denen sie erstaunlich schnell landen.
Ein großer Teil der Forschung zu genetischer Programmierung/evolutionärem Rechnen konzentriert sich darauf, vorzeitige Konvergenz zu vermeiden.
Laut Website ist es „das maßgebliche und meistverwendete KI-Lehrbuch, das an über 1500 Hochschulen eingesetzt wird“.
https://aima.cs.berkeley.edu/
Tja, das war mein Fehler.
Ich besitze Kozas zwei dicke Bücher von 1992 und 1994, also Genetic Programming: On the Programming of Computers by Means of Natural Selection und Genetic Programming II : Automatic Discovery of Reusable Programs.
Die späteren beiden habe ich nicht gelesen.
Die großen Probleme, an denen es damals hakte, waren zum Teil, es schnell genug zu machen, und zum Teil, Ergebnisse zu bekommen, die für Menschen verständlich sind.
Bei Letzterem scheinen große Sprachmodelle deutlich besser zu sein.
Man verbrachte viel Zeit damit, Bäume umzustrukturieren und zu beschneiden, um interpretierbare Ergebnisse zu erhalten; daher schien der Hauptnutzen auf Fälle beschränkt zu sein, in denen es sich lohnt, viele Ressourcen in die Suche nach stärker optimierten Versionen sehr kleiner, dichter Algorithmen zu stecken.
Allerdings gibt es in den meisten Codebasen so viel leichter erreichbare Verbesserungen, dass man selten an den Punkt kommt, an dem sich ein solcher Versuch lohnt.
Konzeptionell mag ich es trotzdem immer noch.
[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
Markov-Chain-Monte-Carlo für Programmsynthese zu verwenden, ist nicht wirklich eine neue Idee.
Die Referenz, die mir sofort einfällt, ist die Arbeit von Josh Tenenbaum.
Auch WebPPL (eine webbasierte probabilistische Programmiersprache) hat viele Demos, etwa zur Synthese von 3D-Raumschiffen.
Die Bücher The Design and Implementation of Probabilistic Programming Languages und Probabilistic Models of Cognition kann ich ebenfalls sehr empfehlen.
Auch die Papers des MIT Probabilistic Computing Project sind einen Blick wert.
[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/
Ich verstehe die hier gemeinte „Magie“ nicht so recht
Bei einem traditionellen Ansatz hätte man wohl zufällige Bilder erzeugt, irgendein Distanzmaß berechnet und diese Distanz dann mit einem Optimierungsverfahren wie Simulated Annealing minimiert
Hier verstehe ich, dass die Differenz zwischen Bildrepräsentationen optimiert wird, aber mir ist nicht klar, wie Token-Änderungen in einem Programm differenzierbar sein können
Die Kernidee scheint zu sein, dass man ein neuronales Modell trainieren kann, das durch zufällige Transformation von Knoten Vorschläge für Programmänderungen macht
Wenn man dieses neuronale Modell ausführt, kann es gemäß einer kontextfreien Grammatik syntaktisch korrekte Änderungen vornehmen, etwa Zahlen nur durch Zahlen ersetzen
Ich frage mich, wie sich das auf Compiler-/Interpreter-Optimierung anwenden ließe
Könnte man Teile der Ausführung, vielleicht auf Assembly-Ebene, „sezieren“ und dabei, ohne die Ausgabe zu verändern, spezialisierte Optimierungen für den kompilierten Code erzeugen, die moderne Compiler deterministisch nicht finden?
Mit Ausgabe ist hier nicht das erzeugte Binary gemeint, sondern die erwartete Programmausgabe
Ich würde nicht erwarten, dass ein solches Tool Assembly „entdeckt“, wenn es nicht auf Compiler-Artefakten trainiert wurde
Das Modell hat kein Konzept davon, wie oder wo Code ausgeführt wird
Nach Jahrzehnten Compiler-Forschung und nach dem Einsatz von Supercompilern sind wir inzwischen an einem Punkt, an dem es nahezu unmöglich ist, neue Optimierungen zu entdecken, die noch spürbare Verbesserungen bringen
Heutige Compiler sind wirklich gut
Der Wert eines solchen Ansatzes könnte allerdings darin liegen, die Absicht des Codes zu optimieren
Wenn erkannt wird, dass Zahlen sortiert werden, könnte der Code durch einen schnelleren Sortieralgorithmus mit denselben funktionalen Eigenschaften ersetzt werden
Wenn ungenutzte Daten gespeichert werden, könnte man aufhören, sie zu speichern
Das betrachtet Code eine Ebene höher als ein Compiler und versteht nicht nur, was er tut, sondern auch warum
Ich habe mithilfe von Obfuskation aus einer kleinen Menge korrekter Funktionen einen großen Datensatz erzeugt und ein Modell gebaut, das zuvor nicht gesehene obfuskierte Binärcodes der jeweils ähnlichsten bekannten Funktion zuordnet
Die Anwendung, an die ich damals dachte, war statische Malware-Analyse, aber Optimierung ist im Grunde die Gegenseite der Obfuskation
Was ich künftig ausprobieren möchte, ist ein Diffusionsmodell, das Obfuskation als zu entfernendes „Rauschen“ behandelt
Eine Erkenntnis war, dass optimierende Compiler sehr regelmäßige Ausgaben erzeugen
Nach der Normalisierung von Adressen wird die „Vokabular“-Größe von Basic Blocks recht klein, etwa wie 2000 Tokens
Bestimmte „Phrasen“ korrelieren mit der Bedeutung des ursprünglichen Quellcodes, egal wie viel Obfuskation darübergelegt wird
Es gibt auch Leute, die Synthesetechniken auf Superoptimierung anwenden
Daher besteht durchaus die Möglichkeit, dass so ein Ansatz dort eingesetzt wird
Früher gab es die Rede davon, dass GitHub Integrationen mit gängigen Build-Tools hinzufügt
Was wäre, wenn man alle Projekte auf GitHub, die mit LLVM kompiliert werden, kompilieren und dann ein Diffusionsmodell auf deren Zwischenrepräsentation laufen lassen könnte?
Könnte Diffusion auch auf Binary-Ebene funktionieren?
Könnte man ein Diffusionsmodell trainieren, das aus einem Prompt das finale Binary eines Programms erzeugt?
Vermutlich wäre ein abstrakter Syntaxbaum besser, aber bei einem Binary ließe sich zumindest sehr einfach und schnell testen, ob es funktioniert
Es gäbe viele Nachteile, aber falls es möglich ist, freue ich mich auf den Tag, an dem man sagt: „Mach mir eine App, die so etwas tut“, und das Diffusionsmodell erzeugt jedes einzelne Byte dieser App
Nur so als Gedanke
Dann wäre die Wahrscheinlichkeit höher, ein gültiges Programm zu erzeugen
Man könnte direkt Maschinencode erzeugen, besonders ohne den Umweg über jede Menge Zwischenschritte wie Python oder JS nehmen zu müssen
Ich würde das gern auch auf SDFs angewendet sehen
Meinst du, eine Distanzfunktion durch algebraische Ausdrücke zu approximieren und die Algebra selbst als „Programmiersprache“ zu betrachten?
Das PDF rendert extrem langsam
Vermutlich liegt es daran, dass es Befehle für programmatisch erzeugte Abbildungen enthält
Es vermittelt dieses Gefühl akademischer Papers, das man heutzutage vermisst
https://arxiv.org/pdf/2405.20519
Der Teil zur Anwendung auf Inverse-Graphics-Aufgaben erinnert mich an dieses Paper, das eine Woche früher erschienen ist: https://arxiv.org/abs/2405.15306