Apa yang membuat kernel Gaussian begitu ajaib untuk PCA, dan juga secara umum?

Saya membaca tentang kernel PCA ( 1 , 2 , 3 ) dengan kernel Gaussian dan polinomial.

• Bagaimana kernel Gaussian memisahkan data nonlinier dengan sangat baik? Tolong beri analisis intuitif, serta yang terlibat secara matematis jika memungkinkan.

• Apa yang dimaksud dengan properti kernel Gaussian (dengan ideal ) yang tidak dimiliki kernel lain? Jaringan saraf, SVM, dan jaringan RBF muncul di pikiran.$\sigma$

• Mengapa kita tidak meletakkan norma melalui, katakanlah, Cauchy PDF dan mengharapkan hasil yang sama?

Saya pikir kunci sihir adalah kelancaran. Jawaban panjang saya yang berikut ini hanya untuk menjelaskan tentang kelancaran ini. Ini mungkin atau mungkin bukan jawaban yang Anda harapkan.

Jawaban singkat:

Mengingat kernel yang pasti positif , terdapat ruang yang sesuai fungsi H . Properti fungsi ditentukan oleh kernel. Ternyata jika k adalah kernel Gaussian, fungsi-fungsi dalam H sangat lancar. Jadi, fungsi yang dipelajari (misalnya, fungsi regresi, komponen utama dalam RKHS seperti pada kernel PCA) sangat lancar. Biasanya asumsi kelancaran masuk akal untuk sebagian besar dataset yang ingin kita atasi. Ini menjelaskan mengapa kernel Gaussian bersifat magis.$k$$\mathcal{H}$$k$$\mathcal{H}$

Jawaban panjang mengapa kernel Gaussian memberikan fungsi yang halus:

Sebuah positif yang pasti kernel mendefinisikan (secara implisit) produk dalam k ( x , y ) = ⟨ φ ( x ) , φ ( y ) ⟩ H untuk vektor fitur φ ( x ) dibangun dari masukan Anda x , dan H adalah ruang Hilbert. Notasi ⟨ φ ( x ) , φ ( y ) $k(x,y)$$k(x,y)=\left\langle \phi(x),\phi(y)\right\rangle _{\mathcal{H}}$$\phi(x)$$x$$\mathcal{H}$$\left\langle \phi(x),\phi(y)\right\rangle$ berarti produk dalam antara dan ϕ ( y ) . Untuk tujuan kami, Anda dapat membayangkan H sebagai ruang Euclidean yang biasa tetapi mungkin dengan jumlah dimensi yang tidak terbatas. Bayangkan vektor biasa yang panjangnya tak terhingga seperti ϕ ( x ) = ( ϕ 1 ( x ) , ϕ 2 ( x ) , ... ) . Dalam metode kernel, $\phi(x)$$\phi(y)$$\mathcal{H}$$\phi(x)=\left(\phi_{1}(x),\phi_{2}(x),\ldots\right)$$\mathcal{H}$adalah ruang fungsi yang disebut mereproduksi kernel Hilbert space (RKHS). Ruang ini memiliki properti khusus yang disebut `` mereproduksi properti '' yang adalah bahwa . Ini mengatakan bahwa untuk mengevaluasi f ( x ) , pertama-tama Anda membuat vektor fitur (panjangnya seperti yang disebutkan) untuk f . Kemudian Anda membangun vektor fitur Anda untuk x dilambangkan dengan ϕ ( x ) (panjang tak terhingga). Evaluasi f ( x $f(x)=\left\langle f,\phi(x)\right\rangle$$f(x)$$f$$x$$\phi(x)$$f(x)$diberikan dengan mengambil produk dalam keduanya. Jelas, dalam praktiknya, tidak ada yang akan membuat vektor panjang yang tak terhingga. Karena kami hanya peduli dengan produk dalamnya, kami langsung mengevaluasi kernel . Memotong perhitungan fitur eksplisit dan secara langsung menghitung produk dalamnya dikenal sebagai "trik kernel".$k$

Apa saja fiturnya?

Saya terus mengatakan fitur tanpa menentukan apa itu. Diberikan kernel k , fitur-fiturnya tidak unik. Tapi ⟨ φ ( x ) , φ ( y ) ⟩ ditentukan secara unik. Untuk menjelaskan kelancaran fungsi, mari kita perhatikan fitur Fourier. Asumsikan sebuah terjemahan invarian kernel k , yang berarti k ( x , y ) = k ( x - $\phi_{1}(x),\phi_{2}(x),\ldots$$k$$\left\langle \phi(x),\phi(y)\right\rangle$$k$ yaitu, kernel hanya tergantung pada perbedaan dari dua argumen. Kernel Gaussian memiliki properti ini. Biarkan k menunjukkan Transformasi Fourier dari k .$k(x,y)=k(x-y)$$\hat{k}$$k$

Dalam sudut pandang Fourier ini, fitur diberikan oleh f : = ( ⋯ , f l / $f$. Ini mengatakan bahwa representasi fitur dari fungsi Andaf diberikan oleh transformasi Fourier-nya dibagi oleh transformasi Fourer dari kernelk. Representasi fiturx, yaituϕ(x) adalah(⋯,$f:=\left(\cdots,\hat{f}_{l}/\sqrt{\hat{k}_{l}},\cdots\right)$$f$$k$$x$$\phi(x)$ di manai=$\left(\cdots,\sqrt{\hat{k}_{l}}\exp\left(-ilx\right),\cdots\right)$ . Orang dapat menunjukkan bahwa properti yang direproduksi berlaku (latihan untuk pembaca).$i=\sqrt{-1}$

Seperti di ruang Hilbert mana pun, semua elemen yang termasuk dalam ruang harus memiliki norma yang terbatas. Mari kita perhatikan norma kuadrat dari :$f\in\mathcal{H}$

$\|f\|_{\mathcal{H}}^{2}=\left\langle f,f\right\rangle _{\mathcal{H}}=\sum_{l=-\infty}^{\infty}\frac{\hat{f}_{l}^{2}}{\hat{k}_{l}}.$

Jadi kapan norma yang terbatas ini, milik ruang? Ini adalah ketika f 2 l tetes lebih cepat dari k l sehingga jumlah konvergen. Sekarang, transformasi Fourier dari kernel Gaussian k ( x , y ) = exp ( - ‖ x - y ‖ $f$$\hat{f}_{l}^{2}$$\hat{k}_{l}$ $k(x,y)=\exp\left(-\frac{\|x-y\|^{2}}{\sigma^{2}}\right)$

adalah Gaussian lain di mana k l menurun secara eksponensial cepat dengan l . Jadi jika f berada di ruang ini, transformasi Fouriernya harus jatuh lebih cepat daripada k . Ini berarti fungsi hanya akan memiliki beberapa komponen frekuensi rendah dengan bobot tinggi secara efektif. Sebuah sinyal dengan hanya komponen frekuensi rendah tidak terlalu banyak bergerak. Ini menjelaskan mengapa kernel Gaussian memberi Anda fungsi yang lancar.$\hat{k}_{l}$$l$$f$$k$

Extra: Bagaimana dengan kernel Laplace?

Jika Anda mempertimbangkan kernel Laplace , transformasi Fourier-nyaadalah distribusi Cauchy yang jauh lebih lambat daripada fungsi eksponensial dalam transformasi Fourier dari kernel Gaussian. Ini berarti suatu fungsifakan memiliki lebih banyak komponen frekuensi tinggi. Akibatnya, fungsi yang diberikan oleh kernel Laplace adalah `` lebih kasar '' daripada yang diberikan oleh kernel Gaussian.$k(x,y)=\exp\left(-\frac{\|x-y\|}{\sigma}\right)$$f$

Apa yang merupakan properti dari kernel Gaussian yang tidak dimiliki kernel lain?

Terlepas dari lebar Gaussian, satu properti adalah bahwa kernel Gaussian adalah `` universal ''. Secara intuitif, ini berarti, mengingat fungsi kontinu terbatas (sewenang-wenang), terdapat fungsi f ∈ H sedemikian sehingga f dan g dekat (dalam arti ‖ ⋅ ‖ ∞ ) hingga presisi yang diperlukan sewenang-wenang. Pada dasarnya, ini berarti kernel Gaussian memberikan fungsi yang dapat mendekati fungsi "bagus" (dibatasi, kontinu) secara sewenang-wenang. Kernel Gaussian dan Laplace bersifat universal. Kernel polinomial, misalnya, tidak.$g$$f\in\mathcal{H}$$f$$g$$\|\cdot\|_{\infty})$

Mengapa kita tidak meletakkan norma melalui, katakanlah, Cauchy PDF dan mengharapkan hasil yang sama?

Secara umum, Anda dapat melakukan apapun yang Anda suka asalkan dihasilkan pasti positif. Kepastian positif didefinisikan sebagai Σ N i = 1 Σ N j = 1 k ( x i , x j ) α i α j > 0 untuk semua a i ∈ R , { x i } N i = 1 dan semua N ∈ N ( set nomor alami). Jika $k$$\sum_{i=1}^{N}\sum_{j=1}^{N}k(x_{i},x_{j})\alpha_{i}\alpha_{j}>0$$\alpha_{i}\in\mathbb{R}$$\{x_{i}\}_{i=1}^{N}$$N\in\mathbb{N}$$k$tidak pasti positif, maka itu tidak sesuai dengan ruang produk dalam. Semua analisis rusak karena Anda bahkan tidak memiliki ruang fungsi seperti yang disebutkan. Meskipun demikian, ini dapat bekerja secara empiris. Misalnya, kernel tangen hiperbolik (lihat nomor 7 di halaman ini )$\mathcal{H}$

$k(x,y) = tanh(\alpha x^\top y + c)$

yang dimaksudkan untuk meniru unit aktivasi sigmoid dalam jaringan saraf, hanya pasti positif untuk beberapa pengaturan dan c . Masih dilaporkan bahwa ia bekerja dalam praktik.$\alpha$$c$

Bagaimana dengan jenis fitur lainnya?

Saya katakan fitur tidak unik. Untuk kernel Gaussian, serangkaian fitur lain diberikan oleh ekspansi Mercer . Lihat Bagian 4.3.1 dari buku proses Gaussian yang terkenal . Dalam hal ini, fitur adalah polinomial Hermite yang dievaluasi pada x .$\phi(x)$$x$

Saya akan melakukan yang terbaik untuk menjawab pertanyaan ini bukan karena saya seorang ahli dalam topik (justru sebaliknya), tetapi karena saya ingin tahu tentang bidang dan topik, dikombinasikan dengan gagasan bahwa itu bisa menjadi pengalaman pendidikan yang baik . Ngomong-ngomong, inilah hasil penelitian amatir singkat saya tentang masalah ini.

TL; DR : Saya akan mempertimbangkan perikop berikut dari makalah penelitian "Koneksi antara operator regularisasi dan kernel vektor dukungan" sebagai jawaban singkat untuk pertanyaan ini:

Kernel Gaussian cenderung menghasilkan kinerja yang baik di bawah asumsi kelancaran umum dan harus dipertimbangkan terutama jika tidak ada pengetahuan tambahan tentang data yang tersedia.

Sekarang, jawaban terperinci (sesuai dengan pemahaman saya; untuk detail matematika, silakan gunakan referensi).

Seperti yang kita ketahui, analisis komponen utama (PCA) adalah pendekatan yang sangat populer untuk pengurangan dimensi , sendirian dan untuk klasifikasi data selanjutnya: http://www.visiondummy.com/2014/05/feature-extraction-using-pca . Namun, dalam situasi, ketika data membawa dependensi non-linear (dengan kata lain, linear tidak dapat dipisahkan ), PCA tradisional tidak berlaku (tidak berkinerja baik). Untuk kasus-kasus itu, pendekatan lain dapat digunakan, dan PCA non-linear adalah salah satunya.

Pendekatan, di mana PCA didasarkan pada menggunakan fungsi kernel biasanya disebut, menggunakan istilah payung "kernel PCA" ( kPCA ). Menggunakan kernel Gaussian radial-function function (RBF) mungkin merupakan variasi yang paling populer. Pendekatan ini dijelaskan secara rinci dalam berbagai sumber, tetapi saya sangat menyukai penjelasan yang sangat baik oleh Sebastian Raschka dalam posting blog ini . Namun, sambil menyebutkan kemungkinan menggunakan fungsi kernel, selain Gaussian RBF, postingan ini berfokus pada yang terakhir karena popularitasnya. Posting blog yang bagus ini , memperkenalkan pendekatan dan trik kernel , menyebutkan satu lagi alasan yang mungkin untuk popularitas kernel Gaussian untuk PCA: dimensi tak terbatas.

Wawasan tambahan dapat ditemukan dalam beberapa jawaban tentang Quora. Secara khusus, membaca diskusi yang sangat bagus ini mengungkapkan beberapa poin tentang kemungkinan alasan popularitas kernel Gaussian, sebagai berikut.

• Kernel Gaussian bersifat universal :

Kernel Gaussian adalah kernel universal yaitu penggunaannya dengan regularisasi yang tepat menjamin prediktor optimal global yang meminimalkan kesalahan estimasi dan perkiraan dari classifier.

• Kernel Gaussian berbentuk lingkaran (yang mengarah ke dimensi tak terbatas yang disebutkan di atas?)
• Kernel Gaussian dapat mewakili "medan yang sangat bervariasi"
• Poin berikut, mendukung kesimpulan utama di atas, lebih baik disampaikan dengan mengutip penulis:

Kernel Gaussian RBF sangat populer dan membuat kernel default yang baik terutama karena tidak adanya pengetahuan ahli tentang data dan domain karena jenis ini juga termasuk kernel polinomial dan linear. Kernel Linear dan Kernel Polinomial adalah kasus khusus dari kernel Gaussian RBF. Kernel Gaussian RBF adalah model non-parametrik yang pada dasarnya berarti bahwa kompleksitas model ini berpotensi tak terbatas karena jumlah fungsi analitik tidak terbatas.

• Kernel Gaussian optimal (pada kehalusan , baca lebih lanjut di sini - penulis yang sama):

Kernel Gaussian hanyalah filter pass band; ia memilih solusi yang paling halus. [...] Gaussian Kernel bekerja paling baik ketika jumlah tak terbatas dari turunan orde tinggi konvergen tercepat - dan itu terjadi untuk solusi paling lancar.

Akhirnya, poin tambahan dari jawaban yang bagus ini :

• Kernel Gaussian mendukung model yang sangat rumit
• Kernel Gaussian lebih fleksibel

CATATAN:

Titik referensi di atas tentang kernel Gaussian menjadi pilihan optimal , terutama ketika tidak ada pengetahuan sebelumnya tentang data, didukung oleh kalimat berikut dari jawaban CV ini :

Dengan tidak adanya pengetahuan para ahli, kernel Radial Basis Function menjadi kernel default yang baik (setelah Anda memantapkannya, ini merupakan masalah yang membutuhkan model non-linear).

Bagi mereka yang ingin tahu tentang perbedaan yang tidak esensial antara kernel Gaussian RBF dan kernel Gaussian standar, jawaban ini mungkin menarik: https://stats.stackexchange.com/a/79193/31372 .

Bagi mereka yang tertarik untuk mengimplementasikan kPCA untuk kesenangan atau bisnis, posting blog yang bagus ini mungkin bermanfaat. Ini ditulis oleh salah satu penulis (pencipta?) Dari Accord.NET - .NET framework sumber terbuka yang sangat menarik untuk analisis statistik, pembelajaran mesin, pemrosesan sinyal dan banyak lagi.

Biarkan saya memasukkan dua sen saya.

Cara saya berpikir tentang kernel Gaussian adalah sebagai pengklasifikasi tetangga terdekat. Apa yang dilakukan kernel Gaussian adalah bahwa ia mewakili setiap titik dengan jarak ke semua titik lain dalam dataset. Sekarang pikirkan tentang pengklasifikasi dengan batas linier atau polinomial, batasnya terbatas pada bentuk tertentu. Namun, ketika Anda melihat tetangga terdekat, batas praktis dapat mengambil bentuk apa pun. Itulah saya pikir mengapa kita berpikir tentang kernel Gaussian juga sebagai non-parametrik, yaitu menyesuaikan batas tergantung pada data. Cara lain untuk memikirkan itu adalah kernel Gaussian menyesuaikan dengan bentuk lokal di suatu wilayah, mirip dengan bagaimana tetangga terdekat secara lokal menyesuaikan batas dengan melihat jarak ke titik-titik lain di wilayah lokal.

Saya tidak memiliki argumen matematis untuk ini, tetapi saya pikir fakta bahwa kernel Gaussian sebenarnya memetakan ke ruang dimensi tak terbatas ada hubungannya dengan keberhasilannya. Untuk kernel linear dan polinomial, produk titik diambil dalam ruang dimensi yang terbatas; karenanya tampaknya lebih kuat untuk melakukan hal-hal di ruang yang lebih besar. Saya harap seseorang memiliki pemahaman yang lebih baik tentang hal-hal ini. Itu juga berarti bahwa jika kita dapat menemukan kernel lain dengan ruang dimensi tak terbatas, mereka juga harus cukup kuat. Sayangnya, saya tidak terbiasa dengan kernel semacam itu.

Untuk poin terakhir Anda, saya pikir Cauchy pdf atau pdf lain yang dalam beberapa hal mengukur jarak ke titik lain harus bekerja sama baiknya. Sekali lagi, saya tidak memiliki argumen matematika yang bagus untuk itu, tetapi koneksi ke tetangga terdekat membuat ini masuk akal.

Sunting:

$\phi_i$$x_i$

$\phi_i$

Alasannya adalah bahwa dimensi VC untuk kernel Gaussian tidak terbatas, dan dengan demikian, mengingat nilai yang benar untuk parameter (sigma), mereka dapat mengklasifikasikan sejumlah besar sampel secara sewenang-wenang dengan benar.

$K(x_{i},x_{j})$$K(x_{i},x_{i}) > 0$$\sigma$

Pertimbangkan sebaliknya, kasus kernel linier, yang hanya dapat menghancurkan empat titik di pesawat.

Anda dapat melihat makalah ini , meskipun sangat teknis. Salah satu buku standar tentang SVM harus membuat konsep ini lebih mudah diakses.