FunSearch: Penemuan Baru di Bidang Matematika dan Sains dengan Memanfaatkan LLM

 (deepmind.google)
1 poin oleh GN⁺ 2023-12-15 | 1 komentar | Bagikan ke WhatsApp
  • FunSearch dari Google DeepMind menggabungkan LLM pralatih dengan evaluator otomatis untuk menelusuri solusi baru yang dapat diverifikasi dalam masalah matematika dan ilmu komputer dalam bentuk kode
  • LLM membuat program baru, evaluator otomatis memberi skor, lalu program dengan skor tinggi dimasukkan kembali ke dalam pool untuk memperbaiki solusi melalui iterasi evolusioner
  • Pada cap set problem, FunSearch menemukan cap set terbesar yang pernah ditemukan hingga kini pada beberapa pengaturan, dan menunjukkan kinerja bahkan pada skala yang sulit ditangani solver komputasi state-of-the-art yang ada
  • Pendekatan yang sama juga diterapkan pada online bin packing, di mana program yang disesuaikan dengan karakteristik data dapat menempatkan jumlah item yang sama ke dalam lebih sedikit bin dibanding heuristik yang ada
  • Karena hasilnya berupa program pendek yang dapat dibaca manusia, peneliti dapat meninjau struktur solusi dan memanfaatkannya untuk kolaborasi manusia-AI dalam menyempurnakan formulasi masalah

Ide dasar FunSearch

  • FunSearch menelusuri fungsi yang ditulis sebagai kode komputer untuk menemukan solusi baru dalam matematika dan ilmu komputer
  • Namanya berasal dari gagasan bahwa sistem ini menelusuri fungsi (function)
  • Karena LLM dapat menghasilkan informasi yang tidak sesuai fakta, FunSearch menggabungkan LLM yang memberi usulan kreatif dengan evaluator otomatis untuk menyaring ide yang keliru
  • Ini merupakan contoh pertama pembuatan penemuan baru dengan LLM pada masalah terbuka sulit di bidang sains dan matematika

Struktur iterasi evolusioner

  • Pengguna terlebih dahulu menuliskan deskripsi masalah dalam bentuk kode
    • Termasuk prosedur untuk mengevaluasi program
    • Juga disertakan program seed untuk menginisialisasi pool program
  • Pada setiap iterasi, sebagian dari pool program saat ini diberikan sebagai input ke LLM
    • LLM menghasilkan program baru berdasarkan program yang sudah ada
    • Program baru dijalankan dan dievaluasi secara otomatis
    • Program dengan skor tinggi ditambahkan kembali ke database program
  • Pengguna dapat mengambil program dengan skor terbaik yang ditemukan sejauh ini kapan saja
  • FunSearch menggunakan Google PaLM 2, tetapi juga kompatibel dengan LLM lain yang dilatih pada kode
  • Struktur penelusurannya juga diperkuat untuk menghadapi masalah kombinatorial yang sulit
    • Dimulai dari pengetahuan umum tentang masalah lalu berfokus pada ide inti yang dibutuhkan untuk penemuan baru
    • Meningkatkan keberagaman ide untuk menghindari stagnasi
    • Menjalankan proses evolusi secara paralel untuk meningkatkan efisiensi

Hasil pada Cap set problem

  • Target penerapan pertamanya adalah cap set problem, yang selama puluhan tahun menyulitkan para matematikawan dari berbagai bidang riset
  • Masalah ini bertujuan mencari ukuran maksimum himpunan titik pada kisi berdimensi tinggi yang tidak memiliki tiga titik segaris, yaitu cap set
  • Masalah ini juga berperan sebagai model bagi persoalan lain dalam extremal combinatorics
  • Karena jumlah kemungkinan tumbuh sangat cepat hingga melampaui jumlah atom di alam semesta, perhitungan brute force tidak dapat digunakan
  • FunSearch menghasilkan solusi dalam bentuk program dan menemukan cap set terbesar yang pernah ditemukan hingga kini pada beberapa pengaturan
  • Hasil ini merupakan peningkatan terbesar pada ukuran cap set dalam 20 tahun terakhir, dan menunjukkan kinerja yang lebih baik bahkan di wilayah skala masalah yang melampaui kemampuan terkini solver komputasi state-of-the-art
  • Ini menunjukkan bahwa sistem tersebut dapat melampaui hasil sebelumnya pada masalah kombinatorial yang sulit dibangun intuisinya, dan berpotensi berlanjut ke masalah teori kombinatorika serupa serta bidang seperti teori komunikasi

Program pendek yang dapat ditafsirkan manusia

  • FunSearch bukan black box yang hanya menghasilkan daftar jawaban, melainkan menghasilkan program yang menunjukkan bagaimana solusi disusun
  • Ini juga selaras dengan cara umum sains menjelaskan penemuan atau fenomena baru melalui proses pembentukannya
  • FunSearch lebih menyukai solusi yang direpresentasikan sebagai program ringkas dengan Kolmogorov complexity yang rendah
    • Kolmogorov complexity adalah panjang program komputer terpendek yang menghasilkan solusi tersebut
    • Program pendek dapat menjelaskan objek yang sangat besar, sehingga membantu memperluas pendekatan ini ke masalah skala besar seperti mencari jarum dalam tumpukan jerami
    • Keluaran program lebih mudah dipahami oleh peneliti
  • Pada beberapa kode keluaran dengan skor tinggi, diamati simetri yang menarik, dan berdasarkan hal ini formulasi masalah disempurnakan untuk memperoleh solusi yang lebih baik
  • Jordan Ellenberg mengatakan bahwa FunSearch memberikan “mekanisme yang sepenuhnya baru untuk mengembangkan strategi serangan”, dan bahwa solusi yang dihasilkan jauh lebih kaya secara konseptual daripada sekadar daftar angka

Penerapan pada Online bin packing

  • FunSearch juga diterapkan pada bin packing, masalah ilmu komputer yang praktis
  • Bin packing adalah masalah menempatkan item dengan ukuran berbeda ke dalam jumlah bin sesedikit mungkin
  • Contoh penerapan nyata mencakup pemuatan kontainer dan alokasi pekerjaan komputasi untuk menekan biaya di data center
  • Online bin packing biasanya ditangani dengan heuristik berbasis pengalaman manusia
    • Untuk tiap situasi spesifik dengan ukuran, waktu, dan kapasitas berbeda, bisa sulit menemukan himpunan aturan yang tepat
  • Meski sangat berbeda dari cap set problem, FunSearch dapat dikonfigurasi dengan mudah dan menghasilkan program yang otomatis disesuaikan dengan karakteristik data
  • Program yang dihasilkan dapat menempatkan jumlah item yang sama ke dalam lebih sedikit bin dibanding heuristik yang ada
  • Pendekatan AI lain seperti jaringan saraf atau reinforcement learning juga dapat efektif untuk masalah kombinatorial yang sulit, tetapi dapat membutuhkan sumber daya besar untuk deployment
  • Karena FunSearch menghasilkan kode yang mudah diperiksa dan dideploy, sistem ini dapat menghasilkan solusi dalam bentuk yang bisa dimasukkan ke berbagai sistem industri nyata

Pembaruan dan perluasan pada 2024

  • Laporan arXiv yang dipublikasikan pada Desember 2024 menunjukkan bahwa pendekatan FunSearch dapat digunakan untuk memperkuat kinerja manusia dalam competitive programming kombinatorial
  • Kompetisi coding tradisional seperti Codeforces menuntut solusi lengkap untuk masalah algoritma klasik dalam batas waktu dan memori
  • Kompetisi kombinatorial menangani masalah kompleks yang bukan mencari satu jawaban benar, melainkan solusi aproksimasi terbaik yang mungkin
  • Pendekatan ini dapat menghasilkan solusi yang lebih baik daripada solusi yang ditemukan peserta di persentil teratas
  • Pendekatan ini memakai struktur kolaboratif di mana programmer manusia menulis backbone dari kode solusi, lalu LLM secara kreatif mengevolusikan fungsi yang mengendalikannya
  • Seiring peningkatan LLM umum, model yang dikhususkan untuk kode tidak lagi diperlukan, dan pendekatan ini dapat digunakan berbasis Gemini 1.5 Flash
  • Selain competitive programming, FunSearch juga digunakan untuk menemukan cara mengoptimalkan fungsi dengan lebih baik dalam framework Bayesian optimization

Arah penemuan berbasis LLM

  • FunSearch menunjukkan bahwa jika diberi mekanisme untuk mencegah halusinasi LLM, LLM dapat dimanfaatkan bukan hanya untuk penemuan matematika baru tetapi juga untuk menghasilkan solusi potensial bagi masalah nyata yang penting
  • Pada masalah lama maupun baru di sains dan industri, pembuatan algoritma yang efektif dan disesuaikan lewat pendekatan berbasis LLM dapat menjadi hal yang umum
  • FunSearch dapat terus ditingkatkan seiring perkembangan umum LLM, dan direncanakan akan diperluas untuk menjangkau berbagai masalah sains dan rekayasa

Bacaan terkait

1 komentar

 
GN⁺ 2023-12-15
Opini Hacker News

  • Saya penasaran seberapa diperlukan LLM di sini
    Sepintas, peran LLM tampaknya adalah menghasilkan sesuatu yang masuk akal seperti fungsi Python yang mengikuti type signature yang diberikan
    Namun, bahkan tanpa LLM pun seharusnya bisa membuat fungsi Python acak yang valid dan memenuhi type signature yang diberikan. Ini seperti latihan [1], tetapi untuk bahasa yang jauh lebih kompleks, dan bahasa yang terbatas mungkin lebih mudah digunakan. Mungkin pendekatan seperti PushGP [2] juga bisa dilakukan
    Pertanyaannya adalah (1) apa nilai tambah LLM di sini, apakah ia secara signifikan mengurangi jumlah evaluasi yang diperlukan untuk konvergensi, dan jika ya bagaimana caranya; (2) apakah teknik genetic programming lain kurang kompetitif pada masalah yang sama dan menghasilkan solusi dengan fitness lebih rendah; (3) jika genetic programming yang lebih tradisional bisa mencapai fitness serupa, apakah ada perbedaan biaya komputasi jika biaya pelatihan LLM juga diperhitungkan
    [1] http://www.davidmontana.net/papers/stgp.pdf
    [2] https://faculty.hampshire.edu/lspector/push.html

    • Ruang keadaan program yang dapat dijalankan jauh lebih besar daripada program yang berguna
      Monyet dan mesin tik saja tidak cukup; alasan memakai Palm2 di sini adalah karena kandidatnya harus masuk akal, bukan acak. Tujuannya agar tidak membuang waktu pada program yang tidak masuk akal
      Selain itu, algoritma genetika berbasis pembuatan program acak punya masalah cold start yang sangat besar. Jika fitness semua kandidat adalah 0, kemungkinan besar tidak ada kemajuan di awal, bahkan mungkin sampai akhir
    • Fungsi yang ditemukan ada di sini: https://github.com/google-deepmind/funsearch/blob/main/cap_s...
      Saya tidak terlalu akrab dengan algoritma genetika, tetapi rasanya yang seperti ini bukan sesuatu yang mustahil ditemukan oleh algoritma genetika. Namun, saya akan terkejut jika ada orang yang sudah benar-benar banyak mencobanya
      Di sisi lain, seperti terlihat pada Lampiran A.2 di paper, pendekatan genetika tanpa LLM tampaknya membutuhkan lebih banyak desain manual daripada pendekatan dengan LLM
    • Algoritma genetika, sekalipun diberi constraint, akan menghasilkan banyak program yang tidak bermakna. Dengan usaha yang cukup, sebagian besar mungkin bisa dibuat benar secara sintaksis, tetapi hanya sampai di situ
      Perbedaan yang dibuat LLM di sini adalah membatasi ruang mutasi yang mungkin, secara garis besar, ke program yang masuk akal secara semantik
      Untuk poin nomor 3, LLM yang sudah dilatih berguna untuk sangat banyak tujuan, jadi jika biaya pelatihannya diamortisasi dari awal, biayanya tidak besar. Mungkin ada biaya tambahan untuk fine-tuning agar sesuai dengan framework FunSearch, tetapi biaya fine-tuning cukup kecil. Dalam framework ini, menggunakannya kemungkinan besar lebih menguntungkan daripada hanya memakai genetic programming
    • Sintesis program induktif pada dasarnya macet selama puluhan tahun karena ruang pencariannya terlalu besar. Sulit melampaui program yang sangat sepele
      LLM sangat mengurangi ruang pencarian, dan tentu saja sering juga menguranginya dengan keliru, tetapi setelah itu sintesis program induktif dapat diterapkan untuk fine-tuning dan pengujian. Tanpa LLM, cara seperti ini sejauh yang saya tahu saat ini tidak mungkin. Sebab bahkan untuk kasus sepele pun kita akan menguji miliaran program yang sama sekali tidak masuk akal
    • Saya mengira stochastic gradient descent dan LLM akan konvergen jauh lebih cepat daripada genetic programming. Yang jelas jauh lebih cepat daripada pencarian acak

  • Konteks pentingnya adalah, temuan ini menunjukkan bahwa suatu angka dalam kombinatorika yang tahun lalu diketahui berada pada rentang 2,218~2,756 kini berada di antara 2,2202~2,756
    Peningkatannya dicapai bukan lewat pembuktian matematika yang berpusat pada logika, melainkan dengan menemukan deret-deret tertentu yang memiliki sifat khusus. Bukan berarti itu tidak rigor
    Ini adalah cara yang menarik dan mungkin berguna untuk menghasilkan contoh, dan pada dasarnya lebih dekat ke algoritma genetika dengan LLM sebagai bumbu

  • Komentar Subbarao terkait “self-play”: https://twitter.com/rao2z/status/1728121216479949048
    Menurut tulisan itu, FunSearch menggunakan metode evolusioner yang digerakkan LLM untuk mendorong dan mengembangkan ide-ide dengan skor tinggi. Ide-ide ini berbentuk program komputer sehingga dapat dijalankan dan dievaluasi secara otomatis
    Pengguna menulis deskripsi masalah dalam bentuk kode. Deskripsi ini mencakup prosedur untuk mengevaluasi program dan program seed untuk menginisialisasi pool program
    Pada setiap iterasi, FunSearch memilih beberapa program dari pool saat ini, lalu LLM secara kreatif memperluasnya untuk membuat program baru, dan program baru tersebut dievaluasi secara otomatis. Yang terbaik ditambahkan kembali ke pool yang ada, membentuk loop perbaikan diri
    Dalam pencarian web, saya memakai pplx.ai dan phind.com dengan cara serupa sebagai evaluator. Saya mengajukan pertanyaan, melihat referensi dan tautan web apa yang mereka ambil, lalu menyempurnakan pertanyaan atau mengajukan pertanyaan lanjutan agar mereka menarik sumber yang lebih mendalam atau berbeda. Ini bekerja lebih baik untuk menemukan permata tersembunyi daripada menelusuri reddit atau Google
    Tech Twitter juga punya banyak konten bagus, jadi karena Grok sudah dibuka untuk semua orang, saya berharap bisa memakainya untuk riset

  • https://twitter.com/gfodor/status/1735348301812383906
    Ada yang mengatakan, “Jika DeepMind telah membuktikan secara definitif bahwa jaringan saraf dapat menghasilkan pengetahuan yang benar-benar baru, maka ini adalah penemuan terpenting sejak api”
    Jika memang begitu, saya penasaran mengapa tidak semua orang membicarakannya. Fakta bahwa ini dilakukan dengan PaLM 2, yang kurang maju dibanding GPT-4 atau Gemini, cukup mengesankan. Rasanya luar biasa membayangkan apa yang bisa dilakukan beberapa generasi model berikutnya jika memanfaatkan metode seperti ini

    • Pekerjaan berat di sini dilakukan oleh algoritma evolusioner
      LLM hanya menggantikan operator mutasi acak dan kira-kira diminta, “tolong usulkan perubahan yang masuk akal untuk Python 20 baris ini.” Rasanya agak terlalu murah hati jika kredit penciptaan pengetahuan diberikan kepada jaringan saraf
      Selain itu, di luar perlunya struktur “sulit dibuat tetapi mudah dievaluasi”, ini sangat bergantung pada sifat masalahnya. Bagian yang ingin dievolusikan harus bisa dipecah menjadi satu fungsi Python yang sangat pendek
    • Saya sampai berkata “Wah!” dengan suara keras
      Bahwa LLM bisa menemukan solusi baru untuk geometri berdimensi tinggi yang tidak mengalami kemajuan selama 20 tahun, itu jauh melampaui sekadar menyambung potongan data pelatihan yang dijiplak agar terlihat masuk akal
      Ini mengisyaratkan ada kedalaman tersembunyi dalam kemampuan LLM, asalkan kita menemukan cara melakukan prompting dan evaluasi dengan benar
      Hasil ini sangat melampaui ekspektasi. Kita tidak tahu penemuan apa yang tersembunyi di balik prompt dan seed acak berikutnya
    • Jaringan saraf sudah sejak lama mampu menghasilkan “pengetahuan baru”
      LLM juga demikian: https://www.nature.com/articles/s41587-022-01618-2
    • Menurut makalahnya, FunSearch saat ini bekerja paling baik pada masalah dengan karakteristik berikut
      a) ada evaluator yang efisien, b) ada umpan balik skor yang kaya yang menguantifikasi tingkat perbaikan, yaitu bukan sinyal biner, c) dapat disediakan kerangka dengan bagian terisolasi yang akan dievolusikan
      Misalnya, masalah pembuatan pembuktian teorema berada di luar cakupan ini, karena tidak jelas bagaimana menyediakan sinyal skor yang cukup kaya
    • Contoh ini terasa relatif terbatas pada pencarian algoritma atau fungsi baru
      Ini memang pekerjaan yang hebat, tetapi jika dibandingkan dengan penemuan api, banyak hal di antaranya, misalnya listrik, rasanya tidak berada di kelas yang sama

  • Singkatnya, ketika diberikan template/kerangka program dan fungsi fitness, mereka menghasilkan populasi program dengan LLM, memakai prompt yang membuat program baru dari k versi lain, dan menemukan bahwa k=2 bagus. Agak biologis. Lalu program dijalankan pada input dan diberi skor dengan fungsi fitness, sementara evolusinya menggunakan model pulau
    Pada prinsipnya, prompt-nya mungkin terasa seperti ini
    def foo_v1(a, b): ...
    def foo_v2(a, b): ...
    # Gunakan foo_v1 dan foo_v2 untuk membuat fungsi baru. Kamu hanya boleh mengubah bagian di dalam kurung kurawal ganda seperti {{ THIS }}
    def foo(a, b): return a + {{}}
    Jika hanya sekitar 1e6 kali panggilan LLM yang dibutuhkan untuk mendapatkan hasil baru, itu jumlah yang cukup mengesankan kecilnya. Disebutkan juga bahwa evaluasi/penilaian memakan waktu beberapa menit
    Di sini menarik untuk memikirkan trade-off antara kedalaman dan keluasan. Ini terkait dengan latensi dan throughput saat menilai program individual maupun populasi. Bagaimana kalau melakukan memoization untuk semua program? Dengan mempertahankan fungsi loss sebagai multidimensi, satu dimensi per input atau bucket input, mungkin kita bisa terlebih dahulu menemukan populasi program yang unggul di wilayah berbeda, lalu menggabungkannya kemudian
    Saya juga penasaran apakah ada pengetahuan awal tentang seberapa langka cap set. Saya ingin tahu apakah sebelumnya sudah ada upaya komputasional dan tidak membuahkan hasil, tetapi bagaimanapun ini keren

  • Memparafrasakan posting Twitter / X itu, ke depannya ini hanya akan semakin baik
    Artinya, kapabilitas AI meningkat secara monoton, sudah begitu selama puluhan tahun, dan dalam kasus ini kapabilitasnya meningkat secara rekursif melalui perbaikan diri. Saya sudah melihat produktivitas coding secara pribadi meningkat sekitar 20–30% lewat autocomplete AI, refactoring berbasis AI, dan diff code review yang dibuat otomatis oleh AI di komentar
    Rasanya AI sedang memasuki era seperti Intel pada tahun 90-an. Untuk membuat kode 2x lebih cepat, kita hanya perlu menunggu revisi berikutnya dari CPU Intel. Sekarang model AI mengambil peran itu. Jika sebagian alur bisnis seperti coding, dukungan pelanggan, dan klasifikasi bug sudah dihubungkan ke sistem LLM, “peningkatan” sistem hanya menjadi soal mengganti nama model
    Setelah integrasi awal, dengan upaya minimal kita bisa berharap selama beberapa tahun ke depan “semuanya secara ajaib menjadi sedikit lebih baik”

    • Menurut saya, tidak ada isi seperti itu di tulisan blog maupun makalah yang ditautkan
      Secara khusus, mereka tidak membandingkan hasil dengan dan tanpa LLM. Sepemahaman saya, makalah ini menunjukkan hasil pemrograman genetik yang menggunakan LLM untuk menghasilkan fungsi kernel Python yang mungkin mengikuti type signature tertentu. LLM tidak mutlak diperlukan untuk pekerjaan ini
      Jadi apakah LLM secara khusus melakukan sesuatu yang istimewa di sini masih menjadi pertanyaan terbuka

  • Salah satu masalah yang didekati adalah masalah cap set
    https://en.m.wikipedia.org/wiki/Cap_set
    Masalah ini mencari himpunan titik terbesar di kisi berdimensi tinggi yang tidak memiliki tiga titik segaris, yaitu cap set. Ini penting karena berperan sebagai model untuk masalah lain dalam kombinatorika ekstremal. Kombinatorika ekstremal mempelajari seberapa besar atau kecil suatu kumpulan bilangan, graf, atau objek lain dapat menjadi. Komputasi brute force tidak efektif untuk masalah ini, karena jumlah kemungkinan yang perlu dipertimbangkan dengan cepat melampaui jumlah atom di alam semesta
    FunSearch menghasilkan solusi dalam bentuk program, dan pada beberapa pengaturan menemukan cap set terbesar yang pernah ditemukan sejauh ini. Ini merupakan peningkatan terbesar dalam ukuran cap set selama 20 tahun terakhir. Selain itu, karena masalah ini tumbuh hingga skala yang jauh melampaui kemampuan solver komputasional mutakhir saat ini, FunSearch mengungguli solver-solver tersebut

  • Saya penasaran bagaimana penalaran simbolik bisa diintegrasikan dengan LLM, atau apakah itu memang memungkinkan

    • Itulah tepatnya yang sedang kami lakukan. Menurut kami ini bukan hanya mungkin, tetapi juga diperlukan untuk aplikasi yang melampaui pembuatan berbasis coba-coba
    • Tampaknya ada semacam paralel dengan gagasan neuro-simbolik yang dieksplorasi Lab V2 di ASU
    • LEAN

  • Makalah FunSearch terbaru dari DeepMind menekankan bahwa mereka menggunakan model bahasa besar yang telah dilatih sebelumnya untuk menghasilkan perbaikan kode
    Menariknya, LLM utama yang digunakan adalah Codey berbasis keluarga model PaLM2, tetapi materi pelengkapnya juga menyebut StarCoder, sebuah LLM open-source
    Namun, repositori GitHub FunSearch tidak menyertakan implementasi LLM semacam itu. Misalnya, sampler.py memuat kode berikut

    class LLM:  
"""Language model that predicts continuation of provided source code."""

def __init__(self, samples_per_prompt: int) -> None:  
self._samples_per_prompt = samples_per_prompt

def _draw_sample(self, prompt: str) -> str:  
"""Returns a predicted continuation of `prompt`."""  
raise NotImplementedError('Must provide a language model.')

    Kode ini menunjukkan bahwa implementasi LLM eksternal diperlukan. Jika StarCoder memang berhasil digunakan, cukup mengejutkan bahwa tidak ada panduan integrasi atau implementasi dasar untuk model itu atau LLM open-source serupa. Jika ada, reproducibility dan aksesibilitas riset ini akan meningkat secara signifikan

  • Terlepas dari apakah ini merupakan pengetahuan baru yang dapat diverifikasi atau tidak, ini adalah studi kasus yang menarik jika memikirkan masalah pembatasan akses AI melalui ukuran model atau cara regulasi lainnya
    Pembatasan semacam itu memberi keuntungan yang tidak adil bagi perusahaan yang dapat menemukan pengetahuan baru atau hukum alam lalu memonetisasinya tanpa membagikannya