Bagaimana SVM 'menemukan' ruang fitur tanpa batas di mana pemisahan linier selalu dimungkinkan?

36

Apa intuisi di balik fakta bahwa SVM dengan Kernel Gaussian memiliki ruang fitur dimensi tak terbatas?

pengguna36162
sumber
1
Saya tidak begitu mengerti pertanyaannya. Apakah Anda ingin penjelasan mengapa ruang fitur yang sesuai adalah dimensi tak terbatas atau interpretasi mengenai apa yang dimaksud hyperplane yang dihasilkan?
Marc Claesen
1
Saya tidak keberatan mendengar keduanya!
user36162
5
Saya pikir ini adalah pertanyaan yang menarik (+1)

Jawaban:

39

Jawaban ini menjelaskan hal berikut:

  1. Mengapa pemisahan sempurna selalu dimungkinkan dengan titik berbeda dan kernel Gaussian (dengan bandwidth yang cukup kecil)
  2. Bagaimana pemisahan ini dapat diartikan sebagai linear, tetapi hanya dalam ruang fitur abstrak yang berbeda dari ruang tempat data tinggal
  3. Bagaimana pemetaan dari ruang data ke ruang fitur "ditemukan". Spoiler: itu tidak ditemukan oleh SVM, itu ditentukan secara implisit oleh kernel yang Anda pilih.
  4. Mengapa ruang fitur adalah dimensi tak terbatas.

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:

Sesuatu seperti ini

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

y^(x)=iwiy(i)K(x(i),x)

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=1y^di lingkungannya. Secara resmi, kami punya

y^(x(k))=i=1ny(k)K(x(i),x(k))=y(k)K(x(k),x(k))+iky(i)K(x(i),x(k))=y(k)+ϵ

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)ik

K(x(i),x(k))=exp(||x(i)x(k)||2/σ2)0.

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

K(x(i),x(j))=Φ(x(i)),Φ(x(j))

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)

y^(x)=iwiy(i)Φ(x(i)),Φ(x)=L(Φ(x))

di mana fungsi linear didefinisikan pada vektor ruang fitur v sebagaiL(v)v

L(v)=iwiy(i)Φ(x(i)),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 (vy^(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)VXRfV Lebih mudah untuk menulis f lebih kompak karena f = n i = 1 α i K x ( i ) di mana K x ( y ) = K ( x , y )

f(x)=i=1nαiK(x(i),x)
f
f=i=1nαiKx(i)
Kx(y)=K(x,y) adalah fungsi yang memberikan "irisan" kernel pada .x

Produk dalam pada ruang bukan produk titik biasa, tetapi produk dalam abstrak yang didasarkan pada kernel:

i=1nαiKx(i),j=1nβjKx(j)=i,jαiβjK(x(i),x(j))

Dengan ruang fitur yang ditentukan dengan cara ini, adalah pemetaan XV , mengambil setiap titik x ke "kernel slice" pada saat itu:ΦXVx

Φ(x)=Kx,whereKx(y)=K(x,y).

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!)VK

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)Kzz. 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

Φ(x(n+1))=i=1nαiΦ(x(i))

Sekarang ambil produk dalam di kedua sisi dengan sewenang-wenang . Dengan identitas Φ ( z ) , Φ ( x ) = K ( z , x ) , kita memperolehxΦ(z),Φ(x)=K(z,x)

K(x(n+1),x)=i=1nαiK(x(i),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.xx(n+1)x(i)

Paul
sumber
6
Pemisahan sempurna tidak mungkin. Contoh tandingan: (0,0, ClasssA), (0,0, ClassB). Selamat mencoba memisahkan kumpulan data ini!
Anony-Mousse
4
Itu ... secara teknis benar, jenis terbaik yang benar! Dapatkan upvote. Saya akan menambahkan catatan di pos.
Paul
3
(I do think your point makes sense if you require a minimum distance between samples of different classes. It may be worth pointing out that in this scenario, the SVM becomes a nearest-neighbor classifier)
Anony-Mousse
1
I'm only addressing the finite training set case, so there's always a minimum distance between points once we are given a training set of n distinct points to work with.
Paul
@Paul Regarding your section 2, I have a question. Let ki be the representer in our RKHS for training point x(i) and kx for arbitrary new point x so that y^(x)=iwiy(i)ki,kx=iwiy(i)ki(x) so the function y^=iziki for some ziR. To me this is like the function space version of y^ being in the column space of X for linear regression and is where the linearity really comes from. Does this description seem accurate? I'm still very much learning this RKHS stuff.
jld
12

The kernel matrix of the Gaussian kernel has always full rank for distinct x1,...,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)||H²=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.

fabee
sumber
I still don't understand it, but you earned an upvote anyway :)
stmax
You mean, you don't understand why the geometry is flat or why it is infinite dimensional? Thanks for the upvote.
fabee
If I have 100 examples, is my feature space 100-dimensional or already infinitely dimensional? Why can I add "uncountably" infinitely many examples? Isn't that a countable infinity? Why does countable/uncountable matter here? I didn't even try thinking about the "flat sphere" yet :D Thanks for your explanations!
stmax
5
I hope you believe me that every new example is linearly independent from all the ones before (except for the same x). In Rn you cannot do that: Every point beyond n must be linearly dependent on the others. For the Gaussian RKHS, if you have 100 different examples, they span a 100 dimensional subspace of the infinite dimensional space. So the span is finite dimensional, but the features space they live in is infinite dimensional. The infinity is uncountable, because every new point in Rn is a new dimension and there are uncountably many points in Rn.
fabee
@fabee: I tried it in a different way, you seem yo know a lot about it, can you take a look at my answer whether I got it more or less 'right' ?
5

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 vectors xi, the binary outcome yi{1,+1} and the Lagrange multipliers are αi.

It is known that the Kernel can be written as K(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 my xi) into some 'new' feature space in which the linear separation will be solved.

For each observation xi, 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 space V 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.: i=1Nγiϕi, where γi are real numbers. So, in fact, V={v=i=1Nγiϕi|(γ1,γ2,γN)RN}

Note that (γ1,γ2,γN) are the coordinates of vector v in the vector space V.

N is the size of the training sample and therefore the dimension of the vector space V can go up to N, depending on whether the ϕi are linear independent. As ϕi(x)=K(xi,x) (see supra, we defined ϕ in this way), this means that the dimension of V depends on the kernel used and can go up to the size of the training sample.

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 to V is defined as

Φ:xiϕi(x)=K(xi,x).

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 values xi 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 i=1Nγiϕi, where γi are real numbers.

Looking at the function f(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 !

The yi 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 space V, 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?

Community
sumber
+1 this is solid. I translated this material into my own expository style and added it to my answer.
Paul
5

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.

salvador
sumber