Ilmuwan

Ilmuwan Komputer Menemukan Batasan Algoritma Penelitian Utama

Ilmuwan Komputer Menemukan Batasan Algoritma Penelitian Utama – Banyak aspek penelitian terapan modern bergantung pada algoritma penting yang disebut penurunan gradien. Ini adalah prosedur yang umumnya digunakan untuk menemukan nilai terbesar atau terkecil dari fungsi matematika tertentu proses yang dikenal sebagai optimalisasi fungsi. Ini dapat digunakan untuk menghitung apa pun mulai dari cara paling menguntungkan untuk memproduksi produk hingga cara terbaik untuk menetapkan shift kepada pekerja.

Ilmuwan Komputer Menemukan Batasan Algoritma Penelitian Utama

thebigvantheory – Namun terlepas dari kegunaan yang luas ini, para peneliti tidak pernah sepenuhnya memahami situasi mana yang paling sulit dihadapi oleh algoritma. Sekarang, pekerjaan baru menjelaskannya, menetapkan bahwa penurunan gradien, pada intinya, menangani masalah komputasi yang sulit secara fundamental. Hasil baru menempatkan batasan pada jenis kinerja yang dapat diharapkan peneliti dari teknik dalam aplikasi tertentu.

“Ada jenis kasus terburuk yang perlu diketahui,” kata Paul Goldberg dari University of Oxford, rekan penulis pekerjaan bersama dengan John Fearnley dan Rahul Savani dari University of Liverpool dan Alexandros Hollender dari Oxford. Hasilnya menerima Penghargaan Kertas Terbaik pada bulan Juni di Simposium tahunan Teori Komputasi.

Anda dapat membayangkan sebuah fungsi sebagai lanskap, di mana ketinggian tanah sama dengan nilai fungsi (“keuntungan”) di tempat itu. Penurunan gradien mencari minimum lokal fungsi dengan mencari arah pendakian paling curam di lokasi tertentu dan mencari menuruni bukit menjauh darinya. Kemiringan lanskap disebut gradien, oleh karena itu disebut gradien keturunan.

Penurunan gradien adalah alat penting dari penelitian terapan modern, tetapi ada banyak masalah umum yang tidak berfungsi dengan baik. Tetapi sebelum penelitian ini, tidak ada pemahaman komprehensif tentang apa yang membuat penurunan gradien berjuang dan kapan—pertanyaan bidang ilmu komputer lain yang dikenal sebagai teori kompleksitas komputasi membantu untuk menjawab.

“Banyak pekerjaan dalam penurunan gradien tidak berbicara dengan teori kompleksitas,” kata Costis Daskalakis dari Massachusetts Institute of Technology.

Kompleksitas komputasi adalah studi tentang sumber daya, seringkali waktu komputasi, yang diperlukan untuk memecahkan atau memverifikasi solusi untuk masalah komputasi yang berbeda. Peneliti mengurutkan masalah ke dalam kelas yang berbeda, dengan semua masalah di kelas yang sama berbagi beberapa karakteristik komputasi mendasar.

Untuk mengambil contoh yang relevan dengan koran baru—bayangkan sebuah kota di mana ada lebih banyak orang daripada rumah dan semua orang tinggal di sebuah rumah. Anda diberi buku telepon dengan nama dan alamat semua orang di kota, dan Anda diminta untuk menemukan dua orang yang tinggal di rumah yang sama. Anda tahu bahwa Anda dapat menemukan jawaban, karena jumlah orang lebih banyak daripada rumah, tetapi mungkin perlu sedikit mencari (terutama jika mereka tidak memiliki nama belakang yang sama).

“Ada jenis kasus terburuk yang perlu diketahui,” kata Paul Goldberg dari University of Oxford, rekan penulis pekerjaan bersama dengan John Fearnley dan Rahul Savani dari University of Liverpool dan Alexandros Hollender dari Oxford. Hasilnya menerima Penghargaan Kertas Terbaik pada bulan Juni di Simposium tahunan Teori Komputasi.

Baca Juga : Menggunakan Teori Matematika Untuk Menemukan Potensi Sebenarnya Dari Algoritma

Anda dapat membayangkan sebuah fungsi sebagai lanskap, di mana ketinggian tanah sama dengan nilai fungsi (“keuntungan”) di tempat itu. Penurunan gradien mencari minimum lokal fungsi dengan mencari arah pendakian paling curam di lokasi tertentu dan mencari menuruni bukit menjauh darinya. Kemiringan lanskap disebut gradien, oleh karena itu disebut gradien keturunan.

Penurunan gradien adalah alat penting dari penelitian terapan modern, tetapi ada banyak masalah umum yang tidak berfungsi dengan baik. Tetapi sebelum penelitian ini, tidak ada pemahaman komprehensif tentang apa yang membuat penurunan gradien berjuang dan kapan pertanyaan bidang ilmu komputer lain yang dikenal sebagai teori kompleksitas komputasi membantu untuk menjawab.

“Banyak pekerjaan dalam penurunan gradien tidak berbicara dengan teori kompleksitas,” kata Costis Daskalakis dari Massachusetts Institute of Technology.

Kompleksitas komputasi adalah studi tentang sumber daya, seringkali waktu komputasi, yang diperlukan untuk memecahkan atau memverifikasi solusi untuk masalah komputasi yang berbeda. Peneliti mengurutkan masalah ke dalam kelas yang berbeda, dengan semua masalah di kelas yang sama berbagi beberapa karakteristik komputasi mendasar.

Sebagai contoh yang relevan dengan koran baru—bayangkan sebuah kota di mana ada lebih banyak orang daripada rumah dan semua orang tinggal di sebuah rumah. Anda diberi buku telepon dengan nama dan alamat semua orang di kota, dan Anda diminta untuk menemukan dua orang yang tinggal di rumah yang sama. Anda tahu Anda dapat menemukan jawaban, karena ada lebih banyak orang daripada rumah, tetapi mungkin perlu beberapa waktu untuk mencarinya (terutama jika mereka tidak memiliki nama belakang yang sama).

Pertanyaan ini termasuk dalam kelas kompleksitas yang disebut TFNP, kependekan dari “fungsi total polinomial nondeterministik.” Ini adalah kumpulan semua masalah komputasi yang dijamin memiliki solusi dan solusinya dapat diperiksa kebenarannya dengan cepat. Para peneliti berfokus pada persilangan dua subset masalah di dalam TNTF.

Subset pertama disebut PLS (pencarian lokal polinomial). Ini adalah kumpulan masalah yang melibatkan pencarian nilai minimum atau maksimum dari suatu fungsi di wilayah tertentu. Masalah-masalah ini dijamin memiliki jawaban yang dapat ditemukan melalui penalaran yang relatif lugas.

Salah satu masalah yang termasuk dalam kategori PLS adalah tugas merencanakan rute yang memungkinkan Anda mengunjungi sejumlah kota tetap dengan jarak perjalanan terpendek yang mungkin karena Anda hanya dapat mengubah perjalanan dengan mengubah urutan pasangan kota yang berurutan. dalam tur. Sangat mudah untuk menghitung panjang rute yang diusulkan dan, dengan batasan cara Anda dapat mengubah rencana perjalanan, mudah untuk melihat perubahan mana yang mempersingkat perjalanan. Anda dijamin akhirnya menemukan rute yang tidak dapat Anda tingkatkan dengan langkah yang dapat diterima minimum lokal.

Bagian kedua dari masalah adalah PPAD (argumen paritas polinomial pada graf berarah). Masalah-masalah ini memiliki solusi yang muncul dari proses yang lebih rumit yang disebut teorema titik tetap Brouwer. Teorema mengatakan bahwa untuk setiap fungsi kontinu, dijamin ada satu titik yang tidak diubah fungsinya titik tetap, seperti yang diketahui. Ini benar dalam kehidupan sehari-hari. Jika Anda mengaduk segelas air, teorema menjamin bahwa pasti ada satu partikel air yang akan berakhir di tempat yang sama dengan asalnya.

Perpotongan antara kelas PLS dan PPAD itu sendiri membentuk kelas masalah yang dikenal sebagai PLS int PPAD. Ini berisi banyak masalah alam yang relevan dengan kompleksitas peneliti. Namun, sampai saat ini peneliti tidak dapat menemukan masalah alam yang lengkap untuk PLS int PPAD—artinya itu adalah contoh masalah yang paling sulit yang termasuk dalam kelas.

Sebelum makalah ini, satu-satunya masalah PLS int PPAD complete yang diketahui adalah konstruksi yang agak artifisial—masalah yang kadang-kadang disebut “Solusi Baik”. Masalah ini menyatukan masalah lengkap dari PLS dan masalah lengkap dari PPAD, membentuk sesuatu yang tidak mungkin ditemui peneliti di luar konteks ini. Dalam makalah baru, para peneliti membuktikan bahwa penurunan gradien sama sulitnya dengan Solusi Baik, membuat penurunan gradien itu sendiri PLS int PPAD-lengkap.

“Sifat komputasi adalah sesuatu yang kita sebagai spesies harus coba pahami secara mendalam dalam semua bentuknya. Dan saya pikir itu harus menjadi alasan yang cukup untuk bersemangat tentang hasil ini, ”kata Tim Roughgarden dari Universitas Columbia. Semua ini tidak berarti bahwa penurunan gradien akan selalu sulit. Faktanya, ini sama cepat dan efektifnya seperti biasanya untuk sebagian besar penggunaan.

“Ada stereotip yang sedikit lucu tentang kompleksitas komputasi yang mengatakan bahwa apa yang sering kita lakukan adalah mengambil masalah yang sering diselesaikan dalam praktik dan membuktikan bahwa itu sebenarnya sangat sulit,” kata Goldberg. Tetapi hasilnya tidak berarti peneliti terapan seharusnya tidak mengharapkan penurunan gradien untuk memberikan solusi yang tepat untuk beberapa masalah di mana presisi penting.

Pertanyaan tentang presisi berbicara tentang perhatian utama dari kompleksitas komputasi—evaluasi kebutuhan sumber daya. Ada hubungan mendasar antara presisi dan kecepatan dalam banyak pertanyaan kompleksitas. Agar algoritme dianggap efisien, Anda harus dapat meningkatkan ketepatan solusi tanpa membayar harga yang tinggi dalam jumlah waktu yang diperlukan untuk menemukan solusi tersebut. Hasil baru ini berarti bahwa untuk aplikasi yang membutuhkan solusi yang sangat tepat, penurunan gradien mungkin bukan pendekatan yang bisa diterapkan.

Misalnya, penurunan gradien sering digunakan dalam pembelajaran mesin dengan cara yang tidak memerlukan presisi ekstrem. Tetapi seorang peneliti pembelajaran mesin mungkin ingin menggandakan ketepatan percobaan. Dalam hal ini, hasil baru menyiratkan bahwa mereka mungkin harus melipatgandakan waktu berjalan algoritma penurunan gradien mereka. Itu tidak ideal, tetapi itu bukan pemecah kesepakatan.

Tetapi untuk aplikasi lain, seperti dalam analisis numerik, peneliti mungkin perlu menyesuaikan presisinya. Untuk mencapai peningkatan seperti itu, mereka mungkin harus mengkuadratkan waktu berjalan penurunan gradien, membuat perhitungannya benar-benar sulit.

“[Itu] mengerem apa yang [mereka] mungkin bisa lakukan,” kata Daskalakis. Mereka harus, dan dalam praktiknya, berkompromi di suatu tempat. Mereka menerima solusi yang kurang tepat, membatasi diri pada masalah yang sedikit lebih mudah, atau menemukan cara untuk mengelola runtime yang berat.

Tapi ini bukan untuk mengatakan bahwa algoritma cepat untuk penurunan gradien tidak ada. Itu mungkin. Tetapi hasilnya tidak berarti bahwa algoritma semacam itu akan segera menyiratkan keberadaan algoritma cepat untuk semua masalah lain di PLS int PPAD—bar yang jauh lebih tinggi daripada sekadar menemukan algoritma cepat untuk penurunan gradien itu sendiri. “Banyak masalah yang mungkin bisa dipecahkan oleh beberapa kemajuan dalam matematika,” kata Daskalakis. “Itulah mengapa kami ingin memiliki masalah yang sangat alami seperti penurunan gradien yang menangkap kompleksitas seluruh persimpangan.”