Program Sentezi için Sözdizim Ağacı Diffusion
(tree-diffusion.github.io)- ICLR 2025 makalesi Tree Diffusion, programları tek tek token üreterek oluşturmak yerine, yürütme sonucunu referans alarak programları yinelemeli biçimde düzenleyen bir sinirsel model öneriyor
- Temel nokta, rastgele bir bağlamdan bağımsız gramerle oluşturulan sözdizim ağaçları üzerinde, görüntü diffusion’ında olduğu gibi gürültüyü geri çevirme yöntemiyle eğitilmesi
- Gürültü, sözdizim ağacındaki rastgele düğümlerin aynı geçerli tipteki başka düğümlerle değiştirilmesi şeklindeki rastgele mutasyonlarla ekleniyor
- Dilbilgisel olarak geçerli durumu koruyarak kodu düzelttiği için, program uzayında arama (search) ile birleştirilmesi kolay
- Inverse graphics alanında görüntüyü onu üreten programa dönüştürür ve aramayla birleştirildiğinde, yürütme sonucuna bakarak gereksinim tanımına uyan grafik programını debug edebilir
Tree Diffusion yaklaşımı
- Tree Diffusion, program sentezi için sözdizim ağacında diffusion uygulayan bir yöntemdir
- Makale, arXiv, kod ve ağırlıklar yayımlanmış durumda
- Mevcut büyük dil modelleri kodu tek tek token üreten otoregresif bir yöntem kullanır ve üretim sürecinde programın çıktı sonucunu gözlemleyen bir geri bildirim yoktur
- LLM’in doğrudan düzenleme önermesini öğreten yaklaşımlar yeterli düzenleme verisi gerektirdiğinden zor olabilir
- Tree Diffusion, bağlamdan bağımsız gramerin sözdizim ağacına eklenen gürültüyü geri çeviren bir modelle programları değiştirir
Gürültü, arama ve uygulama örnekleri
- Gürültü, sözdizim ağacında rastgele bir düğüm seçildikten sonra, değiştirme hedefi olan düğümle aynı geçerli tipteki başka bir düğümle değiştirilmesi şeklindeki rastgele mutasyondur
- Programı sıfırdan sırayla üretmek yerine yinelemeli olarak düzenlerken sözdizim geçerliliğini korur
- Bu özellik sayesinde sinirsel modeli program uzayında arama ile birleştirmek kolaydır
- Inverse graphics görevlerinde, bir görüntüyü girdi olarak alıp o görüntüyü üreten programa dönüştürme yöntemi öğrenilir
- Aramayla birleştirilmiş sistem, grafik programını yazar, yürütme sonucunu kontrol eder ve ardından gereksinim tanımını karşılayacak şekilde debug edebilir
- Elle çizilmiş eskizler için de grafik programı yazabildiğini gösterir
1 yorum
Hacker News yorumları
Bu bana Racket ve MOOC’lar için ipucu üretme konusunda yapılan çalışmalara daha çok benziyor
Hangi üniversite olduğundan emin değilim ama sözdizim ağaçlarını dönüştürüp hedef çözüme ulaşmak için nasıl düzenlenmeleri gerektiğini analiz ederek öğrenciler için ipuçları üreten bir sunum izlemiştim
Muhtemelen yaklaşık 10 yıl önceki bir RacketCon sunumuydu; bu tür bir metodoloji modern makine öğrenimi yaklaşımlarıyla birleştirilebilir belki
Sunumu buldum: https://invidious.baczek.me/watch?v=ijyFC36kVis
Bu tür alt ağaç mutasyonları ilginç; çünkü 90’larda Koza ve Adamı tarafından genetik algoritmalar adı altında epey derinlemesine ele alınmış bir konuydu
Sadece optimizasyon fonksiyonu biraz farklıydı
Makalede program ağaçlarını hızlı üretmeye yönelik genetik algoritmalarla ilgili 2000 tarihli bir referans var ama asıl çalışma eksik gibi görünüyor
Yazarların bunu okuyup o kişilerin çalışmalarını daha derinlemesine incelemesini isterim
FFX ve PGE’nin ikisi de çok hızlı
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
https://arxiv.org/pdf/2209.09675
PGE’yi yapan biri olarak, pekiştirmeli öğrenmenin ve daha yakın zamanda da difüzyon tekniklerinin bu algoritmalara yardımcı olabileceğini düşünüyordum
Tüm algoritmaların, aramayı daha iyi yönlendirecek ya da şaşırtıcı derecede hızlı içine düşülen yerel optimumlardan çıkmayı sağlayacak bir yönteme ihtiyacı var
Genetik programlama/evrimsel hesaplama araştırmalarının çoğu erken yakınsamadan kaçınmaya odaklanıyor
Sitedeki açıklamaya göre bu, “1500’den fazla okulda benimsenmiş, en yetkin ve en yaygın kullanılan yapay zeka ders kitabı”
https://aima.cs.berkeley.edu/
Vay, bu benim hatamdı
Koza’nın 1992 ve 1994’te çıkan iki kalın kitabı, yani Genetic Programming: On the Programming of Computers by Means of Natural Selection ve Genetic Programming II : Automatic Discovery of Reusable Programs bende var
Sonraki iki kitabı okumadım
O dönemde takılınan büyük sorun kısmen bunu yeterince hızlı yapmak, kısmen de sonuçların insanlar tarafından anlaşılabilir olmasını sağlamaktı
İkincisinde özellikle büyük dil modelleri çok daha iyi görünüyor
Anlaşılabilir sonuçlar elde etmek için ağaçları yeniden yapılandırıp budamaya çok zaman harcanıyordu; bu yüzden ana değerinin, çok küçük ve yoğun algoritmaların daha optimize edilmiş sürümlerini bulmaya çok kaynak ayırmaya değen durumlarla sınırlı kaldığını düşünüyorum
Ancak çoğu kod tabanında çok daha kolay toplanacak o kadar çok meyve var ki, böyle bir denemeye değecek noktaya gelmek nadir oluyor
Yine de kavramsal olarak hâlâ hoşuma gidiyor
[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 sentezi için Markov zinciri Monte Carlo kullanmak pek de yeni bir fikir değil
Aklıma hemen gelen kaynak Josh Tenenbaum’un çalışmaları
WebPPL’de (web tabanlı olasılıksal programlama dili) 3D uzay gemisi sentezi gibi pek çok demo da var
The Design and Implementation of Probabilistic Programming Languages ile Probabilistic Models of Cognition kitaplarını da şiddetle tavsiye ederim
MIT Probabilistic Computing Project’in makalelerine de bakmaya değer
[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/
Burada bahsedilen “sihri” pek anlayamıyorum
Geleneksel bir yaklaşım olsaydı rastgele bir görüntü üretir, bir mesafe ölçütü hesaplar, sonra da simulated annealing gibi bir optimizasyon yöntemiyle o mesafeyi en aza indirirdi
Burada görüntü temsilleri arasındaki farkı optimize ettiklerini anlıyorum ama programın token değişikliklerinin nasıl türevlenebilir olabileceğini bilmiyorum
Temel fikir, düğümleri rastgele dönüştürerek program değişikliği önerileri yapan bir sinir ağı modelinin eğitilebilmesi gibi görünüyor
Bu sinir ağı modeli çalıştırıldığında, bağlamdan bağımsız gramer uyarınca sözdizimsel olarak geçerli değişiklikler; örneğin sayıların yalnızca sayılarla değiştirilmesi türünden düzenlemeler yapılabiliyor
Bunu derleyici/yorumlayıcı optimizasyonuna uygulamak nasıl olur merak ediyorum
Çalıştırmanın bir bölümünü, belki assembly düzeyinde “parçalara ayırıp”, çıktıyı değiştirmeden modern derleyicilerin deterministik olarak bulamadığı, derlenmiş koda özgü optimizasyonlar üretebilir mi?
Burada çıktı derlenen ikili dosya değil, beklenen program çıktısı anlamına geliyor
Böyle bir aracın, derleyici çıktıları üzerinde eğitilmeden assembly’yi “keşfetmesini” beklemem
Modelin kodun nasıl veya nerede çalıştığına dair bir kavramı yok
Onlarca yıllık derleyici araştırması ve süper derleyicilerin çalışmasının ardından, artık gözle görülür iyileştirmeler sağlayacak yeni optimizasyonlar keşfetme olasılığının neredeyse imkânsız olduğu bir noktadayız
Günümüz derleyicileri gerçekten çok iyi
Ancak bu tür bir yaklaşımın değeri, kodun niyetini optimize etmekte olabilir
Sayıları sıraladığını anlarsa, kodu aynı işlevsel özelliklere sahip daha hızlı bir sıralama algoritmasıyla değiştirebilir
Kullanılmayan verileri saklıyorsa saklamayı bırakabilir
Koda derleyicinin gördüğünden bir seviye daha yukarıdan bakma; yalnızca ne yaptığını değil, neden yaptığını da anlama bakışı var
Obfuscation kullanarak küçük bir doğru fonksiyon kümesinden büyük bir veri seti oluşturdum ve daha önce görmediği obfuscation uygulanmış ikili kodu bilinen fonksiyonlar arasından en yakın olana sınıflandıran bir model yaptım
Araştırma sırasında aklımdaki uygulama kötü amaçlı yazılımların statik analiziydi, ama optimizasyon aslında obfuscation’ın karşı tarafı
İleride denemek istediğim şey, obfuscation’ı giderilmesi gereken “gürültü” olarak ele alan bir difüzyon modeli
Öğrendiğim şeylerden biri, optimize edici derleyicilerin çok düzenli çıktılar ürettiği
Adresleri normalize ettikten sonra temel blokların “söz dağarcığı” boyutu yaklaşık 2000 token gibi oldukça küçük hale geliyor
Belirli “ifadeler”, üzerine ne kadar obfuscation eklerseniz ekleyin, özgün kaynak kodun anlamıyla korelasyon taşıyor
Sentez tekniklerini süper optimizasyona uygulayanlar da var
Dolayısıyla bu yaklaşımın uygulanma ihtimali var
Eskiden GitHub’ın yaygın derleme araçlarıyla entegrasyon ekleyeceğine dair bir şeyler vardı
GitHub’daki LLVM ile derlenen tüm projeleri derleyip, bunların ara temsili üzerinde bir difüzyon modeli çalıştırabilsek nasıl olurdu?
Difüzyon ikili dosya düzeyinde de çalışabilir mi?
Bir prompt verildiğinde programın nihai ikili dosyasını üreten bir difüzyon modeli eğitilebilir mi?
Muhtemelen soyut sözdizim ağacı daha iyi olurdu, ama ikili dosyalar en azından çalışıp çalışmadığını hızlıca test etmek açısından çok kolay görünüyor
Dezavantajları çok olurdu, ama mümkünse “şöyle bir iş yapan bir uygulama yap” dediğimizde difüzyon modelinin o uygulamanın tüm byte’larını ürettiği günü dört gözle bekliyorum
Sadece meraktan ortaya atıyorum
Böylece geçerli bir program üretme olasılığı daha yüksek olur
Doğrudan makine kodu üretebiliyorken, özellikle Python ya da JS gibi bir sürü ara aşamadan geçmeye gerek yok
SDF’ye de uygulanmış halini görmek isterim
Mesafe fonksiyonunu cebirsel ifadelerle yaklaşık olarak ifade edip, cebirin kendisini “programlama dili” olarak görmeyi mi kastediyorsun?
PDF çok yavaş render ediliyor
Muhtemelen programlamayla üretilmiş şekillerin komutlarını içerdiği içindir
Bugünlerde özlediğim akademik makale hissini veriyor
https://arxiv.org/pdf/2405.20519
Ters grafik çalışmasına uygulanmış kısmı, bir hafta önce çıkan şu makaleyi hatırlatıyor: https://arxiv.org/abs/2405.15306