プログラム合成のための構文木 Diffusion
(tree-diffusion.github.io)- ICLR 2025 論文 Tree Diffusion は、プログラムを1トークンずつ生成する代わりに、実行結果を参照しながらプログラムを反復的に 編集 するニューラルモデルを提案している
- 中核となるのは、任意の文脈自由文法で作られた 構文木 の上で、画像 diffusion のようにノイズを巻き戻す方式で学習する点である
- ノイズは、構文木の任意のノードを同じ 正しい型 の別ノードに置き換えるランダムな変異として追加される
- 文法的に有効な状態を保ったままコードを修正していくため、プログラム空間の 検索(search) と組み合わせやすい
- inverse graphics では、画像を生成プログラムへ変換し、検索と組み合わせることで実行結果を見ながら要求仕様に合うグラフィックスプログラムをデバッグできる
Tree Diffusion のアプローチ
- Tree Diffusion は、プログラム合成のために 構文木上で diffusion を適用する方法である
- 論文、arXiv、コードと重み が公開されている
- 既存の大規模言語モデルは、コードを1トークンずつ生成する 自己回帰方式 を用い、生成過程でプログラムの出力結果を観察するフィードバックがない
- LLM に直接編集を提案するよう学習させる方式は、十分な 編集データ が必要なため難しい場合がある
- Tree Diffusion は、文脈自由文法の構文木に加えられたノイズを巻き戻すモデルとしてプログラムを修正する
ノイズ、検索、適用事例
- ノイズは、構文木で任意のノードを選んだ後、置換対象ノードと同じ 正しい型 の別ノードに置き換えるランダムな変異である
- プログラムを最初から逐次生成するのではなく、反復編集しながら 構文の妥当性 を維持する
- この特性により、ニューラルモデルをプログラム空間の 検索 と組み合わせやすい
- inverse graphics のタスクでは、画像を入力として受け取り、その画像を生成するプログラムへ変換する方法を学習する
- 検索と組み合わせたシステムは、グラフィックスプログラムを作成し、実行結果を確認した後、要求仕様を満たすようにデバッグできる
- 手描きスケッチに対してもグラフィックスプログラムを作成できることを示している
1件のコメント
Hacker News の意見
Racket と MOOC 向けのヒント生成で行われていた研究に、より近いように聞こえる。
どの大学だったかは定かではないが、構文木を変形し、目標の解答に到達するにはどう修正すべきだったかを分析して、学生向けのヒントを生成する発表を見たことがある。
おそらく 10 年ほど前の RacketCon の発表で、こうした方法論を最新の機械学習アプローチと組み合わせられるかもしれない。
発表を見つけた: https://invidious.baczek.me/watch?v=ijyFC36kVis
こうした部分木の変異は、90 年代に Koza と Adamı が遺伝的アルゴリズムという名の下でかなり深く扱っていたテーマなので興味深い。
最適化関数が少し違っていただけだ。
論文にはプログラム木を高速に生成する遺伝的アルゴリズムに関する 2000 年の参考文献が 1 件あるが、中心的な研究は抜けているように見える。
著者たちがこれを読んで、彼らの研究を掘り下げてくれるとよい。
FFX と PGE はどちらも非常に高速だ。
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
https://arxiv.org/pdf/2209.09675
PGE を作った立場から、強化学習、そしてより最近では拡散手法が、こうしたアルゴリズムの助けになり得ると考えてきた。
どのアルゴリズムにも、探索をよりうまく誘導するか、驚くほど早く陥る局所最適解から抜け出させる方法が必要だ。
遺伝的プログラミング／進化計算研究の大半は、早期収束を避けることに焦点を当てている。
サイトの説明によれば、「1500 校以上で採用されている、最も権威があり最も広く使われている AI 教科書」だ。
https://aima.cs.berkeley.edu/
しまった、こちらの間違いだった。
1992 年と 1994 年に出た Koza の分厚い本 2 冊、つまり Genetic Programming: On the Programming of Computers by Means of Natural Selection と Genetic Programming II : Automatic Discovery of Reusable Programs を持っている。
その後の 2 冊は読んでいない。
当時行き詰まっていた大きな問題は、一つには十分に高速化すること、もう一つには結果を人間が理解できる形で出すことだった。
後者については、特に大規模言語モデルのほうがずっと優れているように見える。
解読可能な結果を得るために木を再構成して枝刈りするのに多くの時間を費やすことになり、そのため主な価値は、非常に小さく密度の高いアルゴリズムの、より最適化された版を見つけるために多くのリソースを投入する価値がある場合に限られていたように思う。
ただ、ほとんどのコードベースにはもっと簡単に取れる低い枝の果実があまりにも多く、こうした試みに価値が出る段階まで行くことはめったにない。
それでも概念としては今でも好きだ。
[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
プログラム合成にマルコフ連鎖モンテカルロを使うのは、特に新しいアイデアではない。
すぐ思い浮かんだ参考文献は Josh Tenenbaum の研究だ。
WebPPL（Web 確率的プログラミング言語）にも、3D 宇宙船の合成のようなデモが多い。
The Design and Implementation of Probabilistic Programming Languages と Probabilistic Models of Cognition 関連の本も強くお勧めする。
MIT Probabilistic Computing Project の論文も読む価値がある。
[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/
ここで言う「魔法」がよく理解できない
伝統的なアプローチなら、ランダムな画像を生成し、何らかの距離尺度を計算したうえで、焼きなまし法のような最適化手法でその距離を最小化していたはず
ここでは画像表現間の差分を最適化するということは分かるが、プログラムのトークン変更がどうやって微分可能になり得るのか分からない
重要なアイデアは、ノードをランダムに変形してプログラム修正案を出すニューラルネットワークモデルを学習できる、という点にあるように見える
このニューラルネットワークモデルを実行すると、文脈自由文法に従って構文的に正しい修正、たとえば数値は数値だけで置き換えるといった編集ができる
これをコンパイラ／インタプリタ最適化に適用したらどうなるのか気になる
実行の一部を、場合によってはアセンブリレベルで「解剖」して、出力を変えずに、現代のコンパイラが決定論的には見つけられなかったコンパイル済みコード向けの特殊な最適化を作り出せるだろうか？
ここでいう出力とは、生成されたバイナリではなく、期待されるプログラム出力のこと
こうしたツールがコンパイル成果物で学習されていない限り、アセンブリを「発見」するとは期待しない
モデルには、コードがどのように、あるいはどこで実行されるかという概念がない
何十年にもわたるコンパイラ研究とスーパーコンパイラが動き続けた後なので、今では目に見える改善をもたらす新しい最適化を発見できる可能性は、ほとんど不可能に近いところまで来ている
今日のコンパイラは本当に優秀
ただし、このような方式の価値は、コードの意図を最適化するところにあるかもしれない
数値のソートをしていると判断すれば、同じ機能的性質を持つ、より高速なソートアルゴリズムにコードを置き換えられる
使われていないデータを保存しているなら、保存をやめられる
コンパイラが見るより一段高いレベルでコードを見て、何をしているかだけでなく、なぜそうしているかも理解するという見方がある
難読化を使って小さな正解関数集合から大きなデータセットを作り、未見の難読化バイナリコードを既知の関数のうち最も近いものに分類するモデルを作った
研究当時に念頭に置いていた応用はマルウェアの静的解析だったが、最適化は実のところ難読化の反対側にある
今後やってみたいのは、難読化を取り除くべき「ノイズ」として扱う拡散モデル
学んだことの一つは、最適化コンパイラは非常に規則的な出力を作るということ
アドレスを正規化すると、基本ブロックの「語彙」サイズは約2000トークン程度とかなり小さくなる
特定の「句」は、その上にどれだけ難読化を重ねても、元のソースコードの意味と相関を持つ
合成手法を超最適化に適用している人たちもいる
だから、この方式が適用される可能性はある
以前、GitHubが一般的なビルドツールとの統合を追加するという話があった
GitHub上にある、LLVMでコンパイルされるすべてのプロジェクトをコンパイルし、その中間表現の上で拡散モデルを走らせられたらどうだろう？
拡散はバイナリレベルでも機能するだろうか？
プロンプトを与えるとプログラムの最終バイナリを生成する拡散モデルを学習できるだろうか？
おそらく抽象構文木のほうが良いだろうが、バイナリは少なくとも動作するかどうかを素早くテストするのは非常に簡単そう
欠点は多いだろうが、可能なら「こういうことをするアプリを作って」と言うと拡散モデルがそのアプリの全バイトを生成する日が楽しみ
ただ気になったので投げてみる
そうすれば、有効なプログラムを作れる確率が高くなる
直接機械語コードを生成できるのに、とくにPythonやJSのような中間段階を大量に経由する理由はない
SDFにも適用したところを見てみたい
代数式で距離関数を近似し、代数そのものを「プログラミング言語」と見なすようなことを考えているのかな？
PDFのレンダリングがものすごく遅い
おそらくプログラムで生成した図のコマンドが入っているからだと思う
最近では懐かしい学術論文らしさを感じる
https://arxiv.org/pdf/2405.20519
逆グラフィックスのタスクに適用している部分は、1週間前に出たこの論文を思い出させる: https://arxiv.org/abs/2405.15306