FunSearch: LLM ile matematik ve bilim alanlarında yeni keşifler
(deepmind.google)- Google DeepMind'in FunSearch sistemi, önceden eğitilmiş LLM'leri ve otomatik değerlendiricileri birleştirerek matematik ve bilgisayar bilimi problemlerinde doğrulanabilir yeni çözümleri kod biçiminde arıyor
- LLM yeni programlar üretiyor, otomatik değerlendirici bunları puanlıyor ve yüksek puan alan programlar yeniden havuza eklenerek çözüm evrimsel yineleme ile geliştiriliyor
- cap set problem için bazı ayarlarda bugüne kadar bulunan en büyük cap set keşfedildi ve mevcut son teknoloji hesaplamalı çözücülerin zorlandığı ölçeklerde de güçlü performans gösterildi
- Aynı yaklaşım online bin packing problemine de uygulandı; verinin özelliklerine göre ayarlanmış programlar, mevcut sezgisel yöntemlerden daha az sayıda bin ile aynı sayıda öğeyi yerleştirebildi
- Ortaya çıkan sonuçlar insanların okuyabileceği kısa programlar olduğu için, araştırmacılar çözüm yapısını inceleyebiliyor ve bunu insan-yapay zeka iş birliğiyle problem kurulumunu iyileştirmede kullanabiliyor
FunSearch'ün temel fikri
- FunSearch, matematik ve bilgisayar biliminde yeni çözümler bulmak için bilgisayar kodu olarak yazılmış fonksiyonları arıyor
- Adını, fonksiyonları (function) aramasından alıyor
- LLM'ler gerçeğe aykırı bilgiler üretebildiği için FunSearch, yaratıcı öneriler sunan LLM'yi otomatik bir değerlendirici (evaluator) ile birleştirerek hatalı fikirleri eliyor
- Zor bilimsel ve matematiksel açık problemlerde LLM ile yeni keşif üreten ilk örneklerden biri sayılıyor
Evrimsel yineleme yapısı
- Kullanıcı önce problem tanımını kod biçiminde yazıyor
- Buna programı değerlendirme süreci de dahil oluyor
- Program havuzunu başlatacak bir seed program da ekleniyor
- Her yinelemede mevcut program havuzunun bir bölümü LLM'ye veriliyor
- LLM, mevcut programları temel alarak yeni programlar üretiyor
- Yeni programlar otomatik olarak çalıştırılıp değerlendiriliyor
- Yüksek puan alan programlar yeniden program veritabanına ekleniyor
- Kullanıcı istediği anda o ana kadar bulunan en yüksek puanlı programı alabiliyor
- FunSearch, Google PaLM 2 kullandı ancak kod üzerinde eğitilmiş diğer LLM'lerle de uyumlu
- Zor kombinatoryal problemlere yanıt verebilmek için arama yapısı da güçlendirildi
- Probleme dair genel bilgiden başlayıp yeni keşif için gereken çekirdek fikirlere odaklanıyor
- Fikir çeşitliliğini artırarak tıkanmayı önlüyor
- Evrim sürecini paralel çalıştırarak verimliliği yükseltiyor
Cap set problem üzerindeki sonuçlar
- İlk uygulama hedefi, onlarca yıldır farklı araştırma alanlarındaki matematikçileri zorlayan cap set problem oldu
- Bu problem, yüksek boyutlu bir ızgarada üç noktanın aynı doğru üzerinde bulunmadığı bir nokta kümesinin, yani cap set'in azami büyüklüğünü bulmayı amaçlıyor
- Ayrıca ekstremal kombinatorik (extremal combinatorics) içindeki başka problemlere model görevi görüyor
- Olası durumların sayısı hızla evrendeki atom sayısını aştığı için brute-force hesaplama işe yaramıyor
- FunSearch, program biçimindeki çözümler üreterek bazı ayarlarda bugüne kadar bulunan en büyük cap set'i keşfetti
- Bu sonuç, son 20 yıldaki cap set boyutundaki en büyük artış anlamına geliyor ve problem ölçeği mevcut son teknoloji hesaplamalı çözücülerin bugünkü kapasitesini aştığında da daha iyi performans gösteriyor
- Sezgisel içgörü üretmenin zor olduğu kombinatoryal problemlerde mevcut sonuçların ötesine geçilebildiğini gösterdi ve bunun gelecekte benzer kombinatorik kuram problemleri ile iletişim kuramı gibi alanlara uzanma potansiyeli bulunuyor
İnsan tarafından yorumlanabilir kısa programlar
- FunSearch, yalnızca cevap listesi veren bir kara kutu değil; çözümün nasıl kurulduğunu gösteren programlar üretiyor
- Bu yaklaşım, bilimde yeni keşifleri ya da olguları üretim süreçleriyle açıklama yönündeki genel anlayışla da örtüşüyor
- FunSearch, düşük Kolmogorov complexity'ye sahip, sıkıştırılmış programlar olarak ifade edilen çözümleri tercih ediyor
- Kolmogorov complexity, bir çözümü üreten en kısa bilgisayar programının uzunluğudur
- Kısa programlar çok büyük nesneleri açıklayabildiği için, iğne arar gibi taranan dev problemlere ölçeklenmeye yardımcı oluyor
- Program çıktıları araştırmacıların anlamasını kolaylaştırıyor
- Bazı yüksek puanlı çıktı kodlarında ilgi çekici simetriler gözlendi ve buradan hareketle problem kurulumu rafine edilerek daha iyi çözümler elde edildi
- Jordan Ellenberg, FunSearch'ün “saldırı stratejileri geliştirmek için tamamen yeni bir mekanizma” sunduğunu ve üretilen çözümlerin sayı listelerinden kavramsal olarak çok daha zengin olduğunu söylüyor
Online bin packing uygulaması
- FunSearch, pratik bir bilgisayar bilimi problemi olan bin packing için de uygulandı
- Bin packing, farklı boyutlardaki öğeleri mümkün olan en az sayıda bin içine yerleştirme problemidir
- Gerçek dünyadaki kullanım örnekleri arasında konteyner yükleme ve veri merkezlerinde maliyeti azaltmak için hesaplama işlerinin atanması yer alıyor
- Online bin packing genellikle insanların deneyimine dayalı sezgisel yöntemlerle ele alınıyor
- Boyut, zamanlama ve kapasitenin değiştiği belirli durumların her biri için bir kural kümesi bulmak zor olabilir
- FunSearch, cap set problem'den çok farklı bir problem olmasına rağmen kolayca kuruldu ve verinin özelliklerine göre otomatik ayarlanmış programlar üretti
- Üretilen programlar, mevcut sezgisel yöntemlerden daha az sayıda bin ile aynı sayıda öğeyi yerleştirdi
- Sinir ağları veya pekiştirmeli öğrenme gibi diğer yapay zeka yaklaşımları da zor kombinatoryal problemlerde etkili olabilir, ancak dağıtıma almak için ciddi kaynak gerektirebilir
- FunSearch, denetlenmesi ve dağıtıma alınması kolay kod ürettiği için, çeşitli gerçek endüstriyel sistemlere girebilecek türde çözümler oluşturabiliyor
2024 güncellemesi ve genişleme
- Aralık 2024'te yayımlanan arXiv raporu, FunSearch yaklaşımının kombinatoryal rekabetçi programlamada insan performansını artırmak için kullanılabileceğini gösteriyor
- Codeforces gibi geleneksel kodlama yarışmaları, zaman ve bellek kısıtları içinde klasik algoritma problemlerine tam çözümler gerektiriyor
- Kombinatoryal yarışmalar tek bir doğru cevap değil, mümkün olan en iyi yaklaşık çözümü arayan karmaşık problemlerle ilgileniyor
- Bu yaklaşım, en üst yüzdelik dilimdeki yarışmacıların bulduğundan daha iyi çözümler üretebiliyor
- İnsan programcı çözüm kodunun backbone kısmını yazıyor, LLM ise bunu yöneten fonksiyonları yaratıcı biçimde evrimleştiren bir iş birliği yapısı içinde çalışıyor
- Genel amaçlı LLM'ler geliştikçe, koda özel modeller zorunlu olmaktan çıktı ve yöntem Gemini 1.5 Flash temelinde kullanılabiliyor
- Rekabetçi programlamanın ötesinde FunSearch, Bayesian optimization çerçevesinde fonksiyonları daha iyi optimize etme yollarını bulmak için de kullanılıyor
LLM tabanlı keşiflerin yönü
- FunSearch, LLM'lerin halüsinasyonlarını önleyecek mekanizmalar kurulduğunda, yalnızca yeni matematiksel keşifler için değil, önemli gerçek dünya problemlerine potansiyel çözümler üretmek için de kullanılabileceğini gösteriyor
- Bilim ve endüstrideki eski ya da yeni problemlerde, LLM tabanlı yöntemlerle etkili ve özelleştirilmiş algoritmalar üretmek zamanla yaygın hale gelebilir
- FunSearch, LLM'lerdeki genel ilerlemeye paralel olarak gelişebilir ve yeteneklerini çeşitli bilimsel ve mühendislik problemlerine doğru genişletmesi bekleniyor
1 yorum
Hacker News görüşleri
Burada LLM’in ne kadar gerekli olduğunu merak ediyorum
Görünüşe göre LLM’in rolü, verilen tür imzasını izleyen bir Python fonksiyonu gibi makul görünen bir şey üretmek
Ama LLM olmadan da verilen tür imzasını karşılayan rastgele, geçerli Python fonksiyonları oluşturabilmek gerekir gibi geliyor. [1] ile aynı alıştırma, sadece çok daha karmaşık bir dili hedefliyor; sınırlı bir dil kullanmak da daha rahat olabilir. PushGP [2] gibi bir yaklaşım da mümkün olabilir diye düşünüyorum
Sorularım şunlar: (1) LLM’in burada kattığı değer ne; yakınsama için gereken değerlendirme sayısını ciddi biçimde azaltıyor mu, azaltıyorsa nasıl? (2) Aynı problemde başka genetik programlama teknikleri daha mı az rekabetçi ve daha düşük uygunlukta çözümler mi üretiyor? (3) Daha geleneksel genetik programlama benzer uygunluğa ulaşırsa, LLM eğitim maliyeti de dahil edildiğinde hesaplama maliyeti farkı var mı?
[1] http://www.davidmontana.net/papers/stgp.pdf
[2] https://faculty.hampshire.edu/lspector/push.html
Maymunlar ve daktilolar tek başına yetmez; burada Palm2 kullanılmasının nedeni adayların rastgele değil, makul olması gerektiği. Saçma programlara zaman harcamak istemiyorlar
Üstelik rastgele program üretimine dayalı genetik algoritmalarda cold start sorunu çok büyük. Tüm adayların uygunluğu 0 ise başlangıçta, muhtemelen sonuna kadar da ilerleme olmayabilir
Genetik algoritmalara çok aşina değilim ama bu kadarlık bir şeyi genetik algoritmanın bulamayacağını sanmıyorum. Yine de gerçekten çok denemiş biri varsa şaşırırım
Öte yandan makalenin Ek A.2 bölümünde görüldüğü gibi, LLM’siz genetik bir yaklaşımın LLM yaklaşımına göre daha fazla elle tasarım gerektirmesi muhtemel
Burada LLM’in yarattığı fark, olası mutasyon uzayını büyük ölçüde anlamsal olarak makul programlarla sınırlaması
3. maddeye gelince, eğitilmiş bir LLM çok sayıda amaç için yararlı olduğundan, sıfırdan eğitme maliyeti de amorti edilirse büyük sayılmaz. FunSearch çerçevesine uyacak şekilde ince ayar yapmanın ek maliyeti olabilir, ama ince ayar maliyeti oldukça küçüktür. Bu çerçevede kullanılması, yalnızca genetik programlama kullanmaktan muhtemelen daha avantajlıdır
LLM arama uzayını büyük ölçüde daraltıyor; elbette çoğu zaman yanlış daraltabiliyor, ama ardından tümevarımsal program sentezi uygulanıp ince ayar ve test yapılabiliyor. LLM olmadan bu yaklaşım, bildiğim kadarıyla şu anda mümkün değil. Çünkü en basit durumlarda bile tamamen anlamsız milyarlarca programı test etmek gerekiyor
Önemli bağlam şu: Bu keşif, kombinatorikteki belirli bir sayının geçen yıl bilinen 2.218~2.756 aralığında değil, artık 2.2202~2.756 arasında olduğunu gösterdi
İyileştirme, mantık merkezli bir matematiksel kanıttan ziyade, özel özelliklere sahip belirli dizilerin bulunmasıyla elde edildi. Bu, katı olmadığı anlamına gelmiyor
Örnekler üretmenin ilginç ve muhtemelen yararlı bir yolu; özünde LLM eklenmiş bir genetik algoritmaya oldukça yakın
Subbarao’nun “self-play” ile ilgili yorumu: https://twitter.com/rao2z/status/1728121216479949048
Yazıya göre FunSearch, yüksek puanlı fikirleri öne çıkarıp geliştirmek için LLM ile çalışan evrimsel bir yöntem kullanıyor. Bu fikirler bilgisayar programı biçiminde olduğu için otomatik olarak çalıştırılıp değerlendirilebiliyor
Kullanıcı problem tanımını kod biçiminde yazıyor. Bu tanım, programı değerlendiren prosedürü ve program havuzunu başlatan seed programı içeriyor
Her yinelemede FunSearch mevcut havuzdan bazı programları seçiyor; LLM bunları yaratıcı biçimde genişleterek yeni programlar oluşturuyor ve yeni programlar otomatik olarak değerlendiriliyor. En iyileri mevcut havuza geri eklenerek bir kendini iyileştirme döngüsü oluşturuyor
Web aramasında değerlendirici rolünde pplx.ai ve phind.com’u benzer şekilde kullanıyorum. Bir soru soruyorum, hangi referansları ve web bağlantılarını getirdiğine bakıyorum, ardından daha derin ya da farklı kaynaklar çıkarması için soruyu inceltiyor veya takip soruları soruyorum. Reddit ya da Google’da aramaktan, saklı cevherleri bulmak için daha iyi çalışıyor
Tech Twitter’da da çok iyi içerikler var; Grok herkese açılmışken araştırma için kullanılmasını bekliyorum
https://twitter.com/gfodor/status/1735348301812383906
“DeepMind, sinir ağlarının gerçekten yeni bilgi üretebildiğini kesin olarak kanıtladıysa, bu ateşten sonraki en önemli keşiftir” diyenler var.
Gerçekten öyleyse neden herkesin bunu konuşmadığını merak ediyorum. GPT-4 ya da Gemini’den daha az gelişmiş olan PaLM 2 ile bunu başarmış olmaları etkileyici. Önümüzdeki birkaç nesil modelin bu tür yöntemleri kullanarak neler yapabileceği muazzam olabilir.
LLM, rastgele mutasyon operatörünün yerine geçip “şu 20 satırlık Python’a makul bir değişiklik öner” isteğini alan bir şey gibi. Bilgi üretiminin payını sinir ağına yazmak bana cömert bir değerlendirme gibi geliyor.
Ayrıca “üretmesi zor, değerlendirmesi kolay” bir yapı gerektirmesinin ötesinde, problemin niteliğine çok bağımlı. Evrimleştirmek istediğiniz kısmın çok kısa tek bir Python fonksiyonuna ayrıştırılabilmesi gerekiyor.
LLM’in 20 yıldır ilerleme kaydedilmeyen yüksek boyutlu geometri için yeni bir çözüm bulabilmesi, eğitim verisinden aşırdığı parçaları inandırıcı biçimde birbirine eklemekten çok daha öte.
Doğru şekilde prompt vermeyi ve değerlendirmeyi çözebilirsek LLM yeteneklerinde gizli bir derinlik olduğunu düşündürüyor.
Beklentileri ciddi biçimde aşan bir sonuç. Bir sonraki prompt’un ve rastgele seed’in arkasında hangi keşfin saklı olduğunu bilemeyiz.
LLM’ler için de aynısı geçerli: https://www.nature.com/articles/s41587-022-01618-2
a) verimli bir değerlendirici var, b) iyileşme miktarını nicelleştiren zengin puan geri bildirimi var, yani ikili bir sinyal değil, c) evrimleştirilecek yalıtılmış bir bölümü olan bir iskelet sağlanabiliyor.
Örneğin teorem ispatı üretme problemi bu kapsamın dışında kalıyor; çünkü yeterince zengin bir puan sinyalinin nasıl sağlanacağı net değil.
Harika bir iş olsa da ateşin keşfiyle, aradaki sayısız şeyle, örneğin elektrikle, aynı seviyede görünmüyor.
Özetle, bir program şablonu/iskeleti ve uygunluk fonksiyonu verildiğinde LLM ile bir program popülasyonu üretiyorlar; başka k sürümden yeni program oluşturan bir prompt kullanıyorlar ve k=2’nin iyi olduğunu bulmuşlar. Biraz biyolojik. Ardından programı girdiler üzerinde çalıştırıp uygunluk fonksiyonuyla puanlıyorlar; evrim için de ada modeli kullanıyorlar.
Prompt ilke olarak muhtemelen şöyle bir şeye benziyordur:
def foo_v1(a, b): ...def foo_v2(a, b): ...# foo_v1 ve foo_v2’yi kullanarak yeni bir fonksiyon oluştur. Yalnızca {{ THIS }} gibi çift süslü parantez içindeki kısmı değiştirebilirsindef foo(a, b): return a + {{}}Yeni sonuçları elde etmek için yalnızca yaklaşık 1e6 LLM çağrısı kullanıldıysa bu oldukça etkileyici derecede düşük bir sayı. Değerlendirme/puanlamanın birkaç dakika sürdüğü de söyleniyor.
Burada derinlik ve genişlik arasındaki ödünleşimi düşünmeye değer. Bu, tekil programları ve popülasyonları puanlarken gecikme ve iş hacmiyle bağlantılı. Tüm programlar için memoization yapılsa nasıl olurdu? Kayıp fonksiyonunu çok boyutlu tutup her girdi ya da girdi kovası için bir boyut ayırsak, önce farklı bölgelerde iyi performans gösteren program popülasyonları bulup sonra bunları birleştirmesini sağlayamaz mıyız diye düşünüyorum.
Cap set’in ne kadar nadir olduğuna dair ön bilgi olup olmadığını da merak ediyorum. Daha önce hesaplamalı denemeler yapılıp sonuç alınamadı mı merak ediyorum; yine de çok havalı.
Twitter / X paylaşımını başka şekilde söylersek, bundan sonrası yalnızca daha iyiye gidecek.
Yani AI yetenekleri monoton biçimde artıyor; on yıllardır da böyleydi ve bu durumda yetenekler özyinelemeli şekilde kendini iyileştiriyor. Şimdiden AI otomatik tamamlama, AI tabanlı refactoring ve yorumlarda AI’ın otomatik oluşturduğu code review diff’leriyle kodlama üretkenliğinin kişisel olarak yaklaşık %20–30 arttığını görüyorum.
AI, 90’lardaki Intel dönemine girmiş gibi hissettiriyor. Kodu 2 kat hızlandırmak için Intel CPU’nun bir sonraki revizyonunu beklemek yeterliydi. Şimdi bu rolü AI modelleri üstleniyor. Kodlama, müşteri desteği, hata sınıflandırma gibi iş akışlarının bazı bölümlerini LLM sistemlerine bağladığınızda, sistemi “iyileştirmek” model adını değiştirmek kadar basit hale geliyor.
İlk entegrasyondan sonra, en az çabayla önümüzdeki birkaç yıl boyunca “her şeyin sihirli şekilde biraz biraz daha iyiye gitmesini” bekleyebilirsiniz.
Özellikle LLM kullanılan sonuçlarla kullanılmayan sonuçları karşılaştırmamışlar. Anladığım kadarıyla bu makale, verilen tip imzasına muhtemelen uyan Python kernel fonksiyonlarını LLM ile üretmeye yönelik genetik programlama sonuçlarını gösteriyor. Bu iş için LLM’in mutlaka gerekli olması gerekmiyor.
Dolayısıyla burada özellikle LLM’in özel bir şey yapıp yapmadığı hâlâ açık bir soru.
Ele alınan problemlerden biri cap set problemiydi.
https://en.m.wikipedia.org/wiki/Cap_set
Bu problem, yüksek boyutlu bir ızgarada üç noktası aynı doğru üzerinde yer almayan en büyük nokta kümesini, yani cap set’i bulmakla ilgilidir. Ekstremal kombinatorikteki başka problemler için model görevi gördüğünden önemlidir. Ekstremal kombinatorik, sayı, grafik ya da başka nesne koleksiyonlarının ne kadar büyük veya küçük olabileceğini inceler. Bu problemde kaba kuvvet hesaplama işe yaramaz; çünkü dikkate alınacak olasılık sayısı hızla evrendeki atom sayısını aşar.
FunSearch, program biçiminde çözümler üretti ve bazı ayarlarda şimdiye kadar bulunan en büyük cap set’i buldu. Bu, son 20 yılda cap set boyutundaki en büyük artış. Ayrıca bu problem, mevcut son teknoloji hesaplamalı çözücülerin kapasitesini çok aşan ölçeklere büyüdüğü için FunSearch bu çözücüleri geride bıraktı.
Sembolik akıl yürütmenin LLM’lerle nasıl entegre edileceğini, hatta bunun mümkün olup olmadığını merak ediyorum.
DeepMind’ın yakın tarihli FunSearch makalesi, kod iyileştirmeleri üretmek için önceden eğitilmiş büyük dil modelleri kullandığını vurguluyordu.
İlginç şekilde ana LLM, PaLM2 model ailesini temel alan Codey olsa da ek materyallerde açık kaynak LLM olan StarCoder’dan da söz ediliyor.
Ancak FunSearch’ün GitHub deposunda bu tür LLM uygulamaları yer almıyor. Örneğin
sampler.pyiçinde şu kod var:Bu kod, harici bir LLM uygulamasına ihtiyaç olduğunu gösteriyor. StarCoder başarıyla kullanıldıysa, ona ya da benzer bir açık kaynak LLM’ye yönelik bir entegrasyon rehberinin veya temel uygulamanın bulunmaması şaşırtıcı. Böyle bir içerik olsaydı araştırmanın yeniden üretilebilirliği ve erişilebilirliği büyük ölçüde artardı.
Bunun doğrulanabilir yeni bilgi olup olmamasından bağımsız olarak, model boyutu ya da başka düzenleyici araçlarla yapay zekaya erişimi sınırlama meselesi düşünüldüğünde ilginç bir vaka incelemesi.
Bu tür sınırlamalar, yeni bilgi veya doğa yasaları keşfedip bunları paylaşmadan gelir elde edebilecek şirketlere adil olmayan bir avantaj sağlar.