Apa intuisi di balik fakta bahwa SVM dengan Kernel Gaussian memiliki ruang fitur dimensi tak terbatas?
svm
feature-selection
kernel-trick
pengguna36162
sumber
sumber
Jawaban:
Jawaban ini menjelaskan hal berikut:
1. Mencapai pemisahan sempurna
Pemisahan sempurna selalu dimungkinkan dengan kernel Gaussian (asalkan tidak ada dua poin dari kelas yang berbeda yang persis sama) karena sifat lokalitas kernel, yang mengarah pada batas keputusan yang fleksibel dan sewenang-wenang. Untuk bandwidth kernel yang cukup kecil, batas keputusan akan terlihat seperti Anda hanya menggambar lingkaran kecil di sekitar titik kapan pun mereka diperlukan untuk memisahkan contoh positif dan negatif:
(Kredit: kursus pembelajaran mesin online Andrew Ng ).
Jadi, mengapa ini terjadi dari perspektif matematika?
Pertimbangkan pengaturan standar: Anda memiliki kernel Gaussian dan data pelatihan ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , … , ( x ( n ) ,K(x,z)=exp(−||x−z||2/σ2) dimana y ( i ) nilai-nilai ± 1 . Kami ingin mempelajari fungsi classifier( x( 1 ), y( 1 )) , ( x( 2 ), y( 2 )) , … , ( X( n ), y( n )) y(i) ±1
Sekarang bagaimana kita pernah menetapkan bobot ? Apakah kita memerlukan ruang dimensi tak terbatas dan algoritma pemrograman kuadratik? Tidak, karena saya hanya ingin menunjukkan bahwa saya dapat memisahkan poin dengan sempurna. Jadi saya membuat σ satu miliar kali lebih kecil dari pemisahan terkecil |, | x ( i ) - x ( j ) | | antara dua contoh pelatihan, dan saya baru saja menetapkan w iwi σ ||x(i)−x(j)|| . Ini berarti bahwa semua poin pelatihan adalah miliar sigmas terpisah sejauh kernel yang bersangkutan, dan setiap titik benar-benar mengontrol tanda ywi=1 y^ di lingkungannya. Secara resmi, kami punya
di mana adalah nilai kecil yang sewenang-wenang. Kita tahu ϵ kecil karena x ( k ) berjarak satu miliar sigma dari titik lain, jadi untuk semua i ≠ k kita punyaϵ ϵ x(k) i≠k
Karena sangat kecil, y ( x ( k ) )ϵ y^(x(k)) pasti memiliki tanda yang sama seperti , dan classifier mencapai akurasi yang sempurna pada data pelatihan.y(k)
2. Pembelajaran Kernel SVM sebagai pemisahan linear
Fakta bahwa ini dapat ditafsirkan sebagai "pemisahan linear sempurna dalam ruang fitur dimensi tak terbatas" berasal dari trik kernel, yang memungkinkan Anda untuk menafsirkan kernel sebagai produk dalam di dalam ruang fitur (berpotensi dimensi tak terbatas):
di mana adalah pemetaan dari ruang data ke dalam ruang fitur. Ini mengikuti segera bahwa y ( x ) fungsi sebagai fungsi linear dalam ruang fitur:Φ(x) y^(x)
di mana fungsi linear didefinisikan pada vektor ruang fitur v sebagaiL(v) v
Fungsi ini linier dalam karena itu hanya kombinasi linier produk dalam dengan vektor tetap. Dalam ruang fitur, keputusan batas y ( x ) = 0 hanya L (v y^(x)=0 , tingkat set fungsi linear. Ini adalah definisi hyperplane di ruang fitur.L(v)=0
3. Memahami pemetaan dan ruang fitur
Catatan: Di bagian ini, notasix(i) merujuk pada set poin yang sewenang-wenang dan bukan data pelatihan. Ini adalah matematika murni; data pelatihan tidak masuk ke bagian ini sama sekali!n
Metode kernel tidak pernah benar-benar "menemukan" atau "menghitung" ruang fitur atau pemetaan secara eksplisit. Metode pembelajaran kernel seperti SVM tidak membutuhkannya untuk bekerja; mereka hanya perlu fungsi kernel K .Φ K
Yang mengatakan, adalah mungkin untuk menuliskan formula untukΦ . Ruang fitur yang dipetakan adalah jenis abstrak (dan berpotensi dimensi tak terbatas), tetapi pada dasarnya, pemetaan hanya menggunakan kernel untuk melakukan beberapa rekayasa fitur sederhana. Dalam hal hasil akhir, model yang Anda akhirnya pelajari, menggunakan kernel tidak berbeda dari rekayasa fitur tradisional yang populer diterapkan dalam regresi linier dan pemodelan GLM, seperti mengambil log variabel prediktor positif sebelum memasukkannya ke dalam formula regresi. Matematika sebagian besar ada di sana untuk membantu memastikan kernel bekerja dengan baik dengan algoritma SVM, yang memiliki keunggulan kebanggaan sparsity dan scaling dengan baik untuk dataset besar.Φ
Jika Anda masih tertarik, inilah cara kerjanya. Pada dasarnya kita mengambil identitas kita ingin ditahan, , dan membangun ruang dan produk dalam rupa sehingga memegang dengan definisi. Untuk melakukan ini, kita mendefinisikan sebuah ruang vektor abstrak V di mana masing-masing vektor adalah fungsi dari ruang kehidupan data dalam, X , dengan bilangan real R . Vektor f dalam V adalah fungsi yang dibentuk dari kombinasi linear terbatas dari irisan kernel: f ( x⟨Φ(x),Φ(y)⟩=K(x,y) V X R f V
Lebih mudah untuk menulis f lebih kompak karena
f = n ∑ i = 1 α i K x ( i ) di
mana K x ( y ) = K ( x , y )
Produk dalam pada ruang bukan produk titik biasa, tetapi produk dalam abstrak yang didasarkan pada kernel:
Dengan ruang fitur yang ditentukan dengan cara ini, adalah pemetaan X → V , mengambil setiap titik x ke "kernel slice" pada saat itu:Φ X→V x
Anda dapat membuktikan bahwa adalah ruang produk dalam ketika K adalah kernel pasti positif. Lihat makalah ini untuk detailnya. (Kudos to f coppens untuk menunjukkan ini!)V K
4. Mengapa ruang fitur dimensi tak terbatas?
Jawaban ini memberikan penjelasan aljabar linier yang bagus, tetapi inilah perspektif geometris, dengan intuisi dan bukti.
Intuisi
Untuk setiap titik tetap , kita memiliki fungsi sepotong kernel K z (z . Grafik K z hanya benjolan Gaussian berpusat di zKz(x)=K(z,x) Kz z . Sekarang, jika ruang fitur hanya dimensi terbatas, itu berarti kita bisa mengambil set benjolan terbatas pada set poin tetap dan membentuk setiap benjolan Gaussian di tempat lain. Tetapi jelas tidak mungkin kita bisa melakukan ini; Anda tidak dapat membuat gundukan baru dari gundukan lama, karena gundukan baru bisa sangat jauh dari yang lama. Jadi, tidak peduli berapa banyak vektor fitur (tonjolan) yang kita miliki, kita selalu dapat menambahkan tonjolan baru, dan dalam ruang fitur ini adalah vektor independen baru. Jadi ruang fitur tidak dapat menjadi dimensi terbatas; itu harus tanpa batas.
Bukti
Kami menggunakan induksi. Misalkan Anda memiliki seperangkat titik yang sewenang-wenang sedemikian rupa sehingga vektor Φ ( x ( i ) ) bebas linear dalam ruang fitur. Sekarang menemukan titik x ( n + 1x(1),x(2),…,x(n) Φ(x(i)) yang berbeda dari ininpoin, sebenarnya miliar sigmas jauh dari mereka semua. Kami mengklaim bahwaΦ( x ( n + 1 ) )x(n+1) n Φ(x(n+1)) secara linear bebas dari vektor fitur pertama Φ ( x ( i ) ) .n Φ(x(i))
Bukti oleh kontradiksi. Misalkan sebaliknya itu
Sekarang ambil produk dalam di kedua sisi dengan sewenang-wenang . Dengan identitas ⟨ Φ ( z ) , Φ ( x ) ⟩ = K ( z , x ) , kita memperolehx ⟨Φ(z),Φ(x)⟩=K(z,x)
Di sini adalah variabel bebas, jadi persamaan ini adalah identitas yang menyatakan bahwa dua fungsi adalah sama. Secara khusus, dikatakan bahwa Gaussian berpusat di x ( n + 1 ) dapat direpresentasikan sebagai kombinasi linear dari Gaussians pada titik lain x ( i ) . Jelas secara geometris bahwa seseorang tidak dapat membuat benjolan Gaussian berpusat pada satu titik dari kombinasi terbatas dari gundukan Gaussian yang berpusat pada titik-titik lain, terutama ketika semua benjolan Gaussian lainnya berjarak satu miliar sigma jauhnya. Jadi asumsi kami tentang ketergantungan linier telah menyebabkan kontradiksi, seperti yang kami tunjukkan.x x(n+1) x(i)
sumber
The kernel matrix of the Gaussian kernel has always full rank for distinctx1,...,xm . This means that each time you add a new example, the rank increases by 1 . The easiest way to see this if you set σ very small. Then the kernel matrix is almost diagonal.
The fact that the rank always increases by one means that all projectionsΦ(x) in feature space are linearly independent (not orthogonal, but independent). Therefore, each example adds a new dimension to the span of the projections Φ(x1),...,Φ(xm) . Since you can add uncountably infinitely many examples, the feature space must have infinite dimension. Interestingly, all projections of the input space into the feature space lie on a sphere, since ||Φ(x)||2H=k(x,x)=1 . Nevertheless, the geometry of the sphere is flat. You can read more on that in
Burges, C. J. C. (1999). Geometry and Invariance in Kernel Based Methods. In B. Schölkopf, C. J. C. Burges, & A. J. Smola (Eds.), Advances in Kernel Methods Support Vector Learning (pp. 89–116). MIT Press.
sumber
For the background and the notations I refer to the answer How to calculate decision boundary from support vectors?.
So the features in the 'original' space are the vectorsxi , the binary outcome yi∈{−1,+1} and the Lagrange multipliers are αi .
It is known that the Kernel can be written asK(x,y)=Φ(x)⋅Φ(y) ('⋅ ' represents the inner product.) Where Φ is an (implicit and unknown) transformation to a new feature space.
I will try to give some 'intuitive' explanation of what thisΦ looks like, so this answer is no formal proof, it just wants to give some feeling of how I think that this works. Do not hesitate to correct me if I am wrong. The basis for my explanation is section 2.2.1 of this pdf
I have to 'transform' my feature space (so myxi ) into some 'new' feature space in which the linear separation will be solved.
For each observationxi , I define functions ϕi(x)=K(xi,x) , so I have a function ϕi for each element of my training sample. These functions ϕi span a vector space. The vector space spanned by the ϕi , note it V=span(ϕi,i=1,2,…N) . (N is the size of the training sample).
I will try to argue that this vector spaceV is the vector space in which linear separation will be possible. By definition of the span, each vector in the vector space V can be written as as a linear combination of the ϕi , i.e.: ∑Ni=1γiϕi , where γi are real numbers. So, in fact, V={v=∑Ni=1γiϕi|(γ1,γ2,…γN)∈RN}
Note that(γ1,γ2,…γN) are the coordinates of vector v in the vector space V .
If the kernel is 'complex enough' then theϕi(x)=K(xi,x) will all be independent and then the dimension of V will be N , the size of the training sample.
The transformation, that maps my original feature space toV is defined as
This mapΦ maps my original feature space onto a vector space that can have a dimension that goes up to the size of my training sample. So Φ maps each observation in my training sample into a vector space where the vectors are functions. The vector xi from my training sample is 'mapped' to a vector in V , namely the vector ϕi with coordinates all equal to zero, except the i -th coordinate is 1.
Obviously, this transformation (a) depends on the kernel, (b) depends on the valuesxi in the training sample and (c) can, depending on my kernel, have a dimension that goes up to the size of my training sample and (d) the vectors of V look like ∑Ni=1γiϕi , where γi are real numbers.
Looking at the functionf(x) in How to calculate decision boundary from support vectors? it can be seen that f(x)=∑iyiαiϕi(x)+b . The decision boundary found by the SVM is f(x)=0 .
In other words,f(x) is a linear combination of the ϕi and f(x)=0 is a linear separating hyperplane in the V -space : it is a particular choice of the γi namely γi=αiyi !
Theyi are known from our observations, the αi are the Lagrange multipliers that the SVM has found. In other words SVM find, through the use of a kernel and by solving a quadratic programming problem, a linear separation in the V -spave.
This is my intuitive understanding of how the 'kernel trick' allows one to 'implicitly' transform the original feature space into a new feature spaceV , with a different dimension. This dimension depends on the kernel you use and for the RBF kernel this dimension can go up to the size of the training sample. As training samples may have any size this could go up to 'infinite'. Obviously, in very high dimensional spaces the risk of overfitting will increase.
So kernels are a technique that allows SVM to transform your feature space , see also What makes the Gaussian kernel so magical for PCA, and also in general?
sumber
Unfortunately, fcop's explanation is quite incorrect. First of all he says "It is known that the Kernel can be written as... where ... is an (implicit and unknown) transformation to a new feature space." It's NOT unknown. This is in fact the space the features are mapped to and this is the space that could be infinite dimensional like in the RBF case. All the kernel does is take the inner product of that transformed feature vector with a transformed feature vector of a training example and applies some function to the result. Thus it implicitly represents this higher dimensional feature vector. Think of writing (x+y)^2 instead of x^2+2xy+y^2 for example. Now think what infinite series is represented implicitly by the exponential function... there you have your infinite feature space. This has absolutely nothing to do with the fact that your training set could be infinitely large.
The right way to think about SVMs is that you map your features to a possibly infinite dimensional feature space which happens to be implicitly representable in yet another finite dimensional "Kernel" feature space whose dimension could be as large as the training set size.
sumber