AlphaTensor, dibangun di atas AlphaZero, agen yang telah menunjukkan kinerja manusia super pada permainan papan, seperti catur, Go dan shogi, dan karya ini menunjukkan perjalanan AlphaZero dari bermain game hingga menangani masalah matematika yang belum terpecahkan untuk pertama kalinya.
Orang Mesir kuno menciptakan algoritme untuk mengalikan dua angka tanpa memerlukan tabel perkalian, dan matematikawan Yunani Euclid menjelaskan algoritme untuk menghitung pembagi persekutuan terbesar, yang masih digunakan sampai sekarang.
Selama Zaman Keemasan Islam, matematikawan Persia Muhammad ibn Musa al-Khawarizmi merancang algoritma baru untuk memecahkan persamaan linear dan kuadrat. Bahkan, nama al-Khawarizmi, yang diterjemahkan ke dalam bahasa Latin sebagai Algoritmi, memunculkan istilah algoritma. Namun, terlepas dari keakraban dengan algoritme saat ini – digunakan di seluruh masyarakat mulai dari aljabar kelas hingga penelitian ilmiah mutakhir – proses menemukan algoritme baru sangat sulit, dan merupakan contoh kemampuan penalaran yang luar biasa dari pikiran manusia.
Mereka diterbitkan di Nature. AlphaTensor adalah sistem kecerdasan buatan (AI) pertama untuk menemukan algoritma baru, efisien, dan terbukti benar untuk tugas-tugas mendasar seperti perkalian matriks. Ini menjelaskan pertanyaan terbuka berusia 50 tahun dalam matematika tentang menemukan cara tercepat untuk mengalikan dua matriks.
Dilatih dari awal, AlphaTensor menemukan algoritme perkalian matriks yang lebih efisien daripada algoritme rancangan manusia dan komputer yang ada. Meskipun meningkatkan lebih dari algoritma yang dikenal, mereka mencatat bahwa keterbatasan AlphaTensor adalah kebutuhan untuk pra-mendefinisikan satu set entri faktor potensial F, yang mendiskritkan ruang pencarian tetapi mungkin dapat menyebabkan hilangnya algoritma yang efisien. Arah yang menarik untuk penelitian di masa depan adalah mengadaptasi AlphaTensor untuk mencari F. Salah satu kekuatan penting AlphaTensor adalah fleksibilitasnya untuk mendukung imbalan stokastik dan non-diferensiasi yang kompleks (dari peringkat tensor hingga efisiensi praktis pada perangkat keras tertentu), selain menemukan algoritme untuk operasi kustom di berbagai ruang (seperti bidang terbatas). Mereka percaya ini akan memacu aplikasi AlphaTensor untuk merancang algoritme yang mengoptimalkan metrik yang tidak kami pertimbangkan di sini, seperti stabilitas numerik atau penggunaan energi.
Penemuan algoritma perkalian matriks memiliki implikasi yang luas, karena perkalian matriks merupakan inti dari banyak tugas komputasi, seperti inversi matriks, menghitung determinan, dan menyelesaikan sistem linier.
Proses dan kemajuan mengotomatiskan penemuan algoritmik
Pertama, mereka mengubah masalah menemukan algoritma yang efisien untuk perkalian matriks menjadi permainan pemain tunggal. Dalam permainan ini, papan adalah tensor tiga dimensi (array angka), menangkap seberapa jauh dari benar algoritma saat ini. Melalui serangkaian gerakan yang diizinkan, sesuai dengan instruksi algoritme, pemain mencoba memodifikasi tensor dan menghapus entrinya. Ketika pemain berhasil melakukannya, ini menghasilkan algoritme perkalian matriks yang terbukti benar untuk setiap pasangan matriks, dan efisiensinya ditangkap oleh jumlah langkah yang diambil untuk meniadakan tensor.
Game ini sangat menantang – jumlah algoritme yang mungkin untuk dipertimbangkan jauh lebih besar daripada jumlah atom di alam semesta, bahkan untuk kasus perkalian matriks yang kecil. Dibandingkan dengan permainan Go, yang tetap menjadi tantangan bagi AI selama beberapa dekade, jumlah kemungkinan gerakan pada setiap langkah permainan mereka adalah 30 kali lipat lebih besar (di atas 10^33 untuk salah satu pengaturan yang mereka pertimbangkan).
Pada dasarnya, untuk memainkan permainan ini dengan baik, seseorang perlu mengidentifikasi jarum terkecil dalam tumpukan kemungkinan yang sangat besar. Untuk mengatasi tantangan domain ini, yang secara signifikan menyimpang dari permainan tradisional, kami mengembangkan beberapa komponen penting termasuk arsitektur jaringan saraf baru yang menggabungkan bias induktif khusus masalah, prosedur untuk menghasilkan data sintetis yang berguna, dan resep untuk memanfaatkan simetri masalah.
Mereka kemudian melatih agen AlphaTensor menggunakan pembelajaran penguatan untuk bermain game, dimulai tanpa pengetahuan tentang algoritma perkalian matriks yang ada. Melalui pembelajaran, AlphaTensor secara bertahap meningkat dari waktu ke waktu, menemukan kembali algoritme perkalian matriks cepat historis seperti Strassen, yang pada akhirnya melampaui ranah intuisi manusia dan menemukan algoritme lebih cepat daripada yang diketahui sebelumnya.
Menjelajahi dampak pada penelitian dan aplikasi masa depan
Dari sudut pandang matematika, hasil mereka dapat memandu penelitian lebih lanjut dalam teori kompleksitas, yang bertujuan untuk menentukan algoritma tercepat untuk memecahkan masalah komputasi. Dengan menjelajahi ruang kemungkinan algoritme dengan cara yang lebih efektif daripada pendekatan sebelumnya, AlphaTensor membantu memajukan pemahaman kita tentang kekayaan algoritme perkalian matriks. Memahami ruang ini dapat membuka hasil baru untuk membantu menentukan kompleksitas asimtotik dari perkalian matriks, salah satu masalah terbuka paling mendasar dalam ilmu komputer.
Karena perkalian matriks adalah komponen inti dalam banyak tugas komputasi, mencakup grafik komputer, komunikasi digital, pelatihan jaringan saraf, dan komputasi ilmiah, algoritme yang ditemukan AlphaTensor dapat membuat komputasi di bidang ini secara signifikan lebih efisien. Fleksibilitas AlphaTensor untuk mempertimbangkan segala jenis tujuan juga dapat memacu aplikasi baru untuk merancang algoritme yang mengoptimalkan metrik seperti penggunaan energi dan stabilitas numerik, membantu mencegah kesalahan pembulatan kecil dari bola salju saat algoritme bekerja.
Sementara mereka fokus di sini pada masalah khusus perkalian matriks, kami berharap makalah kami akan menginspirasi orang lain dalam menggunakan AI untuk memandu penemuan algoritmik untuk tugas komputasi mendasar lainnya. Penelitian mereka juga menunjukkan bahwa AlphaZero adalah algoritma yang kuat yang dapat diperluas jauh melampaui domain permainan tradisional untuk membantu memecahkan masalah terbuka dalam matematika. Berdasarkan penelitian kami, mereka berharap dapat memacu kerja yang lebih besar – menerapkan AI untuk membantu masyarakat memecahkan beberapa tantangan paling penting dalam matematika dan sains.
Alam – Menemukan algoritme perkalian matriks yang lebih cepat dengan pembelajaran penguatan
Abstrak
Meningkatkan efisiensi algoritme untuk komputasi dasar dapat berdampak luas, karena dapat memengaruhi kecepatan keseluruhan dari sejumlah besar komputasi. Perkalian matriks adalah salah satu tugas primitif seperti itu, yang terjadi di banyak sistem—dari jaringan saraf hingga rutinitas komputasi ilmiah. Penemuan algoritme otomatis menggunakan pembelajaran mesin menawarkan prospek untuk melampaui intuisi manusia dan mengungguli algoritme rancangan manusia terbaik saat ini. Namun, mengotomatisasi prosedur penemuan algoritme itu rumit, karena ruang kemungkinan algoritme sangat besar. Di sini kami melaporkan pendekatan pembelajaran penguatan mendalam berdasarkan AlphaZero1 untuk menemukan algoritma yang efisien dan terbukti benar untuk perkalian matriks arbitrer. Agen kami, AlphaTensor, dilatih untuk memainkan game pemain tunggal yang tujuannya adalah menemukan dekomposisi tensor dalam ruang faktor berhingga. AlphaTensor menemukan algoritme yang mengungguli kompleksitas canggih untuk banyak ukuran matriks. Yang sangat relevan adalah kasus matriks 4 × 4 di bidang terbatas, di mana algoritma AlphaTensor meningkatkan algoritma dua tingkat Strassen untuk pertama kalinya, sepengetahuan kami, sejak penemuannya 50 tahun yang lalu2. Kami selanjutnya menunjukkan fleksibilitas AlphaTensor melalui kasus penggunaan yang berbeda: algoritme dengan kompleksitas canggih untuk perkalian matriks terstruktur dan peningkatan efisiensi praktis dengan mengoptimalkan perkalian matriks untuk runtime pada perangkat keras tertentu. Hasil kami menyoroti kemampuan AlphaTensor untuk mempercepat proses penemuan algoritmik pada berbagai masalah, dan untuk mengoptimalkan kriteria yang berbeda.
Brian Wang adalah Pemimpin Pemikiran Futuris dan blogger Sains populer dengan 1 juta pembaca per bulan. Blognya Nextbigfuture.com berada di peringkat #1 Blog Berita Sains. Ini mencakup banyak teknologi dan tren yang mengganggu termasuk Luar Angkasa, Robotika, Kecerdasan Buatan, Kedokteran, Bioteknologi Anti-penuaan, dan Nanoteknologi.
Dikenal karena mengidentifikasi teknologi mutakhir, dia saat ini adalah salah satu pendiri startup dan penggalangan dana untuk perusahaan tahap awal yang berpotensi tinggi. Dia adalah Kepala Riset untuk Alokasi untuk investasi teknologi dalam dan Angel Investor di Space Angels.
Sering menjadi pembicara di perusahaan, dia telah menjadi pembicara TEDx, pembicara Universitas Singularitas dan tamu di berbagai wawancara untuk radio dan podcast. Dia terbuka untuk berbicara di depan umum dan memberikan nasihat.
