Apa teorema utama dalam Machine (Deep) Learning?

45

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?

statlearner
sumber
3
@Tim Tead ini sejenis dengan stats.stackexchange.com/questions/2379/… ("Apa masalah besar dalam statistik?").
whuber
2
Ini agak luas. Bisakah Anda setidaknya menentukan subset dari Pembelajaran Mesin? Jika kita membatasi diri pada Pembelajaran Dalam, atau setidaknya untuk pembelajaran yang diawasi, seseorang dapat mencoba jawaban. Tetapi jika Anda bersikeras pada sesuatu seperti "Matematika Pembelajaran Mesin", sebuah jawaban akan membutuhkan waktu lama untuk menulis.
DeltaIV
3
Sehubungan dengan contoh analog @ whuber, saya cenderung mengatakan ini harus tetap terbuka sebagai CW, terutama jika ini dapat terbatas pada subset spesifik ML, seperti pembelajaran yang diawasi , seperti yang diminta DeltaV.
gung - Reinstate Monica
3
@DeltaIV Perhatikan bahwa "Jauh" ada dalam judul.
Amuba mengatakan Reinstate Monica
4
Memahami pertanyaan ini adalah topik dari serangkaian kuliah terbaru yang dipandu oleh David Donoho: lihat stats385.github.io .
user795305

Jawaban:

43

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:

E[(Yf^(X))2|X=x0]=σϵ2+(Ef^(x0)f(x0))2+E[(f^(x0)Ef^(x0))2]=Irreducible error + Bias2 + Variance

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 hanyalah Bias2 + 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 . Pertimbangkan n independen, varians yang sama tetapi tidak sama artinya variabel acak Gaussian:

Xi|μiN(θi,σ2),i=1,,n

dengan kata lain, kita memiliki n komponen Gaussian vektor acak . Kami memiliki satu sampel dari dan kami ingin memperkirakan . Penaksir MLE (dan juga UMVUE) jelas . Pertimbangkan estimator James-SteinXN(θ,σ2I)xXθθ^MLE=x

θ^JS=(1(n2)σ2||x||2)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(n2)σ2||x||2θ^JS n4θ^JS θ^MLE θc0θ^JSθ^MLEXibersifat 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×pX

X=UDVT

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.UN×pDp×pUp×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]RK

K(x,y)=i=1γiϕi(x)ϕi(y)

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 eigenXK:X×XRHKKS={xi,yi}i=1nfHKKkarena teorema Mercer, yang meminimalkan risiko yang diregulasi selalu memiliki representasi terbatas dalam basis yang dibentuk oleh kernel yang dievaluasi pada poin pelatihan, yaitun

minfHKi=1nL(yi,f(xi))+λ||f||HK2=min{cj}1i=1nL(yi,jcjϕj(xi))+λjcj2γj=i=1nαiK(x,xi)

(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:

  • itu tidak memberikan korelasi antara ukuran dari layer tersembunyi dan beberapa ukuran kompleksitas dari fungsi target , seperti misalnya Total Variasi. Jika dan diperlukan untuk kesalahan tetap tumbuh secara eksponensial dengan , maka satu lapisan neural tersembunyi jaringan tidak akan berguna.Nf(x)f(x)=sin(ωx):[0,2π][1,1]Nϵω
  • ia tidak mengatakan apakah jaringan dapat dipelajari . Dengan kata lain asumsikan bahwa diberikan dan , kita tahu bahwa ukuran NN akan mendekati dengan toleransi yang diperlukan dalam hypercube. Kemudian dengan menggunakan set pelatihan ukuran dan prosedur pembelajaran seperti misalnya back-prop, apakah kita memiliki jaminan bahwa dengan meningkatkan kita dapat memulihkan ?F(x)fϵNfMMF
  • akhirnya, dan lebih buruk dari semuanya, itu tidak mengatakan apa-apa tentang kesalahan prediksi jaringan saraf. Apa yang kita benar-benar tertarik adalah perkiraan kesalahan prediksi, setidaknya rata-rata seluruh set pelatihan dari ukuran . Teorema tidak membantu dalam hal ini.M

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:

  • deep neural network (untuk fixed , adalah fungsi yang mengaitkan input dari jaringan neural dengan outputnya) dan kerugian regularisasi keduanya merupakan jumlah positif fungsi homogen dengan derajat yang samaΦ(X,W)WΦW(X)Θ(W)
  • fungsi kerugian adalah cembung dan sekali dapat dibedakan dalam , dalam himpunan kompakL(Y,Φ(X,W)XS

Kemudian:

  • minimum lokal apa pun untuk sedemikian rupa sehingga subnetwork dari memiliki bobot nol, adalah minimum global ( Teorema 1 )L(Y,Φ(X,W))+λΘ(W)Φ(X,W)
  • di atas ukuran jaringan kritis, keturunan lokal akan selalu konvergen ke minimum global dari inisialisasi apa pun ( Teorema 2 ).

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Φl1l2ΦΦ, 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.Φl1l2

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:

  • anggap (gambar input Anda) adalah persegi-integrablef
  • anggap filter Anda bepergian dengan operator terjemahan , yang memetakan gambar input ke salinan terjemahannya sendiri . Kernel konvolusi (filter) yang dipelajari memenuhi hipotesis ini.TtfTtf
  • anggap semua filter, nonlinier, dan penyatuan dalam jaringan Anda memenuhi apa yang disebut kondisi penerimaan yang lemah , yang pada dasarnya adalah semacam keteraturan yang lemah dan kondisi batasan. Kondisi ini dipenuhi oleh kernel konvolusi terpelajar (selama beberapa operasi normalisasi dilakukan pada setiap lapisan), ReLU, sigmoid, tanh, dll, nonlinier, dan dengan pooling rata-rata, tetapi tidak dengan max-pooling. Jadi itu mencakup beberapa (tidak semua) arsitektur CNN dunia nyata.
  • Asumsikan akhirnya bahwa setiap lapisan memiliki faktor penyatuan , yaitu, penyatuan diterapkan pada setiap lapisan dan secara efektif membuang informasi. Kondisi juga cukup untuk versi teorema yang lebih lemah.nSn>1Sn1

Tunjukkan dengan output layer dari CNN, ketika inputnya . Lalu akhirnya:Φn(f)nf

limn|||Φn(Tff)Φn(f)|||=0

(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δ

GE2log2NyNγm+2log(1/δ)m

dimana:

  • GE adalah kesalahan generalisasi, yang didefinisikan sebagai perbedaan antara kerugian yang diharapkan (kerugian rata-rata classifier yang dipelajari pada semua titik uji yang mungkin) dan kerugian empiris (hanya kesalahan set pelatihan yang baik)
  • Ny adalah jumlah kelas
  • m adalah ukuran set pelatihan
  • Nγ adalah jumlah yang meliputi data, jumlah yang terkait dengan struktur ruang input dan dengan pemisahan minimal antara titik-titik kelas yang berbeda dalam set pelatihan. Referensi:

J. Sokolic, R. Giryes, G. Sapiro, dan M. Rodrigues. Kesalahan generalisasi dari pengklasifikasi invarian . Di AISTATS, 2017

DeltaIV
sumber
2
+1. Jawaban yang bagus, bagian terakhir sangat menarik. Pada bagian pertama, teorema Mercer terlihat seperti SVD yang Anda sajikan di atas.
Amoeba berkata Reinstate Monica
1
@amoeba, Anda benar, tetapi 1) tidak semua pembaca sama matematika-nya dengan Anda, sehingga mereka akan segera mengenali kesamaan antara SVD, ekspansi Karhunen-Loeve dan teorema Mercer. Juga 2) teorema lain dari Analisis Fungsional yang "memberdayakan" trik kernel, dan yang saya pilih untuk tidak dimasukkan, lebih sulit dijelaskan daripada teorema Mercer, dan saya sudah merusak hari Sabtu saya :-) Mungkin saya akan menambahkannya besok!
DeltaIV
1
Gauss Markov tampaknya tidak pada tempatnya, tidak pernah melihat orang peduli tentang BIRU di komunitas ML.
Carlos Cinelli
2
Saya setuju bahwa sebagai aturan umum referensi asli (kuno) biasanya memiliki notasi yang membosankan. Yang mengatakan, makalah Mercer sebenarnya mengejutkan modern dalam aspek itu dan saya menambahkannya justru karena itu. :) (Saya katakan pada awalnya, ini jawaban yang sangat bagus, ini hanya komentar setelah upvote)
usεr11852 mengatakan Reinstate Monic
2
Saya suka teorema Mercer di sini, jangan hapus. Dan mengapa tidak memiliki kedua tautan? Tambahkan saja seperti See [here] for a modern exposition, atau sebaliknya, "untuk kertas asli".
Amuba mengatakan Reinstate Monica
11

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:HX{0,1}01

  1. H memiliki properti konvergensi seragam.
  2. H adalah PAC yang bisa dipelajari.
  3. H memiliki dimensi VC yang terbatas.

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.

Mesin epsilon
sumber
6

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

Taimur
sumber
4

Favorit saya adalah ketimpangan Kraft.

Teorema: Untuk setiap metode deskripsi untuk alfabet hingga , kata kode panjang harus memenuhi ketidaksetaraan .CA={1,,m}LC(1),,LC(2)xA2LC(x)1

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.

bayerj
sumber
4

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]mRϵ>0NFNσ

|F(x)f(x)|ϵ
untuk semua .x[0,1]m

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,

Tobias Windisch
sumber
5
Teorema ini sedikit tidak menarik karena tidak khusus untuk jaring saraf. Banyak kelas fungsi lainnya berbagi properti perkiraan yang serupa (dan terkadang lebih kuat). Lihat misalnya teorema Stone-Weierstrass. Hasil yang lebih menarik adalah konsistensi regresi neural net dalam kerangka umum. Juga, harus ada batasan tentang kesalahan generalisasi rata-rata dalam hal kompleksitas jaring dan ukuran sampel pelatihan.
Olivier
1
@ Olivier: Saya sepenuhnya setuju. Tetapi meskipun teorema ini tidak secara eksklusif dikhususkan untuk jaringan saraf, saya masih menganggapnya sebagai pernyataan, bukti yang kuat, dan implikasinya menarik. Sebagai contoh, ia mengatakan bahwa selama Anda menggunakan fungsi aktivasi yang memiliki sifat-sifat yang disebutkan di atas, kemampuan perkiraan jaringan adalah sama (secara kasar). Atau, dikatakan bahwa jaringan saraf siap untuk overfitting karena Anda dapat belajar banyak dengan satu lapisan tersembunyi.
Tobias Windisch
1
Tidak dikatakan persis seperti itu. Ia hanya mengatakan bahwa ada jaringan saraf dengan satu lapisan tersembunyi yang dapat mewakili , tetapi ia tidak memberi tahu Anda apa pun tentang bagaimana tumbuh dengan , misalnya, atau dengan beberapa ukuran kompleksitas (misalnya variasi totalnya ). Itu tidak memberi tahu Anda jika Anda dapat bobot jaringan Anda, mengingat data. Anda akan menemukan bahwa dalam banyak kasus menarik secara eksponensial lebih besar untuk satu jaringan lapisan tersembunyi daripada untuk jaringan multilayer (dalam). Itulah sebabnya tidak ada yang menggunakan satu jaringan lapisan tersembunyi untuk ImageNet atau untuk Kaggle. fNmflearnN
DeltaIV
@DeltaIV: Ada kesalahan ketik pada kalimat terakhir dari komentar saya sebelumnya: kata "belajar" sebenarnya harus "perkiraan" (jika tidak, pernyataan saya tentang "overfitting" tidak masuk akal). Terima kasih atas petunjuknya!
Tobias Windisch
Ya, saya menafsirkannya dalam arti "aproksimasi". Maksud saya adalah bahwa bahkan jika Anda tahu bahwa secara teori Anda dapat memperkirakan fungsi apa pun (pada hypercube terbatas) dengan satu lapisan tersembunyi NN, dalam praktiknya itu tidak berguna dalam banyak kasus. Contoh lain: Proses Gaussian dengan kernel eksponensial kuadrat memiliki properti aproksimasi universal, tetapi mereka tidak menghilangkan semua metode regresi lainnya, juga karena fakta bahwa untuk beberapa masalah jumlah sampel yang diperlukan untuk perkiraan yang akurat tumbuh secara eksponensial.
DeltaIV