Mengoptimalkan Algoritma Optimasi

Algoritma optimasi, mencoba untuk menemukan nilai-nilai minimum fungsi matematika. Antara lain, digunakan untuk mengevaluasi kompromi desain, untuk menilai sistem kontrol, dan untuk menemukan pola dalam data.

Gambaran penerapan masalah computer vision ke dunia nyata. Solusi untuk setiap masalah (bola merah) digunakan untuk menginisialisasi (panah hijau) solusi.

Salah satu cara untuk memecahkan masalah optimasi yang sulit adalah mengubah masalah terkait menjadi jauh lebih sederhana, kemudian secara bertahap menambah kompleksitas, memecahkan setiap masalah baru dan menggunakan solusi sebagai panduan untuk memecahkan berikutnya. Pendekatan ini bekerja dengan baik dalam praktek, tapi tidak pernah ditandai secara teoritis.

Bulan ini, Computer Vision and Pattern Recognition dalam International Conference on Energy Minimization Methods, Hossein Mobahi, Postdoc di MIT Computer Science and Artificial Intelligence Laboratory (CSAIL), dan John Fisher, seorang ilmuwan riset senior di CSAIL, menjelaskan cara untuk menghasilkan urutan fungsi disederhanakan yang menjamin pendekatan terbaik yang dapat ditawarkan metode ini.

"Ada beberapa pertanyaan mendasar tentang metode ini yang kita jawab untuk pertama kalinya," kata Mobahi. "Misalnya, saya memberikan anda mulai dari masalah yang sederhana, tapi saya tidak memberitahu anda bagaimana anda memilih masalah yang sederhana. Ada banyak fungsi yang dapat anda gunakan. Mana yang baik? Bahkan jika saya memberitahu anda apa fungsi untuk digunakan, ada banyak cara untuk mengubah masalah anda yang sebenarnya. Dan transformasi mempengaruhi apa yang anda dapatkan di akhir. "

Bottoming Out

Untuk mengetahui bagaimana optimasi bekerja, anggaplah bahwa anda seorang pengecer kaleng makanan dan ingin menyimpan uang, anda ingin desain yang dapat meminimalkan rasio luas permukaan dengan volume. Rasio merupakan fungsi dari ketinggian kaleng dan jari-jari, jadi jika anda dapat menemukan nilai minimum fungsi, anda akan tahu dimensi optimal kaleng itu. Jika anda seorang desainer mobil mencoba untuk menyeimbangkan biaya komponen yang terbuat dari bahan yang berbeda dengan berat dan hambatan angin mobil, fungsi yang dikenal dalam optimasi adalah "fungsi biaya" - akan jauh lebih kompleks, tetapi prinsipnya adalah sama.

Algoritma Machine-Learning berusaha untuk mengidentifikasi set data yang berguna untuk klasifikasi tugas, fitur visual karakteristik mobil. Mencari set terkecil dengan nilai prediksi terbesar merupakan masalah optimasi.

"Sebagian besar algoritma yang efisien yang kita miliki untuk memecahkan tugas optimasi bekerja berdasarkan pencarian lokal, yang berarti anda menginisialisasi dengan menebak solusi, dan mencoba untuk melihat ke arah mana dapat ditingkatkan, kemudian mengambil langkah, "kata Mobahi. "Dengan menggunakan teknik ini, mereka bisa berkumpul untuk sesuatu yang disebut minimum lokal, yang berarti titik yang dibandingkan dengan lingkungan yang lebih rendah. Tapi mungkin tidak menjadi minimum global. Mungkin ada titik yang jauh lebih rendah, tetapi lebih jauh."

Minimum lokal dijamin akan minimum global, namun, jika fungsi cembung. Fungsi y = x² adalah cembung, karena menggambarkan parabola berpusat pada titik asal. Fungsi y = sin x tidak, karena menggambarkan gelombang sinus yang bergelombang atas dan ke bawah.

Smooth Sailing

Metode Mobahi dan Fisher dimulai dengan mencoba untuk menemukan pendekatan cembung, menggunakan teknik yang disebut Gaussian Smoothing. Gaussian Smoothing mengubah fungsi biaya ke fungsi terkait yang memberikan nilai tidak ke fungsi biaya. Hal ini memiliki efek merapikan setiap dips atau ascents di grafik fungsi biaya.

Bobot ditentukan oleh fungsi Gaussian, atau distribusi normal - bell curve dari statistik dasar. Nilai terdekat lebih ke arah rata-rata dari nilai-nilai yang jauh.

Lebar fungsi Gaussian ditentukan oleh satu parameter. Mobahi dan Fisher dimulai dengan Gaussian yang sangat luas, yang, dalam kondisi tertentu, menghasilkan fungsi cembung. Kemudian mereka terus kontraksi lebar Gaussian, menghasilkan serangkaian masalah perantara. Pada setiap tahap, mereka menggunakan solusi untuk masalah terakhir untuk menginisialisasi solusi untuk yang berikutnya. Pada saat lebar distribusi telah menyusut ke nol, mereka menjadi fungsi biaya, karena setiap nilai hanya rata-rata itu sendiri.