Wie kann SVM einen unendlichen Merkmalsraum finden, in dem eine lineare Trennung immer möglich ist?

36

Was ist die Intuition dahinter, dass eine SVM mit einem Gaußschen Kern einen unendlich dimensionalen Merkmalsraum hat?

user36162
quelle
1
Ich verstehe die Frage nicht wirklich. Möchten Sie eine Erklärung, warum der zugehörige Merkmalsraum unendlich dimensioniert ist, oder eine Interpretation dessen, was die resultierende Hyperebene bedeutet?
Marc Claesen
1
Es würde mir nichts ausmachen, beides zu hören!
user36162
5
Ich denke, das ist eine interessante Frage (+1)

Antworten:

39

Diese Antwort erklärt Folgendes:

  1. Warum eine perfekte Trennung mit bestimmten Punkten und einem Gaußschen Kern (mit ausreichend kleiner Bandbreite) immer möglich ist
  2. Wie diese Trennung als linear interpretiert werden kann, aber nur in einem abstrakten Merkmalsraum, der sich von dem Raum unterscheidet, in dem sich die Daten befinden
  3. Wie die Zuordnung von Datenraum zu Merkmalsraum "gefunden" wird. Spoiler: Wird nicht von SVM gefunden, sondern implizit vom ausgewählten Kernel definiert.
  4. Warum der Merkmalsraum unendlich dimensional ist.

1. Perfekte Trennung erreichen

Mit einem Gaußschen Kernel ist immer eine perfekte Trennung möglich (vorausgesetzt, keine zwei Punkte aus verschiedenen Klassen sind jemals genau gleich), da die Lokalitätseigenschaften des Kernels zu einer willkürlich flexiblen Entscheidungsgrenze führen. Bei einer ausreichend kleinen Kernelbandbreite sieht die Entscheidungsgrenze so aus, als hätten Sie nur kleine Kreise um die Punkte gezogen, wenn diese zur Trennung der positiven und negativen Beispiele benötigt werden:

Etwas wie das

(Quelle: Andrew Ngs Online-Kurs für maschinelles Lernen ).

Warum geschieht dies also aus mathematischer Sicht?

Betrachten Sie den Standard - Setup: Sie haben einen Gauß - Kern und Trainingsdaten ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , , ( x ( n ) ,K(x,z)=exp(-||x-z||2/σ2) wobei die y ( i ) -Werte ± 1 sind . Wir wollen eine Klassifikatorfunktion lernen(x(1),y(1)),(x(2),y(2)),,(x(n),y(n))y(ich)±1

y^(x)=ichwichy(ich)K(x(ich),x)

Wie werden wir nun jemals die Gewichte zuweisen ? Benötigen wir unendlich dimensionale Räume und einen quadratischen Programmieralgorithmus? Nein, weil ich nur zeigen will, dass ich die Punkte perfekt trennen kann. Also mache ich σ eine Milliarde mal kleiner als der kleinste Abstand | | x ( i ) - x ( j ) | | zwischen zwei beliebigen Trainingsbeispielen, und ich setze gerade w i = 1 . Dies bedeutet , dass alle Trainingspunkte sind eine Milliarde Sigmas auseinander , so weit das Kernel betrifft, und jeder Punkt steuert vollständig das Vorzeichen von ywichσ||x(ich)-x(j)||wich=1y^in seiner Nachbarschaft. Formal haben wir

y^(x(k))=ich=1ny(k)K(x(ich),x(k))=y(k)K(x(k),x(k))+ichky(ich)K(x(ich),x(k))=y(k)+ϵ

Wobei ein beliebig kleiner Wert ist. Wir wissen , ε klein ist , weil x ( k ) eine Milliarde Sigmas weg von jedem anderen Punkt ist, so dass für alle i k haben wirϵϵx(k)ichk

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

Da so klein ist, y ( x ( k ) ) hat auf jeden Fall das gleiche Vorzeichen wie y ( k ) und der Klassifikator erreicht perfekte Genauigkeit auf den Trainingsdaten.ϵy^(x(k))y(k)

2. Kernel-SVM-Lernen als lineare Trennung

Die Tatsache, dass dies als "perfekte lineare Trennung in einem unendlich dimensionalen Merkmalsraum" interpretiert werden kann, ergibt sich aus dem Kernel-Trick, mit dem Sie den Kernel als inneres Produkt in einem (möglicherweise unendlich dimensionalen) Merkmalsraum interpretieren können:

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

Dabei ist die Zuordnung vom Datenraum zum Merkmalsraum. Daraus folgt unmittelbar , daß die y ( x ) Funktion als eine lineare Funktion in dem Merkmalsraum:Φ(x)y^(x)

y^(x)=ichwichy(ich)Φ(x(ich)),Φ(x)=L(Φ(x))

wobei die lineare Funktion auf Merkmalsraumvektoren v als definiert istL(v)v

L(v)=ichwichy(ich)Φ(x(ich)),v

Diese Funktion ist in linear, da es sich nur um eine lineare Kombination innerer Produkte mit festen Vektoren handelt. In dem Merkmalsraum, die Entscheidungsgrenze y ( x ) = 0 gerade ist L ( v ) = 0 , der Pegel einer linearen Funktion. Dies ist die eigentliche Definition einer Hyperebene im Objektbereich.vy^(x)=0L(v)=0

3. Grundlegendes zur Zuordnung und zum Funktionsbereich

Hinweis: In diesem Abschnittbezieht sichdie Notation auf eine beliebige Menge von n Punkten und nicht auf die Trainingsdaten. Das ist reine Mathematik; Die Trainingsdaten sind in diesem Abschnitt überhaupt nicht enthalten!x(ich)n

Kernel - Methoden eigentlich nie „finden“ oder „berechnen“ der Merkmalsraum oder die Abbildung explizit. Kernel-Lernmethoden wie SVM benötigen sie nicht, um zu funktionieren. sie müssen nur die Kernfunktion K .ΦK

Es ist jedoch möglich, eine Formel für aufzuschreiben . Der Merkmalsraum, auf den Φ abgebildet wird, ist abstrakt (und möglicherweise unendlich dimensional), aber im Grunde verwendet das Mapping nur den Kernel, um ein einfaches Feature-Engineering durchzuführen. Bezüglich des Endergebnisses unterscheidet sich das Modell, das Sie am Ende mit Kerneln lernen, nicht von dem traditionellen Feature-Engineering, das in der linearen Regression und GLM-Modellierung verwendet wird, z. B. das Protokoll einer positiven Prädiktorvariablen, bevor es in eine Regressionsformel eingegeben wird. Die Mathematik ist meist nur dazu da, um sicherzustellen, dass der Kernel gut mit dem SVM-Algorithmus zusammenarbeitet, der die bekannten Vorteile von Sparsity und Skalierung für große Datensätze bietet.ΦΦ

Wenn Sie immer noch interessiert sind, erfahren Sie hier, wie es funktioniert. Im Grunde nehmen wir die Identität , die wir halten wollen, , und einen Raum und inneres Produkt konstruieren , so dass es per Definition hält. Dazu definieren wir einen abstrakten Vektorraum V, in dem jeder Vektor eine Funktion von dem Raum, in dem sich die Daten befinden, X zu den reellen Zahlen R ist . Ein Vektor f in V ist eine Funktion, die aus einer endlichen linearen Kombination von Kernschnitten gebildet wird: f ( xΦ(x),Φ(y)=K(x,y)VXRfV Es ist zweckmäßig, f kompakterzu schreibenals f = n i = 1 α i K x ( i ) wobei K x ( y ) = K ( x , y ) ist eine Funktion, die bei x eine "Scheibe" des Kernels ergibt.

f(x)=ich=1nαichK(x(ich),x)
f
f=ich=1nαichKx(ich)
Kx(y)=K(x,y)x

Das innere Produkt auf dem Raum ist kein gewöhnliches Punktprodukt, sondern ein abstraktes inneres Produkt, das auf dem Kernel basiert:

ich=1nαichKx(ich),j=1nβjKx(j)=ich,jαichβjK(x(ich),x(j))

Wenn der Merkmalsraum auf diese Weise definiert ist, ist eine Abbildung XV , die jeden Punkt x zu dem "Kernel-Slice" an diesem Punkt bringt:ΦXVx

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

Sie können beweisen, dass ein innerer Produktraum ist, wenn K ein positiver bestimmter Kern ist. Weitere Informationen finden Sie in diesem Dokument. (Ein großes Lob an f coppens für diesen Hinweis!)VK

4. Warum ist der Merkmalsraum unendlich dimensional?

Diese Antwort gibt eine schöne Erklärung für die lineare Algebra, aber hier ist eine geometrische Perspektive, sowohl mit Intuition als auch mit Beweis.

Intuition

Für jeden festen Punkt haben wir eine Kernel-Slice-Funktion K z ( x ) = K ( z , x ) . Der Graph von K z ist nur eine Gauß'sche Erhebung, die bei z zentriert istzKz(x)=K(z,x)Kzz. Wenn der Merkmalsraum nur endlich dimensioniert wäre, würde dies bedeuten, dass wir eine endliche Menge von Erhebungen an einer festen Menge von Punkten nehmen und irgendwo anders eine Gauß'sche Erhebung bilden könnten. Aber es ist klar, dass wir das nicht schaffen können. Aus alten Unebenheiten kann man keine neue Unebenheit machen, weil die neue Unebenheit sehr weit von den alten entfernt sein kann. Egal wie viele Merkmalsvektoren (Bumps) wir haben, wir können immer neue Bumps hinzufügen, und im Merkmalsraum sind dies neue unabhängige Vektoren. Der Merkmalsraum kann also nicht endlich dimensioniert sein. es muss unendlich sein.

Beweis

Wir benutzen Induktion. Angenommen, Sie haben eine beliebige Menge von Punkten , sodass die Vektoren Φ ( x ( i ) ) im Merkmalsraum linear unabhängig sind. Finden Sie nun einen Punkt x ( n + 1 ), der sich von diesen n Punkten unterscheidet, und zwar eine Milliarde Sigmas von allen entfernt. Wir behaupten, dass Φ ( x ( n + 1 ) )x(1),x(2),,x(n)Φ(x(ich))x(n+1)nΦ(x(n+1))ist linear unabhängig von den ersten Merkmalsvektoren Φ ( x ( i ) ) .nΦ(x(ich))

Beweis durch Widerspruch. Nehmen wir das Gegenteil an

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

Nehmen Sie nun das innere Produkt auf beiden Seiten mit einem beliebigen . Durch die Identität Φ ( z ) , Φ ( x ) = K ( z , x ) , so erhalten wirxΦ(z),Φ(x)=K(z,x)

K(x(n+1),x)=ich=1nαichK(x(ich),x)

Hier ist eine freie Variable, daher ist diese Gleichung eine Identität, die besagt, dass zwei Funktionen gleich sind. Insbesondere heißt es, dass ein um x ( n + 1 ) zentrierter Gaußscher als eine lineare Kombination von Gaußschen an anderen Punkten x ( i ) dargestellt werden kann . Es ist geometrisch offensichtlich, dass man aus einer endlichen Kombination von Gauß'schen Erhebungen, die an anderen Punkten zentriert sind, keine Gauß'sche Erhebung erzeugen kann, insbesondere wenn all diese anderen Gauß'schen Erhebungen eine Milliarde Sigmas entfernt sind. Unsere Annahme einer linearen Abhängigkeit hat also zu einem Widerspruch geführt, wie wir gezeigt haben.xx(n+1)x(ich)

Paul
quelle
6
Eine perfekte Trennung ist nicht möglich. Gegenbeispiel: (0,0, ClasssA), (0,0, ClassB). Viel Glück beim Trennen dieses Datensatzes!
Anony-Mousse
4
Das ist ... technisch korrekt, die beste Art von richtig! Habe eine Gegenstimme. Ich werde eine Notiz in der Post hinzufügen.
Paul
3
(Ich denke, Ihr Punkt ist sinnvoll, wenn Sie einen Mindestabstand zwischen Stichproben verschiedener Klassen benötigen. Es kann erwähnenswert sein, darauf hinzuweisen, dass in diesem Szenario der SVM zum Nächsten-Nachbar-Klassifikator wird.)
Anony-Mousse
1
Ich spreche nur den Fall des endlichen Trainingssatzes an, also gibt es immer einen Mindestabstand zwischen Punkten, sobald wir einen Trainingssatz mit verschiedenen Punkten erhalten, mit denen wir arbeiten können. n
Paul
@Paul In Bezug auf Ihren Abschnitt 2 habe ich eine Frage. Sei für die Ausbildung Punkt in unserem RKHS die Representer seiner x ( i ) und k x für beliebige neuen Punkt x , so dass y ( x ) = Σ i w i y ( i )k i , k x= Σ i w i y ( i ) k i ( x ) also die Funktion kichx(ich)kxxy^(x)=ichwichy(ich)kich,kx=ichwichy(ich)kich(x)für einigeZiR. Für mich ist das wie die Funktion Raum Version von y Wesen in dem Säulenraum vonXfürlineare Regression und istwo wirklich die Linearität herkommt. Scheint diese Beschreibung korrekt zu sein? Ich lerne immer noch sehr viel dieses RKHS-Zeug. y^=ichzichkichzichRy^X
Jld
12

Die Kernel - Matrix des Gauß - Kern hat immer vollen Rang für verschiedene . Dies bedeutet, dass bei jedem Hinzufügen eines neuen Beispiels der Rang um 1 erhöht wird . Dies lässt sich am einfachsten feststellen, wenn Sie σ sehr klein einstellen . Dann ist die Kernelmatrix fast diagonal.x1,...,xm1σ

Die Tatsache, dass der Rang immer um eins steigt, bedeutet, dass alle Projektionen im Merkmalsraum linear unabhängig sind (nicht orthogonal, sondern unabhängig). Somit fügt jedes Beispiel eine neue Dimension in der Spannweite der Vorsprünge Φ ( x 1 ) , . . . , Φ ( x m ) . Da Sie unzählige Beispiele hinzufügen können, muss der Feature-Space eine unendliche Dimension haben. Interessanterweise liegen alle Projektionen des Eingaberaums in den Merkmalsraum auf einer Kugel, da | | Φ ( x ) | |Φ(x)Φ(x1),...,Φ(xm). Trotzdem ist die Geometrie der Kugel flach. Mehr dazu lesen Sie in||Φ(x)||H²=k(x,x)=1

Burges, CJC (1999). Geometrie und Invarianz in kernbasierten Methoden. In B. Schölkopf, CJC Burges und AJ Smola (Hrsg.) Unterstützen Fortschritte bei den Kernelmethoden das Vektorlernen (S. 89–116). MIT Press.

Fabee
quelle
Ich verstehe es immer noch nicht, aber du hast dir trotzdem eine positive
Bewertung
Sie verstehen nicht, warum die Geometrie flach oder unendlich dimensional ist? Danke für die positive Bewertung.
Fabee
Wenn ich 100 Beispiele habe, ist mein Feature-Space 100-dimensional oder bereits unendlich dimensional? Warum kann ich unzählige Beispiele hinzufügen? Ist das nicht eine zählbare Unendlichkeit? Warum spielt hier das Zählbare / Unzählbare eine Rolle? Ich habe noch nicht einmal versucht, an die "flache Kugel" zu denken: D Danke für Ihre Erklärungen!
stmax
5
Ich hoffe, Sie glauben mir, dass jedes neue Beispiel linear von allen vorherigen unabhängig ist (mit Ausnahme des gleichen ). In R n ist das nicht möglich: Jeder Punkt hinter n muss linear von den anderen abhängen. Wenn Sie für das Gaußsche RKHS 100 verschiedene Beispiele haben, überspannen sie einen 100-dimensionalen Unterraum des unendlichen dimensionalen Raums. Die Spanne ist also endlich dimensional, aber der Merkmalsraum, in dem sie leben, ist unendlich dimensional. Die Unendlichkeit ist unzählbar, weil jeder neue Punkt in R n eine neue Dimension ist und es unzählbar viele Punkte in R n gibt . xRnnRnRn
Fabee
@fabee: Ich habe es auf eine andere Art versucht. Du scheinst viel darüber zu wissen. Kannst du dir meine Antwort ansehen, ob ich sie mehr oder weniger richtig verstanden habe?
5

Für den Hintergrund und die Notationen verweise ich auf die Antwort Wie berechne ich die Entscheidungsgrenze aus Unterstützungsvektoren? .

xichyich{-1,+1}αich

K(x,y)=Φ(x)Φ(y)Φ

Φ

xich

xichϕich(x)=K(xich,x)ϕichϕichϕichV=speinn(ϕich,ich=1,2,N)N ist die Größe des Trainingsmusters).

VVϕichich=1NγichϕichγichV={v=ich=1Nγichϕich|(γ1,γ2,γN)RN}

(γ1,γ2,γN)vV

NVNϕichϕich(x)=K(xich,x)ϕV

ϕich(x)=K(xich,x)VN

V

Φ:xichϕich(x)=K(xich,x)

ΦΦxichVϕichich

xichVich=1Nγichϕichγich

f(x)f(x)=ichyichαichϕich(x)+bf(x)=0

f(x)ϕich f(x)=0Vγichγich=αichyich

yichαichV

V

Kernel sind also eine Technik, mit der SVM Ihren Funktionsbereich transformieren kann. Siehe auch Was macht den Gaußschen Kernel für PCA so magisch und auch im Allgemeinen?

Gemeinschaft
quelle
+1 das ist solide. Ich habe dieses Material in meinen eigenen Expository-Stil übersetzt und meiner Antwort hinzugefügt.
Paul
5

Leider ist die Erklärung von fcop völlig falsch. Zunächst sagt er: "Es ist bekannt, dass der Kernel als ... wobei ... eine (implizite und unbekannte) Transformation in einen neuen Merkmalsraum geschrieben werden kann." Es ist NICHT unbekannt. Dies ist in der Tat der Raum, auf den die Features abgebildet werden, und dies ist der Raum, der wie im RBF-Fall unendlich dimensional sein kann. Der Kernel nimmt lediglich das innere Produkt dieses transformierten Merkmalsvektors mit einem transformierten Merkmalsvektor eines Trainingsbeispiels und wendet eine Funktion auf das Ergebnis an. Somit repräsentiert es implizit diesen höherdimensionalen Merkmalsvektor. Denken Sie zum Beispiel daran, (x + y) ^ 2 anstelle von x ^ 2 + 2xy + y ^ 2 zu schreiben. Stellen Sie sich nun vor, welche unendlichen Reihen implizit durch die Exponentialfunktion dargestellt werden. Dort haben Sie Ihren unendlichen Merkmalsraum.

Die richtige Art, über SVMs nachzudenken, besteht darin, dass Sie Ihre Features einem möglicherweise unendlichen dimensionalen Feature-Space zuordnen, der implizit in einem weiteren endlichen dimensionalen Feature-Space "Kernel" darstellbar ist, dessen Dimension so groß sein kann wie die Größe des Trainingssatzes.

Salvador
quelle