Implémentation SVM en python
introduction
J'ai implémenté SVM (Support Vector Machine) avec python. J'ai utilisé ["Première reconnaissance de formes"](http://www.amazon.co.jp/ Première reconnaissance de formes-Hirai-Yuzo / dp / 4627849710) comme manuel.
Structure de cet article
- Introduction
- SVM
- Maximiser la marge
- Problème principal
- Méthode du multiplicateur indéterminé de Lagrange
- Conditions KKT
- Double problème
- Comment trouver une solution
- Implémentation en python
- Résultat
- en conclusion
- Information additionnelle
SVM
SVM est une méthode d'apprentissage par discrimination linéaire à deux classes qui réalise la marge maximale. Selon les manuels, l'identification des autres classes est souvent réalisée par des SVM un-à-plusieurs $ K-1 $.
Maximisation de la marge
Considérez l'ensemble de données suivant. Si le nombre total de données est $ N $, alors $ i = 1, ..., N $.
\begin{align}
& D_L = \bigl\{(t_i, {\boldsymbol{x}}_i)\bigr\} \\
& t_i = \{-1, +1\}
\end{align}
En supposant que la marge de la fonction discriminante linéaire est $ \ kappa $, l'équation suivante est valable pour toutes les données d'apprentissage.
|\boldsymbol{w}^T{\boldsymbol{x}}_i + b| \geq \kappa
La valeur absolue est supprimée en remplaçant la valeur normalisée par $ \ kappa $ par $ \ boldsymbol {w} $ et $ b $ et en prenant le produit avec l'enseignant.
t_i(\boldsymbol{w}^T{\boldsymbol{x}}_i + b) \geq 1 \tag{1}
Comme le montre la figure, la marge inter-classes peut être calculée comme la différence de longueur projetée dans la direction $ \ boldsymbol {w} $ pour les données les plus proches du superplan d'identification.
Dans la classe $ t_ {i} = + 1 $, les données les plus proches de l'hyperplan d'identification ont la plus petite longueur de projection dans la direction $ \ boldsymbol {w} $ dans cette classe. Dans la classe $ t_ {i} = -1 $, les données les plus proches de l'hyperplan d'identification ont la plus longue longueur de projection dans la direction $ \ boldsymbol {w} $ dans cette classe. La marge interclasse $ \ rho (\ boldsymbol {w}, b) $ est exprimée par l'équation suivante.
\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}
formule(2)Que,
Problème principal
Envisagez de maximiser la marge interclasse représentée par l'équation (2) sous la contrainte de l'équation (1). C'est le problème majeur.
Fonction d'évaluation (minimisation)
L_p(\boldsymbol{w}) = \frac{1}{2}{\boldsymbol{w}}^{T}\boldsymbol{w}
Contrainte d'inégalité
t_i(\boldsymbol{w}^T{\boldsymbol{x}}_i + b) - 1 \geq 0
Méthode du multiplicateur indécis de Lagrange
Nous utilisons la méthode du multiplicateur indéterminé de Lagrange pour résoudre le problème principal.
La méthode du multiplicateur indéterminé de Lagrange (méthode de Lagrange du multiplicateur de Lagrange) est une méthode mathématique (analytique) d'optimisation dans des conditions contraignantes. Considérons le problème de trouver les extrémités d'une autre fonction sous la contrainte de fixer les valeurs de certaines fonctions pour certaines variables. En préparant des constantes (multiplicateur indéterminé, multiplicateur de Lagrange) pour chaque condition de liaison et en considérant un couplage linéaire avec celles-ci comme coefficients comme une nouvelle fonction (le multiplicateur indéterminé est également une nouvelle variable), le problème de liaison peut être considéré comme une valeur extrême ordinaire. C'est une méthode qui peut être résolue comme un problème. Extrait de [wikipedia](https://ja.wikipedia.org/wiki/Lagrange's indecided multiplicateur method)
Exemple concret
Je n'ai aucune idée de ce dont je parle, alors je vais l'expliquer avec un exemple concret. Envisagez de maximiser $ f (x, y) = y --x $ sous la condition $ g (x, y) = x ^ 2 + y ^ 2 --2 = 0 $. Le problème est que nous utilisons $ (x, y) $ sur la circonférence du rayon $ \ sqrt {2} $ pour maximiser la section de la droite.
D'après la figure, on peut voir que $ f (x, y) $ prend la valeur maximale de $ 2 $ sous la condition de contrainte lorsque le cercle et la ligne droite se touchent. Résolvons cela en utilisant la méthode du multiplicateur indéterminé de Lagrange.
\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}
La fonction de Lagrange dans l'équation (3) est partiellement différenciée par $ x, y, \ lambda $ et égale à $ 0 $, respectivement.
\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}
Remplacez les 1ère et 2ème expressions par la 3ème expression.
\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}
Par conséquent, sous la contrainte de $ g (x, y) = 0 $, $ f (x, y) = y-x $ prend la valeur maximale de 2 $. Pensons à cette valeur maximale en trois dimensions. Dans l'espace 3D, $ z = f (x, y) = y --x $ est une pente et $ g (x, y) = x ^ 2 + y ^ 2 --1 = 0 $ est un cylindre. Puisque nous voulons trouver la valeur maximale de $ z = y --x $ sous la condition de contrainte de $ g (x, y) = 0 $, nous devons seulement trouver la valeur maximale de la coordonnée $ z $ pour la surface où la pente et le cylindre se croisent. Il devient. En d'autres termes, la valeur maximale dans la direction de l'axe $ z $ lorsqu'un cercle de $ x ^ 2 + y ^ 2 --2 = 0 $ est projeté sur le plan $ z = y --x $ est la valeur que vous recherchez. Ceci est illustré sur la figure. Vu de côté, on constate que la valeur maximale dans la direction axiale $ z $ est de 2 $ à l'intersection de la pente et du cylindre, ce qui est cohérent avec le résultat du calcul.
Commentaire
Je vais expliquer pourquoi la valeur minimale peut être obtenue par la méthode du multiplicateur indéterminé de Lagrange. (Peut contenir des erreurs) Sous la condition de contrainte $ g (\ boldsymbol {x}) = 0 $ (ci-après appelée la surface de contrainte), la fonction d'évaluation $ f (\ boldsymbol {x}) $ est dans $ \ boldsymbol {x} ^ \ star $. En prenant la valeur maximale, $ \ boldsymbol {\ nabla} f (\ boldsymbol {x}) $ doit être perpendiculaire au plan de contrainte. C'est parce que $ f (\ boldsymbol {x}) $ peut être encore augmenté le long de la direction du plan de contrainte, en supposant qu'il n'est pas vertical. De plus, $ \ boldsymbol {\ nabla} g (\ boldsymbol {x}) $ est perpendiculaire au plan de contrainte. Par conséquent, dans $ \ boldsymbol {x} ^ \ star $, $ \ boldsymbol {\ nabla} f et \ boldsymbol {\ nabla} g $ sont des vecteurs parallèles, et l'équation suivante est vraie.
\boldsymbol{\nabla}f + \lambda\boldsymbol{\nabla}g = 0 \tag{4}
Ici, la fonction de Lagrange est définie comme suit.
L(\boldsymbol{x}, \lambda) \equiv f(\boldsymbol{x}) + \lambda g(\boldsymbol{x})
L'équation (4) et les contraintes peuvent être dérivées en différenciant partiellement la fonction de Lagrange $ L (\ boldsymbol {x}, \ lambda) $ avec $ \ boldsymbol {x}, \ lambda $. En résolvant cela, le point d'arrêt $ \ boldsymbol {x} ^ \ star $ peut être obtenu. Dans ce $ \ boldsymbol {x} ^ \ star $, il y a $ \ boldsymbol {x} $ qui maximise $ f (\ boldsymbol {x}) $.
Conditions KKT
Maintenant, appliquons la méthode du multiplicateur indéterminé de Lagrange au problème principal. La fonction de Lagrange est définie comme suit.
\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}
Ici, $ \ boldsymbol {\ alpha} = {(\ alpha_1, ..., \ alpha_N)} ^ T (\ alpha_i \ geq 0) $, et $ \ alpha_i $ est le multiplicateur indéterminé de Lagrange. La solution de ce problème d'optimisation $ \ boldsymbol {w} _0, b_0 $ est obtenue comme une solution qui satisfait les conditions KKT suivantes.
**
\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}
Les équations (6) et (7) sont le différentiel partiel égal à $ 0 $ de la fonction de Lagrange, l'équation (8) est la condition de contrainte du problème principal et l'équation (10) est la condition de complémentarité. À partir de la condition de complémentarité de l'équation (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
La condition de complémentarité indique que le superplan discriminant n'est déterminé que par le vecteur de support, sans l'effet de la condition de contrainte par des données autres que le vecteur de support. (Quand je regarde, les conditions KKT semblent être assez profondes, donc je vais continuer avec cette compréhension douce.)
Double problème
Développez l'équation (5) et remplacez-la par la solution optimale et les équations (6) et (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}
À partir de l'équation (6), la solution optimale est représentée par la somme linéaire du multiplicateur indéterminé de Lagrange et des données d'apprentissage, donc elle peut être remplacée par le problème de trouver $ \ alpha_ {i} $. Le multiplicateur indéterminé de Lagrange optimal est obtenu par $ \ boldsymbol {\ alpha} $, qui maximise $ L_ {d} (\ boldsymbol {\ alpha}) $. C'est ce qu'on appelle un problème double par rapport au problème principal. Soit $ \ boldsymbol {1} $ le vecteur de $ N $ $ 1 $, $ \ boldsymbol {H} $ la matrice créée par les données d'apprentissage et $ \ boldsymbol {t} $ le vecteur de données de l'enseignant.
\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}
Fonction d'évaluation (maximisation)
L_{d}(\boldsymbol{\alpha}) = \boldsymbol{\alpha}^T\boldsymbol{1} - \frac{1}{2}\boldsymbol{\alpha}^T\boldsymbol{H}\boldsymbol{\alpha}
Contrainte d'équation
\boldsymbol{\alpha}^T\boldsymbol{t} = 0
La solution optimale du multiplicateur indéterminé de Langlange obtenu en résolvant le problème dual est $ \ tilde {\ boldsymbol {\ alpha}} = (\ tilde {\ alpha} _1, ..., \ tilde {\ alpha} _N) ^ Étant donné T $, la solution optimale peut être trouvée comme suit.
\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ésentent les données vectorielles de support et les enseignants.
Comment trouver une solution
Nous avons déduit que la maximisation des marges peut être obtenue en remplaçant le problème principal par un problème double et en trouvant le $ \ tilde {\ boldsymbol {\ alpha}} $ optimal. Utilisez la méthode de descente la plus raide pour trouver par programme $ \ boldsymbol {\ alpha} $ qui maximise $ L_ {d} (\ boldsymbol {\ alpha}) $. Nous avons ajouté un terme fin pour satisfaire la contrainte du problème dual et redéfini $ L_ {d} (\ boldsymbol {\ alpha}) $ comme suit.
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}
Maintenant, mettez à jour $ \ alpha_i $ avec la méthode de descente la plus raide.
\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}
J'ai fait des calculs difficiles jusqu'à présent, mais la formule finale est magnifique. Cela vous donnera $ \ boldsymbol {\ alpha} $ qui maximise $ L_ {d} (\ boldsymbol {\ alpha}) $.
Implémentation en python
Je l'ai implémenté comme suit. Vous pouvez facilement mettre à jour $ \ alpha_i $. De plus, en raison de l'effet du terme fin, la mise à jour sera effectuée pour que la condition de $ \ boldsymbol {\ alpha} ^ T \ boldsymbol {t} = 0 $ soit satisfaite.
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()
résultat
Les résultats présentés dans la figure ci-dessous ont été obtenus. La couleur des points de données représente la classe. Quand j'ai dessiné ensemble les droites obtenues par calcul, j'ai obtenu un résultat comme celui-là.
en conclusion
Il s'avère que le problème principal pour maximiser la marge est défini dans des conditions d'inégalité, et il est remplacé par le problème dual en utilisant la méthode du multiplicateur indéterminé de Lagrange, et l'optimum $ \ boldsymbol {w} _0, b_0 $ peut être obtenu. J'ai fait.
Information additionnelle
- 2016/05/01 J'ai reçu un commentaire de @skyshk et j'ai corrigé le code.
Recommended Posts