- Transformer dan LLM unggul dalam percakapan, pemahaman gambar, dan pelengkapan kode, tetapi sulit memberikan kinerja yang stabil pada perencanaan multi-langkah dan penalaran tingkat tinggi
- Makalah ini mengubah tugas perencanaan dan solusi optimal menjadi urutan token, lalu memasukkan jejak eksekusi saat A* memecahkan masalah ke dalam data pelatihan
- Searchformer mula-mula meniru proses pencarian A*, lalu di-fine-tune agar menghasilkan urutan pencarian yang lebih pendek sambil tetap mempertahankan rencana optimal
- Dalam eksperimen Sokoban, model keluarga Searchformer menyelesaikan 93,7% tugas uji dan menggunakan rata-rata 26,8% lebih sedikit langkah pencarian dibanding implementasi acuan A*
- Jejak eksekusi memang menambah beban dengan memperpanjang urutan generasi hingga 10×~100×, tetapi bahkan dengan urutan pelatihan yang lebih sedikit daripada model solution-only yang lebih besar, model ini lebih sering menghasilkan rencana optimal pada tugas yang belum pernah dilihat
Hal yang dikuasai Transformer dan tugas perencanaan yang masih lemah
- Arsitektur berbasis Transformer menunjukkan kinerja tinggi pada berbagai tugas
- percakapan setara manusia
- pemahaman gambar berkualitas tinggi
- pembuatan video
- generasi multimodal
- pelengkapan kode
- Model seperti LLM yang dilatih dengan data berskala internet dapat melakukan generalisasi dengan baik pada kasus penggunaan nyata
- Namun, pada tugas perencanaan dan penalaran, keterbatasan masih tetap ada
- LLM masih menunjukkan kekurangan pada tugas perencanaan multi-langkah
- kesulitan juga muncul dalam menjalankan penalaran tingkat tinggi
Keterbatasan prompt berpikir bertahap
- Pendekatan terbaru berupaya meningkatkan kinerja dengan mendorong Transformer untuk menghasilkan “pemikiran” antara sebelum menjawab
- Prompting Chain-of-Thought(CoT) dan Tree-of-thoughts(ToT) mendorong model untuk “berpikir” secara bertahap
- Teknik-teknik ini sering efektif, tetapi karena alasan seperti self-enforcing, justru dapat menurunkan kinerja
- Metode yang bekerja baik pada satu dataset bisa gagal pada dataset lain
- contohnya ketika jenis penalaran yang dibutuhkan berbeda, seperti penalaran spasial dan penalaran matematika
- Cara agar Transformer dan LLM dapat secara stabil melakukan perencanaan, pengambilan keputusan multi-langkah, dan penalaran masih menjadi topik riset yang aktif
Memasukkan dinamika pencarian A* ke dalam data pelatihan
- Pendekatan ini berfokus pada pelatihan Transformer agar lebih tangguh dalam menyelesaikan tugas perencanaan yang kompleks
- Model dilatih, seperti LLM, untuk memprediksi kata berikutnya ketika diberikan urutan kata
- Eksperimen dilakukan pada dataset generatif sintetis yang menggunakan bahasa sintetis dan kosakata sintetis
- Tugas perencanaan dan rencana solusi optimal direpresentasikan sebagai urutan kata yang disebut token
- Proses komputasi yang dijalankan A* dicatat sebagai urutan token jejak eksekusi
- jejak eksekusi membentuk dataset urutan yang memuat dinamika pencarian A*
- melalui urutan yang diperkaya pencarian, Transformer dilatih untuk menghasilkan urutan token yang bersama-sama mengodekan dinamika pencarian A* dan rencana optimal
Prosedur pelatihan Searchformer
- Model akhir, Searchformer, dibuat dalam dua tahap
- pertama, Transformer dilatih untuk meniru proses pencarian A*
- setelah itu, model di-fine-tune agar menemukan rencana dalam lebih sedikit langkah pencarian sambil tetap menghasilkan rencana optimal
- Proses ini disebut search dynamics bootstrapping
- Tujuannya adalah memperoleh Transformer yang dapat menyelesaikan tugas perencanaan kompleks dengan lebih sedikit langkah pencarian dibanding implementasi acuan A*
Eksperimen Sokoban dan kinerja generalisasi
- Pada puzzle Sokoban, model keluarga Searchformer menyelesaikan 93,7% dari seluruh tugas uji
- Rata-rata langkah pencarian 26,8% lebih sedikit dibanding implementasi acuan A*
- Dalam eksperimen yang mengendalikan kompleksitas tugas, ukuran dataset, dan ukuran model, efek memasukkan jejak eksekusi terkonfirmasi
- Memasukkan jejak eksekusi ke dalam data pelatihan meningkatkan panjang urutan generasi hingga 10×~100×
- Meski demikian, kinerja tetap meningkat pada kumpulan tugas uji independen
- Model search-augmented lebih sering menghasilkan rencana optimal pada tugas yang belum pernah dilihat meskipun memiliki urutan pelatihan 10 kali lebih sedikit daripada model solution-only yang lebih besar
- model search-augmented dilatih dengan data yang mencakup deskripsi tugas, solusi, dan jejak eksekusi
- model solution-only dilatih dengan urutan yang hanya mencakup deskripsi tugas dan solusi tugas
- Hasil ini menunjukkan bahwa memasukkan dinamika pencarian A* ke dalam proses pelatihan Transformer dapat meningkatkan kinerja pada tugas perencanaan
1 komentar
Opini Hacker News
Ada juga riset yang lebih menarik yang memakai Transformer untuk perencanaan gerak robot 0
Masalah memindahkan lengan robot dari titik A ke titik B sambil menghindari tabrakan sangat sulit karena berdimensi tinggi dan kontinu, dan metode perencanaan yang ada cenderung berat secara komputasi sekaligus kinerjanya kurang baik
Jadi ini menjadi salah satu alasan mengapa gerakan robot terlihat “tidak alami” dan robot tidak begitu mampu melakukan berbagai tugas yang kita inginkan; pendekatan ini tampaknya cukup kompetitif dibanding metode lain dengan merencanakan jalur yang hampir optimal secara lebih cepat
Sebelum masuk ke arah riset, saya penasaran apakah mereka sudah mencoba algoritma Modified J*, optimisasi A* untuk graf game/pencarian jalur
Kalau penasaran, ada di Game AI Pro 2 0
Makalah ini menguji seberapa baik Transformer memprediksi jejak eksekusi, misalnya dalam kasus seperti compiler JIT, dan apakah itu membantu meningkatkan heuristik di area seperti pencarian jalur
Namun Transformer lambat, jadi saya melihatnya dengan hati-hati
Masalah perencanaan sudah ditangani dengan baik oleh teknik mapan seperti pencarian graf, SAT solver, operations research, dan Prolog
Biasanya intinya adalah optimisasi di antara berbagai alternatif yang mungkin, dan saya tidak yakin Transformer cocok untuk itu
Peran teknik keluarga LLM tampaknya lebih pada menerjemahkan deskripsi bahasa alami menjadi program yang dapat dieksekusi, tetapi Prolog sendiri sejak awal dirancang untuk pemrosesan bahasa alami klasik, jadi sudah cukup dekat
Dulu penerjemahan mesin membutuhkan decoding tata bahasa yang kompleks memakai pencarian, tetapi sekarang menggunakan Transformer dengan decoding yang jauh lebih sederhana dan praktis tidak memerlukan pencarian
Sekarang mungkin kita juga bisa menuju struktur rekursif penuh
Idenya adalah mempelajari heuristik neural architecture search (NAS) dengan model prediksi tercanggih saat ini, lalu mencari blok neural network baru yang lebih baik daripada transformer atau mamba
Singularitas akan datang…
Kalau tertarik pada game sejenis Sokoban, lihat juga https://thinky.gg
Ada varian Sokoban menarik bernama Sokopath, serta varian NP-hard lain bernama Pathology yang tujuannya adalah pergi dari titik A ke titik B dengan jumlah langkah tersingkat
Komunitas mencoba membuat berbagai solver, tetapi menjadi sangat sulit ketika grid lebih dari 5x5, dan komunitas thinky juga menemukan level-level menarik dengan jumlah langkah maksimum yang sangat besar menggunakan simulated annealing
“Pengurangan 26,8% langkah pencarian dibanding pencarian A* standar”
Jadi di Sokoban, ini hanya sedikit lebih baik daripada A* yang jauh dari state-of-the-art (https://festival-solver.site/)
Saya tidak tahu apa yang mengesankan dari makalah ini, atau mengapa masuk Hacker News
Namun jika ada batasan lain yang bisa dimanfaatkan pada domain yang dicari, bisa saja lebih baik daripada A*
Misalnya Jump Point Search memanfaatkan sifat pencarian grid yang hanya dapat bergerak dengan cara tertentu
Kalau kita bisa membuat algoritma pencarian umum yang secara “otomatis” memanfaatkan sifat khusus domain dasar secara efektif tanpa harus dianalisis langsung oleh manusia, rasanya itu akan berguna
A* lebih dekat ke solusi dasar yang “naif”, dan mereka tidak memikirkan desain algoritma secara langsung
Cukup mengesankan bahwa Transformer encoder-decoder sederhana bisa melakukan sejauh ini
“Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ...”
Makalah ini menarik karena merupakan contoh pemakaian Transformer untuk pengambilan keputusan, dan saya tidak terlalu peduli apakah saat ini sudah setingkat A*
Tentu hipotesis itu punya versi kuat dan versi lemah, dan versi kuatnya mungkin tidak benar, tetapi selama tampak seperti kita makin mendekati “satu cara sejati” alam untuk belajar melakukan sesuatu, ini terasa seperti kabar penting
Jika Transformer bisa melakukan perencanaan, mungkin itu berarti kecerdasan buatan umum hanya membutuhkan pendidikan yang lebih baik
Pembelajaran online juga diperlukan, dan masih harus ada beberapa lapisan lain
Untuk pembelajar auditori, ada versi buku audio ringkasan makalah ini
https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f
Saya sangat optimistis soal penggunaan heuristik yang dipelajari pada algoritma diskret seperti A*, Focal search, dan berbagai keluarga integer linear programming
Di sebagian besar pustaka optimisasi diskret modern seperti CPLEX, perbedaan performa dijelaskan oleh heuristik dan tuning
Mengganti rutinitas pencarian optimal yang sudah dipahami baik dengan pendekatan pembelajaran end-to-end terasa kurang meyakinkan, tetapi mungkin itu kekhawatiran yang tidak perlu
Namun para penulis tampaknya melewatkan peluang itu
Saya jadi ingin menyelesaikan tic-tac-toe dengan Transformer lalu mengajukan pendanaan VC
Beberapa tahun lagi mungkin semua orang akan menulis tentang betapa jauh lebih efisien kode sungguhan dibanding AI ;)
Jika mempelajari heuristik yang admissible, kita bisa mempertahankan performa kasus terburuk, dan itulah yang selalu menjadi standar bagi algoritma semacam ini
Sama sekali tidak jarang menemukan solusi yang lebih cepat pada kasus rata-rata atau p99, tetapi tidak memberikan jaminan kasus terburuk
Saya penasaran apakah ada yang menyusun daftar algoritma klasik atau masalah NP-complete yang bisa dilakukan lebih baik dengan deep learning