[PYTHON] Algorithmus für maschinelles Lernen (Support Vector Machine)

Einführung

Schritt für Schritt zur Theorie, Implementierung in Python und Analyse mit scikit-learn über den Algorithmus, der zuvor in "Klassifikation des maschinellen Lernens" verwendet wurde. Ich werde mit lernen. Ich schreibe es zum persönlichen Lernen, daher möchte ich, dass Sie alle Fehler übersehen.

Diesmal über ** Support Vector Machine **. Obwohl seine Geschichte alt ist, ist es eine beliebte Methode im Bereich des maschinellen Lernens. Es hat eine hohe Generalisierungsleistung und war der stärkste Algorithmus, bis es durch tiefes Lernen in ILSVRC2012 besiegt wurde. Ich finde es ziemlich gut, sich daran zu erinnern (Wortschatz).

Die folgenden Seiten wurden auf diese Zeit verwiesen. Vielen Dank. Es scheint, dass es viele andere gute Bücher gibt, also beziehen Sie sich bitte auch darauf.

• Implementierung von PRML Kapitel 7 Support Vector Machine (SVM) in Python
• SVM (Support Vector Machine)
• Support Vector Machine verstehen
• Leicht verständliche SVM.
• Über SVM (Support Vector Machine)
• Support-Vektor-Maschinen von Hand berechnen und verstehen
• Einführung in SMO
• SMO-Implementierung mit Python + NumPy

Theorie

Ich habe versucht, die Theorie gut zu verstehen, aber sie war sehr kompliziert, und es gab Eintrag, der die Theorie fester berührt. Ich werde nur die Essenz beschreiben.

Grobe Übersicht

Die Support Vector Machine ist ein überwachter binärer Klassifikator wie Perceptron und Logistic Regression. Durch die Einführung des Konzepts des Unterstützungsvektors ist es möglich, Klassifizierungsprobleme (XOR usw.) zu klassifizieren, die eine hohe Generalisierungsleistung für unbekannte Daten aufweisen und mit der Kernel-Methode nicht linear klassifiziert werden können. Grob gesagt scheint es ein Klassifikator zu sein, der Perceptron die Margin-Maximierung und die Kernel-Methode gebracht hat.

Theorie

Stellen Sie sich eine Situation vor, in der für die folgenden beiden Merkmalsgrößen eine binäre Klassifizierung erforderlich ist. Der blaue Kreis und der rote Kreis sind die Trainingsdaten. Der blaue Punkt ist 1 (** positives Beispiel ) und der rote Punkt ist -1 ( negatives Beispiel **). Die am Rand gezeichnete grüne Linie sei $ y = ax + b $. Von den positiven und negativen Beispielen wird der Punkt, der der grünen Linie am nächsten liegt, als ** Stützvektor ** bezeichnet, und der Abstand vom Stützvektor zur Grenze wird als ** Rand ** bezeichnet.

Das Problem bei Support-Vektor-Maschinen besteht darin, die Lehrerdaten nach $ a $ und $ b $ zu fragen, die diesen Spielraum maximieren. In Wirklichkeit sind diese Fälle nicht nur praktisch, sondern es gibt viele Fälle, in denen sie nicht richtig unterteilt sind, sondern wir werden zunächst diesen einfachen Fall betrachten.

Der Grund, warum die Support-Vektor-Maschine in verschiedenen Fällen gut klassifizieren kann, besteht darin, dass sie dank dieser Randmaximierung unbekannte Daten gut klassifiziert und bei Verwendung der Daten in der Nähe der Grenzfläche davon abweicht. Es scheint einen Punkt zu geben, der den Wert nicht sehr beeinflusst.

Grundeinstellung

N Lehrerdaten $ \ boldsymbol {x} = (x_0, x_1, \ cdots, x_ {N-1}) $, Klassifizierungsbezeichnung $ \ boldsymbol {t} = (t_0, t_1, \ cdots, t_ { N-1}) $, der Grenzausdruck (als Diskriminanzfunktion bezeichnet) ist $ g (x) = \ boldsymbol {w} ^ Tx + w_0 $. $ \ Boldsymbol {w} $ ist ein Gewichtsvektor von $ \ boldsymbol {x} $.

Margenmaximierung

y=ax+bEin bestimmter Punktx_nDie Entfernung zu$\frac{|ax+b|}{\sqrt{a^2}}([Referenz](https://mathtrain.jp/tentotyokusen))Aberdiesesg(x)DenkenSienach.Irgendwannx_nWanng(x)Entfernung|r|Ist|r|=\frac{|g(x)|}{|w|}Wann表せる。ラベルt_nIst|t_n|=1$Und,t_ng(x)>=0であるこWannから、$|r|=\frac{t_n(\boldsymbol{w}^Tx_n+w_0)}{|w|}$Wannなる。

g(x)Nächstgelegener Punkt vonx_{min}Im|r_{min}|Um zu maximieren$|r_{min}|=\frac{t_{min}(\boldsymbol{w}^Tx_{min}+w_0)}{|w|}Ist das Maximum\boldsymbol{w}Wannw_0$Ich werde danach fragen.

Einschränkungen

Um die obige Gleichung zu maximieren, ist es umso besser, je kleiner der Nenner ist. Wenn er jedoch 0 erreicht, wird er unbestimmt (die Lösung kann nicht eindeutig bestimmt werden). Fügen Sie daher eine Einschränkung hinzu. Unter der Annahme, dass $ g (x) = 1 $ im positiven Beispiel und $ g (x) = -1 $ im negativen Beispiel ist, ist $ t_ng (x) = t_n (\ boldsymbol {w} ^ Tx_n + w_0) ) \ geq 1 $. Dies ist die Grenze und der nächste Punktt_ng(x_{min})=1Rand mit\frac{1}{|w|}Weil es maximiert|w|Sollte minimiert werden. Denken Sie darüber nach, später zu differenzieren\frac{1}{2}|w|^2Es ist sicher, es durch Minimieren zu ersetzen.

Organisieren,$t_n(\boldsymbol{w}^Tx_n+w_0) \geq 1Unter der Bedingung\frac{1}{2}|w|^2Minimieren\boldsymbol{w}Wannw_0$Ich werde danach fragen.

Lagranges unentschlossene Multiplikatormethode

Verwenden Sie eine Methode namens Lagranges unbestimmte Multiplikatormethode, um eine Funktion mit Einschränkungen wie der obigen Gleichung zu minimieren. Dies verwendet die Theorie, dass das Lösen des umgeschriebenen Problems das Lösen des ursprünglichen Problems bedeutet, das als ** duales Problem ** bezeichnet wird.

Einschränkungsausdruckh(x)=t_n(\boldsymbol{w}^Tx_n+w_0)-1Unterf(x)=\frac{1}{2}|w|^2Lagrange-Multiplikator zur Maximierung\lambdaEinführung der Lagrange-Funktion$L(w, w_0, \lambda)=f(w, w_0)-\sum_{i=1}^{N}\lambda_ih(w, w_0)$Ist definiert.

L(w,w_0,\lambda)=\frac{1}{2}|w|^2-\sum_{i=1}^{N}\lambda_i \{ t_i(\boldsymbol{w}^Tx_i+w_0)-1\}

Wenn Sie also ein partielles Differential für $ w $ und $ w_0 $ erstellen und das partielle Differential auf 0 setzen, ist die Lagrange-Funktion ein Ausdruck mit nur $ \ lambda $.

L(\lambda)=\sum_{n=1}^{N}\lambda_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\lambda_n\lambda_mt_nt_mx_n^Tx_m

Ist abgleitet. Die Einschränkung ist

\lambda_n\geq 0 \\
\sum_{i=1}^N\lambda_it_i=0

ist. Dies ersetzt das Problem, $ \ lambda $ zu finden, das $ L (\ lambda) $ maximiert.

Wenn die obige Gleichung teilweise durch $ w $ differenziert ist, $ w = \ sum_ {i = 1} ^ {N} \ lambda_it_ix_i $ kann erhalten werden.

Jetzt, wo wir $ w $ haben, werden wir nach $ w_0 $ fragen. $ g (x) = \ boldsymbol {w} ^ Tx + w_0 = \ sum_ {i = 1} ^ {N} \ lambda_it_ix_ix + w_0 $, und der Rand mit dem Unterstützungsvektor wird auf 1 gesetzt, sodass alle Unterstützung Über den Vektor

t_n(\sum_{m} \lambda_mt_mx_mx_n+w_0)=1

Ist festgelegt. Eigentlich deformiert

w_0=\frac{1}{N_M}\sum_{n}(t_n-\sum_{m}\lambda_mt_mx_mx_n)

Fragen Sie als. Zusammenfassend lässt sich sagen, dass nach $ \ lambda $ gefragt wird

w=\sum_{i=1}^{N}\lambda_it_ix_i \\
w_0=\frac{1}{N_M}\sum_{n}(t_n-\sum_{m}\lambda_mt_mx_mx_n)

Wird endlich berechnet. Wie finden Sie das $ \ lambda $? Tatsächlich kann es mit einer Methode namens SMO (Sequential Minimal Optimization) berechnet werden.

SMO

Zuerst werde ich das zu lösende Problem erneut veröffentlichen.

L(\lambda)=\sum_{n=1}^{N}\lambda_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\lambda_n\lambda_mt_nt_mx_n^Tx_m \\

Einschränkungen

\lambda_n\geq 0 ,\sum_{i=1}^N\lambda_it_i=0

Somit kann das Problem der Maximierung des beschränkten $ L (\ lambda) $ unter Verwendung von SMO gefunden werden.

[Wikipedia](https://ja.wikipedia.org/wiki/%E9%80%90%E6%AC%A1%E6%9C%80%E5%B0%8F%E5%95%8F%E9%A1 Gemäß% 8C% E6% 9C% 80% E9% 81% A9% E5% 8C% 96% E6% B3% 95) wird SMO auf Japanisch als ** sequentielle Methode zur Optimierung minimaler Probleme ** bezeichnet. Nähert sich der Lösung wie der Gradientenmethode iterativ, wählt zwei beliebige Variablen aus und wiederholt sie, bis sie konvergieren. Diese beliebigen 2 Variablen werden als Arbeitssatz bezeichnet. Der Schlüssel ist die Auswahl dieser 2 Variablen.

Als Fluss,

• Wählen Sie eine Variable $ \ lambda_1 $ aus, die die KKT-Bedingung verletzt
• Bestimmen Sie $ \ lambda_2 $
• Aktualisiere $ \ lambda_1, \ lambda_2 $

Dieser Vorgang wird wiederholt, bis keine Variablen mehr vorhanden sind, die die KKT-Bedingungen verletzen.

KKT-Bedingungen

Die Karush-Kuhn-Tucker-Bedingung, nachstehend die KKT-Bedingung genannt, bezieht sich auf die optimale Bedingung, die die Ableitung erster Ordnung erfüllen muss.

Tatsächlich wird die KKT-Bedingung auch in der obigen unbestimmten Lagrange-Multiplikatormethode verwendet.

(1) \frac{\partial{L}}{\partial{w}}=0 (2) \frac{\partial{L}}{\partial{w_0}}=0 (3) t_n(\boldsymbol{w}^Tx_n+w_0) \geq 1 (4) \lambda_n \geq 0 (5) \lambda_n(t_n(\boldsymbol{w}^Tx_n+w_0)-1) = 0

Es ist eine Bedingung. Insbesondere wird die fünfte Bedingung als ** Komplementaritätsbedingung ** bezeichnet.

Überprüfen Sie, ob KKT-Bedingungen verletzt wurden, und bestimmen Sie eine Variable

Komplementäre Bedingung $ \ lambda_n (t_n (\ boldsymbol {w} ^ Tx_n + w_0) -1) = 0 $ (1) Wenn $ \ lambda_n = 0 $, $ t_n (\ boldsymbol {w} ^ Tx_n + w_0) \ geq 1 $ (2) Wenn $ \ lambda_n> 0 $ ist, ist $ t_n (\ boldsymbol {w} ^ Tx_n + w_0) = 1 $

Wird abgeleitet, sodass Sie $ \ lambda $ auswählen können, das diese Anforderung nicht erfüllt. Nehmen wir umgekehrt an, dass eine Lösung gefunden wird, wenn $ \ lambda $ verschwindet. Lassen Sie $ \ lambda $, das hier ausgewählt wurde, $ \ lambda_1 $ sein.

Bestimmen Sie eine andere Variable

Wählen Sie die andere Variable in der folgenden Reihenfolge aus. Zuerst müssen Sie $ \ boldsymbol {w} $ und $ w_0 $ im aktuellen $ \ lambda $ finden. Die Fehlerfunktion zu diesem Zeitpunkt ist $ E_n = (\ boldsymbol {w} ^ Tx_n + w_0) -t_n $ Wird besorgt.

(1) Wählen Sie diese Option, um die Anzahl der variablen Aktualisierungen zu maximieren. Wählen Sie $ n $ aus, um den Fehler von $ E_1 $ im Fall von

$ \ lambda_1 $ zu maximieren.

(2) Existiert nicht an der Grenze

$ t_n (\ boldsymbol {w} ^ Tx_n + w_0) = jeder Punkt, der nicht 1 $ ist

(3) Verbleibend

Variablen aktualisieren

Ich habe entschieden, welche $$ lambda_1 $ und $ \ lambda_2 $ aktualisiert werden sollen, aber es gibt eine lineare Einschränkung $ \ sum_ {i = 1} ^ N \ lambda_it_i = 0 $ beim Aktualisieren. Aktualisieren Sie also unter dieser Bedingung Es gibt Bedarf. Das heißt, wenn Sie ein $ \ lambda $ aktualisieren, müssen Sie das andere $ \ lambda $ anpassen. Lassen Sie $ \ lambda_1 $ und $ \ lambda_2 $ nach dem Update $ \ lambda_1 ^ {new} $ bzw. $ \ lambda_2 ^ {new} $ sein.

\lambda_1^{new}t_1+\lambda_2^{new}t_2=\lambda_1t_1+\lambda_2t_2

Es wird sein. Dies ist unterteilt in den Fall von $ t_1 = t_2 $ und den Fall von $ t_1 \ ne t_2 $.

\lambda_1^{new}=\lambda_1+\frac{t_1(E_2-E_1)}{x_1^2+x_1x_2+x_2^2} \\
\lambda_2^{new}=\lambda_2+t_1t_2(\lambda_1-\lambda_1^{new})

Bekommen Eigentlich brauchten wir einen Prozess namens Clipping, um den möglichen Bereich von $ \ lambda_1 $ und $ \ lambda_2 $ zu finden, aber wir waren erschöpft.

Python-Implementierung

Zuallererst habe ich die Theorie erschöpft und sie ist zu lange her, also werde ich einfach Scikit-Learn implementieren. Es tut uns leid. Ich werde es definitiv eines Tages selbst umsetzen.

Implementierung von Scikit-Learn

Die Implementierung von Python ist ziemlich einfach. Unterstützung mit scikit-learn Verwenden Sie sklearn.svm.LinearSVC für die Klassifizierung von Vektormaschinen. .. Dieses Mal werden wir der Klarheit halber eine Stichprobe verwenden, in der 50 positive und 50 negative Beispiele richtig getrennt sind.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

%matplotlib inline

from sklearn import svm

fig, ax = plt.subplots()    
    
x1_1=np.ones(50)+10*np.random.random(50)
x1_2=np.ones(50)+10*np.random.random(50)
x2_1=-np.ones(50)-10*np.random.random(50)
x2_2=-np.ones(50)-10*np.random.random(50)

x1 = np.c_[x1_1,x1_2]
x2 = np.c_[x2_1,x2_2]
y  = np.array(np.r_[np.ones(50), -np.ones(50)])

model = svm.LinearSVC()
model.fit(np.array(np.r_[x1,x2]), y)

ax.scatter(x1[:,0],x1[:,1],marker='o',color='g',s=100)
ax.scatter(x2[:,0],x2[:,1],marker='s',color='b',s=100)

w = model.coef_[0]

x_fig = np.linspace(-12.,12.,100)
y_fig = [-w[0]/w[1]*xi-model.intercept_/w[1] for xi in x_fig]
ax.plot(x_fig, y_fig)

plt.show()

Es wurde so klassifiziert. Es ist natürlich.

Zusammenfassung

Ich bin am Ende erschöpft, aber ich denke, ich könnte die Atmosphäre erfassen (ich kann es nicht erfassen w). Dieses Mal haben wir die Grundlagen in den Grundlagen abgeleitet, die Beispiele (harter Rand), die linear trennbar sind und positive und negative Beispiele richtig klassifizieren können.

Für eine Support-Vektor-Maschine, die weiter fortgeschritten oder realitätsnaher ist, müssen Fälle berücksichtigt werden, in denen eine lineare Trennung nicht möglich ist (Kernel-Methode), und Fälle, in denen positive und negative Beispiele nicht richtig klassifiziert werden können (weicher Rand), sondern die grundlegende Theorie Ist fast das gleiche wie diesmal.

Ab dem nächsten Mal möchte ich mich mit diesem Bereich befassen.

** Ergänzung **: Geschrieben