प्रोग्राम synthesis के लिए Syntax Tree Diffusion
(tree-diffusion.github.io)- ICLR 2025 का पेपर Tree Diffusion प्रोग्राम को एक-एक token बनाकर जनरेट करने के बजाय, execution result को देखते हुए प्रोग्राम को बार-बार edit करने वाला एक neural model प्रस्तावित करता है
- इसका मुख्य विचार यह है कि किसी भी context-free grammar से बने syntax tree पर, image diffusion की तरह noise को वापस हटाने के तरीके से training की जाती है
- noise को syntax tree के किसी भी node को उसी valid type वाले किसी दूसरे node से बदलने वाली random mutation के रूप में जोड़ा जाता है
- कोड को grammar की दृष्टि से valid बनाए रखते हुए सुधारा जाता है, इसलिए इसे program space की search के साथ जोड़ना आसान है
- inverse graphics में यह image को उसे बनाने वाले प्रोग्राम में बदलता है, और search के साथ मिलकर execution result देखते हुए आवश्यक specification के अनुसार graphics program को debug कर सकता है
Tree Diffusion का दृष्टिकोण
- Tree Diffusion प्रोग्राम synthesis के लिए syntax tree पर diffusion लागू करने की एक विधि है
- पेपर, arXiv, code and weights सार्वजनिक किए गए हैं
- मौजूदा बड़े language model कोड को एक-एक token जनरेट करने वाली autoregressive पद्धति का उपयोग करते हैं, और generation process के दौरान प्रोग्राम output को देखने वाला feedback नहीं होता
- LLM को सीधे edit सुझाने के लिए train करने वाली पद्धति के लिए पर्याप्त edit data चाहिए होता है, इसलिए यह कठिन हो सकता है
- Tree Diffusion context-free grammar के syntax tree पर डाले गए noise को वापस हटाने वाले model के रूप में प्रोग्राम को संशोधित करता है
noise, search, और उपयोग के मामले
- noise syntax tree में किसी random node को चुनकर, उसे replacement target node के समान valid type वाले दूसरे node से बदलने वाली random mutation है
- प्रोग्राम को शुरुआत से क्रमवार जनरेट करने के बजाय, बार-बार edit करते हुए syntactic validity बनाए रखी जाती है
- इस गुण की वजह से neural model को program space की search के साथ जोड़ना आसान हो जाता है
- inverse graphics कार्य में image को input लेकर, उस image को बनाने वाले प्रोग्राम में बदलने की विधि सीखी जाती है
- search के साथ जुड़ा सिस्टम graphics program लिख सकता है, execution result की जाँच कर सकता है, और आवश्यक specification को पूरा करने के लिए उसे debug कर सकता है
- यह भी दिखाया गया है कि हाथ से बनाए गए sketch के लिए भी graphics program लिखा जा सकता है
1 टिप्पणियां
Hacker News टिप्पणियाँ
यह Racket और MOOC के लिए hint generation पर किए गए काम से ज़्यादा मिलता-जुलता लगता है
पक्का याद नहीं कि वह किस विश्वविद्यालय का था, लेकिन मैंने एक प्रस्तुति देखी थी जिसमें syntax tree को modify करके और यह analyze करके कि target solution तक पहुँचने के लिए उसे कैसे बदलना था, छात्रों के लिए hints बनाए जाते थे
शायद यह लगभग 10 साल पहले की RacketCon प्रस्तुति थी, और हो सकता है कि इस तरह की methodology को आधुनिक machine learning approaches के साथ जोड़ा जा सके
प्रस्तुति मिल गई: https://invidious.baczek.me/watch?v=ijyFC36kVis
इस तरह के subtree mutation को 90 के दशक में Koza और Adami ने genetic algorithms के नाम से काफ़ी गहराई से देखा था, इसलिए यह दिलचस्प है
बस optimization function थोड़ा अलग था
पेपर में program tree को तेज़ी से generate करने वाले genetic algorithms पर 2000 की एक reference है, लेकिन लगता है कि मुख्य काम छूट गया है
अच्छा होगा अगर लेखक इसे पढ़ें और उन लोगों के काम में और गहराई से जाएँ
FFX और PGE दोनों ही बहुत तेज़ हैं
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
https://arxiv.org/pdf/2209.09675
PGE बनाने वाले के नज़रिए से, मैं लंबे समय से सोचता रहा हूँ कि reinforcement learning और, हाल में, diffusion techniques ऐसे algorithms में मददगार हो सकती हैं
हर algorithm को या तो search को बेहतर दिशा देने का कोई तरीका चाहिए, या फिर हैरान करने वाली तेजी से फँस जाने वाले local optima से बाहर निकालने का
genetic programming / evolutionary computation पर ज़्यादातर research का फ़ोकस premature convergence से बचने पर रहा है
साइट के विवरण के अनुसार, यह “1500 से अधिक स्कूलों में अपनाई गई सबसे authoritative और सबसे व्यापक रूप से इस्तेमाल की जाने वाली AI textbook” है
https://aima.cs.berkeley.edu/
ओह, मेरी गलती थी
मेरे पास 1992 और 1994 की Koza की दो मोटी किताबें हैं: Genetic Programming: On the Programming of Computers by Means of Natural Selection और Genetic Programming II : Automatic Discovery of Reusable Programs
बाद की दो किताबें मैंने नहीं पढ़ीं
उस समय बड़ी अड़चनें आंशिक रूप से इसे काफ़ी तेज़ बनाना थीं, और आंशिक रूप से यह सुनिश्चित करना था कि परिणाम इंसानों के लिए समझने लायक हों
दूसरे मामले में, खासकर बड़े language models अब काफ़ी बेहतर लगते हैं
readable results पाने की कोशिश में tree को restructure और prune करने में बहुत समय लग जाता था, इसलिए शायद इसकी मुख्य उपयोगिता उन्हीं मामलों तक सीमित रह गई जहाँ बहुत छोटे और सघन algorithms के और अधिक optimized versions खोजने के लिए काफ़ी resources लगाना उचित हो
लेकिन ज़्यादातर codebases में इससे कहीं आसान सुधार के मौके इतने ज़्यादा होते हैं कि चीज़ें उस बिंदु तक बहुत कम पहुँचती हैं जहाँ ऐसा प्रयास करना वाजिब लगे
फिर भी, concept के रूप में यह अब भी पसंद है
[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
program synthesis में Markov chain Monte Carlo का इस्तेमाल कोई बिल्कुल नया विचार नहीं है
जो reference सबसे पहले याद आता है, वह Josh Tenenbaum का काम है
WebPPL (web probabilistic programming language) में भी 3D spaceship synthesis जैसी बहुत-सी demos हैं
The Design and Implementation of Probabilistic Programming Languages और Probabilistic Models of Cognition से जुड़ी किताबें भी ज़ोरदार सिफ़ारिश के लायक हैं
MIT Probabilistic Computing Project के papers भी देखने लायक हैं
[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/
यहाँ जिस “जादू” की बात हो रही है, वह ठीक से समझ नहीं आ रहा।
पारंपरिक approach में शायद random image generate की जाती, फिर कोई distance metric निकाला जाता, और फिर simulated annealing जैसी optimization method से उस दूरी को minimize किया जाता।
यहाँ image representations के बीच के अंतर को optimize करने की बात समझ आती है, लेकिन program के token changes कैसे differentiable हो सकते हैं, यह समझ नहीं आ रहा।
मुख्य विचार शायद यह है कि एक neural network model को इस तरह train किया जा सकता है कि वह nodes को random तरीके से modify करके program edits के सुझाव दे।
इस neural network model को चलाने पर context-free grammar के अनुसार syntactically valid edits किए जा सकते हैं, जैसे किसी संख्या को केवल किसी दूसरी संख्या से replace करना।
सोच रहा हूँ कि इसे compiler/interpreter optimization पर कैसे लागू किया जा सकता है।
क्या execution के किसी हिस्से को, शायद assembly level पर, “dissect” करके ऐसे specialized optimizations निकाले जा सकते हैं जो output बदले बिना, compiled code के लिए खास हों और जिन्हें modern compilers deterministic तरीके से न खोज पाते हों?
यहाँ output से मतलब generated binary नहीं, बल्कि expected program output है।
मुझे नहीं लगता कि ऐसा tool, compiled artifacts पर train किए बिना, assembly को “discover” कर पाएगा।
model के पास यह concept नहीं है कि code कैसे या कहाँ execute होता है।
compiler research और supercompilers पर दशकों का काम हो चुका है, इसलिए अब ऐसे नए optimizations मिलना, जो साफ़ तौर पर बड़ा सुधार दें, लगभग असंभव के करीब पहुँच चुका है।
आज के compilers वाकई बहुत अच्छे हैं।
लेकिन इस तरह के approach की value code की intent को optimize करने में हो सकती है।
अगर यह समझ जाए कि code number sorting कर रहा है, तो वह उसी functional property वाला कोई तेज sorting algorithm लगा सकता है।
अगर unused data store किया जा रहा है, तो उसे store करना बंद कर सकता है।
यह compiler की तुलना में एक level ऊपर से code को देखने का नज़रिया है, जहाँ सिर्फ यह नहीं देखा जाता कि code क्या कर रहा है, बल्कि यह भी कि वह ऐसा क्यों कर रहा है।
मैंने obfuscation का उपयोग करके छोटे से correct function set से बड़ा dataset बनाया, और एक ऐसा model बनाया जो unseen obfuscated binary code को known functions में सबसे नज़दीकी function के रूप में classify करे।
उस समय मेरे दिमाग में application malware static analysis था, लेकिन optimization दरअसल obfuscation का उल्टा है।
आगे मैं एक diffusion model पर काम करना चाहूँगा जो obfuscation को हटाए जाने वाले “noise” की तरह treat करे।
एक बात जो सीखी, वह यह कि optimizing compilers बहुत regular output बनाते हैं।
addresses normalize करने के बाद basic blocks की “vocabulary” का size काफ़ी छोटा, लगभग 2000 tokens जैसा, रह जाता है।
कुछ खास “phrases” इस बात से correlation रखते हैं कि original source code का meaning क्या था, चाहे ऊपर कितनी भी obfuscation चढ़ा दी गई हो।
कुछ लोग synthesis techniques को superoptimization पर भी apply कर रहे हैं।
इसलिए संभव है कि यह approach वहाँ लागू हो सके।
पहले कभी GitHub के सामान्य build tools के साथ integration जोड़ने की बात हुई थी।
अगर GitHub पर मौजूद हर LLVM se compile hone wala project को compile किया जाए, और उसके intermediate representation पर diffusion model चलाया जाए, तो क्या होगा?
क्या diffusion binary level पर भी काम कर सकता है?
अगर prompt दिया जाए, तो क्या ऐसा diffusion model train किया जा सकता है जो program का final binary generate करे?
शायद abstract syntax tree बेहतर होगा, लेकिन binary पर कम से कम यह तेज़ी से test करना बहुत आसान होगा कि वह काम करता है या नहीं।
कमियाँ बहुत होंगी, लेकिन अगर यह संभव हुआ तो उस दिन का इंतज़ार रहेगा जब हम कहेंगे “ऐसा app बना दो जो यह काम करे” और diffusion model उस app के सारे bytes generate कर देगा।
बस जिज्ञासा से पूछ रहा हूँ।
इससे valid program बनने की संभावना अधिक होगी।
सीधे machine code generate किया जा सकता है, और खासकर Python या JS जैसे कई intermediate steps से गुज़रने की ज़रूरत नहीं पड़ेगी।
इसे SDF पर लागू होते देखना चाहूँगा।
क्या आपका मतलब है कि algebraic expressions से distance function approximate की जाए, और algebra को ही एक “programming language” की तरह देखा जाए?
PDF render होने में बहुत slow है।
शायद इसलिए कि इसमें programmatically generated figures के commands शामिल हैं।
इससे आजकल कम दिखने वाला वह academic paper वाला feel आता है।
https://arxiv.org/pdf/2405.20519
inverse graphics work पर लागू किया गया हिस्सा एक हफ़्ता पहले आए इस paper की याद दिलाता है: https://arxiv.org/abs/2405.15306