introduction

Auparavant, j'ai résumé le SVM hard margin dans "SVM implementation with python". La dernière fois, nous avons optimisé en ajoutant une condition de contrainte au terme fin, mais cette fois nous l'avons optimisé à l'aide d'une méthode appelée méthode de l'ensemble actif. J'ai utilisé ["Support Vector Machine"](https://www.amazon.co.jp/Support Vector Machine-Machine Learning Professional Series-Takeuchi-Ichiro / dp / 4061529064) comme manuel.

Structure de cet article

Introduction
SVM à marge souple
Problème principal
Double problème
Méthode de réglage actif
Implémentation en python
Résultat
en conclusion

SVM à marge souple

Pour l'introduction de SVM, reportez-vous à "Implémentation SVM avec python". Explique la maximisation de la marge, la méthode du multiplicateur indéterminé de Lagrange et les conditions KKT.

Problème principal

Dans le SVM à marge souple, des variables non négatives $ \ xi_i \ geq 0, i \ in [n] $ sont introduites, et les conditions de contrainte sont définies comme suit.

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

$ \ Xi_ {i} $ rend la marge inférieure à $ 1 $, permettant à $ \ boldsymbol x_i $ de traverser la marge et d'entrer différentes classes. Si une erreur de classification se produit, $ \ xi_ {i}> 1 $, donc si $ \ sum_ {i \ in [n]} \ xi_ {i} $ est inférieur ou égal à un entier $ K $, l'erreur de classification se produira. Le nombre est également inférieur à $ K $. A partir de là, on peut voir que les erreurs de classification peuvent être supprimées en rendant $ \ sum_ {i \ in [n]} \ xi_ {i} $ aussi petit que possible. Sur la base de ce qui précède, le problème principal de la SVM à marge souple est défini comme suit.

\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}

Le coefficient $ C $ est une constante positive appelée coefficient de régularisation. Le premier terme de la fonction objectif a le sens de maximiser la marge. Le deuxième terme supprime le degré de violation de la contrainte d'origine $ \ boldsymbol w ^ T \ boldsymbol x_i + b \ geq 1 $ de sorte que $ \ xi_ {i} $ soit aussi petit que possible. Le coefficient de régularisation $ C $ est un paramètre d'ajustement du degré de cette suppression. L'augmentation de $ C $ s'approche de la marge ferme, et à $ C = \ infty $, $ \ boldsymbol \ xi $ ajoute une valeur infinie à la fonction objectif si l'élément $ \ boldsymbol \ xi $ a une valeur. Est toujours $ \ boldsymbol 0 $. Inversement, réduire la valeur de $ C $ permettra une mauvaise classification.

Double problème

Maintenant, considérons d'exprimer le problème principal de manière double. Introduisez les multiplicateurs indéterminés de Lagrange $ \ alpha_i \ geq 0, \ \ i \ in [n] $ et $ \ mu_i \ geq 0, \ \ i \ in [n] $. La fonction de Lagrange est définie comme suit.

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}

La différenciation partielle de $ L $ en $ \ boldsymbol w, b, \ boldsymbol \ xi $ est $ 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}

En remplaçant les équations (2), (3) et (4) par l'équation (1), le résultat est le suivant.

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}

Le problème dual peut être exprimé comme suit en résumant les conditions de contrainte équations (3) et (4) et $ \ xi_i \ geq 0 $ et l'équation (5).

\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}

Enfin, $ y_ {i} y_ {j} {\ boldsymbol x_i} ^ T \ boldsymbol x_j $ en tant que $ i, j $ élément $ \ boldsymbol Q \ in \ mathbb {R} ^ {n \ times n S'il est défini comme} $, le problème dual peut être exprimé dans un vecteur.

\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}

Méthode de jeu actif

La fonction objectif est maximisée sous les équations de contrainte (7) et (8). Cette fois, nous utiliserons la méthode de l'ensemble actif comme solution standard pour les problèmes d'optimisation contraints. L'ensemble de $ i $ tel que $ \ alpha_i = 0 $ ou $ \ alpha_i = C $ est appelé l'ensemble actif pour la condition de contrainte de la marge souple SVM. Les trois ensembles sont définis comme suit en fonction de l'état de la contrainte d'inégalité de la variable double.

\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}

Si vous savez à quel ensemble appartient chaque cas, alors $ \ alpha_i = 0, \ i \ in O $ et $ \ alpha_i = C, \ i \ in I $. Il vous suffit de résoudre le double problème pour $ i \ en M $. Le double problème pour l'ensemble $ M $ est le suivant (le processus de dérivation est omis).

\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}

Pour ce problème, nous introduisons une nouvelle variable double, $ \ nu $, pour obtenir la fonction de Lagrange suivante.

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)

Si nous définissons la différenciation pour $ \ boldsymbol \ alpha_M ^ {} $ comme $ \ boldsymbol 0 $ et la arrangeons avec la condition de contrainte d'équation, nous pouvons la réduire à l'équation linéaire suivante.

\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ésente le biais $ b $ lorsque le point sur la marge est $ M $. En d'autres termes, $ \ nu $ lorsque l'optimum $ \ boldsymbol \ alpha_M ^ {} $ est obtenu est le biais optimal $ b $. Puisque l'ensemble $ \ {O, M, I } $ ne peut pas être connu à l'avance, la méthode de l'ensemble actif résout l'équation (9) en donnant une valeur initiale appropriée et met à jour l'ensemble actif. Enfin, l'algorithme d'optimisation par la méthode de l'ensemble actif est affiché.

Entrée: données d'entraînement $ (\ boldsymbol X, \ boldsymbol Y) $
Résultat: Solution optimale pour le problème double $ \ boldsymbol \ alpha, $ Bias $ b $
Initialisation: $ \ boldsymbol \ alpha \ leftarrow \ boldsymbol 0, \ \ I \ leftarrow \ phi, \ \ M \ leftarrow \ phi, \ \ O \ leftarrow [n] $
** while ** $ \ y_ {i} \ f (\ boldsymbol x_i) <1, \ \ i \ in O $ ou $ y_ {i} \ f (\ boldsymbol x_i)> 1, \ \ i \ $ i $ existe dans I $ ** do **
Passer de $ I $ ou $ O $ à $ 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|OuI = \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|OuO = \phi
\ \ \ M \leftarrow M \cup i_I, I \leftarrow I \backslash i_I
Cependant, $ 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
Remplacez la solution de l'équation linéaire (9) par $ \ boldsymbol \ alpha_M ^ {new} $
\boldsymbol d \leftarrow \boldsymbol \alpha_M^{new} - \boldsymbol \alpha_M^{ \ }
\boldsymbol \alpha_M^{ \ } \in [0, C]^{|M|}Largeur de pas maximale dans la zone de\eta \geq 0Par\boldsymbol \alpha_M^{ \ } \leftarrow \boldsymbol \alpha_M^{ \ } + \eta \boldsymbol dâge, Passer de $ M $ à $ I $ ou $ O $ s'il y a un $ i $ qui atteint une limite de contrainte
until ( \ \boldsymbol \alpha_M^{ \ } = \boldsymbol \alpha_M^{new} \ )
end while

Dans l'optimisation de la marge souple SVM par la méthode de l'ensemble actif, Ajoutez les données les plus violentes de $ I $ ou $ O $ à $ M $, et trouvez $ \ boldsymbol \ alpha_M ^ {} $ dans cet état. Les données sont déplacées entre $ I $ ou $ O $ et $ M $, et l'apprentissage se termine lorsqu'il n'y a pas de données violées.

Implémentation en python

Je l'ai implémenté comme suit (désolé pour le code sale). Vous avez peut-être mal compris l'algorithme ou commis une erreur dans l'implémentation, car l'apprentissage peut ne pas converger. Je ne peux pas le réparer moi-même, alors veuillez le déboguer (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)

résultat

J'ai tracé une ligne droite en utilisant le $ \ boldsymbol w $ appris et j'ai enregistré le résultat sous forme d'image. Les résultats sont montrés plus bas.

en conclusion

Nous avons optimisé le problème dual en utilisant la méthode de l'ensemble actif. Veuillez noter qu'il est fort possible que le code d'implémentation soit incorrect.

[PYTHON] Optimisation SVM par la méthode de l'ensemble actif