- DiffLogic CA adalah pendekatan automata seluler yang menggabungkan Neural Cellular Automata dan Differentiable Logic Gate Networks, sehingga tetap mempertahankan status sel diskret sambil mempelajari aturan lokal berbasis gradien
- Setiap sel memiliki status berupa vektor biner n-dimensi, dan baik tahap persepsi maupun tahap pembaruan diproses dengan jaringan gerbang logika untuk menghitung langsung status berikutnya
- Dalam eksperimen Conway's Game of Life, model mempelajari seluruh aturan dengan melatih satu langkah pada 512 konfigurasi kisi periodik 3x3, dan dalam inferensi hard juga mereproduksi pola representatif seperti glider, block, loaf, dan boat
- Eksperimen pembentukan pola membuat checkerboard 16x16 dalam 20 langkah, tetap bekerja pada kisi 4 kali lebih besar dan waktu 4 kali lebih lama, serta menunjukkan toleransi kesalahan terhadap sel yang rusak dan pemulihan diri setelah reaktivasi
- Model juga menghasilkan kontur lizard yang lebih kompleks dan G RGB 8 warna, tetapi pembelajaran struktur kompleks membutuhkan banyak penyetelan hyperparameter, dan NCA hierarkis serta gerbang mirip LSTM masih menjadi kandidat perbaikan
Masalah yang ditargetkan DiffLogic CA
- Automata seluler biasanya ditangani dengan terlebih dahulu menetapkan aturan lokal, lalu mengamati pola emergen yang muncul sebagai hasilnya
- DiffLogic CA mengeksplorasi cara mempelajari aturan lokal yang menghasilkan pola kompleks yang diinginkan dengan cara yang sepenuhnya dapat didiferensiasikan
- Neural Cellular Automata yang ada dapat mempelajari pola dan perilaku arbitrer, tetapi pada dasarnya tidak beroperasi dalam ruang status diskret sehingga interpretabilitasnya lebih rendah, dan pembaruan status kontinu membutuhkan biaya perkalian matriks
- Differentiable Logic Gate Networks telah digunakan untuk menemukan rangkaian logika kombinasional, tetapi operasinya belum dibuktikan dalam pengaturan NCA yang rekursif di ruang dan waktu
- Seluruh eksperimen dapat direproduksi di notebook
Struktur dasar Neural Cellular Automata
- Neural Cellular Automata menggabungkan deep learning dengan automata seluler klasik, sehingga aturan pembaruan dipelajari dengan gradient descent alih-alih merancang aturan secara manual
- Setiap sel pada Growing-NCA memiliki vektor status n-dimensi di atas kisi 2D
- 3 channel RGB merepresentasikan warna sel
- Channel Alpha merepresentasikan viabilitas sel; jika nilai alpha lebih besar dari 0,1, sel dianggap hidup
- Hidden channel lainnya menyampaikan informasi yang lebih kompleks tentang lingkungan sekitar
- Pembaruan dilakukan dalam dua tahap
- Tahap persepsi: Sobel filter diterapkan per channel untuk memperkirakan gradien spasial, lalu membuat perception vector yang menggabungkan status sel saat ini dan informasi sekitar
- Tahap pembaruan: Jaringan saraf dengan sekitar 8.000 parameter diterapkan secara identik ke semua sel untuk menentukan bagaimana setiap sel akan berubah
- Karena semua operasi dapat didiferensiasikan, keseluruhan sistem dapat mempelajari pola atau perilaku tertentu
Cara kerja Differentiable Logic Gate Networks
- Deep Differentiable Logic Gate Networks menggunakan gerbang logika seperti AND, OR, XOR sebagai unit dasar, bukan neuron buatan
- Jaringan terdiri dari lapisan-lapisan gerbang, dan setiap gerbang memiliki struktur sparse yang menerima input dari dua gerbang pada lapisan sebelumnya
- Koneksi diinisialisasi secara acak lalu tidak berubah selama pelatihan; pelatihan hanya menentukan operasi logika apa yang dilakukan oleh tiap gerbang
- Selama pelatihan, gerbang logika diskret tidak digunakan apa adanya; dua mekanisme berikut dipakai
- Relaksasi kontinu: operasi diskret seperti hard AND diganti dengan versi yang dapat didiferensiasikan dan menerima input antara 0 dan 1
- Pemilihan gerbang probabilistik: setiap gerbang memiliki distribusi probabilitas atas 16 kemungkinan operasi biner untuk dua input, dan mempelajari parameter 16-dimensi yang direpresentasikan dengan softmax
- Setelah pelatihan selesai, setiap gerbang dikunci ke operasi dengan probabilitas tertinggi, dan saat inferensi hanya melakukan operasi biner murni
- Untuk stabilitas pelatihan, distribusi gerbang awal diatur condong ke gerbang pass-through
Struktur DiffLogic CA
- DiffLogic CA mengikuti struktur kisi 2D NCA, tetapi merepresentasikan status tiap sel sebagai vektor biner n-dimensi
- Status sel dan channel digunakan dengan makna yang sama, dan vektor status biner berperan sebagai memori kerja yang menyimpan informasi dari iterasi sebelumnya
- Tahap persepsi menggunakan kernel berbasis jaringan gerbang logika, bukan Sobel filter
- Setiap kernel adalah rangkaian terpisah dengan struktur koneksi tetap, dan jenis gerbangnya dipelajari
- Kernel dihitung per channel
- Setiap rangkaian menggunakan 4 lapisan yang dirancang untuk menghitung interaksi antara sel pusat dan sel tetangga
- Tahap pembaruan memasukkan input berupa gabungan memori lama sel dan informasi yang diterima dari tetangga ke Differentiable Logic Gate Network untuk menghitung status baru
- Berbeda dari pembaruan gaya ODE pada NCA standar yang menambahkan status secara bertahap, model ini langsung mengeluarkan status biner berikutnya
- Operasi satu ronde dapat dilihat sebagai dua register
- Register abu-abu berisi status sel yang ada
- Register oranye menyimpan hasil tahap persepsi
- Setelah pembaruan, status baru ditulis ke register abu-abu, dan register oranye dikosongkan untuk ronde berikutnya
- Struktur ini bekerja seperti jaringan komputer kecil independen, tempat setiap sel berkomunikasi dengan tetangganya dan mengambil keputusan dari hasil pengamatannya
Eksperimen 1: Mempelajari Conway's Game of Life
- Game of Life adalah automata seluler biner; setiap sel hidup atau mati pada generasi berikutnya bergantung pada status 8 tetangganya dan statusnya sendiri saat ini
- Aturannya ada empat
- Sel mati akan hidup pada generasi berikutnya jika memiliki tepat 3 tetangga hidup
- Sel hidup bertahan jika memiliki 2 atau 3 tetangga hidup
- Sel hidup mati jika memiliki kurang dari 2 tetangga hidup
- Sel hidup mati jika memiliki lebih dari 3 tetangga hidup
- Karena eksperimen ini menargetkan aturan yang tidak bergantung pada pengulangan status sebelumnya, status sel ditetapkan 1 bit
- Konfigurasi model adalah sebagai berikut
- 16 kernel rangkaian persepsi
- Struktur node tiap kernel persepsi adalah
[8, 4, 2, 1] - Jaringan pembaruan memiliki 23 lapisan
- 16 lapisan pertama masing-masing memiliki 128 node
- Lapisan berikutnya adalah
[64, 32, 16, 8, 4, 2, 1]
- Data pelatihan mencakup seluruh 512 konfigurasi yang mungkin pada kisi periodik 3x3
- Karena status berikutnya tiap sel ditentukan oleh dirinya dan 8 tetangganya, ada 512 kemungkinan konfigurasi 3x3
- Jika semua status berikutnya untuk satu langkah dapat diprediksi dengan benar, itu setara dengan mempelajari seluruh aturan Game of Life
- Fungsi loss menjumlahkan selisih kuadrat antara kisi prediksi dan kisi jawaban
- Soft loss dan hard loss sama-sama konvergen sepenuhnya, dan rangkaian yang dipelajari dalam inferensi hard mereproduksi pola Game of Life bahkan pada kisi yang lebih besar
- Jumlah gerbang aktif, tidak termasuk pass-through A dan B, adalah 336, dan OR serta AND paling sering digunakan di jaringan persepsi dan jaringan pembaruan
- Rangkaian yang dihasilkan dapat diinteraksikan langsung sebagai rangkaian Game of Life
Eksperimen 2: Pembentukan pola checkerboard
- Eksperimen pembentukan pola diatur untuk mempelajari aturan yang berevolusi dari status awal arbitrer menuju gambar target
- Karena loss hanya dihitung pada timestep terakhir, model harus menemukan aturan transisi diskret tanpa supervisi per tahap antara
- Status sel berukuran 8 bit, dan DiffLogic CA diiterasikan selama 20 langkah
- Konfigurasi model adalah sebagai berikut
- 16 kernel rangkaian persepsi
- Setiap kernel memiliki 8, 4, dan 2 gerbang per lapisan
- Jaringan pembaruan memiliki 16 lapisan
- 10 lapisan pertama masing-masing memiliki 256 gerbang
- Lapisan berikutnya adalah
[128, 64, 32, 16, 8, 8]
- Fungsi loss adalah jumlah selisih kuadrat antara channel pertama kisi prediksi dan kisi target pada timestep terakhir
- Model dilatih untuk memulihkan pola checkerboard 16x16 dalam 20 langkah
- Soft loss dan hard loss sama-sama konvergen, dan pembentukan pola yang jelas terlihat pada channel pertama
- Model tidak memiliki bias arah bawaan, tetapi muncul sifat pola yang merambat dari kiri bawah ke kanan atas
- Jumlah gerbang aktif, tidak termasuk pass-through A dan B, adalah 22, dan setelah pruning seluruh fungsi pembentukan checkerboard pada praktiknya dapat diimplementasikan dengan 5 gerbang logika
- Rangkaian tetap bekerja saat diperluas ke kisi 4 kali lebih besar dan waktu 4 kali lebih lama, sehingga aturan yang dipelajari bukan bentuk overfitting hanya pada ukuran kisi tertentu
Kerusakan, pemulihan diri, dan pembaruan asinkron
- Dalam eksperimen checkerboard, dilakukan dua eksperimen kerusakan dengan mengasumsikan sebagian sel mengalami kegagalan
- Menonaktifkan secara permanen sel pada area besar untuk mensimulasikan komponen yang rusak
- Mengaktifkan kembali sel yang dinonaktifkan setelah sejumlah langkah
- Sistem mempertahankan integritas pola bahkan dalam kondisi kerusakan permanen, dan setelah sel yang dinonaktifkan kembali online, sistem kembali menghasilkan pola yang benar
- Meski toleransi kesalahan dan pemulihan diri tidak dirancang secara eksplisit, perilakunya menunjukkan kerusakan yang terlokalisasi dan fungsi keseluruhan tidak runtuh mendadak
- Dalam eksperimen pembaruan asinkron, tidak semua sel diperbarui secara bersamaan; pada tiap langkah hanya subset sel acak yang diperbarui
- Pelatihan asinkron diperkirakan lebih sulit daripada NCA yang ada
- Pada tiap langkah, model harus mengeluarkan seluruh status baru, bukan inkremental
- Model harus menangani kombinasi sel-sel sekitar yang maju atau tertinggal pada tahap yang berbeda-beda
- Pada checkerboard, pelatihan asinkron berhasil relatif mudah, dan menggunakan urutan pembaruan berbeda dari status awal yang sama tetap merekonstruksi pola target dalam 50 langkah
- Aturan lama yang dilatih secara sinkron juga tetap bekerja saat diterapkan pada inferensi asinkron
- Dalam pengujian yang secara acak menonaktifkan persegi 10x10 piksel di area gambar pada setiap timestep inferensi, sel yang dilatih asinkron pulih sedikit lebih cepat dari kerusakan
- Ketika error diukur sebagai jumlah selisih absolut antara target dan gambar rekonstruksi, pelatihan asinkron meningkatkan ketahanan terhadap gangguan semacam ini
Eksperimen 3: Pertumbuhan kontur lizard
- Eksperimen lizard adalah penghormatan untuk karya NCA asli, dan memeriksa apakah DiffLogic CA dapat mempelajari bentuk arbitrer
- Tidak seperti checkerboard yang merupakan pola teratur dan sangat dapat dikompresi, kontur lizard membutuhkan lebih banyak hafalan
- Pengaturannya adalah sebagai berikut
- Status sel berukuran 128 bit
- DiffLogic CA diiterasikan selama 12 langkah
- Kernel rangkaian persepsi berjumlah 4
- Setiap kernel memiliki 8, 4, 2, dan 1 gerbang per lapisan
- Jaringan pembaruan memiliki 10 lapisan
- 8 lapisan pertama masing-masing memiliki 512 gerbang
- Lapisan terakhir adalah
[256, 128]
- Model dilatih untuk menghasilkan pola lizard 20x20 dalam 12 langkah
- Kondisi awalnya adalah seed di pusat untuk memecah simetri seperti NCA, dan kondisi batas periodik diterapkan pada tepi kisi
- Saat dievaluasi pada kisi 40x40 yang lebih besar, model juga berhasil menghasilkan pola pertumbuhan lizard, menunjukkan bahwa solusinya tidak memanfaatkan kondisi batas
- Soft loss dan hard loss sama-sama konvergen ke 0
- Jumlah gerbang aktif, tidak termasuk pass-through A dan B, adalah 577
- Kernel persepsi terutama menggunakan gerbang TRUE, dan rangkaian pembaruan menggunakan hampir semua gerbang yang tersedia
- Pembelajaran pembentukan pola kompleks sulit dioptimalkan dan membutuhkan penyetelan hyperparameter yang luas
Eksperimen 4: Pembentukan G berwarna
- Karena eksperimen sebelumnya pada dasarnya berfokus pada gambar monokrom, eksperimen ini menghasilkan gambar warna 16x16 sebagai status target yang lebih kompleks
- Status sel memiliki 64 channel, dan model menghasilkan huruf G berwarna selama 15 langkah
- Tiga channel pertama merepresentasikan nilai RGB seperti konvensi NCA standar, tetapi di sini tiap nilai dibatasi pada representasi biner 0 atau 1 sehingga membentuk palet 8 warna
- Konfigurasi model adalah sebagai berikut
- 4 kernel rangkaian persepsi
- Setiap kernel terdiri dari 3 lapisan dengan 8, 4, dan 2 gerbang
- Jaringan pembaruan memiliki 11 lapisan
- 8 lapisan pertama masing-masing memiliki 512 node
- 3 lapisan terakhir adalah
[256, 128, 64]
- Status awal seluruhnya 0, dan kondisi batas periodik tidak digunakan
- Fungsi loss menjumlahkan selisih kuadrat antara kisi prediksi dan kisi target hanya untuk tiga channel pertama, yaitu channel 0, 1, dan 2, pada timestep terakhir
- Soft loss dan hard loss konvergen, dan model merekonstruksi G berwarna dalam 15 langkah
- Jumlah gerbang aktif, tidak termasuk pass-through A dan B, adalah 927
- Gerbang TRUE dan FALSE banyak digunakan baik di jaringan persepsi maupun jaringan pembaruan, dan di jaringan pembaruan gerbang OR paling banyak digunakan
- Rangkaian ini lebih kompleks daripada eksperimen sebelumnya, baik dari sisi pencarian hyperparameter maupun ukuran rangkaian
Tantangan tersisa dan arah perbaikan
- DiffLogic CA mengusulkan struktur dan metode pelatihan NCA baru yang menggunakan status sel sepenuhnya diskret dan memperbarui status dengan rangkaian biner rekursif yang dipelajari
- Dengan mengganti komponen jaringan saraf dengan Deep Differentiable Logic Networks, model ini menggabungkan fleksibilitas pembelajaran terdiferensiasi dengan gerbang logika diskret
- Replikasi Game of Life dan eksperimen pembentukan pola menunjukkan bahwa gerbang logika yang dapat didiferensiasikan dapat diterapkan pada automata seluler
- Hasilnya mengonfirmasi bahwa Differentiable Logic Gate Networks dapat dipelajari secara efektif bahkan dalam struktur rekursif
- Model saat ini menunjukkan kemungkinan pembelajaran pola, tetapi pembelajaran untuk menghasilkan bentuk dan struktur yang lebih kompleks masih sulit
- Sebagai arah perbaikan, diusulkan struktur NCA hierarkis dan gerbang khusus yang membantu pelupaan status
- Jika mekanisme gating mirip LSTM diintegrasikan ke proses pembaruan status, model dapat mengombinasikan status masa lalu dan kandidat status yang baru dihitung secara lebih kaya, sehingga meningkatkan dinamika dan daya ekspresi model
1 komentar
Opini Hacker News
Sangat menarik. Saya sedang mencari substrat mesin Turing universal baru, mengumpulkannya seperti Pokémon untuk eksperimen pemrograman genetik. Dulu saya juga pernah mengutak-atik cellular automata seperti rule 30/110, tetapi pendekatan ini jauh lebih meyakinkan.
Saya tidak pernah terpikir untuk memodelkan kernel seperti rangkaian logika digital. Batasan logika Boolean, gate, dan rangkaian tampaknya menghasilkan tekstur yang menarik untuk membentuk lanskap fitness. Parameter hasilnya bisa langsung diterjemahkan menjadi implementasi hardware, atau dikompilasi menjadi program sederhana setelah melalui tahap optimasi tambahan. Ini terlihat lebih baik daripada berurusan dengan floating point ajaib di dalam black box berisi puluhan miliar parameter.
Menarik sekali. Michael Levin adalah orang yang paling baik dalam merumuskan masalah bagaimana sel hewan bisa bekerja sama tanpa struktur hierarkis. Misalnya, ada eksperimen biologi yang menunjukkan bahwa meski sel mata pada embrio katak dipindahkan, sel itu tetap bergerak ke lokasi tempat mata seharusnya berada.
Menurut saya pertanyaan yang belum benar-benar ia jawab adalah bagaimana sel tahu kapan harus berhenti. Memahami pengorganisasian non-hierarkis juga merupakan kunci untuk memahami cara masyarakat bekerja, serta memecahkan dilema tahanan pada berbagai skala di dunia yang mengorganisasi dirinya sendiri. Ini juga soal memahami dan memodelkan kompleksitas mentah. Ini pertama kalinya saya melihat kemampuan untuk memodelkan hal semacam ini, dan ada begitu banyak arah yang bisa berkembang dari sini.
Belakangan ini saya banyak memikirkan kecerdasan, dan rasanya kita sedang berada di titik penentu untuk mengetahui cara kerja kecerdasan, atau setidaknya membuat lompatan besar dalam memahaminya. Kecerdasan tampak seperti perilaku yang muncul secara alami, tidak jauh berbeda dari mekanika Newton klasik atau listrik.
Pada akhirnya tampaknya semua kembali ke aturan sederhana. Bagaimana jika semua hal di otak yang tidak diskret sebenarnya hanya infrastruktur yang menopang proses inti yang sederhana tetapi penting, yang benar-benar melakukan pekerjaan? Bagaimana jika pada akhirnya, di level paling bawah, semuanya adalah gerbang logika dan sinyal listrik? Sepertinya masa depan akan sangat menarik.
Ada sisi yang menarik dalam pendekatan seperti ini, terutama dari segi kemampuan generalisasi. Namun saya penasaran apa visi besarnya. Apa yang akan bisa kita lakukan ke depannya? Secara filosofis, apa yang diajarkannya kepada kita tentang dunia? Kita sudah tahu bahwa cellular automata 1D setara dengan Turing, jadi dari satu sudut pandang NCA atau metode seperti ini tidak terlalu mengejutkan.
Akan muncul cellular automata yang berinteraksi dengan lingkungan, serta automata yang berinteraksi dengan sistem level rendah maupun institusi level tinggi. Dengan aproksimasi tertentu, manusia pun hanyalah sel-sel individual yang berinteraksi di dalam jaringan semacam ini. Menurut saya masa depan kecerdasan bukanlah LLM, melainkan sistem automata yang memiliki aspek metabolik. Automata yang berevolusi bersama, mengonsumsi energi, menghasilkan nilai, bersaing, dan saling memodelkan.
Kita bukan sedang digantikan, melainkan berpartisipasi dalam transformasi yang membuat batas antara sistem teknologi dan sistem seluler menjadi kabur lalu akhirnya hilang. Saya sangat bersyukur bisa menyaksikan ini. Referensi: https://x.com/zzznah/status/1803712504910020687
Saya suka bermain-main dengan cellular automata dalam karya seni. Mengejutkan pola seperti apa yang bisa muncul. Contoh: https://gods.art/math_videos/hex_func27l_21.html
Sepertinya saya juga perlu mencoba DLCA ini.
Ada banyak ide keren di sini. Mungkin hanya pengamatan kecil, tetapi komputasi ini memiliki state. Setiap sel memiliki memori dan persepsi terhadap lingkungan sekitarnya.
Sebaliknya, neural network modern umumnya tidak memiliki state. Misalnya, saya penasaran apakah pernah ada riset tentang LLM yang memiliki state.
Ini memang promosi diri, tetapi sangat relevan: Robustness and the Halting Problem for Multicellular Artificial Ontogeny (2011)
Itu adalah cellular automata dengan aturan pembaruan berupa perceptron yang digabungkan dengan difusi isotropik. Kami mengoptimalkan bobot neural network agar cellular automata menggambar suatu gambar, dan jika terganggu, ia juga bisa self-healing dengan membuat ulang gambar tersebut. Saat itu automatic differentiation belum semudah diakses seperti sekarang, jadi kami mengoptimalkan bobot dengan evolutionary strategies. Tentu saja, kemungkinan besar gradient descent akan jauh lebih baik.
Bisakah ini digunakan untuk ARC-AGI Challenge? Sepertinya juga bisa dikombinasikan dengan pendekatan terbaru ini: https://news.ycombinator.com/item?id=43259182
Benar-benar luar biasa. Sebagai orang yang sudah lama hanya mengamati dan banyak menggunakan modeling serta simulasi, saya melihat potensi besar untuk lebih memahami perilaku emergent dalam model perilaku aktor yang kompleks.
Saya ingin melihatnya diterapkan pada hal-hal seperti model predator/mangsa, dan model-model lain yang tampak sederhana tetapi pada skala sangat besar menghasilkan hasil emergent yang kompleks. Saya akan terus mengikuti pekerjaan ini.
Pola checkerboard pada hasilnya tampak seperti kebalikan dari pola target, yaitu seperti NOT. Namun tidak ada penyebutan tentang hal ini. Saya penasaran apakah itu tidak cukup penting untuk disebutkan, atau saya yang melewatkan sesuatu.