[PYTHON] Einführung in das maschinelle Lernen - Hard Margin SVM Edition-
1. Was ist Support Vector Machine (SVM)?
In der vorherigen Einführung in das maschinelle Lernen von Simple Perceptron verwendet die Lernmethode von Simple Perceptron den Gradienten der Fehlerfunktion, um die Fehlerfunktion immer kleiner zu machen. Es war das. Diese Methode weist jedoch die folgenden zwei Probleme auf.
-Die Generalisierungsfähigkeit des Modells ist nicht garantiert.
- Aufgrund linear trennbarer Probleme nicht verfügbar.
Hier bezieht sich das Modell auf die Formel von $ f (x) $ nach Abschluss des Trainings. Darüber hinaus bezieht sich die Verallgemeinerungsfähigkeit auf die Fähigkeit, Klassenbezeichnungen und Funktionswerte nicht nur für zum Zeitpunkt des Trainings angegebene Trainingsdaten, sondern auch für unbekannte neue Daten korrekt vorherzusagen. Erstens besteht der Zweck der Verwendung von maschinellem Lernen wie Simple Perceptron darin, zu klassifizieren, ob E-Mails, die nicht zum Lernen verwendet werden, bei Spam-E-Mails gut Spam sind. Es reicht keinesfalls aus, nur zuvor gesendete E-Mails zu klassifizieren. Dafür reichen Signaturen aus, nicht für die Rolle des maschinellen Lernens.
SVM ist übrigens ein Algorithmus, der die beiden oben genannten Probleme löst.
Die Lösung für diese beiden Punkte war die Einführung von Margin-Maximierung und Kernel-Tricks.
Der Rand bezieht sich auf den Abstand zwischen der Linie _f (x) _ und den beiden Klassen.
Diese Randmaximierung ist ein Versuch, die Generalisierungsfähigkeit zu maximieren, indem der Abstand entsprechend M in der folgenden Abbildung maximiert wird.
Der Kernel-Trick bezieht sich auf die Abbildung von Daten aus dem ursprünglichen Datenraum auf einen höherdimensionalen Raum und die Durchführung einer linearen Datenanalyse für diesen höherdimensionalen Raum.
Es ist eine etwas schwierige Geschichte, aber Sie können sich vorstellen, dass der Kernel-Trick so etwas wie das folgende Bild macht.
"Warum können zwei Probleme mithilfe von Margin-Maximierung und Kernel-Tricks gelöst werden?" Wird später beschrieben.
2. SVM-Formulierung
In der vorherigen Einführung in das maschinelle Lernen von Simple Perceptron und den bisher beschriebenen Inhalten, wenn die Daten beim Lernen der Daten Rauschen aufweisen Er erwähnte nicht einmal, was zu tun war.
Bei der Implementierung von Simple Perceptron wurde das Lernen fortgesetzt, "bis der Fehler Null wurde".
In diesem Fall würde die vorherige Implementierung beispielsweise die Parameter für immer anpassen, wenn die Daten wie in der folgenden Abbildung aussehen.
Natürlich können Anpassungen vorgenommen werden, um das Lernen zu beenden, wenn festgestellt wird, dass der Fehler das Minimum geworden ist, aber selbst in diesem Fall nimmt die Genauigkeit der Klassifizierung aufgrund des Vorhandenseins von Rauschen ab.
Selbst bei SVM weist die als SVM mit hartem Rand bezeichnete Implementierung die Schwäche auf, dass sie schwach ist, wenn die Daten mit Rauschen gemischt werden.
Daher war die Idee eine SVM mit weichem Rand, die selbst dann stark ist, wenn die Daten mit Rauschen gemischt werden.
Ein rauschresistentes Modell wie dieses SVM mit weichem Rand wird als robustes Modell bezeichnet.
In der realen Welt gibt es viele verrauschte Daten und SVMs mit weichen Rändern werden für die meisten Aufgaben verwendet.
SVM mit hartem Rand ist einfacher einzuhalten als SVM mit weichem Rand, daher werde ich diesmal nur SVM mit hartem Rand erläutern.
2.1 Hessens Formel
Wie Sie vielleicht in Lehrbüchern der High School Nummer II kennen, werde ich die hessische Formel erläutern, die zur Ableitung des Spielraums verwendet wird. Hier wird kein offizieller Beweis erbracht, nur wie es verwendet wird. Die Hessen-Formel ist eine Formel zur Berechnung des Abstands zwischen einem Punkt und einer geraden Linie und wird nach der folgenden Formel berechnet.
Punkt A.(x_0,y_0)Aus ergibt sich die Länge d der senkrechten Linie zur Geraden ax + um + c = 0\\
d=\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}
Bei der Ableitung der SVM wird das Folgende verwendet, das eine mehrdimensionale Erweiterung davon ist.
Datenpunkt A.=(x_1,x_2,...,x_m)Vom Superplane f(x)=w^Tx+\Die Entfernung zu Theta\\
d=\frac{|w^Tx+\theta|} {||w||}
2.2 Lagranges unentschlossene Multiplikatormethode
Die unbestimmte Multiplikatormethode von Lagrange wird verwendet, wenn der Spielraum unter den unten beschriebenen Bedingungen maximiert wird. Die unbestimmte Multiplikatormethode von Lagrange ist eine Methode zur Optimierung eines Problems als gewöhnliches Extremwertproblem unter bestimmten Bedingungen. Ein Beispiel für den zweidimensionalen Fall ist unten gezeigt. Problem beim Finden des Punktes $ (a, b) $, an dem $ f (x, y) $ der Maximalwert unter der Randbedingung $ g (x, y) = 0 $ ist
\left\{
\begin{array}{ll}
Maximieren& f(x,y) \\
Einschränkungen& g(x,y)=0
\end{array}
\right.
Denk an.\\
Zu diesem Zeitpunkt kann die folgende Funktion definiert werden, wenn der unentschlossene Multiplikator $ \ lambda $ betrachtet wird, der als Lagrange-Multiplikator bezeichnet wird.
L(x,y,\lambda)=f(x,y)-\lambda g(x,y) \\
Punkt(a,b)damit\frac{\partial g}{\partial x}\neq0 und\frac{\partial g}{\partial y}\Wenn neq 0\\
\frac{\partial L}{\partial x}=\frac{\partial L}{\partial y}=\frac{\partial L}{\partial \lambda}=0 \\
Durch Finden des Punktes $ (x, y) $, der die Bedingung als Stopppunkt erfüllt, kann der Maximalwert $ (x, y) $ gefunden werden.
Auch hier bezieht sich der Stopppunkt auf den Punkt, an dem die Differenzierung 0 wird. SVM wird unter Verwendung des Folgenden verallgemeinert, was eine Erweiterung auf allgemein mehrdimensional ist. Unter $ M $ -Beschränkungen ist $ g_k (x_1, ..., x_n) = 0, (k = 1, ..., M) $ Problem beim Finden des n-dimensionalen Punktes $ x = (x_1, ..., x_n) $ wobei $ f (x_1, ..., x_n) $ der Maximalwert ist
\left\{
\begin{array}{ll}
Maximieren& f(x_1,...,x_n) \\
Einschränkungen& g_k(x_1,...,x_n)=0,(k=1,...,M)
\end{array}
\right.
Denk an.\\
Zu diesem Zeitpunkt wurde ein unentschlossener Multiplikator als Lagrange-Multiplikator bezeichnet\lambda=(\lambda_1,...,\lambda_M)In Anbetracht dessen kann die folgende Funktion definiert werden.\\
L(x_1,...,x_n,\lambda)=f(x_1,...,x_n)-\sum_{k=1}^M\lambda_k g_k(x_1,...,x_n) \\
Punkt(x_1,...,x_M)damit\nabla g_k=(\frac{\partial f}{\partial x_1},...,\frac{\partial f}{\partial x_n})\neq (0,...,0)Wann,\\
N+M Bedingungen:\frac{\partial L}{\partial \alpha}=0(\alpha=x_1,...,x_n,\lambda_1,...,\lambda_M)\\
Punkte zu treffen(x_1,...,x_n)Der Punkt, der zum Maximalwert wird, indem er als Stopppunkt ermittelt wird(x_1,...,x_n)Ist gesucht.
2.3. KKT-Bedingungen (Karush-Kuhn-Tucker)
Betrachten Sie ein mathematisches Programmierproblem mit den folgenden Ungleichheitsbeschränkungen für die differenzierbaren Funktionen $ f und g_i $.
\left\{
\begin{array}{ll}
Minimieren& f(x) \\
Einschränkungen& g_i(x) \leq 0 (i=1,...,m)
\end{array}
\right.
Die folgende Formel ist die KKT-Bedingung für das Obige.
\left\{
\begin{array}{l}
\nabla f(\hat{x})+\sum_{i=1}^m \hat{\lambda_i} \nabla g_i(\hat{x})=0 \\
\hat{\lambda_i} \geq 0,g_i(\hat{x})\leq 0,\hat{\lambda_i} g_i(\hat{x}) = 0 (i=1,...,m)
\end{array}
\right.
Hier mit der obigen Formel
\hat{\lambda_i} \geq 0,g_i(\hat{x})\leq 0,\hat{\lambda_i} g_i(\hat{x}) = 0 (i=1,...,m)
Gibt an, dass mindestens eines von $ \ hat {\ lambda_i} und g_i (\ hat {x}) $ für jedes $ i $ 0 ist, was allgemein als Komplementaritätsbedingung bezeichnet wird.
2.4 Ableitung der SVM mit hartem Rand
Wenn die Gesamtzahl der Trainingsdaten n ist, wird der Mindestabstand d zwischen den Trainingsdaten und der Superplane unten durch "2.1. Hessische Formel" angegeben.
d=min_{i=1,...,n}\{\frac{|w^Tx_i+\theta|}{||w||}\} \\
Hier ist $ min_ {i = 1, ..., n} $ eine Funktion, die den Wert zurückgibt, wenn $ i $ den kleinsten Wert unter $ 1 bis n $ im Berechnungsergebnis annimmt.
Ich möchte $ w $ und $ \ theta $ finden, die diesen Mindestabstand $ d $ maximieren. Die Formel hierfür lautet wie folgt.
d_{max}=max_{w,\theta}[min_{i=1,...,n}\{\frac{|w^Tx_i+\theta|}{||w||}\}]
Hier ist $ max_ {w, \ theta} $ eine Funktion, die den Wert mit dem größten Berechnungsergebnis in der Funktion unter den möglichen $ w $ und $ \ theta $ zurückgibt.
In diesem Moment,
d_{max}=max_{w,\theta}[\frac{1}{||w||}min_{i=1,...,n}\{|w^Tx_i+\theta|\}] \\
Kann ausgedrückt werden als.
min_{i=1,2,...,n}|w^Tx_i+\theta|=1
Dieser Wille
max_{w,\theta}\frac{1}{||w||} \\
Die Diskriminanzfunktion also\\
Vom Superplane zu den Trainingsdaten auf beiden Seiten M.=\frac{1}{||w||}Weg
\frac{2}{||w||}Breite von(Rand: Rand)haben.\\
max_{w,\theta}\frac{1}{||w||}Ist min von der rechnerischen Seite_{w,\theta}\frac{1}{2}||w||^Entspricht 2.\\
Auch das Lehrerlabel t_Mit i wird die Randbedingung min_{i=1,2,...,n}|w^Tx_i+\theta|=1 kann wie folgt geschrieben werden.\\
t_i(w^Tx_i+\theta)\geq 1,(i=1,2,...,n) \\
Wenn die Berechnungsergebnisse der Lehrerdaten $ t_i $ und der Diskriminanzfunktion $ w ^ Tx_i + \ theta $ inkonsistent sind, ist $ t_i (w ^ Tx_i + \ theta) <1
\left\{
\begin{array}{l}
min_{w,\theta}\frac{1}{2}||w||^2 \\
Einschränkungen:t_i(w^Tx_i+\theta)\geq 1,(i=1,2,...,n)
\end{array}
\right.
Zu diesem Zeitpunkt kann die folgende Funktion definiert werden, wenn der unentschlossene Multiplikator $ \ lambda (\ lambda_i \ geq 0) $ betrachtet wird, der als Lagrange-Multiplikator bezeichnet wird. Es kann durch das Problem ersetzt werden, den Mindestwert dieser Funktion zu finden.
L(w,\theta,\lambda)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\lambda_i{t_i(w^Tx_i+\theta)-1} \\
Beim Minimalwert ist die Steigung von L.(Steigung)Sollte 0 sein\\
\frac{\partial L}{\partial b}=\sum_{i=1}^{N}\lambda_it_i=0 \\
\frac{\partial L}{\partial w}=w-\sum_{i=1}^{N}\lambda_i t_i x_i=0 \\
\frac{\partial L}{\partial w}Wenn die rechte Seite von transformiert wird, wird es wie folgt.\\
w=\sum_{i=1}^{N}\lambda_i t_i x_i \\
L(w,\theta,\lambda)Wird erweitert, um die Berechnung zu vereinfachen.\\
L(w,\theta,\lambda)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\lambda_it_iw^Tx_i+\lambda_it_i\theta-\lambda_i \\
L(w,\theta,\lambda)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\lambda_it_iw^Tx_i-\theta\sum_{i=1}^{N}\lambda_it_i+\sum_{i=1}^{N}\lambda_i \\
Hier\Theta\sum_{i=1}^{N}Es ist, weil es eine Konstante ist.\\
L(w,\theta,\lambda)Zu\sum_{i=1}^{N}\lambda_it_i=0,w=\sum_{i=1}^{N}\lambda_i t_i x_Ersatz i.\\
L(w,\theta,\lambda)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\lambda_it_ix_i\sum_{j=1}^{N}\lambda_j t_j x_j-\theta×0+\sum_{i=1}^{N}\lambda_i \\
L(w,\theta,\lambda)=\frac{1}{2}w\cdot w-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_i \\
L(w,\theta,\lambda)=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_i \\
L(w,\theta,\lambda)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_i \\
Dies kann wie folgt als duales Format organisiert werden.\\
\left\{
\begin{array}{l}
max_{\lambda}-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_i \\
Einschränkungen:\sum_{i=1}^{N}\lambda_it_i=0,\lambda_i\geq 0
\end{array}
\right. \\
Ein solches Problem wird als konvexes sekundäres Planungsproblem für $ \ lambda_i $ bezeichnet. Wenn die Lösung $ \ hat {\ lambda_i} (> 0) $ dieser Gleichung gefunden wird, wird $ \ hat {w} $ aus $ w = \ sum_ {i = 1} ^ {N} \ lambda_i t_i x_i $ erhalten. .. Durch dieses konvexe quadratische Design ist die lokale optimale Lösung immer die globale optimale Lösung. Die optimale Lösung $ \ hat {w}, \ hat {\ theta}, \ hat {\ lambda} $ muss die KKT-Komplementärbedingung $ \ hat {\ lambda_i} t_i (w ^ Tx_i + \ theta) -1 = 0 $ erfüllen Muss sein. Wenn die Ungleichheitsbedingung $ t_i (w ^ Tx_i + \ theta) -1> 0 $ erfüllt ist, muss $ \ lambda_i = 0 $ aus der Komplementärbedingung erfüllt sein. Daher ist diese Einschränkung nicht mehr gültig. Wenn $ t_i (w ^ Tx_i + \ theta) -1 = 0 $ ist, dann ist $ \ lambda_i> 0 $, sodass die Einschränkung gültig ist. Daraus wird nur die Einschränkung durch den Punkt (im Folgenden Unterstützungsvektor) aktiviert, der den Rand bestimmt, der $ t_i (w ^ Tx_i + \ theta) -1 = 0 $ erfüllt. Da die Anzahl der Unterstützungsvektoren erheblich kleiner als die ursprüngliche Anzahl der Abtastwerte ist, wird bei der Identifizierung viel Rechenaufwand eingespart.
Schließlich wird die SVM wie folgt abgeleitet.
f(x)=w^Tx+\theta,w=\sum_{i=1}^{N}\lambda_i t_i x_Von i\\
\hat{f}(x)=\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j +\theta
Der Wert von $ \ theta $ ergibt sich aus der Komplementationsbedingung $ t_i (w ^ Tx_i + \ theta) -1 = 0 $ wie folgt.
t_i(w^Tx_i+\theta)-1=0,w=\sum_{i=1}^{N}\lambda_i t_i x_Von i\\
t_i(\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j+\theta)-1=0 \\
T auf beiden Seiten_Teilen Sie durch i\\
\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j+\theta - \frac{1}{t_i}=0\\
\Übertragungsbedingungen außer Theta\\
\theta=\frac{1}{t_i} -\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j\\
\frac{1}{t_i}Ist t_i\in \{1,-1\}Weil es t ist_Weil gesagt werden kann, dass es äquivalent zu i ist\\
\theta=t_i -\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j
Wenn $ \ theta $ in einer tatsächlichen Implementierung gefunden wird, wird häufig der Durchschnitt unter Verwendung aller Unterstützungsvektoren ermittelt, die die Bedingungen unter Berücksichtigung der Stabilität bei der numerischen Berechnung erfüllen. Bei der Mittelwertbildung wird $ \ theta $ nach der folgenden Formel berechnet.
\theta = \frac{1}{N_S} \sum_{n \in S}(t_n - \sum_{m \in S}\hat{\lambda}_mt_m x_n^T x_m) \\
S:Satz von Unterstützungsvektoren(=\{s_1,s_2,...,s_{N_S}\}) \\
N_S:Anzahl der Unterstützungsvektoren
Schließlich wird die Identifikationsgrenze durch die folgende Formel gezogen.
\hat{f}(x)=\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j + \frac{1}{N_S} \sum_{n \in S}(t_n - \sum_{m \in S}\hat{\lambda}_mt_m x_n^T x_m)
3. Kernel-Trick
Durch die Optimierung der Marge kann erwartet werden, dass die Generalisierungsfähigkeit im Vergleich zum einfachen Perceptron verbessert wird. Die bisherige Implementierung kann jedoch nur linear trennbare Probleme lösen. Ein Kernel-Trick wurde entwickelt, um dieses Problem zu lösen. Wie ich zu Beginn des Kernel-Tricks erklärt habe, besteht es darin, "Daten aus dem ursprünglichen Datenraum auf einen höherdimensionalen Raum abzubilden und eine lineare Datenanalyse für diesen höherdimensionalen Raum durchzuführen". Hier wird nur beschrieben, wie es implementiert wird, und es ist zu weit fortgeschritten, um zu erklären, warum es die Implementierung selbst nicht beeinflusst. Daher werde ich es weglassen. Die folgende Gleichung, die schließlich früher erhalten wurde, wird transformiert.
\hat{f}(x)=\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j + \frac{1}{N_S} \sum_{n \in S}(t_n - \sum_{m\in S}\hat{\lambda}_mt_m x_n^T x_m)
Mach das.
\hat{f}(x)=\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i K(x_i,x_j) + \frac{1}{N_S} \sum_{n \in S}(t_n - \sum_{m \in S}\hat{\lambda}_mt_m K(x_n,x_m)
$ K (\ cdot, \ cdot) $ ist eine Kernelfunktion. Wenn Sie mehr über Kernel-Tricks erfahren möchten, lernen Sie die Kernel-Methode kennen. Insbesondere ist es notwendig, den regenerativen nuklearen Hilbert-Raum, den Representer-Satz und den Mercer-Satz zu untersuchen.
4. SVM-Lernalgorithmus
Es gibt drei typische Methoden zur Optimierung von $ \ lambda $.
4.1. Lernen nach der Methode des steilsten Abstiegs
Die Methode mit dem steilsten Abstieg ist ein Algorithmus, der aus der Steigung der Funktion nach dem Minimalwert einer Funktion sucht. $ n $ Ermitteln Sie den Mindestwert dieser Funktion mit $ f (x) $ als Funktion, die den folgenden Vektor $ x = (x1, x2, ..., xn) $ als Argument verwendet. Die Gradientenmethode verwendet eine iterative Methode, um $ x $ näher an die Lösung zu bringen. Wenn sich die Lösung in der $ k $ -ten Iteration an der Position von $ x ^ (k) $ befindet, aktualisiert die Methode mit dem steilsten Abstieg den Wert wie folgt. Bei der Minimierung der Funktion
x^{(k+1)} = x^{(k)}-\alpha \nabla f(x^{(k)})
Beim Maximieren einer Funktion
x^{(k+1)} = x^{(k)}+\alpha \nabla f(x^{(k)})
Das Lernen verhält sich wie in der folgenden Abbildung dargestellt, die so aktualisiert wird, dass sie einen Hang hinunter rollt.
Die Figur ist zur Visualisierung eindimensional, das Gleiche gilt jedoch für mehrdimensionale Fälle.
Verwenden Sie eine beliebige Zahl für den Wert von $ \ alpha $. (Im Allgemeinen eine Zahl zwischen 0 und 1)
Wenn $ \ alpha $ zu groß ist, ist die Entfernung den Hügel hinunter mit einer Aktualisierung groß, und es ist nicht möglich, kleine Kurven zu fahren, sodass die Lücke zwischen dem tatsächlichen Mindestwert und dem berechneten ungefähren Wert groß ist.
Wenn $ \ alpha $ zu klein ist, erhöht sich der Rechenaufwand erheblich, da die Entfernung den Hang hinunter mit einer Aktualisierung kurz ist.
Daher ist das richtige Einstellen des Werts von $ \ alpha $ auch ein Schaufenster für Ingenieure des maschinellen Lernens.
Dieses Mal werden wir die Methode mit dem steilsten Abstieg implementieren, die am einfachsten zu implementieren ist.
Die Formulierung der Methode mit dem steilsten Abstieg zu SVM ist unten gezeigt. Betrachten Sie die Variable $ \ lambda $, die $ L (w, \ theta, \ lambda) $ maximiert.
\lambda_i^{(k+1)}=\lambda_i^{(k)}+\alpha \nabla L(w,\theta,\lambda) \\
\lambda_i^{(k+1)}=\lambda_i^{(k)}+\alpha \frac{\partial L(w,\theta,\lambda)}{\partial \lambda} \\
L(w,\theta,\lambda)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_Von i\\
\lambda_i^{(k+1)}=\lambda_i^{(k)}+\alpha (1-\sum_{j=1}^{N} \lambda_j t_i t_j x_i^T x_j) \\
\lambda_i^{(k+1)}=\lambda_i^{(k)}+\alpha (1-\sum_{j=1}^{N} \lambda_j t_i t_j K(x_i,x_j))
Die Variable $ \ lambda $ wird durch die obige Formel aktualisiert.
4.2. Lernen mit dem SMO-Algorithmus
Der SMO-Algorithmus ist eine Optimierungsmethode, bei der zwei zu optimierende Variablen ausgewählt und iterativ aktualisiert werden. Es wird auch in der weltberühmten SVM-Bibliothek LIBSVM verwendet. Die Implementierung selbst ist C ++ auf der folgenden Seite. http://web.cs.iastate.edu/~honavar/smo-svm.pdf http://www.cs.mcgill.ca/~hv/publications/99.04.McGill.thesis.gmak.pdf Ich werde hier nicht mehr darauf eingehen, aber ich werde es mit einem Kommentar veröffentlichen.
4.3. Lernen durch probabilistische Gradientenabstiegsmethode
Die probabilistische Gradientenabstiegsmethode (SGD) ist für Laien eine Verbesserung gegenüber der Methode des steilsten Abstiegs, dem Batch-Lernen, gegenüber dem Online-Lernen. In einem kürzlich erschienenen Papier wird eine Implementierung mit dem Namen Pegosas vorgeschlagen. http://ttic.uchicago.edu/%7Enati/Publications/PegasosMPB.pdf Durch die Verwendung der probabilistischen Gradientenabstiegsmethode scheint es, dass Online-Lernen mit SVM durchgeführt werden kann. Da wir die Details des Algorithmus hier nicht kennen, werden wir ihn weglassen. Ich möchte es bald implementieren.
5. SVM-Implementierungsbeispiel mit hartem Rand von Python
Es scheint möglich zu sein, aber der Unterstützungsvektor kann nicht berechnet werden oder ein seltsamer Unterstützungsvektor kann berechnet werden. Wahrscheinlich ist die Ursache der Implementierungsteil der Methode mit dem steilsten Abstieg, der die Anzahl der Aktualisierungen bestimmt, um einen Fehler zu machen. Wenn der Wert des Lagrange-Multiplikators konvergiert, scheint der Unterstützungsvektor richtig gefunden zu werden. Wenn Sie die Ursache kennen, lassen Sie es mich bitte wissen. Als ich als Student SVM einmal implementiert habe, hatte ich keinen so seltsamen Stolperstein, also ist es eher ein Rätsel. (Der damalige Quellcode ging verloren) Da der Unterstützungsvektor beim Überlaufen mit der Aktualisierungsformel der Methode mit dem steilsten Abstieg nicht berechnet wird, Wenn ich motiviert werde, setze ich eine Obergrenze für den Wert.
# -*- coding: utf-8 -*-
#Dateiname ist svm.py
import numpy as np
import random
from math import fabs
from scipy.linalg import norm
import matplotlib.pyplot as plt
#SVM-Klasse
class svm:
#Anfangswerteinstellung
def __init__(self,kernel='linear',sigma=1.,degree=1.,threshold=1e-5,loop=500,LR=0.2):
self.kernel = kernel
#Im Fall eines linearen Kernels entspricht dies dem Setzen aller Parameter des polymorphen Kernels auf 1.
if self.kernel == 'linear':
self.kernel = 'poly'
self.degree = 1.
#RBF und Poly(Polygon)Parameter für den Kernel
self.sigma = sigma
self.degree = degree
#Schwellenwert zum Auffinden des Unterstützungsvektors
self.threshold = threshold
#Anzahl der Updates
self.loop = loop
#Lernrate
self.LR = LR
#Methode zur Berechnung des Kernels
def build_kernel(self,X):
self.K = np.dot(X,X.T)
if self.kernel == 'poly':
self.K = (1. + 1. / self.sigma * self.K)**self.degree
if self.kernel == 'rbf':
self.xsquared = (np.diag(self.K)*np.ones((1,self.N))).T
b = np.ones((self.N,1))
self.K -= 0.5*(np.dot(self.xsquared,b.T) + np.dot(b,self.xsquared.T))
self.K = np.exp(self.K/(2.*self.sigma**2))
#Methoden des Lernteils von SVM
def train_svm(self,X,t):
#Die steilste Abstiegsmethode begann
# self.Ersetzen Sie N durch die Anzahl der Zeilen von X.
self.N = np.shape(X)[0]
#Kernel berechnen
self.build_kernel(X)
count = 0
#Initialisierung des Lagrange-Multiplikators
lam = np.ones((self.N,1))
#Schleife für die angegebene Anzahl von Updates
while(count < self.loop):
for i in range(self.N):
ans = 0
for j in range(self.N):
#Teil der Erneuerungsformel für die Methode des steilsten Abstiegs
ans += lam[j]*t[i]*t[j]*self.K[i,j]
#Erneuerungsformel der steilsten Abstiegsmethode
lam[i] += self.LR * (1-ans)
#Da der Lagrange-Multiplikator 0 oder mehr ist, wird bei einem negativen Wert 0 eingesetzt.
if lam[i] < 0:
lam[i] = 0
count += 1
#Die steilste Abstiegsmethode endet
#Extrahieren Sie den Lagrange-Multiplikator, der den Schwellenwert überschreitet, als Unterstützungsvektor
self.sv = np.where(lam>self.threshold)[0]
#Anzahl der Unterstützungsvektoren
self.nsupport = len(self.sv)
print self.nsupport,"support vector found"
#Speichern Sie nur die Daten jedes Unterstützungsvektors
self.X = X[self.sv,:]
self.lam = lam[self.sv]
self.t = t[self.sv]
#Formel für w
self.w = np.array([0.,0.])
for i in range(self.nsupport):
self.w += self.lam[i]*self.t[i]*self.X[i]
#Berechnungsformel von θ
self.b = np.sum(self.t)
for n in range(self.nsupport):
self.b -= np.sum(self.lam*self.t*np.reshape(self.K[self.sv[n],self.sv],(self.nsupport,1)))
self.b /= len(self.lam)
#Klassifizierungsteil für lineare oder polymorphe Kernel
if self.kernel == 'poly':
def classifier(Y):
K = (1. + 1./self.sigma*np.dot(Y,self.X.T))**self.degree
self.y = np.zeros((np.shape(Y)[0],1))
for j in range(np.shape(Y)[0]):
for i in range(self.nsupport):
self.y[j] += self.lam[i]*self.t[i]*K[j,i]
return self.y
#Klassifizierungsteil für RBF-Kernel
elif self.kernel == 'rbf':
def classifier(Y):
K = np.dot(Y,self.X.T)
c = (1./self.sigma * np.sum(Y**2,axis=1)*np.ones((1,np.shape(Y)[0]))).T
c = np.dot(c,np.ones((1,np.shape(K)[1])))
aa = np.dot(self.xsquared[self.sv],np.ones((1,np.shape(K)[0]))).T
K = K - 0.5*c - 0.5*aa
K = np.exp(K/(2.*self.sigma**2))
self.y = np.zeros((np.shape(Y)[0],1))
for j in range(np.shape(Y)[0]):
for i in range(self.nsupport):
self.y[j] += self.lam[i]*self.t[i]*K[j,i]
self.y[j] += self.b
return self.y
else:
print "[Error] There is not this Kernel --",self.kernel
return
self.classifier = classifier
if __name__ == "__main__":
from svm import svm
#Trainingsdaten definieren
cls1 = [] #Klasse 1
cls2 = [] #Klasse 2
mean1 = [-1, 2]
mean2 = [1, -1]
cov = [[1.0,0.8], [0.8, 1.0]]
N = 100
#Erstellen Sie Trainingsdaten der Klasse 1 mit Zufallszahlen
cls1.extend(np.random.multivariate_normal(mean1, cov, N/2))
#Erstellen Sie Trainingsdaten der Klasse 2 mit Zufallszahlen
cls2.extend(np.random.multivariate_normal(mean2, cov, N/2))
#Datenmatrix X erstellen
X = np.vstack((cls1, cls2))
#Etikett erstellen t
t = []
for i in range(N/2):
t.append(1.0) #Klasse 1
for i in range(N/2):
t.append(-1.0) #Klasse 2
t = np.array(t)
#Trainingsdaten zeichnen
x1, x2 = np.array(cls1).transpose()
plt.plot(x1, x2, 'rx')
x1, x2 = np.array(cls2).transpose()
plt.plot(x1, x2, 'bx')
sv = svm(kernel='linear',degree=3)
#Lerne svm
sv.train_svm(X,t)
#Unterstützungsvektor zeichnen
for n in sv.sv:
plt.scatter(X[n,0], X[n,1], s=80, c='c', marker='o')
#Identifikationsgrenzen zeichnen
step = 0.1
f0,f1 = np.meshgrid(np.arange(np.min(X[:,0])-0.5, np.max(X[:,0])+0.5, step), np.arange(np.min(X[:,1])-0.5, np.max(X[:,1])+0.5, step))
out = sv.classifier(np.c_[np.ravel(f0),np.ravel(f1)]).T
out = out.reshape(f0.shape)
plt.contour(f0,f1,out,1)
plt.show()
6. Referenzen
6.1 Hessens Beamter
Wenn in 2 Dimensionen http://www004.upp.so-net.ne.jp/s_honma/urawaza/distance.htm Wenn in 3D http://yosshy.sansu.org/distance1.htm
6.2 Lagranges unbestimmte Multiplikatormethode
http://fd.kuaero.kyoto-u.ac.jp/sites/default/files/Lagrange1.pdf https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95
6.3. KKT-Bedingungen
http://www.msi.co.jp/nuopt/glossary/term_da98193bc878eb73f1624989004cfa809e13590a.html 6.4. SVM Machine Learning: An Algorithmic Perspective, Second Edition (Chapman & Hall/Crc Machine Learning & Pattern Recognition) [Data Science 6 Maschinelles Lernen mit R gelernt](http://www.amazon.co.jp/%E3%83%9E%E3%82%B7%E3%83%B3%E3%83%A9%E3% 83% BC% E3% 83% 8B% E3% 83% B3% E3% 82% B0-R% E3% 81% A7% E5% AD% A6% E3% 81% B6% E3% 83% 87% E3% 83% BC% E3% 82% BF% E3% 82% B5% E3% 82% A4% E3% 82% A8% E3% 83% B3% E3% 82% B9-6-% E8% BE% BB% E8 % B0% B7-% E5% B0% 86% E6% 98% 8E / dp / 4320019261 / ref = sr_1_2? E = UTF8 & qid = 1453064931 & sr = 8-2 & Schlüsselwörter =% E3% 83% 9E% E3% 82% B7% E3 % 83% B3% E3% 83% A9% E3% 83% BC% E3% 83% 8B% E3% 83% B3% E3% 82% B0) Masaaki Tsujitani (Autor), Kunio Takezawa (Autor), Akitetsu Kim (Bearbeiten) [Support Vector Machine](http://www.amazon.co.jp/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3 % 82% AF% E3% 83% 88% E3% 83% AB% E3% 83% 9E% E3% 82% B7% E3% 83% B3-% E6% A9% 9F% E6% A2% B0% E5% AD% A6% E7% BF% 92% E3% 83% 97% E3% 83% AD% E3% 83% 95% E3% 82% A7% E3% 83% 83% E3% 82% B7% E3% 83% A7% E3% 83% 8A% E3% 83% AB% E3% 82% B7% E3% 83% AA% E3% 83% BC% E3% 82% BA-% E7% AB% B9% E5% 86% 85 -% E4% B8% 80% E9% 83% 8E / dp / 4061529064 / ref = sr_1_1? Dh = UTF8 & qid = 1453064806 & sr = 8-1 & Schlüsselwörter =% E3% 82% B5% E3% 83% 9D% E3% 83% BC % E3% 83% 88% E3% 83% 99% E3% 82% AF% E3% 83% 88% E3% 83% AB% E3% 83% 9E% E3% 82% B7% E3% 83% B3) Ichiro Takeuchi (Autor), Masayuki Karasuyama (Autor) [Erste Mustererkennung](http://www.amazon.co.jp/%E3%81%AF%E3%81%98%E3%82%81%E3%81%A6%E3%81%AE% E3% 83% 91% E3% 82% BF% E3% 83% BC% E3% 83% B3% E8% AA% 8D% E8% AD% 98-% E5% B9% B3% E4% BA% 95-% E6% 9C% 89% E4% B8% 89 / dp / 4627849710 / ref = sr_1_1? Dh = UTF8 & qid = 1453065064 & sr = 8-1 & Schlüsselwörter =% E3% 81% AF% E3% 81% 98% E3% 82% 81% E3 % 81% A6% E3% 81% AE% E3% 83% 91% E3% 82% BF% E3% 83% BC% E3% 83% B3% E8% AA% 8D% E8% AD% 98) Yuzo Hirai (Autor) Pegasos: Primal Estimated sub-GrAdient SOlver for SVM Shai Shalev-Shwartz,Yoram Singer,Nathan Srebro
Recommended Posts