Jądro SVM: Chcę intuicyjnego zrozumienia mapowania do przestrzennej przestrzeni cech i tego, jak to umożliwia separację liniową

15

Próbuję zrozumieć intuicję stojącą za SVM jądra. Teraz rozumiem, jak działa liniowy SVM, dzięki czemu tworzona jest linia decyzyjna, która najlepiej dzieli dane. Rozumiem również zasadę przenoszenia danych do przestrzeni o większych wymiarach oraz sposób, w jaki może to ułatwić znalezienie liniowej linii decyzyjnej w tej nowej przestrzeni. Nie rozumiem, w jaki sposób jądro jest używane do rzutowania punktów danych na tę nową przestrzeń.

Wiem o jądrze, że skutecznie reprezentuje „podobieństwo” między dwoma punktami danych. Ale jak to się ma do projekcji?

Karnivaurus
źródło
3
Jeśli przejdziesz do wystarczająco dużej przestrzeni wymiarowej, wszystkie punkty danych treningowych można idealnie oddzielić płaszczyzną. To nie znaczy, że będzie miał jakąkolwiek moc predykcyjną. Myślę, że przejście do przestrzeni o bardzo dużych wymiarach jest moralnym odpowiednikiem (formy) nadmiernego dopasowania.
Mark L. Stone,
@Mark L. Kamień: to prawda (+1), ale pytanie, jak jądro może mapować w nieskończonej przestrzeni wymiarowej, może być dobrym pytaniem? Jak to działa? Próbowałem, zobacz moją odpowiedź
Byłbym ostrożny, nazywając mapowanie funkcji „projekcją”. Mapowanie cech jest zasadniczo transformacją nieliniową.
Paul,
Bardzo pomocny post na temat sztuczki jądra wizualizuje wewnętrzną przestrzeń produktu jądra i opisuje, w jaki sposób w tym celu wykorzystuje się wysokowymiarowe wektory cech, mam nadzieję, że odpowiada to zwięźle na pytanie: eric-kim.net/eric-kim-net/ posts / 1 / kernel_trick.html
JStrahl

Odpowiedzi:

6

Niech h(x) będzie rzutem na przestrzeń dużego wymiaru F. Zasadniczo funkcja jądra K(x1,x2)=h(x1),h(x2) , który jest wewnętrzny produkt uboczny. Nie jest więc używany do rzutowania punktów danych, ale raczej do wyniku projekcji. Można to uznać za miarę podobieństwa, ale w SVM to coś więcej.

Optymalizacja w celu znalezienia najlepszej oddzielającej hiperpłaszczyzny w F obejmuje h(x) tylko poprzez formę produktu wewnętrznego. To znaczy, jeśli znasz K(,) , nie musisz znać dokładnej formy h(x) , co ułatwia optymalizację.

Każde jądro K(,) ma również odpowiednie h(x) . Więc jeśli używasz SVM z tym jądrem, to domyślnie znajdujesz liniową linię decyzyjną w przestrzeni, na którą mapuje h(x) .

Rozdział 12 elementów statystycznego uczenia się zawiera krótkie wprowadzenie do SVM. Daje to więcej szczegółów na temat połączenia między jądrem a mapowaniem funkcji: http://statweb.stanford.edu/~tibs/ElemStatLearn/

Lii
źródło
to znaczy, że przez jądro jest unikalnym bazowy h ( x ) ? K(x,y)h(x)
2
@fcoppens No; dla trywialnego przykładu rozważmy oraz - h . Istnieje jednak unikalna przestrzeń Hilberta odpowiadająca temu jądrowi. hh
Dougal,
@Dougal: W takim razie mogę się z tobą zgodzić, ale w powyższej odpowiedzi było powiedziane „odpowiadające ”, więc chciałem się upewnić. W przypadku RKHS widzę, ale czy uważasz, że można wyjaśnić w „intuicyjny sposób”, jak ta transformacja h wygląda dla jądra K ( x , y ) ? hhK.(x,y)
@fcoppens Zasadniczo nie; znalezienie wyraźnych reprezentacji tych map jest trudne. Jednak w przypadku niektórych jąder nie jest to ani zbyt trudne, ani wcześniej.
Dougal,
1
@ fcoppens masz rację, h (x) nie jest unikalne. Możesz łatwo wprowadzić zmiany do h (x), zachowując jednocześnie iloczyn wewnętrzny <h (x), h (x ')>. Można je jednak traktować jako funkcje podstawowe, a zajmowana przez nich przestrzeń (tj. RKHS) jest wyjątkowa.
Lii,
4

Przydatne właściwości jądra SVM nie są uniwersalne - zależą od wyboru jądra. Aby uzyskać intuicję, pomocne jest spojrzenie na jedno z najczęściej używanych jąder, jądro Gaussa. Co ciekawe, to jądro zamienia SVM w coś podobnego do k-najbliższego sąsiada klasyfikatora.

Ta odpowiedź wyjaśnia, co następuje:

  1. Dlaczego perfekcyjne rozdzielenie pozytywnych i negatywnych danych treningowych jest zawsze możliwe przy jądrze Gaussa o wystarczająco małej przepustowości (kosztem przeregulowania)
  2. Jak ten podział można interpretować jako liniowy w przestrzeni cech.
  3. Jak jądro jest używane do konstruowania mapowania z przestrzeni danych na przestrzeń cech. Spoiler: przestrzeń cech jest bardzo matematycznie abstrakcyjnym obiektem z niezwykłym abstrakcyjnym produktem wewnętrznym opartym na jądrze.

1. Osiągnięcie idealnej separacji

Idealne rozdzielenie jest zawsze możliwe w przypadku jądra Gaussa ze względu na jego właściwości lokalizacyjne, które prowadzą do arbitralnie elastycznej granicy decyzji. Dla wystarczająco małej przepustowości jądra granica decyzyjna będzie wyglądać tak, jakbyś po prostu narysował małe kółka wokół punktów, ilekroć są one potrzebne do oddzielenia pozytywnych i negatywnych przykładów:

Coś takiego

( Źródło: internetowy kurs uczenia maszynowego Andrew Ng ).

Dlaczego więc dzieje się to z matematycznego punktu widzenia?

Rozważ standardową konfigurację: masz jądro Gaussa i dane treningowe ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , , ( x ( n ) ,K(x,z)=exp(||xz||2/σ2) gdzie wartości y ( i ) wynoszą ± 1 . Chcemy nauczyć się funkcji klasyfikatora(x(1),y(1)),(x(2),y(2)),,(x(n),y(n))y(i)±1

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

Jak teraz przypiszemy wagi ? Czy potrzebujemy nieskończonych przestrzeni wymiarowych i algorytmu programowania kwadratowego? Nie, ponieważ chcę tylko pokazać, że mogę doskonale rozdzielić punkty. Czynię więc σ miliard razy mniejszą niż najmniejsza separacja | | x ( i ) - x ( j ) | | pomiędzy dowolnymi dwoma przykładami treningu, a ja właśnie ustawiłem w i = 1 . Oznacza to, że wszystkie punkty szkoleniowe są mld Sigmas siebie aż do jądra jest zaniepokojony, a każdy punkt całkowicie kontroluje znak ywiσ||x(i)x(j)||wi=1y^w jego sąsiedztwie. Formalnie mamy

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)+ϵ

gdzie jest jakąś dowolnie małą wartością. Wiemy ε jest mała, ponieważ x ( k ) jest miliard Sigmas dala od jakiegokolwiek innego punktu, więc dla wszystkich i k mamyϵϵx(k)ik

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

Ponieważ jest tak mała, y ( x ( k ) ) na pewno ma taki sam znak jak y ( k ) i klasyfikator osiąga doskonałą dokładność na danych treningowych. W praktyce byłoby to okropnie nadmierne, ale pokazuje ogromną elastyczność jądra Gaussa SVM i to, jak może działać bardzo podobnie do najbliższego klasyfikatora sąsiadów.ϵy^(x(k))y(k)

2. Uczenie się SVM jądra jako separacji liniowej

Fakt, że można to interpretować jako „idealne rozdzielenie liniowe w nieskończonej wymiarowej przestrzeni cech” pochodzi z sztuczki jądra, która pozwala interpretować jądro jako abstrakcyjny produkt wewnętrzny, jakąś nową przestrzeń cech:

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

gdzie jest odwzorowaniem z przestrzeni danych na przestrzeń cech. Wynika stąd bezpośrednio, że w r ( x ) funkcji w funkcji liniowej w przestrzeni cech:Φ(x)y^(x)

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

gdzie funkcja liniowa jest zdefiniowana na wektorach przestrzeni cech v jakoL(v)v

L(v)=iwiy(i)Φ(x(i)),v

Ta funkcja jest liniowa w ponieważ jest to tylko liniowa kombinacja produktów wewnętrznych ze stałymi wektorami. W przestrzeni funkcji granica decyzja r ( x ) = 0 jest tylko L ( V ) = 0 , zestaw poziom funkcji liniowej. To jest właśnie definicja hiperpłaszczyzny w przestrzeni cech.vy^(x)=0L(v)=0

3. W jaki sposób jądro jest używane do konstruowania przestrzeni cech

Kernel methods never actually "find" or "compute" the feature space or the mapping Φ explicitly. Kernel learning methods such as SVM do not need them to work; they only need the kernel function K. It is possible to write down a formula for Φ but the feature space it maps to is quite abstract and is only really used for proving theoretical results about SVM. If you're still interested, here's how it works.

Basically we define an abstract vector space V where each vector is a function from X to R. A vector f in V is a function formed from a finite linear combination of kernel slices:

f(x)=i=1nαiK(x(i),x)
(Here the x(i) are just an arbitrary set of points and need not be the same as the training set.) It is convenient to write f more compactly as
f=i=1nαiKx(i)
where Kx(y)=K(x,y) is a function giving a "slice" of the kernel at x.

The inner product on the space is not the ordinary dot product, but an abstract inner product based on the kernel:

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

This definition is very deliberate: its construction ensures the identity we need for linear separation, Φ(x),Φ(y)=K(x,y).

With the feature space defined in this way, Φ is a mapping XV, taking each point x to the "kernel slice" at that point:

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

You can prove that V is an inner product space when K is a positive definite kernel. See this paper for details.

Paul
źródło
Świetne wytłumaczenie, ale myślę, że przegapiłeś minus dla definicji jądra gaussowskiego. K (x, z) = exp (- || x − z || 2 / σ2). Jak napisano, nie ma to sensu z ϵ znalezionym w części (1)
hqxortn
1

For the background and the notations I refer to 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.

As said by @Lii (+1) the Kernel can be written as K(x,y)=h(x)h(y) ('' represents the inner product.

I will try to give some 'intuitive' explanation of what this h 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.

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

I will try to argue that 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.

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.

The transformation, that maps my original feature space to V is defined as

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

This map Φ maps my original feature space onto a vector space that can have a dimension that goed up to the size of my training sample.

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, γ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.

In other words, f(x) is a linear combination of the ϕi and this is a linear separator 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.

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
źródło
"for each element of my training sample" -- is element here referring to a row or column (i.e. feature )
user1761806
co to jest x i x_i? Jeśli mój X jest wejściem 5 kolumn i 100 wierszy, jakie byłyby x i x_i?
user1761806,
@user1761806 an element is a row. The notation is explained in the link at the beginning of the answer
1

Transform predictors (input data) to a high-dimensional feature space. It is sufficient to just specify the kernel for this step and the data is never explicitly transformed to the feature space. This process is commonly known as the kernel trick.

Let me explain it. The kernel trick is the key here. Consider the case of a Radial Basis Function (RBF) Kernel here. It transforms the input to infinite dimensional space. The transformation of input x to ϕ(x) can be represented as shown below (taken from http://www.csie.ntu.edu.tw/~cjlin/talks/kuleuven_svm.pdf)

enter image description here

The input space is finite dimensional but the transformed space is infinite dimensional. Transforming the input to an infinite dimensional space is something that happens as a result of the kernel trick. Here x which is the input and ϕ is the transformed input. But ϕ is not computed as it is, instead the product ϕ(xi)Tϕ(x) is computed which is just the exponential of the norm between xi and x.

There is a related question Feature map for the Gaussian kernel to which there is a nice answer /stats//a/69767/86202.

The output or decision function is a function of the kernel matrix K(xi,x)=ϕ(xi)Tϕ(x) and not of the input x or transformed input ϕ directly. enter image description here

prashanth
źródło
0

Mapping to a higher dimension is merely a trick to solve a problem that is defined in the original dimension; so concerns such as overfitting your data by going into a dimension with too many degrees of freedom are not a byproduct of the mapping process, but are inherent in your problem definition.

Basically, all that mapping does is converting conditional classification in the original dimension to a plane definition in the higher dimension, and because there is a 1 to 1 relationship between the plane in the higher dimension and your conditions in the lower dimension, you can always move between the two.

Taking the problem of overfitting, clearly, you can overfit any set of observations by defining enough conditions to isolate each observation into its own class, which is equivalent of mapping your data to (n-1)D where n is the number of your observations.

Taking the simplest problem, where your observations are [[1,-1], [0,0], [1,1]] [[feature, value]], by moving into the 2D dimension and separating your data with a line, your are simply turning the conditional classification of feature < 1 && feature > -1 : 0 to defining a line that passes through (-1 + epsilon, 1 - epsilon). If you had more data points and needed more condition, you just needed to add one more degree of freedom to your higher dimension by each new condition that your define.

You can replace the process of mapping to a higher dimension with any process that provides you with a 1 to 1 relationship between the conditions and the degrees of freedom of your new problem. Kernel tricks simply do that.

Hou
źródło
1
As a different example, take the problem where the phenomenon results in observations of the form of [x, floor(sin(x))]. Mapping your problem into a 2D dimension is not helpful here at all; in fact, mapping to any plane will not be helpful here, which is because defining the problem as a set of x < a && x > b : z is not helpful in this case. The simplest mapping in this case is mapping into a polar coordinate, or into the imaginary plane.
Hou