Al Rahimi baru-baru ini memberikan ceramah yang sangat provokatif di NIPS 2017 membandingkan Machine Learning saat ini dengan Alkimia. Salah satu klaimnya adalah bahwa kita perlu kembali ke perkembangan teoretis, untuk memiliki teorema sederhana yang membuktikan hasil dasar.
Ketika dia mengatakan itu, saya mulai mencari teorema utama untuk ML, tetapi tidak dapat menemukan referensi yang bagus yang masuk akal dari hasil utama. Jadi, inilah pertanyaan saya: apa teorema matematika utama saat ini (teori) dalam ML / DL dan apa yang mereka buktikan? Saya kira pekerjaan Vapnik akan pergi ke suatu tempat di sini. Sebagai tambahan, apa masalah utama teoretis terbuka?
machine-learning
deep-learning
theory
statlearner
sumber
sumber
Jawaban:
Seperti yang saya tulis di komentar, pertanyaan ini sepertinya terlalu luas bagi saya, tetapi saya akan berusaha menjawabnya. Untuk menetapkan beberapa batasan, saya akan mulai dengan sedikit matematika yang mendasari sebagian besar ML, dan kemudian berkonsentrasi pada hasil terbaru untuk DL.
The bias-varian tradeoff disebut dalam buku-buku yang tak terhitung jumlahnya, kursus, MOOCs, blog, tweet, dsb di ML, jadi kami tidak bisa memulai tanpa menyebutkan itu:
Bukti di sini: https://web.stanford.edu/~hastie/ElemStatLearn/
The Gauss-Markov Teorema (ya, regresi linear akan tetap merupakan bagian penting dari Machine Learning, tidak peduli apa: kesepakatan dengan itu) mengklarifikasi bahwa, ketika model linear adalah benar dan beberapa asumsi pada jangka error adalah valid, OLS memiliki minimum rata kuadrat error (yang dalam ekspresi di atas hanyalahBias2 + Variance ) hanya di kalangan berisi estimator linier dari model linear. Dengan demikian bisa jadi ada penduga linier dengan bias (atau penduga nonlinier) yang memiliki kesalahan kuadrat rata-rata yang lebih baik, dan dengan demikian kesalahan prediksi yang lebih baik, daripada OLS. Dan ini membuka jalan ke semua arsenal regularisasi (regresi ridge, LASSO, pembusukan berat badan, dll.) Yang merupakan pekerja keras dari ML. Bukti diberikan di sini (dan di banyak buku lain):
https://www.amazon.com/Linear-Statribution-Models-James-Stapleton/dp/0470231467
Mungkin lebih relevan dengan ledakan pendekatan regularisasi, seperti dicatat oleh Carlos Cinelli dalam komentar, dan pasti lebih menyenangkan untuk dipelajari, adalah teorema James-Stein . Pertimbangkann independen, varians yang sama tetapi tidak sama artinya variabel acak Gaussian:
dengan kata lain, kita memilikin− komponen Gaussian vektor acak . Kami memiliki satu sampel dari dan kami ingin memperkirakan . Penaksir MLE (dan juga UMVUE) jelas . Pertimbangkan estimator James-SteinX∼N(θ,σ2I) x X θ θ^MLE=x
Jelas, jika , menyusutkan estimasi MLE ke nol. The James-Stein teorema menyatakan bahwa untuk , ketat mendominasi , yaitu, memiliki MSE lebih rendah . Mungkin mengejutkan, bahkan jika kita menyusut terhadap konstanta , masih mendominasi . Karena(n−2)σ2≤||x||2 θ^JS n≥4 θ^JS θ^MLE ∀ θ c≠0 θ^JS θ^MLE Xi bersifat independen, mungkin tampak aneh bahwa, ketika mencoba memperkirakan ketinggian tiga orang yang tidak terkait, termasuk sampel dari jumlah apel yang diproduksi di Spanyol, dapat meningkatkan perkiraan kami secara rata-rata . Titik kunci di sini adalah "rata-rata": kesalahan kuadrat rata-rata untuk estimasi simultan semua komponen vektor parameter lebih kecil, tetapi kesalahan kuadrat untuk satu atau lebih komponen mungkin lebih besar, dan memang sering terjadi, ketika Anda memiliki pengamatan "ekstrim".
Menemukan bahwa MLE, yang memang merupakan penaksir "optimal" untuk kasus estimasi univariat, dicopot untuk estimasi multivariat, cukup mengejutkan pada saat itu, dan menyebabkan minat yang besar pada penyusutan, yang lebih dikenal sebagai regularisasi dalam bahasa ML. Orang bisa mencatat beberapa kesamaan dengan model campuran dan konsep "kekuatan meminjam": memang ada beberapa koneksi, seperti yang dibahas di sini
Pandangan terpadu tentang penyusutan: apa hubungan (jika ada) antara paradoks Stein, regresi ridge, dan efek acak dalam model campuran?
Referensi: James, W., Stein, C., Estimasi dengan Quadratic Loss . Prosiding Simposium Berkeley Keempat tentang Statistik Matematika dan Probabilitas, Volume 1: Kontribusi untuk Teori Statistik, 361--379, University of California Press, Berkeley, California, 1961
Analisis Komponen Utama adalah kunci untuk topik penting pengurangan dimensi, dan didasarkan pada Dekomposisi Nilai Singular : untuk setiap matriks nyata (meskipun teorema dengan mudah digeneralisasikan ke matriks kompleks) kita dapat menulisN×p X
di mana ukuran adalah ortogonal, adalah diagonal matriks dengan elemen diagonal nonnegatif dan ukuran lagi orthogonal. Untuk bukti dan algoritma tentang cara menghitungnya lihat: Golub, G., dan Van Loan, C. (1983), perhitungan Matrix , pers John Hopkins University, Baltimore.U N×p D p×p U p×p
Teorema Mercer adalah batu fondasi untuk banyak metode ML yang berbeda: spline pelat tipis, mesin vektor pendukung, perkiraan Kriging dari proses acak Gaussian, dll. Pada dasarnya, adalah salah satu dari dua teorema di balik apa yang disebut trik kernel . Misalkan menjadi fungsi atau kernel kontinu symmmetric. jika adalah semidefinit positif, maka ia mengakui basis ortornormal dari fungsi eigen yang sesuai dengan nilai eigen nonnegatif:K(x,y):[a,b]×[a,b]→R K
Pentingnya teorema ini untuk teori ML disaksikan oleh jumlah referensi yang didapatnya dalam teks-teks terkenal, seperti misalnya teks Rasmussen & Williams pada proses Gaussian .
Referensi: J. Mercer, Fungsi dari tipe positif dan negatif, dan hubungannya dengan teori persamaan integral. Transaksi filosofis dari Royal Society of London. Seri A, Berisi Makalah dari Karakter Matematika atau Fisik, 209: 415-446, 1909
Ada juga presentasi yang lebih sederhana di Konrad Jörgens, operator integral Linear , Pitman, Boston, 1982.
Teorema lain yang, bersama dengan teorema Mercer, menjabarkan fondasi teoretis dari trik kernel, adalah teorema representer . Misalkan Anda memiliki ruang sampel dan kernel semidefinit positif simetris . Juga membiarkan menjadi RKHS terkait dengan . Akhirnya, biarkan menjadi sampel pelatihan. Teorema mengatakan bahwa di antara semua fungsi , yang semuanya mengakui representasi tak terbatas dalam hal fungsi eigenX K:X×X→R HK K S={xi,yi}ni=1 f∈HK K karena teorema Mercer, yang meminimalkan risiko yang diregulasi selalu memiliki representasi terbatas dalam basis yang dibentuk oleh kernel yang dievaluasi pada poin pelatihan, yaitun
(teorema adalah persamaan terakhir). Referensi: Wahba, G. 1990, Model Spline untuk Data Observasional , SIAM, Philadelphia.
The pendekatan Teorema yang universal telah sudah dikutip oleh pengguna Tobias Windisch dan jauh lebih relevan dengan Machine Learning daripada untuk analisis fungsional, bahkan jika mungkin tidak tampak begitu pada pandangan pertama. Masalahnya adalah bahwa teorema hanya mengatakan bahwa jaringan semacam itu ada, tetapi:
Titik sakit yang lebih kecil dengan versi teorema Hornik adalah bahwa ia tidak berlaku untuk fungsi aktivasi ReLU. Namun, Bartlett sejak itu membuktikan versi yang diperluas yang mencakup celah ini.
Sampai sekarang, saya kira semua teorema yang saya anggap terkenal oleh siapa pun. Jadi sekarang saatnya untuk bersenang-senang :-) Mari kita lihat beberapa teorema Deep Learning :
Asumsi:
Kemudian:
Ini sangat menarik: CNN hanya terbuat dari lapisan konvolusional, ReLU, max-pooling, ReLU yang terhubung penuh dan lapisan linier adalah fungsi yang homogen secara positif , sementara jika kita memasukkan fungsi aktivasi sigmoid, ini tidak benar lagi, yang sebagian dapat menjelaskan superior kinerja dalam beberapa aplikasi ReLU + max pooling sehubungan dengan sigmoids. Terlebih lagi, teorema hanya berlaku jika juga secara positif homogen dalam derajat yang sama dengan . Sekarang, menyenangkan fakta adalah bahwa atau regularisasi, meskipun positif homogen, tidak memiliki derajat yang sama (derajatΘ W Φ l1 l2 Φ Φ , dalam kasus CNN sederhana yang disebutkan sebelumnya, meningkat dengan jumlah lapisan). Sebaliknya, metode regularisasi yang lebih modern seperti normalisasi batch dan path-SGD memang sesuai dengan fungsi regularisasi yang homogen secara positif dengan derajat yang sama dengan , dan dropout, yang tidak sesuai dengan kerangka kerja ini, memiliki kemiripan yang kuat. Hal ini mungkin menjelaskan mengapa, dalam rangka untuk mendapatkan akurasi yang tinggi dengan CNNs, dan regularisasi tidak cukup, tetapi kita perlu untuk mempekerjakan segala macam trik jahat, seperti putus sekolah dan angkatan normalisasi! Sepengetahuan saya, ini adalah hal yang paling dekat dengan penjelasan tentang kemanjuran normalisasi batch, yang sebaliknya sangat tidak jelas, sebagaimana dicatat oleh Al Rahimi dalam ceramahnya.Φ l1 l2
Pengamatan lain yang dilakukan beberapa orang, berdasarkan Teorema 1 , adalah bahwa ia dapat menjelaskan mengapa ReLU bekerja dengan baik, bahkan dengan masalah neuron mati . Menurut intuisi ini, fakta bahwa, selama pelatihan, beberapa neuron ReLU "mati" (pergi ke nol aktivasi dan kemudian tidak pernah pulih dari itu, karena untuk gradien ReLU adalah nol) adalah "fitur, bukan bug ", karena jika kita telah mencapai minimum dan subnetwork penuh telah mati, maka kita terbukti mencapai minimum global (di bawah hipotesis Teorema 1x<0 ). Saya mungkin kehilangan sesuatu, tetapi saya pikir interpretasi ini terlalu jauh. Pertama-tama, selama pelatihan, ReLU dapat "mati" dengan baik sebelum kita mencapai minimun lokal. Kedua, harus dibuktikan bahwa ketika unit ReLU "mati", mereka selalu melakukannya melalui subnetwork penuh: satu-satunya kasus di mana ini sepele benar adalah ketika Anda hanya memiliki satu lapisan tersembunyi, dalam hal ini tentu saja setiap neuron tunggal adalah sebuah subnetwork. Tetapi secara umum saya akan sangat berhati-hati dalam melihat "neuron mati" sebagai hal yang baik.
Referensi:
B. Haeffele dan R. Vidal, Optimalitas global dalam pelatihan jaringan saraf , Dalam Konferensi IEEE tentang Visi Komputer dan Pengenalan Pola, 2017.
B. Haeffele dan R. Vidal. Optimalitas global dalam faktorisasi tensor, pembelajaran dalam, dan di luar , arXiv, abs / 1506.07540, 2015.
Klasifikasi gambar memerlukan representasi pembelajaran yang tidak berubah-ubah (atau setidaknya kuat, yaitu, sangat peka lemah) terhadap berbagai transformasi seperti lokasi, pose, sudut pandang, pencahayaan, ekspresi, dll. Yang umumnya ada dalam gambar alami, tetapi tidak mengandung info untuk tugas klasifikasi. Hal yang sama untuk pengenalan suara: perubahan nada, volume, kecepatan, aksen. dll. tidak boleh mengarah pada perubahan klasifikasi kata. Operasi seperti konvolusi, penyatuan maks, penyatuan rata-rata, dll., Yang digunakan dalam CNN, memiliki tujuan yang persis seperti ini, jadi secara intuitif kami berharap mereka akan bekerja untuk aplikasi ini. Tetapi apakah kita memiliki teorema untuk mendukung intuisi ini? Ada teorema invarian terjemahan vertikal, yang, terlepas dari namanya, tidak ada hubungannya dengan terjemahan dalam arah vertikal, tetapi pada dasarnya ini adalah hasil yang mengatakan bahwa fitur yang dipelajari dalam lapisan berikut semakin banyak berubah, seiring dengan meningkatnya jumlah lapisan. Ini bertentangan dengan teorema invarians terjemahan horizontal yang lebih lama yang berlaku untuk jaringan yang tersebar, tetapi tidak untuk CNN. Teorema ini sangat teknis, namun:
Tunjukkan dengan output layer dari CNN, ketika inputnya . Lalu akhirnya:Φn(f) n f
(Bilah tripel bukan kesalahan) yang pada dasarnya berarti bahwa setiap lapisan mempelajari fitur yang menjadi lebih dan lebih invarian, dan dalam batas jaringan yang sangat jauh kita memiliki arsitektur yang sangat invarian. Karena CNN memiliki jumlah lapisan yang terbatas, mereka bukan terjemahan-invarian yang sempurna, yang merupakan sesuatu yang terkenal bagi para praktisi.
Referensi: T. Wiatowski dan H. Bolcskei, Teori Matematika Jaringan Syaraf Konvolusional Dalam untuk Ekstraksi Fitur , arXiv: 1512.06293v3 .
Untuk menyimpulkan, banyak batasan untuk kesalahan generalisasi dari Deep Neural Network berdasarkan dimensi Vapnik-Chervonkensis atau pada kompleksitas Rademacher tumbuh dengan jumlah parameter (beberapa bahkan secara eksponensial), yang berarti mereka tidak dapat menjelaskan mengapa DNN bekerja dengan sangat baik. dalam praktiknya bahkan ketika jumlah parameter jauh lebih besar dari jumlah sampel pelatihan. Faktanya, teori VC tidak terlalu berguna dalam Deep Learning.
Sebaliknya, beberapa hasil dari tahun lalu mengikat kesalahan generalisasi dari pengklasifikasi DNN dengan kuantitas yang tidak tergantung pada kedalaman dan ukuran jaringan saraf, tetapi hanya bergantung pada struktur set pelatihan dan ruang input. Di bawah beberapa asumsi teknis yang cukup pada prosedur pembelajaran, dan pada set pelatihan dan ruang input, tetapi dengan asumsi yang sangat sedikit pada DNN (khususnya, CNN tercakup sepenuhnya), kemudian dengan probabilitas setidaknya , kami memiliki1−δ
dimana:
J. Sokolic, R. Giryes, G. Sapiro, dan M. Rodrigues. Kesalahan generalisasi dari pengklasifikasi invarian . Di AISTATS, 2017
sumber
See [here] for a modern exposition
, atau sebaliknya, "untuk kertas asli".Saya pikir teorema berikut yang Anda singgung dianggap cukup mendasar dalam pembelajaran statistik.
Teorema (Vapnik dan Chervonenkis, 1971) Misalkan adalah kelas fungsi hipotesis dari domain ke dan biarkan fungsi kerugian menjadi kerugian . Kemudian, yang berikut ini setara:H X {0,1} 0−1
Terbukti dalam versi kuantitatif di sini:
VN Vapnik dan AY Chervonenkis: Pada konvergensi frekuensi kejadian relatif yang seragam dengan probabilitasnya. Teori Probabilitas dan Penerapannya, 16 (2): 264–280, 1971.
Versi yang dirumuskan di atas bersama dengan paparan yang bagus dari hasil lain dari teori belajar tersedia di sini :
Shalev-Shwartz, Shai, dan Shai Ben-David. Memahami pembelajaran mesin: Dari teori ke algoritma. Pers universitas Cambridge, 2014.
sumber
Trik Kernel adalah ide umum yang digunakan di banyak tempat, dan berasal dari banyak matematika abstrak tentang Hilbert Spaces. Terlalu banyak teori bagi saya untuk mengetik (menyalin ...) menjadi jawaban di sini, tetapi jika Anda membaca sekilas ini, Anda bisa mendapatkan ide bagus tentang dasar-dasarnya yang keras:
http://www.stats.ox.ac.uk/~sejdinov/teaching/atml14/Theory_2014.pdf
sumber
Favorit saya adalah ketimpangan Kraft.
Ketidaksetaraan ini berkaitan kompresi dengan kepadatan probabilitas : diberi kode, panjang hasil yang diwakili oleh kode itu adalah probabilitas log negatif dari model yang diidentifikasi oleh kode.
Lebih jauh, teorema makan siang gratis untuk pembelajaran mesin memiliki saudara yang kurang dikenal yaitu teorema tanpa kompresi hiper, yang menyatakan bahwa tidak semua urutan dapat dikompresi.
sumber
Saya tidak akan menyebutnya teorema utama , tetapi saya pikir yang berikut (kadang-kadang disebut sebagai teorema aproksimasi Universal) adalah yang menarik (dan setidaknya bagi saya mengejutkan) karena menyatakan kekuatan aproksimasi dari jaringan saraf umpan maju.
Teorema: Misalkan menjadi fungsi kontinu yang tidak konstan dan meningkat secara monoton. Untuk fungsi fungsi berkelanjutan dan sembarang , terdapat integer dan multeparter perceptron dengan satu lapisan tersembunyi memiliki Neuron yang memiliki sebagai aktivasi berfungsi agarσ f:[0,1]m→R ϵ>0 N F N σ
Tentu saja, karena ini adalah pernyataan tentang keberadaan , dampaknya bagi para praktisi dapat diabaikan.
Bukti dapat ditemukan di Hornik, Kemampuan Aproksimasi Jaringan Feedforward Muitilayer, Neural Networks 4 (2), 1991,
sumber
Posting yang bagus berfokus pada pertanyaan ini (khususnya pembelajaran mendalam daripada teorema pembelajaran mesin umum) ada di sini:
https://medium.com/mlreview/modern-theory-of-deep-learning-why-does-it-works-so-well-9ee1f7fb2808
Ini memberikan ringkasan yang dapat diakses dari teorema utama yang muncul untuk kemampuan jaringan saraf yang dalam untuk menggeneralisasi dengan baik.
sumber