Perpanjangan pertama AlphaZero ke matematika membuka kemungkinan baru untuk penelitian
Algoritma telah membantu matematikawan melakukan operasi fundamental selama ribuan tahun. 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 bin Musa al-Khawarizmi merancang algoritma baru untuk menyelesaikan persamaan linear dan kuadrat. Bahkan, nama al-Khawarizmi, diterjemahkan ke dalam bahasa Latin sebagai algoritma, menyebabkan 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.
Dalam kami kertas, diterbitkan hari ini di Nature, kami perkenalkan AlfaTensor, 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.
Makalah ini adalah batu loncatan dalam misi DeepMind untuk memajukan sains dan membuka kunci masalah paling mendasar menggunakan AI. Sistem kami, AlphaTensor, dibangun di atas AlphaZero, agen yang memiliki 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.
perkalian matriks
Perkalian matriks adalah salah satu operasi paling sederhana dalam aljabar, yang biasa diajarkan di kelas matematika sekolah menengah. Tetapi di luar kelas, operasi matematika yang sederhana ini memiliki pengaruh yang sangat besar di dunia digital kontemporer dan ada di mana-mana dalam komputasi modern.
Operasi ini digunakan untuk memproses gambar di smartphone, mengenali perintah ucapan, menghasilkan grafik untuk game komputer, menjalankan simulasi untuk memprediksi cuaca, mengompresi data dan video untuk dibagikan di internet, dan banyak lagi. Perusahaan di seluruh dunia menghabiskan banyak waktu dan uang untuk mengembangkan perangkat keras komputasi untuk melipatgandakan matriks secara efisien. Jadi, bahkan perbaikan kecil pada efisiensi perkalian matriks dapat berdampak luas.
Selama berabad-abad, matematikawan percaya bahwa algoritma perkalian matriks standar adalah yang terbaik yang bisa dicapai dalam hal efisiensi. Namun pada tahun 1969, matematikawan Jerman Volken Strassen mengejutkan komunitas matematika dengan menunjukkan bahwa algoritma yang lebih baik memang ada.
Dengan mempelajari matriks yang sangat kecil (ukuran 2 × 2), ia menemukan cara yang cerdik untuk menggabungkan entri matriks untuk menghasilkan algoritma yang lebih cepat. Meskipun penelitian selama beberapa dekade mengikuti terobosan Strassen, versi yang lebih besar dari masalah ini tetap belum terpecahkan – sejauh tidak diketahui seberapa efisien mungkin untuk mengalikan dua matriks yang sekecil 3×3.
Dalam makalah kami, kami mengeksplorasi bagaimana teknik AI modern dapat memajukan penemuan otomatis algoritma perkalian matriks baru. Berdasarkan kemajuan intuisi manusia, AlphaTensor menemukan algoritme yang lebih efisien daripada keadaan seni untuk banyak ukuran matriks. Algoritme rancangan AI kami mengungguli algoritme rancangan manusia, yang merupakan langkah maju yang besar dalam bidang penemuan algoritmik.
Proses dan kemajuan mengotomatiskan penemuan algoritmik
Pertama, kami 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 game Go, yang tersisa tantangan bagi AI selama beberapa dekade, jumlah kemungkinan gerakan pada setiap langkah permainan kami adalah 30 kali lipat lebih besar (di atas 1033 untuk salah satu pengaturan yang kami 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.
Kami kemudian melatih agen AlphaTensor menggunakan pembelajaran penguatan untuk memainkan game, dimulai tanpa pengetahuan tentang algoritme 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.
Misalnya, jika algoritme tradisional yang diajarkan di sekolah mengalikan matriks 4×5 dengan 5×5 menggunakan 100 perkalian, dan angka ini dikurangi menjadi 80 dengan kecerdikan manusia, AlphaTensor telah menemukan algoritme yang melakukan operasi yang sama hanya dengan menggunakan 76 perkalian.
Di luar contoh ini, algoritme AlphaTensor meningkatkan algoritme dua tingkat Strassen dalam bidang terbatas untuk pertama kalinya sejak penemuannya 50 tahun lalu. Algoritma untuk mengalikan matriks kecil ini dapat digunakan sebagai primitif untuk mengalikan matriks yang jauh lebih besar dengan ukuran arbitrer.
Selain itu, AlphaTensor juga menemukan serangkaian algoritme yang beragam dengan kompleksitas mutakhir – hingga ribuan algoritme perkalian matriks untuk setiap ukuran, menunjukkan bahwa ruang algoritme perkalian matriks lebih kaya dari yang diperkirakan sebelumnya.
Algoritma dalam ruang yang kaya ini memiliki sifat matematis dan praktis yang berbeda. Memanfaatkan keragaman ini, kami mengadaptasi AlphaTensor untuk secara khusus menemukan algoritme yang cepat pada perangkat keras tertentu, seperti GPU Nvidia V100, dan Google TPU v2. Algoritme ini mengalikan matriks besar 10-20% lebih cepat daripada algoritme yang umum digunakan pada perangkat keras yang sama, yang menunjukkan fleksibilitas AlphaTensor dalam mengoptimalkan tujuan arbitrer.
Menjelajahi dampak pada penelitian dan aplikasi masa depan
Dari sudut pandang matematika, hasil kami 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 algoritma 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 kami 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 kami 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, kami berharap dapat memacu kerja yang lebih besar – menerapkan AI untuk membantu masyarakat memecahkan beberapa tantangan paling penting dalam matematika dan sains.
