Pengantar
Matematikawan menyukai teka-teki yang bagus. Bahkan sesuatu yang abstrak seperti mengalikan matriks (tabel angka dua dimensi) dapat terasa seperti permainan saat Anda mencoba menemukan cara paling efisien untuk melakukannya. Ini seperti mencoba memecahkan Kubus Rubik dalam gerakan sesedikit mungkin — menantang, tetapi memikat. Kecuali untuk Kubus Rubik, jumlah gerakan yang mungkin dilakukan pada setiap langkah adalah 18; untuk perkalian matriks, bahkan dalam kasus yang relatif sederhana, setiap langkah dapat menampilkan lebih dari 1012 Pilihan.
Selama 50 tahun terakhir, para peneliti telah mendekati masalah ini dengan banyak cara, semuanya berdasarkan pencarian komputer yang dibantu oleh intuisi manusia. Bulan lalu, sebuah tim di perusahaan kecerdasan buatan DeepMind menunjukkan cara mengatasi masalah dari arah yang baru, melaporkan dalam a kertas in Alam bahwa mereka telah berhasil melatih jaringan saraf untuk menemukan algoritme baru yang cepat untuk perkalian matriks. Seolah-olah AI telah menemukan strategi yang tidak diketahui untuk memecahkan Kubus Rubik yang sangat rumit.
"Ini hasil yang sangat rapi," kata Josh Alman, seorang ilmuwan komputer di Universitas Columbia. Tetapi dia dan spesialis perkalian matriks lainnya juga menekankan bahwa bantuan AI semacam itu akan melengkapi daripada menggantikan metode yang ada — setidaknya dalam waktu dekat. “Ini seperti proof of concept untuk sesuatu yang bisa menjadi terobosan,” ujar Alman. Hasilnya hanya akan membantu para peneliti dalam pencarian mereka.
Seolah ingin membuktikan maksudnya, tiga hari setelah itu Alam kertas keluar, sepasang peneliti Austria mengilustrasikan bagaimana metode baru dan lama dapat saling melengkapi. Mereka menggunakan pencarian berbantuan komputer konvensional untuk lebih meningkatkan salah satu algoritme yang ditemukan jaringan saraf.
Hasilnya menunjukkan bahwa, seperti proses memecahkan Kubus Rubik, jalan menuju algoritme yang lebih baik akan penuh liku-liku.
Mengalikan Matriks
Perkalian matriks adalah salah satu operasi paling mendasar dan ada di mana-mana dalam semua matematika. Untuk mengalikan sepasang n-oleh-n matriks, masing-masing dengan n2 elemen, Anda mengalikan dan menjumlahkan elemen-elemen ini bersama-sama dalam kombinasi tertentu untuk menghasilkan produk, sepertiga n-oleh-n matriks. Resep standar untuk mengalikan dua n-oleh-n matriks membutuhkan n3 operasi perkalian, jadi matriks 2 kali 2, misalnya, membutuhkan delapan kali perkalian.
Untuk matriks yang lebih besar, dengan ribuan baris dan kolom, proses ini dengan cepat menjadi tidak praktis. Namun pada tahun 1969, matematikawan Volker Strassen menemukan prosedur untuk mengalikan sepasang matriks 2-kali-2 menggunakan tujuh, bukan delapan langkah perkalian, dengan mengorbankan lebih banyak langkah penjumlahan.
Algoritme Strassen tidak perlu berbelit-belit jika Anda hanya ingin mengalikan sepasang matriks 2-kali-2. Tapi dia menyadari itu juga akan berhasil untuk matriks yang lebih besar. Itu karena elemen matriks itu sendiri bisa menjadi matriks. Misalnya, sebuah matriks dengan 20,000 baris dan 20,000 kolom dapat ditata ulang sebagai matriks 2 kali 2 yang empat elemennya masing-masing adalah matriks berukuran 10,000 kali 10,000. Masing-masing matriks ini kemudian dapat dibagi lagi menjadi empat blok berukuran 5,000 kali 5,000, dan seterusnya. Strassen dapat menerapkan metodenya untuk mengalikan matriks 2 kali 2 pada setiap tingkat hierarki bersarang ini. Saat ukuran matriks meningkat, penghematan dari perkalian yang lebih sedikit tumbuh.
Penemuan Strassen mengarah pada pencarian algoritme yang efisien untuk perkalian matriks, yang sejak saat itu mengilhami dua subbidang yang berbeda. Seseorang berfokus pada pertanyaan prinsip: Jika Anda membayangkan mengalikan dua n-oleh-n matriks dan biarkan n berlari menuju tak terhingga, bagaimana jumlah langkah perkalian dalam skala algoritma tercepat yang mungkin dengan n? Itu rekor saat ini untuk penskalaan terbaik, n2.3728596, milik Alman dan Virginia Vassilevska Williams, seorang ilmuwan komputer di Massachusetts Institute of Technology. (Baru-baru ini tidak diterbitkan pracetak melaporkan peningkatan kecil menggunakan teknik baru.) Tetapi algoritme ini hanya kepentingan teoretis, menang atas metode seperti Strassen hanya untuk matriks yang sangat besar.
Subbidang kedua berpikir dalam skala yang lebih kecil. Segera setelah pekerjaan Strassen, ilmuwan komputer Amerika Israel Shmuel Winograd menunjukkan bahwa Strassen telah mencapai batas teoretis: Tidak mungkin mengalikan matriks 2 kali 2 dengan langkah perkalian kurang dari tujuh. Tetapi untuk semua ukuran matriks lainnya, jumlah minimum perkalian yang diperlukan tetap menjadi pertanyaan terbuka. Dan algoritme cepat untuk matriks kecil dapat memiliki dampak yang sangat besar, karena iterasi berulang dari algoritme semacam itu dapat mengalahkan algoritme Strassen ketika matriks berukuran wajar dikalikan.
Sayangnya, banyaknya kemungkinan sangat besar. Bahkan untuk matriks 3 kali 3, "jumlah kemungkinan algoritme melebihi jumlah atom di alam semesta," kata Alhussein Fawzi, seorang peneliti DeepMind dan salah satu pemimpin pekerjaan baru.
Dihadapkan dengan menu pilihan yang memusingkan ini, para peneliti telah membuat kemajuan dengan mengubah perkalian matriks menjadi masalah matematika yang sama sekali berbeda — yang lebih mudah ditangani oleh komputer. Ini mungkin untuk mewakili tugas abstrak mengalikan dua matriks sebagai jenis objek matematika tertentu: array angka tiga dimensi yang disebut tensor. Peneliti kemudian dapat memecah tensor ini menjadi sejumlah komponen dasar, yang disebut tensor “peringkat-1”; masing-masing akan mewakili langkah yang berbeda dalam algoritma perkalian matriks yang sesuai. Artinya, menemukan algoritme perkalian yang efisien sama dengan meminimalkan jumlah suku dalam dekomposisi tensor — semakin sedikit suku, semakin sedikit langkah yang terlibat.
Dengan cara ini, para peneliti telah menemukan yang baru algoritma yang berkembang biak n-oleh-n matriks menggunakan lebih sedikit dari standar n3 langkah perkalian untuk banyak ukuran matriks kecil. Tetapi algoritme yang mengungguli tidak hanya standar tetapi juga algoritme Strassen untuk matriks kecil tetap tidak terjangkau — hingga sekarang.
Game Aktif
Tim DeepMind mendekati masalah tersebut dengan mengubah dekomposisi tensor menjadi permainan pemain tunggal. Mereka mulai dengan algoritme pembelajaran mendalam yang diturunkan dari AlphaGo — AI DeepMind lain yang ada di tahun 2016 belajar memainkan permainan papan Go cukup baik untuk mengalahkan pemain manusia top.
Semua algoritme pembelajaran mendalam dibangun di sekitar jaringan saraf: jaring neuron buatan yang diurutkan ke dalam lapisan, dengan koneksi yang kekuatannya dapat bervariasi yang menunjukkan seberapa besar pengaruh setiap neuron pada lapisan berikutnya. Kekuatan koneksi ini di-tweak selama banyak iterasi dari prosedur pelatihan, di mana jaringan saraf belajar mengubah setiap input yang diterimanya menjadi output yang membantu algoritme mencapai tujuan keseluruhannya.
Dalam algoritme baru DeepMind, yang dijuluki AlphaTensor, input mewakili langkah-langkah di sepanjang jalan menuju skema perkalian matriks yang valid. Input pertama ke jaringan saraf adalah tensor perkalian matriks asli, dan outputnya adalah tensor peringkat-1 yang dipilih AlphaTensor untuk gerakan pertamanya. Algoritme mengurangi tensor peringkat-1 ini dari input awal, menghasilkan tensor yang diperbarui yang diumpankan kembali ke jaringan sebagai input baru. Proses ini berulang hingga akhirnya setiap elemen dalam tensor awal dikurangi menjadi nol, artinya tidak ada lagi tensor peringkat-1 yang harus dihilangkan.
Pada saat itu, jaringan neural telah menemukan dekomposisi tensor yang valid, karena secara matematis dijamin bahwa jumlah semua tensor peringkat-1 sama persis dengan tensor awal. Dan langkah-langkah yang diperlukan untuk sampai ke sana dapat diterjemahkan kembali ke dalam langkah-langkah algoritma perkalian matriks yang sesuai.
Inilah permainannya: AlphaTensor berulang kali menguraikan tensor menjadi kumpulan komponen peringkat-1. Setiap kali, AlphaTensor mendapat hadiah jika menemukan cara untuk mengurangi jumlah langkah. Tetapi jalan pintas menuju kemenangan sama sekali tidak intuitif, sama seperti Anda terkadang harus mengacak wajah yang tertata sempurna di Kubus Rubik sebelum Anda dapat menyelesaikan semuanya.
Tim sekarang memiliki algoritme yang, secara teoritis, dapat memecahkan masalah mereka. Mereka hanya harus melatihnya terlebih dahulu.
Jalan Baru
Seperti semua jaringan saraf, AlphaTensor membutuhkan banyak data untuk dilatih, tetapi dekomposisi tensor adalah masalah yang sangat sulit. Ada beberapa contoh dekomposisi efisien yang dapat diberikan oleh para peneliti ke jaringan. Sebagai gantinya, mereka membantu algoritme memulai dengan melatihnya pada masalah invers yang jauh lebih mudah: menambahkan banyak tensor peringkat-1 yang dibuat secara acak.
“Mereka menggunakan soal yang mudah untuk menghasilkan lebih banyak data untuk soal yang sulit,” kata Michael Littman, seorang ilmuwan komputer di Brown University. Menggabungkan prosedur pelatihan mundur ini dengan pembelajaran penguatan, di mana AlphaTensor menghasilkan data pelatihannya sendiri saat melakukan kesalahan mencari dekomposisi yang efisien, bekerja jauh lebih baik daripada salah satu metode pelatihan itu sendiri.
Tim DeepMind melatih AlphaTensor untuk menguraikan tensor yang mewakili perkalian matriks hingga 12 kali 12. Itu mencari algoritma cepat untuk mengalikan matriks bilangan real biasa dan juga algoritma khusus untuk pengaturan yang lebih terbatas yang dikenal sebagai aritmatika modulo 2. (Ini adalah matematika berdasarkan hanya dua angka, jadi elemen matriks hanya bisa 0 atau 1, dan 1 + 1 = 0.) Para peneliti sering memulai dengan ruang yang lebih terbatas namun tetap luas ini, dengan harapan algoritme yang ditemukan di sini dapat disesuaikan dengan mengerjakan matriks bilangan asli.
Setelah pelatihan, AlphaTensor menemukan kembali algoritme Strassen dalam hitungan menit. Ia kemudian menemukan hingga ribuan algoritma cepat baru untuk setiap ukuran matriks. Ini berbeda dari algoritma yang paling terkenal tetapi memiliki jumlah langkah perkalian yang sama.
Dalam beberapa kasus, AlphaTensor bahkan mengalahkan rekor yang ada. Penemuannya yang paling mengejutkan terjadi dalam aritmatika modulo 2, di mana ia menemukan algoritme baru untuk mengalikan matriks 4-kali-4 dalam 47 langkah perkalian, peningkatan dari 49 langkah yang diperlukan untuk dua iterasi algoritme Strassen. Itu juga mengalahkan algoritma paling terkenal untuk matriks 5-kali-5 modulo 2, mengurangi jumlah perkalian yang diperlukan dari rekor sebelumnya 98 menjadi 96. (Namun rekor baru ini masih tertinggal dari 91 langkah yang diperlukan untuk mengalahkan Algoritme Strassen menggunakan matriks 5-kali-5.)
Hasil profil tinggi yang baru menciptakan banyak kegembiraan, dengan beberapa peneliti menumpuk pujian pada peningkatan berbasis AI pada status quo. Tapi tidak semua orang di komunitas perkalian matriks begitu terkesan. “Saya merasa agak overhyped,” kata Vassilevska Williams. “Itu alat lain. Ini tidak seperti, 'Oh, komputer mengalahkan manusia,' Anda tahu?
Para peneliti juga menekankan bahwa aplikasi langsung dari algoritma pemecah rekor 4-kali-4 akan terbatas: Tidak hanya valid dalam aritmatika modulo 2, tetapi dalam kehidupan nyata ada pertimbangan penting selain kecepatan.
Fawzi setuju bahwa sungguh, ini baru permulaan. “Ada banyak ruang untuk perbaikan dan penelitian, dan itu hal yang bagus,” katanya.
Sentuhan Terakhir
Kekuatan terbesar AlphaTensor dibandingkan dengan metode pencarian komputer yang mapan juga merupakan kelemahan terbesarnya: AlphaTensor tidak dibatasi oleh intuisi manusia tentang seperti apa algoritme yang bagus, sehingga tidak dapat menjelaskan pilihannya. Itu menyulitkan peneliti untuk belajar dari pencapaiannya.
Tapi ini mungkin bukan kerugian sebesar kelihatannya. Beberapa hari setelah hasil AlphaTensor, matematikawan Manuel Kauer dan mahasiswa pascasarjananya Jakob Moosbauer, keduanya dari Universitas Johannes Kepler Linz di Austria, melaporkan langkah maju lainnya.
Pengantar
Ketika makalah DeepMind keluar, Kauers dan Moosbauer sedang dalam proses mencari algoritma perkalian baru menggunakan pencarian berbantuan komputer konvensional. Tetapi tidak seperti kebanyakan pencarian seperti itu, yang memulai dari awal dengan prinsip panduan baru, metode mereka bekerja dengan berulang kali mengutak-atik algoritme yang ada dengan harapan dapat menghemat lebih banyak perkalian darinya. Mengambil algoritme AlphaTensor untuk matriks 5-kali-5 modulo 2 sebagai titik awal, mereka terkejut menemukan bahwa metode mereka mengurangi jumlah langkah perkalian dari 96 menjadi 95 hanya setelah beberapa detik komputasi.
AlphaTensor juga membantu mereka melakukan perbaikan lain secara tidak langsung. Sebelumnya, Kauers dan Moosbauer tidak bersusah payah menjelajahi ruang matriks berukuran 4 kali 4, meyakini bahwa tidak mungkin mengalahkan dua iterasi algoritme Strassen. Hasil AlphaTensor mendorong mereka untuk mempertimbangkan kembali, dan setelah satu minggu waktu perhitungan mulai dari awal, metode mereka memunculkan algoritme 47 langkah lain yang tidak terkait dengan yang ditemukan AlphaTensor. "Jika seseorang memberi tahu kami bahwa ada sesuatu untuk ditemukan untuk 4-kali-4, kami dapat melakukannya lebih awal," kata Kauers. "Tapi oke, begitulah cara kerjanya."
Littman mengharapkan lebih banyak kejutan seperti itu, menyamakan situasinya dengan pertama kali seorang pelari menyelesaikan satu mil dalam waktu kurang dari empat menit, suatu prestasi yang secara luas dianggap mustahil. “Orang-orang bilang, 'Oh, tunggu, kita bisa melakukan ini,' dan sekarang banyak orang bisa melakukannya,” katanya.
Ke depan, Fawzi berharap untuk menggeneralisasi AlphaTensor untuk menangani tugas matematika dan komputasi yang lebih luas, sama seperti leluhurnya AlphaGo akhirnya bercabang ke game lain.
Kauers melihat ini sebagai tes lakmus sebenarnya untuk penerapan pembelajaran mesin untuk menemukan algoritme baru. Dia menunjukkan bahwa pencarian untuk algoritma perkalian matriks cepat adalah masalah kombinatorial yang pencarian komputer, dengan atau tanpa bantuan manusia, sangat cocok. Tapi tidak semua masalah matematika begitu mudah dijabarkan. Jika pembelajaran mesin dapat menemukan ide algoritmik baru secara kualitatif, katanya, “ini akan menjadi pengubah permainan.”
