Mengapa mempelajari optimasi cembung untuk pembelajaran mesin teoretis?

27

Saya sedang mengerjakan pembelajaran mesin teoretis - pembelajaran transfer, untuk lebih spesifik - untuk Ph.D.

  • Karena penasaran, mengapa saya harus mengikuti kursus tentang optimasi cembung?

  • Apa kesimpulan dari optimasi cembung yang dapat saya gunakan dalam penelitian saya tentang pembelajaran mesin teoretis?

Upendra Pratap Singh
sumber
2
Tidak jelas apakah Anda keberatan dengan bagian cembung, bagian pengoptimalan, atau keduanya.
Mehrdad
Perhatikan bahwa jawaban yang Anda terima jelas salah. Mungkin Anda bisa melihat pertanyaan ini lagi dan memilih jawaban yang jauh lebih masuk akal.
xji
Convex Optimization dan Math Optimization adalah alat untuk membangun model - teknik ini digunakan untuk membangun model / melakukan kontrol / mencari parameter dari fenomena yang dapat dimengerti hingga beberapa ketidakpastian.
bruziuz
Machine Learning adalah tentang membangun perkiraan fungsi seperti metode penghitungan, dan sejauh yang Anda ketahui salah satu fungsi pilih konsep yang kira-kira meminimalkan kerugian (yang non-cembung atau bahkan terburuk termasuk variabel indikator), jadi ML bermain bagus dengan optimasi non-cembung.
bruziuz
FYI "Optimasi cembung tidak dapat digunakan untuk pembelajaran mendalam - S.Boyd" - youtu.be/uF3htLwUHn0?t=2810
bruziuz

Jawaban:

60

Algoritma pembelajaran mesin menggunakan optimisasi setiap saat. Kami meminimalkan kehilangan, atau kesalahan, atau memaksimalkan semacam fungsi skor. Gradient descent adalah algoritma optimisasi "hello world" yang tercakup dalam semua kursus pembelajaran mesin. Jelas dalam kasus regresi, atau model klasifikasi, tetapi bahkan dengan tugas-tugas seperti pengelompokan, kami mencari solusi yang secara optimal sesuai dengan data kami (mis. K-means meminimalkan jumlah kuadrat dalam-klaster). Jadi, jika Anda ingin memahami bagaimana algoritma pembelajaran mesin bekerja, belajar lebih banyak tentang optimasi membantu. Selain itu, jika Anda perlu melakukan hal-hal seperti penyetelan hyperparameter, maka Anda juga langsung menggunakan optimasi.

Orang dapat berargumen bahwa optimasi cembung seharusnya tidak begitu menarik untuk pembelajaran mesin karena alih-alih berurusan dengan fungsi cembung , kita sering menghadapi permukaan kehilangan seperti yang di bawah ini, yang jauh dari cembung .

Contoh lanskap kehilangan nyata dan non-cembung.

(sumber: https://www.cs.umd.edu/~tomg/projects/landscapes/ dan arXiv: 1712.09913 )

Meskipun demikian, seperti yang disebutkan dalam jawaban lain, optimisasi cembung lebih cepat, lebih sederhana dan kurang intensif secara komputasional, sehingga seringkali lebih mudah untuk "mengembungkan" masalah (membuatnya ramah optimasi cembung), kemudian menggunakan optimasi non-cembung. Sebagai contoh, gradient descent dan alike algoritme umumnya digunakan dalam pembelajaran mesin, terutama untuk jaringan saraf, karena mereka "bekerja", berskala, dan secara luas diimplementasikan dalam perangkat lunak yang berbeda, namun mereka bukan yang terbaik yang bisa kita dapatkan dan memiliki perangkap mereka , seperti yang dibahas oleh ceramah Ali Rahimi di NIPS 2017 .

Di sisi lain, algoritma optimasi non-cembung seperti algoritma evolusioner tampaknya mendapatkan pengakuan yang lebih dan lebih dalam komunitas ML, misalnya pelatihan jaringan saraf dengan neuroevolution tampaknya menjadi topik penelitian terbaru (lihat juga arXiv: 1712.07897 ).

Tim
sumber
5
jawaban ini sepertinya tidak membahas "cembung"
Haitao Du
@ hxd1011 Saya mengomentarinya.
Tim
Jawaban bagus! Benar-benar membahas betapa pentingnya optimasi untuk ML, dan bagaimana ML menyederhanakan dengan menggunakan perkiraan cembung yang bekerja dengan gradient descent.
ChuckCottrill
Ini harus menjadi jawaban yang diterima.
Jan Kukacka
11

Saya pikir ada dua pertanyaan di sini.

  • Mengapa mempelajari pengoptimalan
  • Mengapa optimasi cembung

Saya pikir @Tim memiliki jawaban yang bagus tentang mengapa optimasi. Saya sangat setuju dan akan merekomendasikan siapa pun yang tertarik dalam pembelajaran mesin untuk menguasai optimasi berkelanjutan. Karena proses optimasi / mencari solusi yang lebih baik dari waktu ke waktu, adalah proses pembelajaran untuk komputer.

Saya ingin berbicara lebih banyak tentang mengapa kami tertarik pada fungsi cembung. Alasannya sederhana: optimasi cembung adalah "lebih mudah untuk diselesaikan", dan kami memiliki banyak algoritma andal untuk dipecahkan.

Tetapi apakah dunia ini cembung? Tidak. Kenapa terobsesi dengan cembung? Periksa metafora ini

Seorang polisi melihat seorang lelaki mabuk sedang mencari sesuatu di bawah lampu jalan dan menanyakan apa yang telah hilang dari si mabuk. Dia bilang dia kehilangan kuncinya dan mereka berdua melihat di bawah lampu jalan bersama. Setelah beberapa menit, polisi itu bertanya apakah dia yakin dia kehilangan mereka di sini, dan si pemabuk menjawab, tidak, dan bahwa dia kehilangan mereka di taman. Polisi itu bertanya mengapa dia mencari di sini, dan si pemabuk menjawab, "di sinilah cahayanya".

Haitao Du
sumber
2
Tapi secara metaforis, itu sebabnya Anda mendapatkan senter. Mencari kunci dalam gelap sulit untuk dilakukan, jadi Anda mengadaptasinya menjadi masalah yang Anda tahu cara mengatasinya. Jika Anda mengerjakan masalah dengan algoritma non-cembung dan menghasilkan solusi yang akan menelan biaya 3 juta dolar, dan saya bekerja dengan masalah yang sama dengan optimasi cembung dan mengambil jawaban saya dan menemukan solusi untuk masalah non-cembung yang harganya 2 juta dolar, saya telah menemukan jawaban yang lebih baik.
prosfilaes
Jawaban ini cacat pada banyak tingkatan. Membandingkan analisis cembung dengan efek lampu jalan memang salah . Saya akan menyarankan Anda untuk merujuk ke buku teks pengantar Convex Optimization oleh Boyd dan Vandenberghe untuk mempelajari lebih lanjut tentang topik tersebut.
Digio
2

Yang paling penting adalah bahwa pembelajaran mesin diterapkan untuk masalah di mana tidak ada solusi optimal yang tersedia. Yang terbaik yang dapat Anda lakukan adalah menemukan perkiraan yang baik.

Sebaliknya, ketika Anda memiliki masalah optimasi, ada solusi optimal, tetapi biasanya tidak dapat ditemukan dalam waktu yang wajar atau dengan kekuatan pemrosesan yang masuk akal.

Alat dan algoritma yang Anda gunakan pada dasarnya berbeda. Jadi, sementara saya akan mengatakan bahwa tidak ada manfaat langsung dari mengambil kelas optimisasi, selalu baik untuk mengetahui sedikit tentang bidang terkait. Jika Anda dapat mengenali masalah pengoptimalan, Anda akan tahu bahwa Anda tidak harus mengatasinya dengan algoritma pembelajaran mesin melainkan dengan algoritma pengoptimalan. Itu saja bernilai banyak, menurut saya.

Toby
sumber
33
Ya, dalam pembelajaran mesin kami mencari perkiraan terbaik. Tetapi Anda salah dengan mengatakan bahwa kedua hal itu "berbeda secara mendasar". Algoritma ML menggunakan optimasi untuk meminimalkan fungsi kerugian dan menemukan parameter optimal yang diberikan data dan tujuan. Saat Anda menyetel hyperparameter Anda, Anda mencari kombinasi optimal dari mereka. Dalam setiap kasus, Anda memaksimalkan atau meminimalkan sesuatu untuk mencapai tujuan Anda, jadi Anda menggunakan beberapa jenis optimasi.
Tim
@Tim: Benar, saya seharusnya mengutarakannya secara berbeda.
Toby
17
jika Anda setuju, maka Anda mungkin harus mengulanginya.
Tim
19
Jawaban ini jelas salah. Sejumlah besar masalah pembelajaran mesin bermuara pada masalah optimisasi.
Pasang kembali Monica
2
Klaim bahwa dalam "masalah pengoptimalan, solusi optimal biasanya tidak dapat ditemukan" salah. Khususnya dalam konteks optimasi cembung (yang ditanyakan oleh OP), solusi optimal dapat dengan mudah ditemukan (misalnya penurunan gradien dengan tingkat pembelajaran yang membusuk dijamin akan menyatu dengan fungsi fungsi cembung yang optimal). Masalah besar adalah bahwa banyak masalah dalam pembelajaran mesin adalah non-cembung .
Jan Kukacka
2

Seperti yang dikatakan hxd1011, masalah cembung lebih mudah dipecahkan, baik secara teoritis maupun (biasanya) dalam praktiknya. Jadi, bahkan untuk masalah non-cembung, banyak algoritma optimasi dimulai dengan "langkah 1. mengurangi masalah menjadi satu cembung" (mungkin di dalam loop sementara).

Hal serupa terjadi dengan pencarian akar nonlinier. Biasanya solusinya (misalnya, dengan metode Newton) berbunyi "langkah 1. Mengurangi masalah linear, karena kita tahu bagaimana menyelesaikannya".

Federico Poloni
sumber
1

Jika minat Anda terletak pada optimasi (cembung) yang diterapkan pada pembelajaran dalam (Anda menyebutkan transfer pembelajaran, yang banyak digunakan dalam praktik dengan jaringan saraf) aplikasi, saya sangat menyarankan Anda untuk mempertimbangkan membaca bab 8 (optimasi untuk pelatihan jaringan saraf dalam) dari http : //www.deeplearningbook.org/

Ada diskusi tentang optimasi cembung, dan mengapa itu belum begitu sukses ketika diterapkan jaringan saraf yang dalam. Tentu saja, mungkin Anda bisa melakukan riset di bidang ini yang akan mengubah konsensus saat ini!

FXQuantTrader
sumber
0

Seperti yang saya dengar dari Jerome H. Friedman metode yang dikembangkan dalam Machine Learning sebenarnya bukan milik komunitas Machine Learning dengan sendirinya.

Dari sudut pandang saya Machine Learning lebih mirip kumpulan berbagai metode dari bidang lain.

Dari sudut pandang Pembelajaran Statistik, tiga pertanyaan utama untuk regresi dan klasifikasi adalah:

  1. Apa fungsi keluarga dari mana Anda menarik aproksimasi

  2. Apa kriteria bagaimana Anda menarik suatu fungsi

  3. Apa metode untuk menemukan fungsi terbaik


Untuk beroperasi dengan cara konstruktif pada (1) - tidak begitu jelas bagaimana menggunakan optimisasi matematika dapat membantu

Untuk beroperasi dengan cara konstruktif pada (2) - sudah jelas bahwa tujuan adalah tujuannya. Dan optimisasi matematika dapat membantu.

Untuk beroperasi dengan beberapa cara konstruktif pada (3) - Anda perlu optimisasi matematika.


Ada beberapa bagian optimasi matematika:

  1. Optimasi Cembung / Analisis Cembung - area matematika yang sangat keren. Non-diferensiasi bukan masalah. Dan ada 50 generalisasi fungsi cembung dari mana lebih banyak berguna dalam hal aplikasi adalah quasiconvex dan log-cekung.

Juga ada cara bagaimana menangani "stochasticity" dalam beberapa cara, bahkan "Tidak ada yang tahu bagaimana menyelesaikan optimasi cembung stochastic"

  1. NonConvex Optimization - biasanya orang dengan ini berarti sesuatu yang objektif, tetapi kelengkungan dapat bervariasi. Orang-orang di planet ini tidak tahu bagaimana menyelesaikannya dengan tepat. Dan pada kenyataannya semua mehtod membuat leverage menjadi (1)

  2. Optimalisasi kombinatorial - bahkan lebih liar daripada (2), sekarang untuk parameter yang Anda temukan Anda bahkan tidak dapat menerapkan operator minus. Salah satu contoh adalah "daerah" di Pohon Keputusan. Jadi ada dua cara bagaimana menghadapinya: a) Convexify problem dan gunakan metode dari (1) b) Buat brute force. Tidak berfungsi untuk sejumlah besar parameter. c) Buat kekuatan kasar tetapi dengan beberapa langkah serakah. Itu adalah sesuatu yang dilakukan CART.


Jadi setidaknya saya pikir saya memberi tahu Anda bahwa:

I) Optimasi Cembung adalah hal utama untuk sebagian besar masalah optimisasi.

II) "01:15 Optimalisasi sebenarnya subjek yang lebih besar daripada ML atau AI, tetapi sebenarnya subjek yang lebih besar." ( https://www.youtube.com/watch?v=uF3htLwUHn0&t=992s )

bruziuz
sumber
Ini sedikit singkat berdasarkan standar situs ini sebagai jawaban - apakah Anda pikir Anda dapat mengembangkannya? Kalau tidak, itu mungkin paling cocok sebagai komentar.
Silverfish
Baik. Saya akan memperluas, tetapi sebenarnya mungkin untuk menulis artikel tentang koneksi dengan berbagai bidang. Sebenarnya saya bertanya kepada Stephen P. Boyd tentang pertanyaan yang berkaitan dengan apa yang dipikirkan orang sebelumnya dan kapan - youtu.be/XV1E-Jnc4SU?t=242 . Dia mengatakan bahwa hari ini dunia telah retak.
bruziuz
1
@Silverfish Saya perbarui, sekarang teks panjang bukan satu kalimat.
bruziuz