Einführung

Ich habe SVM (Support Vector Machine) mit Python implementiert. Ich habe ["Erste Mustererkennung"](http://www.amazon.co.jp/ Erste Mustererkennung - Hirai-Yuzo / dp / 4627849710) als Lehrbuch verwendet.

Struktur dieses Artikels

Einführung
SVM
Marge maximieren
Hauptproblem
Lagrange unbestimmte Multiplikatormethode
KKT-Bedingungen
Doppeltes Problem
So finden Sie eine Lösung
Implementierung in Python
Ergebnis
abschließend
Zusätzliche Information

SVM

SVM ist eine lineare Diskriminierungslernmethode mit zwei Klassen, die den maximalen Spielraum realisiert. Lehrbüchern zufolge wird die Identifizierung anderer Klassen häufig durch $ K-1 $ Eins-zu-Viele-SVMs realisiert.

Margenmaximierung

Betrachten Sie den folgenden Datensatz. Wenn die Gesamtzahl der Daten $ N $ beträgt, ist $ i = 1, ..., N $.

\begin{align}
& D_L = \bigl\{(t_i, {\boldsymbol{x}}_i)\bigr\} \\
& t_i = \{-1, +1\}
\end{align}

Unter der Annahme, dass der Rand der linearen Diskriminanzfunktion $ \ kappa $ ist, gilt die folgende Gleichung für alle Trainingsdaten.

|\boldsymbol{w}^T{\boldsymbol{x}}_i + b| \geq \kappa

Der absolute Wert wird entfernt, indem der normalisierte Wert durch $ \ kappa $ durch $ \ boldsymbol {w} $ und $ b $ ersetzt und das Produkt mit dem Lehrer genommen wird.

t_i(\boldsymbol{w}^T{\boldsymbol{x}}_i + b) \geq 1 \tag{1}

Wie in der Abbildung gezeigt, kann der Abstand zwischen Klassen als Längenunterschied berechnet werden, der in Richtung $ \ boldsymbol {w} $ für die Daten projiziert wird, die der unterscheidenden Superebene am nächsten liegen.

In der Klasse von $ t_ {i} = + 1 $ haben die Daten, die der Identifikationshyperebene am nächsten liegen, die kleinste Projektionslänge in der Richtung $ \ boldsymbol {w} $ in dieser Klasse. In der Klasse von $ t_ {i} = -1 $ haben die Daten, die der Identifikationshyperebene am nächsten liegen, die längste Projektionslänge in der Richtung $ \ boldsymbol {w} $ in dieser Klasse. Der Zwischenklassenrand $ \ rho (\ boldsymbol {w}, b) $ wird durch die folgende Gleichung ausgedrückt.

\begin{align}
\rho(\boldsymbol{w}, b) &= \min_{\boldsymbol{x} \in C_{y=+1}}\frac{{\boldsymbol{w}}^T\boldsymbol{x}}{||\boldsymbol{w}||} - \max_{\boldsymbol{x} \in C_{y=-1}}\frac{{\boldsymbol{w}}^T\boldsymbol{x}}{||\boldsymbol{w}||} \\
\\
&= \frac{1-b}{||\boldsymbol{w}||} - \frac{-1-b}{||\boldsymbol{w}||} \\
\\
&= \frac{2}{||\boldsymbol{w}||} \tag{2}
\end{align}

Formel(2)Als,||\boldsymbol{w}||Es ist ersichtlich, dass der Zwischenklassenrand durch Minimieren maximiert wird. Außerdem wird der Zwischenklassenrand nur durch die Daten bestimmt, die der unterscheidenden Superebene am nächsten liegen. Die Daten, die dieser Identifikationshyperebene am nächsten liegen, werden als Unterstützungsvektor bezeichnet.

Hauptproblem

Erwägen Sie, den durch Gleichung (2) dargestellten Zwischenklassenrand unter der Bedingung von Gleichung (1) zu maximieren. Dies ist das Hauptproblem.

Bewertungsfunktion (Minimierung)

L_p(\boldsymbol{w}) = \frac{1}{2}{\boldsymbol{w}}^{T}\boldsymbol{w}

Ungleichheitsbeschränkung

t_i(\boldsymbol{w}^T{\boldsymbol{x}}_i + b) - 1 \geq 0

Lagrange unentschlossene Multiplikatormethode

Wir verwenden die unbestimmte Lagrange-Multiplikatormethode, um das Hauptproblem zu lösen.

Die unbestimmte Multiplikatormethode von Lagrange (Lagrange-Methode des Lagrange-Multiplikators) ist eine mathematische (analytische) Methode zur Optimierung unter Bindungsbedingungen. Betrachten Sie das Problem, den Extremwert einer anderen Funktion unter der Bedingung zu finden, dass die Werte einiger Funktionen für einige Variablen festgelegt sind. Durch die Vorbereitung von Konstanten (unbestimmter Multiplikator, Lagrange-Multiplikator) für jede Bindungsbedingung und die Berücksichtigung einer linearen Kopplung mit diesen als Koeffizienten als neue Funktion (der unbestimmte Multiplikator ist auch eine neue Variable) kann das Bindungsproblem als gewöhnlicher Extremwert angesehen werden. Es ist eine Methode, die als Problem gelöst werden kann. Zitiert aus [wikipedia](https://ja.wikipedia.org/wiki/Lagranges unentschlossene Multiplikatormethode)

Konkretes Beispiel

Ich habe keine Ahnung, wovon ich spreche, deshalb erkläre ich es mit einem konkreten Beispiel. Betrachten Sie die Maximierung von $ f (x, y) = y - x $ unter der Bedingung $ g (x, y) = x ^ 2 + y ^ 2 - 2 = 0 $. Das Problem ist, dass wir $ (x, y) $ am Umfang des Radius $ \ sqrt {2} $ verwenden, um den Abschnitt der geraden Linie zu maximieren.

Aus der Abbildung ist ersichtlich, dass $ f (x, y) $ unter der Randbedingung den Maximalwert von $ 2 $ annimmt, wenn sich der Kreis und die gerade Linie berühren. Lassen Sie uns dies mit der unbestimmten Lagrange-Multiplikatormethode lösen.

\begin{align}
L(x, y, \lambda) &= f(x, y) + \lambda g(x, y) \\
\\
&= y - x + \lambda(x^2 + y^2 - 2) \tag{3}
\end{align}

Die Lagrange-Funktion in Gleichung (3) wird teilweise durch $ x, y, \ lambda $ bzw. gleich $ 0 $ unterschieden.

\begin{align}
& \frac{\partial L}{\partial x} = -1 + 2\lambda x = 0 \\
& \frac{\partial L}{\partial y} = 1 + 2\lambda y = 0 \\
& \frac{\partial L}{\partial \lambda} = x^2 + y^2 - 2 = 0
\end{align}

Ersetzen Sie den 1. und 2. Ausdruck durch den 3. Ausdruck.

\begin{align}
& \Bigl(\frac{1}{2\lambda}\Bigr)^2 + \Bigl(-\frac{1}{2\lambda}\Bigr)^2 - 2 = 0 \\
\\
& \lambda = \pm \frac{1}{2}, x = \pm 1, y = \mp 1
\end{align}

Daher nimmt $ f (x, y) = y-x $ unter der Bedingung $ g (x, y) = 0 $ den Maximalwert von $ 2 $ an. Lassen Sie uns über diesen Maximalwert in drei Dimensionen nachdenken. Im 3D-Raum ist $ z = f (x, y) = y - x $ eine Steigung und $ g (x, y) = x ^ 2 + y ^ 2 - 1 = 0 $ ist ein Zylinder. Da wir den Maximalwert von $ z = y - x $ unter der Randbedingung $ g (x, y) = 0 $ ermitteln möchten, müssen wir nur den Maximalwert der $ z $ -Koordinate für die Oberfläche ermitteln, auf der sich die Steigung und der Zylinder schneiden. Es wird. Mit anderen Worten, der Maximalwert in Richtung der $ z $ -Achse, wenn ein Kreis von $ x ^ 2 + y ^ 2 - 2 = 0 $ auf die Ebene $ z = y - x $ projiziert wird, ist der Wert, den Sie finden möchten. Dies ist in der Abbildung dargestellt. Von der Seite betrachtet zeigt sich, dass der Maximalwert in Richtung der $ z $ -Achse im Schnittpunkt von Steigung und Zylinder $ 2 $ beträgt, was mit dem Berechnungsergebnis übereinstimmt.

Kommentar

Ich werde erklären, warum der Minimalwert mit der unbestimmten Lagrange-Multiplikatormethode erhalten werden kann. (Kann Fehler enthalten) Unter der Randbedingung $ g (\ boldsymbol {x}) = 0 $ (im Folgenden als Constraint-Oberfläche bezeichnet) befindet sich die Bewertungsfunktion $ f (\ boldsymbol {x}) $ in $ \ boldsymbol {x} ^ \ star $. Bei Verwendung des Maximalwerts muss $ \ boldsymbol {\ nabla} f (\ boldsymbol {x}) $ senkrecht zur Einschränkungsebene stehen. Dies liegt daran, dass $ f (\ boldsymbol {x}) $ entlang der Richtung der Einschränkungsebene weiter erhöht werden kann, vorausgesetzt, es ist nicht vertikal. Außerdem steht $ \ boldsymbol {\ nabla} g (\ boldsymbol {x}) $ senkrecht zur Einschränkungsebene. Daher sind in $ \ boldsymbol {x} ^ \ star $ $ \ boldsymbol {\ nabla} f und \ boldsymbol {\ nabla} g $ parallele Vektoren, und die folgende Gleichung gilt.

\boldsymbol{\nabla}f + \lambda\boldsymbol{\nabla}g = 0 \tag{4}

Hier ist die Lagrange-Funktion wie folgt definiert.

L(\boldsymbol{x}, \lambda) \equiv f(\boldsymbol{x}) + \lambda g(\boldsymbol{x})

Gleichung (4) und Einschränkungen können abgeleitet werden, indem die Lagrange-Funktion $ L (\ boldsymbol {x}, \ lambda) $ teilweise mit $ \ boldsymbol {x}, \ lambda $ differenziert wird. Durch Lösen dieses Problems kann der Stopppunkt $ \ boldsymbol {x} ^ \ star $ erhalten werden. In diesem $ \ boldsymbol {x} ^ \ star $ gibt es $ \ boldsymbol {x} $, das $ f (\ boldsymbol {x}) $ maximiert.

KKT-Bedingungen

Wenden wir nun die unbestimmte Multiplikatormethode dieses Lagrange auf das Hauptproblem an. Die Lagrange-Funktion ist wie folgt definiert.

\tilde{L}_{p}(\boldsymbol{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}{\boldsymbol{w}}^T\boldsymbol{w} - \sum_{i=1}^{N}\alpha_i(t_i(\boldsymbol{w}^T{\boldsymbol{x}}_i + b) - 1) \tag{5}

Hier ist $ \ boldsymbol {\ alpha} = {(\ alpha_1, ..., \ alpha_N)} ^ T (\ alpha_i \ geq 0) $ und $ \ alpha_i $ der unbestimmte Lagrange-Multiplikator. Die Lösung dieses Optimierungsproblems $ \ boldsymbol {w} _0, b_0 $ wird als Lösung erhalten, die die folgenden KKT-Bedingungen erfüllt.

** **

\begin{align}
& \left.\frac{\partial \tilde{L}_p(\boldsymbol{w}, b, \boldsymbol{\alpha})}{\partial \boldsymbol{w}}\right|_{\boldsymbol{w} = \boldsymbol{w}_0} = \boldsymbol{w}_0 - \sum_{i=1}^{N}\alpha_{i}t_i{\boldsymbol{x}}_i = 0 \tag{6} \\
& \frac{\partial \tilde{L}_p(\boldsymbol{w}, b, \boldsymbol{\alpha})}{\partial b} = \sum_{i=1}^{N}\alpha_{i}t_i = 0 \tag{7} \\
& \\
& t_i(\boldsymbol{w}^T{\boldsymbol{x}}_i + b) - 1 \geq 0 \tag{8} \\
& \\
& \alpha_i \geq 0 \tag{9} \\
& \\
& \alpha_i(t_i(\boldsymbol{w}^T{\boldsymbol{x}}_i + b) - 1) = 0 \tag{10}
\end{align}

Die Gleichungen (6) und (7) sind das partielle Differential gleich $ 0 $ der Lagrange-Funktion, Gleichung (8) ist die Randbedingung des Hauptproblems und Gleichung (10) ist die Komplementaritätsbedingung. Aus der Komplementaritätsbedingung von Gleichung (10)

t_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) - 1 > 0 \Rightarrow \alpha_i = 0 \\
t_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) - 1 = 0 \Rightarrow \alpha_i \geq 0

Die Komplementaritätsbedingung zeigt an, dass die diskriminante Superebene nur durch den Unterstützungsvektor bestimmt wird, ohne dass die Einschränkungsbedingung durch die anderen Daten als den Unterstützungsvektor beeinflusst wird. (Wenn ich nachschaue, scheinen die KKT-Bedingungen ziemlich tief zu sein, also werde ich mit diesem weichen Verständnis weitermachen.)

Doppeltes Problem

Erweitern Sie Gleichung (5) und ersetzen Sie die optimale Lösung und die Gleichungen (6) und (7).

\begin{align}
L_{d}(\boldsymbol{\alpha}) &= \frac{1}{2}{\boldsymbol{w}_{0}}^{T}\boldsymbol{w}_{0} - \sum_{i=1}^{N}\alpha_{i}t_{i}{\boldsymbol{w}_{0}}^{T}{\boldsymbol{x}}_{i} - b\sum_{i=1}^{N}\alpha_{i}t_{i} + \sum_{i=1}^{N}\alpha_{i} \\
&= \frac{1}{2}{\boldsymbol{w}_{0}}^{T}\boldsymbol{w}_{0} - {\boldsymbol{w}_{0}}^{T}\boldsymbol{w}_{0} - 0 + \sum_{i=1}^{N}\alpha_{i} \\
&= \sum_{i=1}^{N}\alpha_{i} - \frac{1}{2}{\boldsymbol{w}_{0}}^{T}\boldsymbol{w}_{0} \\
&= \sum_{i=1}^{N}\alpha_{i} - \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}t_{i}t_{j}{\boldsymbol{x}_i}^T{\boldsymbol{x}}_j
\end{align}

Aus Gleichung (6) wird die optimale Lösung durch die lineare Summe des unbestimmten Lagrange-Multiplikators und der Trainingsdaten dargestellt, so dass sie durch das Problem des Findens von $ \ alpha_ {i} $ ersetzt werden kann. Der optimale unbestimmte Lagrange-Multiplikator wird durch $ \ boldsymbol {\ alpha} $ erhalten, wodurch $ L_ {d} (\ boldsymbol {\ alpha}) $ maximiert wird. Dies wird in Bezug auf das Hauptproblem als Doppelproblem bezeichnet. Sei $ \ boldsymbol {1} $ der Vektor von $ N $ $ 1 $, $ \ boldsymbol {H} $ die durch die Trainingsdaten erzeugte Matrix und $ \ boldsymbol {t} $ der Lehrerdatenvektor.

\begin{align}
& \boldsymbol{1} = (1,...,1)^T \\
\\
& \boldsymbol{H} = (H_{ij} = {t_it_j\boldsymbol{x}_i}^T\boldsymbol{x}_j) \\
\\
& \boldsymbol{t} = (t_1,...,t_N)^T
\end{align}

Bewertungsfunktion (Maximierung)

L_{d}(\boldsymbol{\alpha}) = \boldsymbol{\alpha}^T\boldsymbol{1} - \frac{1}{2}\boldsymbol{\alpha}^T\boldsymbol{H}\boldsymbol{\alpha}

Gleichungsbeschränkung

\boldsymbol{\alpha}^T\boldsymbol{t} = 0

Die optimale Lösung des unbestimmten Langlange-Multiplikators, der durch Lösen des Doppelproblems erhalten wird, ist $ \ tilde {\ boldsymbol {\ alpha}} = (\ tilde {\ alpha} _1, ..., \ tilde {\ alpha} _N) ^ Bei gegebenem T $ kann die optimale Lösung wie folgt gefunden werden.

\begin{align}
& \boldsymbol{w}_0 = \sum_{i=1}^{N}\tilde{\alpha}_{i}t_i{\boldsymbol{x}}_i \\
& b_0 = \frac{1}{t_s} - {\boldsymbol{w}_0}^T\boldsymbol{x}_s
\end{align}

$ \ boldsymbol {x} _s, t_s $ repräsentieren Unterstützungsvektordaten und Lehrer.

So finden Sie eine Lösung

Wir haben abgeleitet, dass die Margenmaximierung erreicht werden kann, indem das Hauptproblem durch ein Doppelproblem ersetzt und das optimale $ \ tilde {\ boldsymbol {\ alpha}} $ gefunden wird. Verwenden Sie die Methode mit dem steilsten Abstieg, um programmgesteuert $ \ boldsymbol {\ alpha} $ zu finden, das $ L_ {d} (\ boldsymbol {\ alpha}) $ maximiert. Wir haben einen feinen Term hinzugefügt, um die Einschränkung des dualen Problems zu erfüllen, und $ L_ {d} (\ boldsymbol {\ alpha}) $ wie folgt neu definiert.

L_{d}(\boldsymbol{\alpha}) = \boldsymbol{\alpha}^T\boldsymbol{1} - \frac{1}{2}\boldsymbol{\alpha}^T\boldsymbol{H}\boldsymbol{\alpha} - \frac{1}{2}\beta\boldsymbol{\alpha}^T\boldsymbol{t}\boldsymbol{t}^T\boldsymbol{\alpha}

Aktualisieren Sie nun $ \ alpha_i $ mit der Methode mit dem steilsten Abstieg.

\begin{align}
{\alpha_i}' &= {\alpha_i} + \eta\frac{L_{d}(\boldsymbol{\alpha})}{\alpha_i}　\\
&= {\alpha_i} + \eta(1 - \sum_{j=1}^{N}\alpha_{j}t_{i}t_{j}{\boldsymbol{x}_i}^T{\boldsymbol{x}}_j - \beta\sum_{j=1}^{N}\alpha_{j}t_{i}t_j)
\end{align}

Ich habe bisher schwierige Berechnungen durchgeführt, aber die endgültige Formel ist wunderschön. Dadurch erhalten Sie $ \ boldsymbol {\ alpha} $, das $ L_ {d} (\ boldsymbol {\ alpha}) $ maximiert.

Implementierung in Python

Ich habe es wie folgt implementiert. Sie können $ \ alpha_i $ einfach aktualisieren. Aufgrund der Auswirkung des feinen Ausdrucks wird die Aktualisierung auch so durchgeführt, dass die Bedingung von $ \ boldsymbol {\ alpha} ^ T \ boldsymbol {t} = 0 $ erfüllt ist.

`svm.py`


import numpy
from matplotlib import pyplot
import sys

def f(x, y):
	return x - y

if __name__ == '__main__':

	param = sys.argv
	
	numpy.random.seed()
	N = 30
	d = 2
	X = numpy.random.randn(N, d)
	T = numpy.array([1 if f(x, y) > 0 else - 1 for x, y in X])
	alpha = numpy.zeros(N)
	beta = 1.0
	eta_al = 0.0001 # update ratio of alpha
	eta_be = 0.1 # update ratio of beta
	itr = 1000
	
	for _itr in range(itr):
		for i in range(N):
			delta = 1 - (T[i] * X[i]).dot(alpha * T * X.T).sum() - beta * T[i] * alpha.dot(T)
			alpha[i] += eta_al * delta
		for i in range(N):
			beta += eta_be * alpha.dot(T) ** 2 / 2

	index = alpha > 0
	w = (alpha * T).T.dot(X)
	b = (T[index] - X[index].dot(w)).mean()
	
	if '-d' in param or '-s' in param:
		seq = numpy.arange(-3, 3, 0.02)
		pyplot.figure(figsize = (6, 6))
		pyplot.xlim(-3, 3)
		pyplot.ylim(-3, 3)
		pyplot.plot(seq, -(w[0] * seq + b) / w[1], 'k-')
		pyplot.plot(X[T ==  1,0], X[T ==  1,1], 'ro')
		pyplot.plot(X[T == -1,0], X[T == -1,1], 'bo')

		if '-s' in param:
			pyplot.savefig('graph.png')

		if '-d' in param:
			pyplot.show()

Ergebnis

Die in der folgenden Abbildung gezeigten Ergebnisse wurden erhalten. Die Farbe der Datenpunkte repräsentiert die Klasse. Als ich die durch Berechnung erhaltenen geraden Linien zusammen zeichnete, erhielt ich ein solches Ergebnis.

abschließend

Es stellt sich heraus, dass das Hauptproblem für die Maximierung der Marge unter Ungleichheitsbedingungen festgelegt ist und dieses durch das doppelte Problem unter Verwendung der unbestimmten Lagrange-Multiplikatormethode ersetzt wird und das optimale $ \ boldsymbol {w} _0, b_0 $ erhalten werden kann. Ich tat.

Zusätzliche Information

2016/05/01 Ich habe einen Kommentar von @skyshk erhalten und den Code korrigiert.

SVM-Implementierung in Python