[PYTHON] Maschinelles Lernen: Überwacht - Support Vector Machine
Ziel
Verstehen Sie die Support-Vektor-Maschine mit mathematischen Formeln und probieren Sie sie mit scicit-learn aus.
Es wird davon ausgegangen, dass Sie bereits Differentialintegration und lineare Algebra gelernt haben.
Theorie
Die Unterstützungsvektormaschine trainiert, um den Abstand zwischen dem Unterstützungsvektor und der Unterscheidungsgrenze basierend auf einer kleinen Datenmenge zu maximieren, die als Unterstützungsvektor bezeichnet wird und die Unterscheidungsgrenze bestimmt.
Obwohl die Support-Vektor-Maschine ein lineares Unterscheidungsmodell ist, wird sie häufig als ausgezeichnetes Klassifizierungsmodell verwendet, da sie aufgrund von Kernel-Tricks in hohem Maße auf nichtlineare Unterscheidungsprobleme erweiterbar ist.
Ursprünglich ein binäres Klassifizierungsmodell, wird es auch zur Klassifizierung, Regression und Erkennung von Anomalien in mehreren Klassen verwendet.
Klassifizierung nach Support Vector Machine
Ableitung der Support-Vektor-Maschine
Betrachten Sie zunächst das Problem der binären linearen Klassifizierung. Hier sind die Trainingsdaten $ x = (x_1, ..., x_n) $, der Zielwert ist $ t = (t_1, ..., t_n) $, aber $ t \ in \ {-1, 1 \ Wenn } $ und der Parameter $ w $ ist, ist das lineare Modell der Diskriminanzmodellausgabe $ y $
y(x) = w^T x + b
Es kann ausgedrückt werden als. Wir werden den Bias $ b $ hier explizit schreiben. Unter der Annahme einer linearen Trennbarkeit ist $ y (x_i) = 1 $, wenn $ t_i = 1 $ und $ y (x_i) = -1 $, wenn $ t_i = -1 $, also alle Trainingsdaten Über $ t_n y (x_n)> 0 $ gilt.
Die Unterstützungsvektormaschine zielt darauf ab, den Spielraum zu maximieren, der der Abstand von der Identifikationsgrenze $ y = w ^ Tx + b $ zu den nächsten Trainingsdaten ist, wie in der folgenden Abbildung gezeigt.
Aus der Formel des Abstands zwischen dem Punkt und der Ebene kann der Abstand zwischen dem Punkt der Trainingsdaten und der Identifikationsgrenzfläche durch die folgende Formel ausgedrückt werden.
\frac{|w^Tx + b|}{||w||}
Wenn nur die Trainingsdaten $ t_i y (x_i)> 0 $ berücksichtigt werden, die korrekt klassifiziert sind,
\frac{t_i ( w^Tx_i + b )}{||w||}
Es wird sein. Da der Rand der Abstand von den Trainingsdaten ist, der der Unterscheidungsgrenze am nächsten liegt, und die Parameter $ w und b $ erhalten werden sollen, die den Rand maximieren, kann die folgende Formel definiert werden.
\newcommand{\argmax}{\mathop{\rm argmax}\limits}
\argmax_{w, b} \frac{1}{||w||} \min_i \{ t_i (w^Tx_i + b) \}
Wenn Sie nun $ w, b $ so skalieren, dass $ t_i (w ^ Tx + b) = 1 $ ist, erfüllen alle Trainingsdaten die folgenden Einschränkungen.
t(w^Tx + b) \geq 1
des Weiteren,
\newcommand{\argmin}{\mathop{\rm argmin}\limits}
\argmin_{w, b} = \frac{1}{2}||w^2|| \\
t_i(w^Tx_i + b) \geq 1
Unterstützung des maschinellen Lernens von Vektoren
Um die Parameter einer Support-Vektor-Maschine zu finden, müssen Sie ein eingeschränktes Optimierungsproblem lösen. Wenn wir also den Lagrange-Multiplikator $ a = (a_1, ..., a_n) $ einführen, der $ a \ geq 0 $ ist,
L(w, b, a) = \frac{1}{2} ||w^2|| - \sum^n_{i=1} a_i \{ t_i(w^Tx_i + b) - 1 \}
Es wird sein. Wenn dieses $ L $ in Bezug auf die Parameter $ w und b $ differenziert und als 0 gelöst wird,
\begin{align}
\frac{\partial L}{\partial w} &= w - \sum^n_{i=1}a_i t_i x_i = 0\\
w &= \sum^n_{i=1}a_i t_i x_i \\
\frac{\partial L}{\partial b} &= \sum^n_{i=1}a_i t_i = 0 \\
0 &= \sum^n_{i=1}a_i t_i
\end{align}
Ersetzen Sie diese in $ L (w, b, a) $ und löschen Sie $ w, b $
\begin{align}
L(a) &= \frac{1}{2} w^T w - \sum^n_{i=1} a_i t_i w^T x_i - b \sum^n_{i=1} a_i t_i + \sum^n_{i=1} a_i \\
&= \frac{1}{2} w^T w - w^T w + \sum^n_{i=1} a_i \\
&= \sum^n_{i=1} a_i - \frac{1}{2} w^T w \\
&= \sum^n_{i=1} a_i - \frac{1}{2} \sum^n_{i,j=1} a_i a_j t_i t_j x^T_i x_j
\end{align}
Daher müssen wir das folgende eingeschränkte quadratische Planungsproblem lösen, das in Bezug auf das Hauptproblem als duales Problem bezeichnet wird. Da es eine Eins-zu-Eins-Entsprechung zwischen dem Hauptproblem und dem Doppelproblem gibt, ist es ausreichend, das Doppelproblem anstelle des Hauptproblems zu lösen.
L(a) = \sum^n_{i=1} a_i - \frac{1}{2} \sum^n_{i,j = 1} a_i a_j t_i t_j k(x_i, x_j) \\
a_i \geq 0 \\
\sum^n_{i=1} a_n t_n = 0
In der obigen Gleichung repräsentiert $ k (x_i, x_j) = x ^ T_i x_j $ eine Kernelfunktion, die hier ein linearer Kernel ist. Wenn Sie dies lösen, erhalten Sie eine spärliche Lösung, sodass nur eine kleine Datenmenge, die dem Unterstützungsvektor entspricht, $ a_i \ neq 0 $ ist und die anderen $ a_i = 0 $.
Wenn Sie den Strafbegriff $ \ frac {1} {2} \ lambda \ sum ^ n_ {i, j = 1} a_i a_j t_i t_j $ mit dem Hyperparameter $ \ lambda $ hinzufügen, damit die Randbedingung des dualen Problems erfüllt ist,
L(a) = \sum^n_{i=1} a_i - \frac{1}{2} \sum^n_{i,j = 1} a_i a_j t_i t_j k(x_i, x_j) - \frac{1}{2} \lambda \sum^n_{i,j = 1} a_i a_j t_i t_j
Es wird sein. Differenzieren von $ L (a) $ in Bezug auf $ a_i $
\frac{\partial L}{\partial a_i} = 1 - \sum^n_{j=1} a_j t_i t_j k(x_i, x_j) - \lambda \sum^n_{j=1} a_j t_i t_j
Es wird sein. Unter der Annahme, dass das Maximierungsproblem durch die Gradientenmethode mit einer Lernrate von $ \ eta $ gelöst wird,
\begin{align}
\hat{a_i} &= a_i + \eta \frac{\partial L}{\partial \alpha_i} \\
&= a_i + \eta \left( 1 - \sum^n_{j=1} a_j t_i t_j k(x_i, x_j) - \lambda \sum^n_{j=1} a_j t_i t_j \right)
\end{align}
Es wird sein. Konvergenz ist garantiert, da dieses Problem ein konvexes quadratisches Optimierungsproblem ist. Darüber hinaus speichert die Support-Vektor-Maschine $ n $ Support-Vektor-Daten und klassifiziert sie bei der Vorhersage basierend auf dem Support-Vektor.
Da der Parameter $ w $ von $ a $ abgeleitet ist, leiten wir schließlich den Bias $ b $ ab. Klassifizieren Sie anhand der neuen Daten $ x_j $ nach folgender Formel:
y(x) = \sum^m_{j=1} a_j t_j k(x_i, x_j) + b
Wenn es korrekt klassifiziert werden kann, ist $ t_i y (x_i) = 1 $ erfüllt.
t_i \left( \sum^m_{j=1} a_it_ik(x_i, x_j) + b \right) = 1
Es wird sein. Hier ist ab $ t ^ 2_i = 1 $,
\begin{align}
t_i \left( \sum^m_{j=1} a_j t_j k(x_i, x_j) + b \right) &= t^2_i \\
\sum^m_{j=1} a_j t_j k(x_i, x_j) + b &= t_i \\
\end{align}
Daher ist die Vorspannung $ b $
b = \frac{1}{n} \sum^n_{i=1} \left( t_i - \sum^m_{j=1} a_j t_j k(x_i, x_j) \right)
Es wird sein. Wenn die Anzahl der Daten 100.000 oder mehr beträgt, setzen Sie den Argumentverlust von SGDClassifier auf "Scharnier" und empfehlen Sie eine Unterstützungsvektormaschine nach der Methode des probabilistischen Gradientenabfalls.
Weicher Rand
Die Support-Vektor-Maschine im vorherigen Abschnitt wird als harter Rand bezeichnet, und ein weicher Rand, der eine geringe Anzahl von Fehlklassifizierungen zulässt, wird vorgeschlagen. Für weiche Ränder würden wir die Slack-Variable $ \ xi $ und den Hyperparameter $ C $ einführen, um die folgende Gleichung zu lösen:
\argmin_{w, b, \xi} \frac{1}{2} ||w||^2 + C \sum^n_{i=1} \xi_i \\
\xi_i \geq 0 \\
t_i (w^T x_i + b) \geq 1 - \xi_i \\
Kernel-Trick
Bis zum vorherigen Abschnitt haben wir den Fall betrachtet, in dem eine lineare Identifizierung möglich ist. Bei realen Problemen gibt es jedoch nur wenige linear identifizierbare Probleme. Wenn Sie eine nichtlineare Unterscheidung auf einer Support-Vektor-Maschine durchführen möchten, können Sie genau das gleiche Optimierungsproblem wie das lineare Unterscheidungsproblem aus der Kernelfunktion $ K (x_i, x_j) $ lösen. Das Vermeiden solcher nichtlinearer Transformationen wird als Kernel-Trick bezeichnet.
Kernelfunktionen, die auf Support-Vektor-Maschinen verwendet werden können, müssen die folgenden Bedingungen erfüllen, dass es sich um positive Wertfunktionen handelt.
\sum_{i,j} a_i a_j K(x_i, x_j) > 0
Die typischen Kernelfunktionen sind unten aufgeführt.
Linearer Kernel
Der lineare Kernel ist die lineare Unterstützungsvektormaschine bis zum vorherigen Abschnitt.
k(x_i, x_j) = x_i \cdot x_j
Polygonaler Kernel
Der polymorphe Kernel transformiert sich in höhere Dimensionen des Grades $ p $. $ P, \ gamma, c $ werden als Hyperparameter inkrementiert.
k(x_i, x_j) = (\gamma x_i \cdot x_j + c)^p
Kernel der Radial Basis Function (RBF)
Der Kern der Strahlungsbasisfunktion transformiert sich theoretisch in unendliche Dimensionen. Wird am häufigsten als nichtlinearer Kernel verwendet. Sie müssen den Hyperparameter $ \ gamma $ anpassen.
k(x_i, x_j) = \exp \left( -\gamma || x_i - x_j ||^2 \right)
Sigmaid Kernel
Der Sigmoid-Kernel ist eher eine halbfeste Wertfunktion als eine positive Wertfunktion, weist jedoch Ähnlichkeiten mit neuronalen Netzen auf.
k(x_i, x_j) = \tanh (\gamma x_i \cdot x_j + c)
Implementierung
Ausführungsumgebung
Hardware-
・ CPU Intel (R) Core (TM) i7-6700K 4,00 GHz
Software
・ Windows 10 Pro 1909 ・ Python 3.6.6 ・ Matplotlib 3.1.1 ・ Numpy 1.19.2 ・ Scikit-Learn 0.23.2
Programm zum Ausführen
Das implementierte Programm wird auf [GitHub] veröffentlicht (https://github.com/sho-watari/MachineLearning/blob/master/Supervised).
svm_classification.py
svm_regression.py
svm_anomaly.py
Ergebnis
Klassifizierung nach Support Vector Machine
Klassifizierung nach LinearSVC
Ich habe den Brustkrebs-Datensatz verwendet, der auch in Logistic Regression verwendet wurde.
Accuracy 94.74%
Precision, Positive predictive value(PPV) 96.92%
Recall, Sensitivity, True positive rate(TPR) 94.03%
Specificity, True negative rate(TNR) 95.74%
Negative predictive value(NPV) 91.84%
F-Score 95.45%
Vergleich des Hyperparameters C.
Durch Verringern des Hyperparameters $ C $ wird der Spielraum von der Diskriminanzgrenze vergrößert und durch Erhöhen des Spielraums verringert.
Vergleich der Kernelfunktionen
Die Diskriminanzgrenzen sind im linearen Kern gerade, aber im polygonalen Kern kreisförmig, im Sigmoid-Kern gekrümmt und im RBF-Kern komplexer.
Vergleich der Hyperparameter γ im RBF-Kernel
Durch Verringern des RBF-Kernel-Hyperparameters $ \ gamma $, der häufig bei der Durchführung einer nichtlinearen Diskriminierung verwendet wird, werden die Diskriminanzgrenzen gelockert und durch Erhöhen verschärft. Der Hyperparameter $ \ gamma $ ist ein überzeugendes Ergebnis, da er als Umkehrung der Verteilung angesehen werden kann.
Klassifizierung mehrerer Klassen
Wir haben den Iris-Datensatz für mehrklassifizierte Daten verwendet.
Rückgabe per Support Vector Machine
Die Daten des Regressionsproblems wurden ausgeführt, indem der Sinuskurve eine Zufallszahl hinzugefügt und $ k = 5 $ gesetzt wurde.
Abnormalitätserkennung durch Support-Vektor-Maschine
Die Erkennung von Anomalien verwendet eine 1-Klassen-Support-Vektor-Maschine. In der folgenden Abbildung werden andere Bereiche als der blaue Bereich als abnormale Werte behandelt.
Referenz
Christpher M. Bishop, "Pattern Recognition and Machine Learning", Springer, 2006.
Recommended Posts