Algorithme d'apprentissage automatique (machine vectorielle de support)

introduction

Pas à pas sur la théorie, l'implémentation en python et l'analyse à l'aide de scikit-learn sur l'algorithme précédemment repris dans "Classification of Machine Learning" J'étudierai avec. Je l'écris pour un apprentissage personnel, alors j'aimerais que vous oubliez toute erreur.

Cette fois sur ** Support Vector Machine **. Bien que son histoire soit ancienne, c'est une méthode populaire dans le domaine de l'apprentissage automatique. Il a des performances de généralisation élevées et était l'algorithme le plus puissant jusqu'à ce qu'il soit vaincu par l'apprentissage profond dans ILSVRC2012. Je pense que c'est assez bon de se souvenir de ça (vocabulaire).

Les sites suivants ont été mentionnés cette fois. Merci beaucoup. Il semble qu'il existe de nombreux autres bons livres, veuillez donc vous y référer également.

• Implémentation de PRML Chapter 7 Support Vector Machine (SVM) en Python
• SVM (Support Vector Machine)
• Comprendre la machine vectorielle de support
• SVM facile à comprendre.
• À propos de SVM (Support Vector Machine)
• Calcul manuel et compréhension des machines vectorielles de support
• Introduction à SMO
• SMO implémenté avec Python + NumPy

Théorie

J'ai essayé de bien comprendre la théorie, mais c'était très compliqué, et il y avait entrée qui touche plus fermement la théorie. , Je ne décrirai que l'essence.

Aperçu approximatif

La machine vectorielle de support est un classificateur binaire supervisé tel que Perceptron et régression logistique. En introduisant le concept de vecteur de support, il est possible de classer les problèmes de classification (XOR, etc.) qui ont des performances de généralisation élevées pour des données inconnues et qui ne peuvent pas être classés linéairement en utilisant la méthode du noyau. En gros, cela semble être un classificateur qui a apporté la maximisation des marges et la méthode du noyau à Perceptron.

Théorie

Prenons une situation où une classification binaire est requise pour les deux quantités de caractéristiques suivantes. Le cercle bleu et le cercle rouge sont respectivement les données d'entraînement. Le point bleu est 1 (** exemple positif ) et le point rouge est -1 ( exemple négatif **). Soit la ligne verte tracée sur la bordure $ y = ax + b $. Parmi les exemples positifs et négatifs, le point le plus proche de la ligne verte est appelé le ** vecteur de support **, et la distance du vecteur de support à la limite est appelée la ** marge **.

Le problème est que la machine à vecteurs de support demande aux données de l'enseignant $ a $ et $ b $ qui maximisent cette marge. En réalité, non seulement ces cas sont pratiques, mais il existe de nombreux cas où ils ne sont pas correctement divisés, mais nous examinerons d'abord ce cas simple.

La raison pour laquelle la machine à vecteurs de support peut bien classer dans divers cas est que grâce à cette maximisation des marges, elle classe bien les données inconnues et, en utilisant les données proches de la surface limite, elle dévie. Il semble y avoir un point que cela n'affecte pas beaucoup la valeur.

Réglage initial

N données enseignants $ \ boldsymbol {x} = (x_0, x_1, \ cdots, x_ {N-1}) $, étiquette de classification $ \ boldsymbol {t} = (t_0, t_1, \ cdots, t_ { N-1}) $, l'expression de la frontière (appelée fonction discriminante) est $ g (x) = \ boldsymbol {w} ^ Tx + w_0 $. $ \ Boldsymbol {w} $ est un vecteur de poids de $ \ boldsymbol {x} $.

Maximisation de la marge

y=ax+bUn certain pointx_nLa distance à$\frac{|ax+b|}{\sqrt{a^2}}([référence](https://mathtrain.jp/tentotyokusen))Maisçag(x)Pensez-y.Quelquepointx_nQuandg(x)Distance|r|Est|r|=\frac{|g(x)|}{|w|}Quand表せる。ラベルt_nEst|t_n|=1$Et,t_ng(x)>=0であるこQuandから、$|r|=\frac{t_n(\boldsymbol{w}^Tx_n+w_0)}{|w|}$Quandなる。

g(x)Point le plus proche dex_{min}Dans|r_{min}|Pour maximiser$|r_{min}|=\frac{t_{min}(\boldsymbol{w}^Tx_{min}+w_0)}{|w|}Est le maximum\boldsymbol{w}Quandw_0$Je vais demander.

Contraintes

Pour maximiser l'équation ci-dessus, plus le dénominateur est petit, mieux c'est, mais quand il atteint 0, il devient indéfini (la solution ne peut pas être déterminée de manière unique), alors ajoutez une contrainte. En supposant que $ g (x) = 1 $ dans l'exemple positif et $ g (x) = -1 $ dans l'exemple négatif, $ t_ng (x) = t_n (\ boldsymbol {w} ^ Tx_n + w_0) ) \ geq 1 $. C'est la limite et le point le plus prochet_ng(x_{min})=1Marge avec\frac{1}{|w|}Parce qu'il maximise|w|Doit être minimisé. Penser à se différencier plus tard\frac{1}{2}|w|^2Il est prudent de le remplacer en minimisant.

Organiser,$t_n(\boldsymbol{w}^Tx_n+w_0) \geq 1Sous condition\frac{1}{2}|w|^2Minimiser\boldsymbol{w}Quandw_0$Je vais demander.

La méthode du multiplicateur indécis de Lagrange

Pour minimiser une fonction avec des contraintes comme l'équation ci-dessus, utilisez une méthode appelée méthode du multiplicateur indéterminé de Lagrange. Cela utilise la théorie selon laquelle résoudre le problème réécrit signifie résoudre le problème d'origine, appelé le ** problème double **.

Expression de contrainteh(x)=t_n(\boldsymbol{w}^Tx_n+w_0)-1En dessous def(x)=\frac{1}{2}|w|^2Multiplicateur de Lagrange pour maximiser\lambdaIntroduction de la fonction Lagrange$L(w, w_0, \lambda)=f(w, w_0)-\sum_{i=1}^{N}\lambda_ih(w, w_0)$Est défini.

L(w,w_0,\lambda)=\frac{1}{2}|w|^2-\sum_{i=1}^{N}\lambda_i \{ t_i(\boldsymbol{w}^Tx_i+w_0)-1\}

Donc, si vous faites un différentiel partiel pour $ w $ et $ w_0 $ et que vous définissez le différentiel partiel sur 0, la fonction de Lagrange sera une expression avec seulement $ \ lambda $.

L(\lambda)=\sum_{n=1}^{N}\lambda_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\lambda_n\lambda_mt_nt_mx_n^Tx_m

Est dérivé. La contrainte est

\lambda_n\geq 0 \\
\sum_{i=1}^N\lambda_it_i=0

est. Cela remplace le problème de trouver $ \ lambda $ qui maximise $ L (\ lambda) $.

Si l'équation ci-dessus est partiellement différenciée par $ w , $ w = \ sum_ {i = 1} ^ {N} \ lambda_it_ix_i $$ peut être obtenu.

Maintenant que nous avons $ w $, nous allons demander $ w_0 . $ g (x) = \ boldsymbol {w} ^ Tx + w_0 = \ sum_ {i = 1} ^ {N} \ lambda_it_ix_ix + w_0 $$, et la marge avec le vecteur de support est définie sur 1, donc tout support À propos du vecteur

t_n(\sum_{m} \lambda_mt_mx_mx_n+w_0)=1

Est établi. En fait déformé

w_0=\frac{1}{N_M}\sum_{n}(t_n-\sum_{m}\lambda_mt_mx_mx_n)

Demandez comme. Pour résumer, après que $ \ lambda $ demande

w=\sum_{i=1}^{N}\lambda_it_ix_i \\
w_0=\frac{1}{N_M}\sum_{n}(t_n-\sum_{m}\lambda_mt_mx_mx_n)

Est enfin calculé. Alors, comment trouvez-vous que $ \ lambda $? En fait, il peut être calculé à l'aide d'une méthode appelée SMO (Sequential Minimal Optimization).

SMO

Tout d'abord, je republierai le problème à résoudre.

L(\lambda)=\sum_{n=1}^{N}\lambda_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\lambda_n\lambda_mt_nt_mx_n^Tx_m \\

Contraintes

\lambda_n\geq 0 ,\sum_{i=1}^N\lambda_it_i=0

Ainsi, le problème de la maximisation de la contrainte $ L (\ lambda) $ peut être trouvé en utilisant SMO.

[Wikipédia](https://ja.wikipedia.org/wiki/%E9%80%90%E6%AC%A1%E6%9C%80%E5%B0%8F%E5%95%8F%E9%A1 Selon% 8C% E6% 9C% 80% E9% 81% A9% E5% 8C% 96% E6% B3% 95), SMO est appelée ** méthode d'optimisation séquentielle des problèmes minimaux ** en japonais. Approche de manière itérative la solution, comme la méthode du gradient, en sélectionnant deux variables quelconques et en les répétant jusqu'à ce qu'elles convergent. Ces 2 variables arbitraires sont appelées Working Set, et comment sélectionner ces 2 variables est la clé.

En tant que flux,

• Sélectionnez une variable $ \ lambda_1 $ qui viole la condition KKT
• Déterminez $ \ lambda_2 $
• Mettre à jour $ \ lambda_1, \ lambda_2 $

Ce processus est répété jusqu'à ce qu'il n'y ait plus de variables qui enfreignent les conditions KKT.

Conditions KKT

La condition de Karush-Kuhn-Tucker, ci-après la condition KKT, fait référence à la condition optimale que la dérivée de premier ordre doit satisfaire.

En fait, la condition KKT est également utilisée dans la méthode du multiplicateur indéterminé de Lagrange ci-dessus.

(1) \frac{\partial{L}}{\partial{w}}=0 (2) \frac{\partial{L}}{\partial{w_0}}=0 (3) t_n(\boldsymbol{w}^Tx_n+w_0) \geq 1 (4) \lambda_n \geq 0 (5) \lambda_n(t_n(\boldsymbol{w}^Tx_n+w_0)-1) = 0

C'est une condition. En particulier, la cinquième condition est appelée ** condition de complémentarité **.

Vérifiez les violations de condition KKT et déterminez une variable

Condition complémentaire $ \ lambda_n (t_n (\ boldsymbol {w} ^ Tx_n + w_0) -1) = 0 $ (1) Si $ \ lambda_n = 0 $, $ t_n (\ boldsymbol {w} ^ Tx_n + w_0) \ geq 1 $ (2) Si $ \ lambda_n> 0 $, $ t_n (\ boldsymbol {w} ^ Tx_n + w_0) = 1 $

Sera dérivé, vous pouvez donc choisir $ \ lambda $ qui ne répond pas à cette exigence. Inversement, supposons qu'une solution soit trouvée lorsque $ \ lambda $ disparaît. Soit $ \ lambda $ sélectionné ici $ \ lambda_1 $.

Déterminez une autre variable

Sélectionnez l'autre variable dans l'ordre suivant. Tout d'abord, vous devez trouver $ \ boldsymbol {w} $ et $ w_0 $ dans le $ \ lambda $ actuel. La fonction d'erreur à ce moment est $ E_n = (\ boldsymbol {w} ^ Tx_n + w_0) -t_n $ ça ira.

(1) Sélectionnez pour maximiser le nombre de mises à jour de variables Sélectionnez $ n $ qui maximise l'erreur de $ E_1 $ dans le cas de

$ \ lambda_1 $.

(2) N'existe pas sur la frontière

$ t_n (\ boldsymbol {w} ^ Tx_n + w_0) = tout point qui n'est pas 1 $

(3) Restant

Mettre à jour les variables

J'ai décidé quels $$ lambda_1 $ et $ \ lambda_2 $ mettre à jour, mais lors de la mise à jour, il y a une contrainte linéaire $ \ sum_ {i = 1} ^ N \ lambda_it_i = 0 $, alors mettez à jour dans ces conditions Il y a un besoin. Autrement dit, si vous mettez à jour un $ \ lambda $, vous devez ajuster l'autre $ \ lambda $. Soit $ \ lambda_1 $ et $ \ lambda_2 $ après la mise à jour $ \ lambda_1 ^ {new} $ et $ \ lambda_2 ^ {new} $, respectivement.

\lambda_1^{new}t_1+\lambda_2^{new}t_2=\lambda_1t_1+\lambda_2t_2

Ce sera. Ceci est divisé entre le cas de $ t_1 = t_2 $ et le cas de $ t_1 \ ne t_2 $.

\lambda_1^{new}=\lambda_1+\frac{t_1(E_2-E_1)}{x_1^2+x_1x_2+x_2^2} \\
\lambda_2^{new}=\lambda_2+t_1t_2(\lambda_1-\lambda_1^{new})

Obtenir En fait, nous avions besoin d'un processus appelé clipping pour trouver la plage possible de $ \ lambda_1 $ et $ \ lambda_2 $, mais nous étions épuisés.

implémentation python

Tout d'abord, j'ai épuisé la théorie, et cela fait trop longtemps, donc je vais simplement implémenter scikit-learn. Pardon. Je vais certainement le mettre en œuvre par moi-même un jour.

Implémentation de scikit-learn

L'implémentation de python est assez simple. Support avec scikit-learn Utilisez sklearn.svm.LinearSVC pour la classification des machines vectorielles. .. Cette fois, par souci de clarté, nous utiliserons un échantillon dans lequel 50 exemples positifs et 50 exemples négatifs sont correctement séparés.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

%matplotlib inline

from sklearn import svm

fig, ax = plt.subplots()    
    
x1_1=np.ones(50)+10*np.random.random(50)
x1_2=np.ones(50)+10*np.random.random(50)
x2_1=-np.ones(50)-10*np.random.random(50)
x2_2=-np.ones(50)-10*np.random.random(50)

x1 = np.c_[x1_1,x1_2]
x2 = np.c_[x2_1,x2_2]
y  = np.array(np.r_[np.ones(50), -np.ones(50)])

model = svm.LinearSVC()
model.fit(np.array(np.r_[x1,x2]), y)

ax.scatter(x1[:,0],x1[:,1],marker='o',color='g',s=100)
ax.scatter(x2[:,0],x2[:,1],marker='s',color='b',s=100)

w = model.coef_[0]

x_fig = np.linspace(-12.,12.,100)
y_fig = [-w[0]/w[1]*xi-model.intercept_/w[1] for xi in x_fig]
ax.plot(x_fig, y_fig)

plt.show()

C'était classé comme ça. C'est naturel.

Résumé

Je suis épuisé à la fin, mais je pense que je pourrais saisir l'atmosphère (je ne peux pas la saisir w). Cette fois, nous avons dérivé les bases des bases, qui sont linéairement séparables et peuvent classer correctement les cas positifs et négatifs (marge dure).

Pour une machine à vecteurs de support plus avancée ou plus proche de la réalité, il est nécessaire de considérer les cas où la séparation linéaire n'est pas possible (méthode du noyau) et les cas où les exemples positifs et négatifs ne peuvent pas être correctement classés (marge souple), mais la théorie de base Est presque le même que cette fois.

À partir de la prochaine fois, je voudrais parler de ce domaine.

** Ajout **: Écrit