Langkah Raksasa Berisiko Dapat Memecahkan Masalah Optimasi Lebih Cepat | Majalah Quanta

Masalah pengoptimalan bisa rumit, tetapi membuat dunia bekerja lebih baik. Pertanyaan semacam ini, yang mencari cara terbaik untuk melakukan sesuatu, benar-benar ada di mana-mana. GPS ponsel Anda menghitung rute terpendek ke tujuan Anda. Situs web perjalanan mencari kombinasi penerbangan termurah yang cocok dengan rencana perjalanan Anda. Dan aplikasi pembelajaran mesin, yang belajar dengan menganalisis pola dalam data, mencoba menyajikan jawaban yang paling akurat dan manusiawi untuk setiap pertanyaan yang diberikan.

Untuk masalah pengoptimalan sederhana, menemukan solusi terbaik hanyalah masalah aritmatika. Tetapi pertanyaan dunia nyata yang menarik minat matematikawan dan ilmuwan jarang sekali sederhana. Pada tahun 1847, ahli matematika Prancis Augustin-Louis Cauchy sedang mengerjakan contoh rumit yang sesuai — perhitungan astronomi — ketika dia memelopori metode umum pengoptimalan yang sekarang dikenal sebagai penurunan gradien. Sebagian besar program pembelajaran mesin saat ini sangat bergantung pada teknik, dan bidang lain juga menggunakannya untuk menganalisis data dan memecahkan masalah teknik.

Matematikawan telah menyempurnakan penurunan gradien selama lebih dari 150 tahun, tetapi bulan lalu, sebuah pelajaran membuktikan bahwa asumsi dasar tentang teknik ini mungkin salah. “Ada beberapa kali saya terkejut, [seperti] intuisi saya rusak,” kata Ben Grimmer, seorang ahli matematika terapan di Universitas Johns Hopkins dan penulis tunggal studi tersebut. Hasil yang berlawanan dengan intuisinya menunjukkan bahwa penurunan gradien dapat bekerja hampir tiga kali lebih cepat jika melanggar aturan yang telah lama diterima tentang cara menemukan jawaban terbaik untuk pertanyaan tertentu. Sementara kemajuan teoretis kemungkinan tidak berlaku untuk masalah-masalah rumit yang ditangani oleh pembelajaran mesin, hal itu telah menyebabkan para peneliti mempertimbangkan kembali apa yang mereka ketahui tentang teknik tersebut.

“Ternyata kami tidak memiliki pemahaman penuh” tentang teori di balik penurunan gradien, kata Shuvomoy Das Gupta, seorang peneliti pengoptimalan di Massachusetts Institute of Technology. Sekarang, katanya, kita "lebih dekat untuk memahami apa yang dilakukan penurunan gradien."

Teknik itu sendiri tampak sederhana. Ini menggunakan sesuatu yang disebut fungsi biaya, yang terlihat seperti garis lengkung halus yang berkelok-kelok naik turun melintasi grafik. Untuk titik mana pun di garis itu, ketinggian mewakili biaya dalam beberapa cara - berapa banyak waktu, energi, atau kesalahan yang akan ditimbulkan operasi saat disetel ke pengaturan tertentu. Semakin tinggi titiknya, semakin jauh dari ideal sistem tersebut. Secara alami, Anda ingin mencari titik terendah di jalur ini, di mana biayanya paling kecil.

Algoritme penurunan gradien merasakan jalan mereka ke bawah dengan memilih satu titik dan menghitung kemiringan (atau gradien) kurva di sekitarnya, lalu bergerak ke arah kemiringan yang paling curam. Bayangkan ini seperti merasakan jalan menuruni gunung dalam kegelapan. Anda mungkin tidak tahu persis ke mana harus bergerak, berapa lama Anda harus mendaki, atau seberapa dekat Anda dengan permukaan laut pada akhirnya, tetapi jika Anda menuruni turunan yang paling tajam, pada akhirnya Anda akan tiba di titik terendah di area tersebut.

Berbeda dengan pendaki gunung metaforis, peneliti pengoptimalan dapat memprogram algoritme penurunan gradien mereka untuk mengambil langkah dalam berbagai ukuran. Lompatan raksasa memang menggoda tetapi juga berisiko, karena bisa melampaui jawabannya. Sebaliknya, kebijaksanaan konvensional lapangan selama beberapa dekade adalah mengambil langkah kecil. Dalam persamaan penurunan gradien, ini berarti ukuran langkah tidak lebih besar dari 2, meskipun tidak ada yang bisa membuktikan bahwa ukuran langkah yang lebih kecil selalu lebih baik.

Dengan kemajuan dalam teknik pembuktian dengan bantuan komputer, ahli teori optimasi telah mulai menguji teknik yang lebih ekstrim. Dalam satu penelitian, pertama diposting di 2022 dan baru diterbitkan in Pemrograman Matematika, Das Gupta, dan lainnya menugaskan komputer untuk menemukan panjang langkah terbaik untuk algoritme yang dibatasi hanya untuk menjalankan 50 langkah — semacam masalah pengoptimalan meta, karena mencoba mengoptimalkan pengoptimalan. Mereka menemukan bahwa 50 anak tangga yang paling optimal memiliki panjang yang bervariasi secara signifikan, dengan satu anak tangga di tengah urutan mencapai hampir sepanjang 37, jauh di atas tutup tipikal dengan panjang 2.

Temuan menunjukkan bahwa peneliti pengoptimalan telah melewatkan sesuatu. Penasaran, Grimmer berusaha mengubah hasil numerik Das Gupta menjadi teorema yang lebih umum. Untuk melewati batas 50 langkah acak, Grimmer mengeksplorasi berapa panjang langkah optimal untuk urutan yang dapat diulang, semakin mendekati jawaban optimal dengan setiap pengulangan. Dia menjalankan komputer melalui jutaan permutasi urutan panjang langkah, membantu menemukan yang paling cepat menyatu pada jawaban.

Grimmer menemukan bahwa urutan tercepat selalu memiliki satu kesamaan: Langkah tengah selalu besar. Ukurannya bergantung pada jumlah langkah dalam urutan berulang. Untuk urutan tiga langkah, langkah besar memiliki panjang 4.9. Untuk urutan 15 langkah, algoritme merekomendasikan satu langkah dengan panjang 29.7. Dan untuk rangkaian 127 langkah, yang terpanjang yang diuji, lompatan pusat yang besar adalah 370 kekalahan. Pada awalnya kedengarannya seperti angka yang sangat besar, kata Grimmer, tetapi ada cukup langkah total untuk mengimbangi lompatan raksasa itu, jadi bahkan jika Anda meniup melewati bagian bawah, Anda masih bisa kembali dengan cepat. Makalahnya menunjukkan bahwa urutan ini dapat mencapai titik optimal hampir tiga kali lebih cepat daripada dengan mengambil langkah kecil yang konstan. "Kadang-kadang, Anda harus benar-benar overcommit," katanya.

Pendekatan siklus ini mewakili cara berpikir yang berbeda tentang penurunan gradien, kata Aymeric Dieuleveut, seorang peneliti optimisasi di École Polytechnique di Palaiseau, Prancis. “Intuisi ini, yang seharusnya saya pikirkan tidak selangkah demi selangkah, tetapi sebagai beberapa langkah secara berurutan — saya pikir ini adalah sesuatu yang diabaikan oleh banyak orang,” katanya. "Ini bukan cara yang diajarkan." (Grimmer mencatat bahwa pembingkaian ulang ini juga diusulkan untuk kelas masalah serupa dalam tesis master tahun 2018 oleh Jason Altschuler, seorang peneliti pengoptimalan yang sekarang berada di University of Pennsylvania.)

Namun, sementara wawasan ini dapat mengubah cara peneliti berpikir tentang penurunan gradien, kemungkinan besar mereka tidak akan mengubah cara teknik tersebut digunakan saat ini. Kertas Grimmer hanya berfokus pada fungsi halus, yang tidak memiliki kekusutan tajam, dan fungsi cembung, yang berbentuk mangkuk dan hanya memiliki satu nilai optimal di bagian bawah. Fungsi-fungsi semacam ini mendasar bagi teori tetapi kurang relevan dalam praktiknya; program pengoptimalan yang digunakan peneliti pembelajaran mesin biasanya jauh lebih rumit. Ini membutuhkan versi penurunan gradien yang memiliki "begitu banyak lonceng dan peluit, dan begitu banyak nuansa," kata Grimmer.

Beberapa dari teknik tambahan ini bisa berjalan lebih cepat daripada pendekatan langkah besar Grimmer, katanya Gauthier Gidel, seorang peneliti optimisasi dan pembelajaran mesin di University of Montreal. Namun teknik ini memerlukan biaya operasional tambahan, jadi harapannya adalah penurunan gradien reguler dapat menang dengan kombinasi ukuran langkah yang tepat. Sayangnya, percepatan tiga kali lipat studi baru ini tidak cukup.

“Ini menunjukkan sedikit peningkatan,” kata Gidel. “Tapi saya kira pertanyaan sebenarnya adalah: Bisakah kita benar-benar menutup celah ini?”

Hasilnya juga memunculkan misteri teoretis tambahan yang membuat Grimmer terjaga di malam hari. Mengapa pola ukuran anak tangga yang ideal semuanya memiliki bentuk yang simetris? Tidak hanya langkah terbesar selalu tepat di tengah, tetapi pola yang sama muncul di kedua sisinya: Terus memperbesar dan membagi urutan, katanya, dan Anda mendapatkan "pola hampir fraktal" dari langkah yang lebih besar dikelilingi oleh langkah yang lebih kecil . Pengulangan menunjukkan struktur dasar yang mengatur solusi terbaik yang belum berhasil dijelaskan oleh siapa pun. Tapi Grimmer, setidaknya, penuh harapan.

"Jika saya tidak bisa memecahkannya, orang lain akan melakukannya," katanya.