Einführung

Zuvor habe ich die SVM mit hartem Rand in "SVM-Implementierung mit Python" zusammengefasst. Beim letzten Mal haben wir optimiert, indem wir dem Feinbegriff eine Einschränkungsbedingung hinzugefügt haben. Dieses Mal haben wir sie jedoch mithilfe einer Methode optimiert, die als aktive Mengenmethode bezeichnet wird. Ich habe ["Support Vector Machine"](https://www.amazon.co.jp/Support Vector Machine-Machine Learning Professional Series-Takeuchi-Ichiro / dp / 4061529064) als Lehrbuch verwendet.

Struktur dieses Artikels

Einführung
SVM mit weichem Rand
Hauptproblem
Doppeltes Problem
Aktive Set-Methode
Implementierung in Python
Ergebnis
abschließend

Weicher Rand SVM

Informationen zur Einführung von SVM finden Sie unter "Implementieren von SVM mit Python". Erklärt die Margenmaximierung, die unbestimmte Lagrange-Multiplikatormethode und die KKT-Bedingungen.

Hauptproblem

In der SVM mit weichem Rand werden nicht negative Variablen $ \ xi_i \ geq 0, i \ in [n] $ eingeführt und die Randbedingungen wie folgt definiert.

y_i(\boldsymbol w^T \boldsymbol x_i + b) \geq 1 - \xi_i, \ \ i \in [n]

Mit $ \ Xi_ {i} $ wird der Rand kleiner als $ 1 $, sodass $ \ boldsymbol x_i $ den Rand überschreiten und verschiedene Klassen eingeben kann. Wenn eine Fehlklassifizierung auftritt, ist dies $ \ xi_ {i}> 1 $. Wenn also $ \ sum_ {i \ in [n]} \ xi_ {i} $ kleiner oder gleich einer Ganzzahl $ K $ ist, tritt eine Fehlklassifizierung auf. Die Zahl ist auch weniger als $ K $. Daraus ist ersichtlich, dass eine Fehlklassifizierung unterdrückt werden kann, indem $ \ sum_ {i \ in [n]} \ xi_ {i} $ so klein wie möglich gemacht wird. Basierend auf dem Obigen ist das Hauptproblem der SVM mit weichem Rand wie folgt definiert.

\begin{align}
& \min_{\boldsymbol w, b, \boldsymbol \xi} \frac{1}{2}\|\boldsymbol w\|^2 + C\sum_{i \in [n]} \xi_{i} \\
& \\
& s.t. \ \ y_i(\boldsymbol w^T \boldsymbol x_i + b) \geq 1 - \xi_i, \ \ i \in [n] \\
& \\
& \ \ \ \ \ \ \ \ \xi_{i} \geq 0, \ \ i \in [n]
\end{align}

Der Koeffizient $ C $ ist eine positive Konstante, die als Regularisierungskoeffizient bezeichnet wird. Der erste Term der Zielfunktion hat die Bedeutung der Maximierung der Marge. Der zweite Term unterdrückt den Grad der Verletzung der ursprünglichen Einschränkung $ \ boldsymbol w ^ T \ boldsymbol x_i + b \ geq 1 $, so dass $ \ xi_ {i} $ so klein wie möglich ist. Der Regularisierungskoeffizient $ C $ ist ein Parameter zum Einstellen des Grades dieser Unterdrückung. Das Erhöhen von $ C $ nähert sich dem harten Rand, und bei $ C = \ infty $ fügt $ \ boldsymbol \ xi $ der Zielfunktion einen unendlichen Wert hinzu, wenn das Element $ \ boldsymbol \ xi $ einen Wert hat. Ist immer $ \ boldsymbol 0 $. Umgekehrt führt eine Verkleinerung von $ C $ zu einer Fehlklassifizierung.

Doppeltes Problem

Lassen Sie uns nun überlegen, das Hauptproblem auf zwei Arten auszudrücken. Führen Sie unbestimmte Lagrange-Multiplikatoren $ \ alpha_i \ geq 0, \ \ i \ in [n] $ und $ \ mu_i \ geq 0, \ \ i \ in [n] $ ein. Die Lagrange-Funktion ist wie folgt definiert.

L(\boldsymbol w, b, \boldsymbol \xi, \boldsymbol \alpha, \boldsymbol \mu)
 = \frac{1}{2}\|\boldsymbol w\|^2 + C\sum_{i \in [n]} \xi_{i} - \sum_{i \in [n]} \alpha_i(y_i(\boldsymbol w^T \boldsymbol x_i + b) - 1 + \xi_i) - \sum_{i \in [n]} \mu_i \xi_i \tag{1}

Die teilweise Differenzierung von $ L $ bei $ \ boldsymbol w, b, \ boldsymbol \ xi $ beträgt $ 0 $.

\begin{align}
& \frac{\partial L}{\partial \boldsymbol w} = \boldsymbol w - \sum_{i \in [n]}\alpha_{i}y_i{\boldsymbol{x}}_i = \boldsymbol 0 \tag{2} \\
& \\
& \frac{\partial L}{\partial b} = \sum_{i \in [n]}\alpha_{i}y_i = 0 \tag{3} \\
& \\
& \frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \tag{4} \\
\end{align}

Wenn man die Gleichungen (2), (3) und (4) in die Gleichung (1) einsetzt, ist das Ergebnis wie folgt.

L = -\frac{1}{2} \sum_{i, \ j \in [n]}\alpha_{i}\alpha_{j}y_{i}y_{j}{\boldsymbol{x}_i}^T\boldsymbol x_j + \sum_{i \in [n]}\alpha_i \tag{5}

Das doppelte Problem kann wie folgt ausgedrückt werden, indem die Randbedingungen (3) und (4) und $ \ xi_i \ geq 0 $ und Gleichung (5) für die Randbedingungen zusammengefasst werden.

\begin{align}
& \max_{\boldsymbol \alpha} -\frac{1}{2} \sum_{i, \ j \in [n]}\alpha_{i}\alpha_{j}y_{i}y_{j}{\boldsymbol{x}_i}^T\boldsymbol x_j + \sum_{i \in [n]}\alpha_i \\
& \\
& s.t. \ \ \sum_{i \in [n]}\alpha_{i}y_i = 0 \\
& \\
& \ \ \ \ \ \ \ \ \ 0 \leq \alpha_i \leq C, \ \ i \in [n]
\end{align}

Schließlich ist $ y_ {i} y_ {j} {\ boldsymbol x_i} ^ T \ boldsymbol x_j $ als $ i, j $ Element $ \ boldsymbol Q \ in \ mathbb {R} ^ {n \ times n Wenn definiert als} $, kann das doppelte Problem in einem Vektor ausgedrückt werden.

\begin{align}
& \max_{\boldsymbol \alpha} -\frac{1}{2} \boldsymbol \alpha^T\boldsymbol{Q\alpha} + \boldsymbol 1^T \boldsymbol \alpha \tag{6} \\
& \\
& s.t. \ \ \boldsymbol y^T \boldsymbol \alpha = 0 \tag{7} \\
& \\
& \ \ \ \ \ \ \ \ \boldsymbol 0 \leq \boldsymbol \alpha \leq C \boldsymbol 1 \tag{8}
\end{align}

Aktive Set-Methode

Die Zielfunktion wird unter den Randbedingungsgleichungen (7) und (8) maximiert. Dieses Mal verwenden wir die Active-Set-Methode als Standardlösung für eingeschränkte Optimierungsprobleme. Eine Menge von $ i $, so dass $ \ alpha_i = 0 $ oder $ \ alpha_i = C $, wird als aktive Menge für die Randbedingung der SVM mit weichem Rand bezeichnet. Die drei Mengen sind gemäß dem Zustand der Ungleichheitsbedingung der dualen Variablen wie folgt definiert.

\begin{align}
& O = \bigl\{ \ i \in [n] \ \ | \ \ \alpha_i = 0 \ \bigr\} \\
& M = \bigl\{ \ i \in [n] \ \ | \ \ 0 < \alpha_i < C \ \bigr\} \\
& I = \bigl\{ \ i \in [n] \ \ | \ \ \alpha_i = C \ \bigr\}
\end{align}

Wenn Sie wissen, zu welcher Menge jeder Fall gehört, dann ist $ \ alpha_i = 0, \ i \ in O $ und $ \ alpha_i = C, \ i \ in I $. Sie müssen nur das doppelte Problem für $ i \ in M $ lösen. Das doppelte Problem für die Menge $ M $ ist wie folgt (der Ableitungsprozess wird weggelassen).

\begin{align}
& \max_{\boldsymbol \alpha_M} -\frac{1}{2} {\boldsymbol \alpha}_M^T{\boldsymbol Q}_M \boldsymbol \alpha_M^{ \ } - C \boldsymbol 1^T {\boldsymbol Q}_{I, M} \boldsymbol \alpha_M^{ \ } + \boldsymbol 1^T \boldsymbol \alpha_M^{ \ }
& \\
& s.t. \boldsymbol y_M^T \boldsymbol \alpha_M^{ \ } = -C \boldsymbol 1^T \boldsymbol y_I^{ \ }
\end{align}

Für dieses Problem führen wir eine neue duale Variable, $ \ nu $, ein, um die folgende Lagrange-Funktion zu erhalten.

L = -\frac{1}{2} {\boldsymbol \alpha}_M^T{\boldsymbol Q}_M \boldsymbol \alpha_M^{ \ } - C \boldsymbol 1^T {\boldsymbol Q}_{I, M} \boldsymbol \alpha_M^{ \ } + \boldsymbol 1^T \boldsymbol \alpha_M^{ \ } - \nu \left(\boldsymbol y_M^T \boldsymbol \alpha_M^{ \ } + C \boldsymbol 1^T \boldsymbol y_I^{ \ }\right)

Wenn wir die Differenzierung für $ \ boldsymbol \ alpha_M ^ {} $ als $ \ boldsymbol 0 $ festlegen und zusammen mit der Gleichungsbeschränkungsbedingung anordnen, können wir sie auf die folgende lineare Gleichung reduzieren.

\begin{bmatrix}
\boldsymbol Q_M & \boldsymbol y_M^{ \ } \\
\boldsymbol y_M^T & 0
\end{bmatrix}
\begin{bmatrix}
\boldsymbol \alpha_M^{ \ } \\
\nu
\end{bmatrix} = -C
\begin{bmatrix}
\boldsymbol Q_{M, I} \boldsymbol 1 \\
\boldsymbol 1^T \boldsymbol y_I^{ \ }
\end{bmatrix} +
\begin{bmatrix}
\boldsymbol 1 \\
0
\end{bmatrix} \tag{9}

$ \ nu $ repräsentiert die Verzerrung $ b $, wenn der Punkt am Rand $ M $ ist. Mit anderen Worten, $ \ nu $, wenn das optimale $ \ boldsymbol \ alpha_M ^ {} $ erhalten wird, ist die optimale Vorspannung $ b $. Da die Menge $ \ {O, M, I } $ nicht im Voraus bekannt sein kann, löst die Methode der aktiven Menge Gleichung (9), indem sie einen geeigneten Anfangswert angibt und die aktive Menge aktualisiert. Schließlich wird der Optimierungsalgorithmus nach der Active-Set-Methode gezeigt.

Eingabe: Trainingsdaten $ (\ boldsymbol X, \ boldsymbol Y) $
Ausgabe: Optimale Lösung für das doppelte Problem $ \ boldsymbol \ alpha, $ Bias $ b $
Initialisierung: $ \ boldsymbol \ alpha \ leftarrow \ boldsymbol 0, \ \ I \ leftarrow \ phi, \ \ M \ leftarrow \ phi, \ \ O \ leftarrow [n] $
** während ** $ \ y_ {i} \ f (\ boldsymbol x_i) <1, \ \ i \ in O $ oder $ y_ {i} \ f (\ boldsymbol x_i)> 1, \ \ i \ $ i $ existiert in I $ ** do **
Wechseln Sie von $ I $ oder $ O $ zu $ M $ if \left|1 - y_{i_O} \ f(\boldsymbol x_{i_O}) \right| \geq \left|1 - y_{i_I} \ f(\boldsymbol x_{i_I}) \right|OderI = \phi
\ \ \ M \leftarrow M \cup i_O, O \leftarrow O \backslash i_O
if \left|1 - y_{i_O} \ f(\boldsymbol x_{i_O}) \right| < \left|1 - y_{i_I} \ f(\boldsymbol x_{i_I}) \right|OderO = \phi
\ \ \ M \leftarrow M \cup i_I, I \leftarrow I \backslash i_I
$ I_O = argmax_ {i \ in O} -y_i \ f (\ boldsymbol x_i), \ \ i_I = argmax_ {i \ in I} \ y_i \ f (\ boldsymbol x_i) $
repeat
Ersetzen Sie die Lösung der linearen Gleichung (9) durch $ \ boldsymbol \ alpha_M ^ {new} $
\boldsymbol d \leftarrow \boldsymbol \alpha_M^{new} - \boldsymbol \alpha_M^{ \ }
\boldsymbol \alpha_M^{ \ } \in [0, C]^{|M|}Maximale Schrittweite im Bereich von\eta \geq 0Durch\boldsymbol \alpha_M^{ \ } \leftarrow \boldsymbol \alpha_M^{ \ } + \eta \boldsymbol dAlter, Wechseln Sie von $ M $ zu $ I $ oder $ O $, wenn ein $ i $ eine Einschränkungsgrenze erreicht
until ( \ \boldsymbol \alpha_M^{ \ } = \boldsymbol \alpha_M^{new} \ )
end while

Bei der Optimierung von Soft Margin SVM durch die Active-Set-Methode Fügen Sie $ M $ die am meisten verletzenden Daten von $ I $ oder $ O $ hinzu und suchen Sie $ \ boldsymbol \ alpha_M ^ {} $ in diesem Zustand. Daten werden zwischen $ I $ oder $ O $ und $ M $ verschoben, und das Lernen endet, wenn keine Daten verletzt werden.

Implementierung in Python

Ich habe es wie folgt implementiert (Entschuldigung für den schmutzigen Code). Das Lernen konvergiert möglicherweise nicht, sodass Sie den Algorithmus möglicherweise falsch verstanden oder einen Fehler in der Implementierung gemacht haben. Ich kann es nicht selbst reparieren, bitte debuggen Sie es (Dogeza).

`activeset.py`


import numpy
from matplotlib import pyplot
import sys

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

def g(T, X, w, b):
	return T * (X.dot(w) + b)

def argmax(T, X, w, b, li):
	return numpy.argmax(g(T[li], X[li], w, b))

def solver(T, X, C, li, lm):
	Ti, Tm = T[li], T[lm]
	Xi, Xm = X[li], X[lm]
	Qm = (Tm.reshape(-1, 1) * Xm).dot(Xm.T * Tm)
	Qmi = (Tm.reshape(-1, 1) * Xm).dot(Xi.T * Ti)
	A = numpy.vstack((numpy.hstack((Qm, Tm.reshape(-1, 1))), numpy.hstack((Tm, 0))))
	B = -C * numpy.vstack((Qmi.sum(axis = 1).reshape(-1, 1), Ti.sum()))
	B[:-1] += 1
	return numpy.linalg.inv(A).dot(B)

def calc_eta(d, alpha):
	index = (d != 0) * (alpha[lm] >= 0) * (alpha[lm] <= C)
	eta_z = (0 - alpha[lm][index]) / d[index]
	eta_c = (C - alpha[lm][index]) / d[index]
	return numpy.hstack((eta_z[eta_z > 0], eta_c[eta_c > 0]))

def set_to_list(_set):
	return list(_set)

def move(_from, _to, value):
	_from.remove(value)
	_to.add(value)

def graph(T, X, w, param):
    seq = numpy.arange(-5, 5, 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], 'b^')

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


if __name__ == '__main__':

	param = sys.argv

	numpy.random.seed()
	N = 20
	dim = 2
	X = numpy.random.randn(N, dim)
	T = numpy.array([1 if f(x, y) > 0 else - 1 for x, y in X])
	X[T == 1, 1] += 0.5
	X[T == -1, 1] -= 0.5

    # initialize
	alpha = numpy.zeros(N)
	w = numpy.zeros(dim)
	b = 0
	C = 0.1
	I, M, O = set(), set(), set(range(N))
	li, lm, lo = set_to_list(I), set_to_list(M), set_to_list(O)

	while numpy.argwhere(g(T[lo], X[lo], w, b) < 1).size > 0 or numpy.argwhere(g(T[li], X[li], w, b) > 1).size > 0:
		flag = 0
		if I == set():
			io = argmax(-1 * T, X, w, b, lo)
			move(O, M, lo[io])
			flag = 1
		if O == set():
			ii = argmax(T, X, w, b, li)
			move(I, M, li[ii])
			flag = 1
		if flag == 0:
			io = argmax(-1 * T, X, w, b, lo)
			ii = argmax(T, X, w, b, li)
			if abs(1 - g(T[lo[io]], X[lo[io]], w, b)) >= abs(1 - g(T[li[ii]], X[li[ii]], w, b)):
				move(O, M, lo[io])
			else:
				move(I, M, li[ii])
		while M != set():
			li, lm, lo = set_to_list(I), set_to_list(M), set_to_list(O)
			solve = solver(T, X, C, li, lm)
			alpha_new = solve[:-1, 0]
			if numpy.array_equal(alpha[lm], alpha_new):
				break
			if alpha_new[(alpha_new < 0) + (alpha_new > C)].size == 0:
				alpha[lm] = alpha_new
			else:
				d = alpha_new - alpha[lm]
				eta = calc_eta(d, alpha)
				if eta.size == 0 or d[d != 0].sum() == 0:
					break
				alpha[lm] += eta.min() * d
				for i in numpy.argwhere(alpha[lm] <= 0)[:, 0]:
					move(M, O, lm[i])
				for j in numpy.argwhere(alpha[lm] >= C)[:, 0]:
					move(M, I, lm[j])

		w = ((alpha * T).reshape(-1, 1) * X).sum(axis = 0)
		b = solve[-1, 0]
		li, lm, lo = set_to_list(I), set_to_list(M), set_to_list(O)

	if '-d' in param or '-s' in param:
		graph(T, X, w, param)

Ergebnis

Ich habe mit dem gelernten $ \ boldsymbol w $ eine gerade Linie gezeichnet und das Ergebnis als Bild gespeichert. Die Ergebnisse sind unten gezeigt.

abschließend

Wir haben das Doppelproblem mit der Active-Set-Methode optimiert. Bitte beachten Sie, dass die Wahrscheinlichkeit groß ist, dass der Implementierungscode falsch ist.

[PYTHON] SVM-Optimierung durch aktive Set-Methode