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

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. margin.png

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. kernel.png

"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. noise.png 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}}

hesse.png

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,||w||IstiWeil das Ergebnis nicht davon abhängtminWeil es aus der Funktion genommen werden kann

d_{max}=max_{w,\theta}[\frac{1}{||w||}min_{i=1,...,n}\{|w^Tx_i+\theta|\}] \\

Kann ausgedrückt werden als. w^Tx+\theta=0Wann,\frac{1}{||w||}Egal welchen Wert es braucht Da $ d_max $ zu 0 wird und $ w und \ theta $ nicht eindeutig bestimmt werden, werden die folgenden Einschränkungen hinzugefügt.

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 . Das heißt, das Erfüllen der oben genannten Einschränkungsbedingungen zeigt an, dass keine falsche Identifizierung aufgetreten ist. Unter der Bedingung, dass keine falsche Identifizierung aufgetreten ist\frac{1}{2}||w||^2$Kann auf das Problem der Minimierung reduziert werden. Wenn dies formuliert ist, wird es wie folgt.

\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. steepest.png 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

Einführung in das maschinelle Lernen - Hard Margin SVM Edition-
Einführung in das maschinelle Lernen
[Python] Einfache Einführung in das maschinelle Lernen mit Python (SVM)
Eine Einführung in das maschinelle Lernen
Super Einführung in das maschinelle Lernen
Einführung in das maschinelle Lernen Schreiben von Notizen
Einführung in TensorFlow - Hallo World Edition
Einführung in die Python-Umweltvorbereitung (Mac Edition)
Einführung in die Bibliothek für maschinelles Lernen SHOGUN
Einführung in Deep Learning ~ Dropout Edition ~
Einführung in Python Django (2) Mac Edition
Einführung in das maschinelle Lernen: Funktionsweise des Modells
Eine Einführung in OpenCV für maschinelles Lernen
Einführung in MQTT (Einführung)
Einführung in Scrapy (1)
Eine Einführung in maschinelles Lernen für Bot-Entwickler
Erste Schritte mit Supervisor
Einführung in Tkinter 1: Einführung
Einführung in PyQt
Einführung in Scrapy (2)
Einführung in Scrapy (4)
Einführung in discord.py (2)
[Für Anfänger] Einführung in die Vektorisierung beim maschinellen Lernen
Eine grobe Einführung in die neuronale maschinelle Übersetzungsbibliothek
Einführung in das maschinelle Lernen mit Simple Perceptron
Einführung in Lightning Pytorch
Erste Schritte mit Web Scraping
Einführung in nichtparametrische Felder
Einführung in EV3 / MicroPython
Einführung in die Python-Sprache
Einführung in die TensorFlow-Bilderkennung
Einführung in OpenCV (Python) - (2)
Maschinelles Lernen studieren-Pandas Edition-
Einführung in PyQt4 Teil 1
Einführung in Private Chainer
Einführung in das maschinelle Lernen mit scikit-learn-Von der Datenerfassung bis zur Parameteroptimierung
20200329_Einführung in die Datenanalyse mit Python 2nd Edition Personal Summary
Maschinelles Lernen mit Nogisaka 46 und Keyakizaka 46 Teil 1 Einführung
Einführung in die Socket-API in C Language 2nd Client Edition