WikiDer > Support-Vektor-Maschine

Support-Vektor-Maschine (SVM) ist a Algorithmus im Bereich der kontrollierten maschinelles Lernen. Die Methode basiert auf der Theorie des statistischen Lernens der Russen Vapnik und Chervonenkis.^[1] Es hat viele verschiedene Anwendungen in Einstufung und Regressionsanalyse.

Prinzip

In diesem Beispiel ist H₂ und H₃ zwei akzeptable lineare Trennungen zwischen den beiden Klassen. huh₁ ist keine gute Scheidung; sie stuft 5 Instanzen der schwarzen Klasse als weiß ein. Außerdem ist H₃ vorzuziehen H₂; ein neues Objekt nur geringfügig rechts von den vorhandenen schwarzen Objekten würde von H . als weiße Klasse gezählt₂, was intuitiv falsch ist. huh₃ ist die optimale Trennung, da der Abstand zwischen der Linie und den beiden Klassen maximal ist.

Eine SVM ist ein Binärklassifikator; es ordnet Objekte anhand einer Reihe von Attributen einer von zwei Klassen zu. Dazu muss sie zuerst numerisches Modell mache diese Objekte zu Punkten in a Vektorraum. In der Trainingsphase wendet die SVM eine lineare Trennung zwischen den beiden Klassen anhand einer Sammlung von Beispielen an, von denen angegeben wird, zu welcher Klasse sie gehören. so gut wie möglich voneinander (diese Trennung ist a Hyperebene; in zwei Dimensionen ist es eine gerade Linie). Danach kann die SVM entscheiden, zu welcher Klasse sie für ein neues zu klassifizierendes Objekt gehört, indem sie entlang der Seite der Hyperebene schaut, auf der der entsprechende Punkt im Raum liegt.

Die "bestmögliche" Trennung bedeutet, dass der Abstand um die Schnittstelle, dh der Abstand zwischen der Schnittstelle und den nächstgelegenen Beispielen jeder Klasse, so groß wie möglich ist. Diese nächsten Beispiele heißen die Stützvektoren.

Das Verfahren ist auch in Fällen nützlich, in denen eine lineare Trennung zwischen den beiden Klassen nicht möglich ist (durch eine entsprechende Transformation, dem sogenannten "Kernel-Trick"), und auch in Fällen, in denen Rauschen oder Fehler in den Daten zu einigen Beispiele können sich auf der falschen Seite der Schnittstelle befinden. Computerimplementierungen von SVM können Probleme mit Tausenden von Dimensionen handhaben.

Lineare Klassifizierung

Der binäre lineare Klassifikator unterteilt Objekte in zwei Klassen, eine positive und eine negative, die mit 1 bzw. -1 gekennzeichnet sind. Die Erfassung von Trainingsdaten ${displaystyle {mathcal {D}}}$ besteht dann aus nein Punkte und ihre Bezeichnungen:

${displaystyle {mathcal {D}}=left{(mathbf {x} _{i},y_{i})mid mathbf {x} _{i}in mathbb {R} ^{p},,y_{i} in {-1,1},i=1,2,Punkte Nacht}}$

in welchem ja_ich ist 1 oder −1, um anzugeben, zu welcher Klasse der Punkt gehört ${displaystyle mathbf {x} _{i}}$ gehört. Jeder ${displaystyle mathbf {x} _{i}}$ ist ein p-dimensional RealVektor; jedes von den p Elemente im Vektor beschreibt eine Eigenschaft eines Beispielobjekts.

In der Trainingsphase muss die SVM die trennende Hyperebene bestimmen, die die Punkte mit verbindet ${displaystyle y_{i}=1}$ trennt sich von den Punkten mit ${displaystyle y_{i}=-1}$. Eine Hyperebene wird durch eine Gleichung der Form . bestimmt

${displaystyle mathbf {w} cdot mathbf {x} -b=0,,}$

in welchem ${displaystyle cdot }$ es internes Produkt von zwei Vektoren. ${displaystyle {mathbf {w}}}$ ist der normaler Vektor die senkrecht zur Hyperebene steht und ${displaystyle {frac {b}{|mathbf {w} |}}}$ ist der Abstand von der Hyperebene zum Ursprung gemäß der Richtung des Normalenvektors (${displaystyle |mathbf {w} |}$ ist der Norm des Vektors ${displaystyle {mathbf {w}}}$).

Die trennende Hyperebene wird so bestimmt, dass der sogenannte Rand, das ist der kleinste Abstand zur Hyperebene, für beide Klassen maximal ist, um einen möglichst großen Abstand zu gewährleisten. Die geometrische Interpretation davon lautet: Die optimale Hyperebene ist senkrecht relativ zur kürzesten Linie zwischen den konvexe Schalen der beiden Klassen und schneidet diese Linie genau in der Mitte.

Für eine linear separierbare Trainingsmenge sind unendlich viele Trennungsebenen möglich.

Die beste Schnittstelle (in Rot) ist die mit dem größten Spielraum. Die eingekreisten Beispiele sind die Stützvektoren.

Die optimale trennende Hyperebene erfüllt die Anforderung:

${displaystyle max _{mathbf {w} ,b}min{||mathbf {x} -mathbf {x_{i}} ||:mathbf {w} cdot mathbf {x} b=0,i=1,dots n }}$

Um diese optimale Hyperebene zu konstruieren, a Optimierungsproblem gelöst, was wie folgt formuliert werden kann:

minimieren in Bezug auf ${displaystyle mathbf {w} ,b:{frac {1}{2}}||mathbf {w} ||^{2}}$

mit den Bedingungen ${displaystyle y_{i}(mathbf {w} cdot mathbf {x} _{i} b)geq 1,i=1,dots n}$

Dies ist ein konvex-quadratisches (d. h. nichtlineares) Programmierproblem. Es wird normalerweise gelöst durch die Lagrange-Dual Problem, das unter bestimmten Bedingungen (den sogenannten Kuhn-Tucker-Bedingungen) die gleiche Lösung hat. Das duale Problem ist oft einfacher zu lösen als das primäre, mit Software "von der Stange".

Beachten Sie, dass die Lage der trennenden Hyperebene nur von wenigen Beispielen abhängt, nämlich denjenigen, die ihr am nächsten sind. Das nennt man Stützvektoren (Dies sind die eingekreisten Punkte in der Abbildung oben). Punkte, die weiter von der Hyperebene entfernt sind, können aus dem Trainingssatz weggelassen werden, ohne die Position der Hyperebene zu ändern; wird ein Stützvektor weggelassen, ändert sich die trennende Hyperebene.

Sobald die optimalen Werte von ${displaystyle mathbf {w} ,b}$ berechnet, kann die SVM in der Entscheidungsphase einen neuen Vektor erzeugen ${displaystyle mathbf {x} _{*}}$ klassifizieren durch Berechnung der Entscheidungsfunktion

${displaystyle f(mathbf {x} )=operatorname {sgn}(mathbf {w} cdot mathbf {x} _{*} b)}$

was 1 oder -1 zurückgibt (oder 0, wenn der Vektor genau auf der Schnittstelle liegt).

Nicht trennbare Klassen

In den meisten realen Fällen können die Trainingsbeispiele nicht scharf linear in zwei Klassen getrennt werden. Dies kann beispielsweise an Messfehlern oder Rauschen in den Daten liegen oder es gibt eine Grauzone, in der sich die beiden Klassen überschneiden. Für diesen Fall kann das Optimierungsproblem durch Hinzufügen eines zusätzlichen "Strafterms" modifiziert werden. Es hat dann folgende Form:

minimieren in Bezug auf ${displaystyle mathbf {w} ,b,xi _{i},i=1,Punkte n}$: ${displaystyle {frac {1}{2}}||mathbf {w} ||^{2} Summe _{i=1}^{n}xi _{i}}$,

mit den Einschränkungen ${displaystyle y_{i}(mathbf {w} cdot mathbf {x} _{i} b)geq 1-xi _{i};xi _{i}geq 0,i=1,dots n}$

Also geben wir für jedes Trainingsbeispiel eine zusätzliche Variable ein ${displaystyle xi_{i}}$ im. Diese "Restvariable" (englisch: Schlupfvariable) ist ein Maß für die mögliche Überschreitung der Randbedingungen (der Abstand auf der falschen Seite der trennenden Hyperebene für die ich-das Beispiel) und durch deren Eingabe in die Zielfunktion sorgen wir dafür, dass diese Überschreitungen so gering wie möglich gehalten werden. Es besteht auch ein Kompromiss zwischen dem Wunsch nach einem möglichst großen Spielraum um die Trennfläche einerseits und möglichst wenigen Überschreitungen andererseits. Die zu wählende positive Konstante ${Anzeigestil C}$ weist in diesem Zusammenhang auf die Bedeutung hin, die wir den Überschreitungen beimessen.

Das Doppelproblem

Wir finden den Normalenvektor ${displaystyle mathbf {w} }$ wie ein lineare Kombination der Trainingsbeispiele schreiben:

${displaystyle mathbf {w} = Summe _{i=1}^{n}alpha _{i}y_{i}mathbf {x} _{i}}$

Die Variablen ${displaystyle alpha_{i}}$ sein Lagrange-Multiplikatoren. Die duale Form ist dann das Maximierungsproblem:

maximieren ${displaystyle sum _{i=1}^{n}alpha _{i}-{frac {1}{2}}sum _{i=1}^{n}sum _{j=1}^{n} alpha _{i}alpha _{j}y_{i}y_{j}(mathbf {x} _{i}cdot mathbf {x} _{j})}$

über ${displaystyle alpha _{i},i=1,Punkte n}$

und mit den Bedingungen:

${displaystyle 0leq alpha _{i}leq C}$ und ${Anzeigestilsumme _{i=1}^{n}alpha _{i}y_{i}=0}$.

Beachten Sie, dass die restlichen Variablen ${displaystyle xi_{i}}$ treten hier nicht mehr auf und die Konstante C ist nicht mehr in der Zielfunktion, sondern als Einschränkung für die Variablen. Die Entscheidungsfunktion lautet dann:

${displaystyle f(mathbf {x} )=operatorname {sgn}(mathbf {w} cdot mathbf {x} b)=operatorname {sgn} left(sum _{i=1}^{n}alpha _{i}y_ {i}(mathbf {x} _{i}cdot mathbf {x} ) Bucht)}$

Die Trainingsbeispiele, deren Lagrange-Variablen ${displaystyle alpha_{i}eq 0}$ heißt der Stützvektoren. Diese befinden sich entweder am Rand (wenn ${displaystyle y_{i}(mathbf {w} cdot mathbf {x} ) b)=1}$) oder am Rand (${displaystyle xi_{i}>0}$). Nur diese Stützvektoren tragen zur Entscheidungsfunktion bei.

Nichtlineare Klassifikation

Transformation von nichtlinearer zu linearer Trennung

Algorithmen wie SVM zeichnen sich dadurch aus, dass sie auch dann verwendet werden können, wenn die Originaldaten nicht linear trennbar sind. Wir nehmen daher an, dass es a Bild${displaystyle phi (mathbf {x} )}$ existiert von diesem Eingaberaum in einen anderen, höherdimensionalen interner Produktraum. Dieser Raum heißt auf Englisch de Feature-Raum (Beachten Sie, dass der Eingaberaum nicht einmal ein innerer Produktraum sein muss). Wir können dann SVM im Merkmalsraum anwenden, indem wir überall in den Algorithmus einfügen ${displaystyle mathbf {x} }$ ersetzt werden durch ${displaystyle phi (mathbf {x} )}$. Aber der Algorithmus verwendet ${displaystyle mathbf {x} }$ nur in internen Produkten ${displaystyle mathbf {w} cdot mathbf {x} }$, die ersetzt werden durch ${displaystyle phi (mathbf {w} )cdot phi (mathbf {x} )}$. Eine (nichtlineare) reelle Funktion ${displaystyle K(mathbf {x} ,mathbf {z} )}$ im Eingaberaum entsprechend dem Skalarprodukt von ${displaystyle phi (mathbf {x} )}$ und ${displaystyle phi (mathbf {z} )}$ im Merkmalsraum heißt a Kernelfunktion oder kurz Kernel.

${displaystyle K(mathbf {x} ,mathbf {z} )=phi (mathbf {x} )cdot phi (mathbf {z} )}$

Wir können nun das Punktprodukt im linearen SVM-Algorithmus durch den Kernel ersetzen. Der große Vorteil davon Kernel-Trick ist, dass wir die Vektoren ${displaystyle phi (mathbf {x} )}$ im Merkmalsraum müssen nicht explizit berechnet werden. Solche Berechnungen können sehr zeitaufwendig sein, während ${displaystyle K(mathbf {x} ,mathbf {z} )}$ oft leicht zu berechnen. Der Merkmalsraum kann viele Dimensionen haben, in manchen Fällen sogar unendlich viele. Mit Kerneln wird der potenzielle Umfang von SVMs enorm. Zum Beispiel wurden Kernel für Graphen, Strings und andere Objekte formuliert. Die Herausforderung besteht darin, einen geeigneten Kernel zu finden, der die Daten in einem Merkmalsraum linear trennbar macht; der Erfolg einer SVM hängt von der Wahl des Kernels, den Parametern des Kernels und der Konstante ab C für die Überschreitungen der Schnittstelle.

Der lineare Klassifikator ist nur ein Sonderfall, bei dem der Eingaberaum ein innerer Produktraum ist, der mit dem Merkmalsraum zusammenfällt. Aber auch in diesem Fall ist es manchmal sinnvoll, anstelle des inneren Produkts eine Kernel-Funktion zu verwenden.

Beispiel

Die Kernel-Funktion

${displaystyle K(mathbf {x} ,mathbf {z} )=(mathbf {x} cdot mathbf {z} )^{2}}$

entspricht dem Bild eines Eingaberaums mit nein Bemaßungen zu einem Merkmalsraum mit nein² Abmessungen, zum Beispiel mit nein=3:

${displaystyle mathbf {x} =(x_{1},x_{2},x_{3})}$

${displaystyle phi (mathbf {x} )=(x_{1}x_{1},x_{1}x_{2},x_{1}x_{3},x_{2}x_{1},x_{2 }x_{2},x_{2}x_{3},x_{3}x_{1},x_{3}x_{2},x_{3}x_{3})}$

Das kann man hier leicht nachprüfen ${displaystyle K(mathbf {x} ,mathbf {z} )=(mathbf {x} cdot mathbf {z} )^{2}=(x_{1}z_{1} x_{2}z_{2} x_{ 3}z_{3})^{2}=(phi (mathbf {x} )cdot phi (mathbf {z} ))}$

Erweiterung auf mehrere Klassen

Der einfachste Weg, Daten mit einer SVM in mehrere Klassen zu klassifizieren, besteht darin, das Problem in separate binäre Probleme aufzuteilen. Beim "eins-zu-eins"-Ansatz wird für jedes Klassenpaar eine binäre SVM trainiert. Wenn da k Klassen erhalten ein k(k-1)/2 Entscheidungsfunktionen. In der Entscheidungsphase wird jede Entscheidungsfunktion angewendet, was zu einer "Stimme" für eine Klasse führt. Die letzte Wahl fällt auf die Klasse, die die meisten Stimmen gesammelt hat. Beim „Einer-gegen-Alles“-Ansatz k Entscheidungsfunktionen, die zwischen einer Klasse und allen anderen unterscheiden. In der Entscheidungsphase wird nicht nur das Vorzeichen berücksichtigt, sondern auch der Wert jeder Funktion. Die Funktion mit der höchsten Punktzahl bestimmt die Klasse (die Funktionen der Klassifikatoren müssen kalibriert werden, damit die Punktzahlen vergleichbar sind; die Skalierung ändert die Ergebnisse einer SVM nicht).

Anwendungen

SVMs sind in vielen Bereichen nützlich, wie zum Beispiel:

• in der Textklassifikation (zum Beispiel at Spamfilter);
• Erkennen handgeschriebener Zeichen;
• Klassifizieren von Bildern (zum Beispiel entscheiden, ob ein Foto ein Gesicht darstellt oder nicht);
• in der biomedizinischen Forschung, zum Beispiel zur Klassifizierung von Gewebeproben.^[2]

Externe Links

• Andreas Ng. "Support Vector Machines" (Skript zur Vorlesung)
• OpenCV, "Einführung zur Unterstützung von Vektormaschinen"
• SVM^Licht (Computerprogramm von Thorsten Joachims)
• Support-Vektor-Maschinen (Webseite zum Buch Support-Vektor-Maschinen von John Shawe-Taylor und Nello Cristianini, Cambridge University Press, 2000)