[PYTHON] Machine Learning: Supervisé - Support Vector Machine
Cible
Comprenez la machine vectorielle de support avec des formules mathématiques et essayez-la avec scicit-learn.
On suppose que vous avez déjà appris l'intégration différentielle et l'algèbre linéaire.
théorie
La machine à vecteurs de support s'entraîne pour maximiser la marge entre le vecteur de support et la limite d'identification sur la base d'une petite quantité de données appelée vecteur de support qui détermine la limite d'identification.
Bien que la machine à vecteurs de support soit un modèle de discrimination linéaire, elle est largement utilisée comme un excellent modèle de classification car elle est hautement extensible aux problèmes de discrimination non linéaire dus aux astuces du noyau.
À l'origine, un modèle de classification binaire, il est également utilisé pour la classification multiclasse, la régression et la détection d'anomalies.
Classification par machine à vecteurs de support
Dérivation de la machine de vecteur de support
Considérons d'abord le problème de classification linéaire binaire. Ici, les données d'entraînement sont $ x = (x_1, ..., x_n) $, la valeur cible est $ t = (t_1, ..., t_n) $, mais $ t \ in \ {-1, 1 \ Si } $ et le paramètre est $ w $, le modèle linéaire du modèle discriminant en sortie $ y $ est
y(x) = w^T x + b
Cela peut être exprimé par. Nous écrirons explicitement ici le biais $ b $. En supposant la séparabilité linéaire, $ y (x_i) = 1 $ lorsque $ t_i = 1 $ et $ y (x_i) = -1 $ lorsque $ t_i = -1 $, donc toutes les données d'apprentissage Environ $ t_n y (x_n)> 0 $ tient.
La machine à vecteurs de support vise à maximiser la marge, qui est la distance de la limite d'identification $ y = w ^ Tx + b $ aux données d'apprentissage les plus proches, comme indiqué dans la figure ci-dessous.
À partir de la formule de la distance entre un point et un plan, la distance entre un point dans les données d'apprentissage et l'interface d'identification peut être exprimée par la formule suivante.
\frac{|w^Tx + b|}{||w||}
De plus, en ne considérant que les données d'apprentissage $ t_i y (x_i)> 0 $ correctement classées,
\frac{t_i ( w^Tx_i + b )}{||w||}
Ce sera. Puisque la marge est la distance des données d'apprentissage la plus proche de la limite de discrimination et que les paramètres $ w et b $ qui maximisent la marge doivent être obtenus, la formule suivante peut être définie.
\newcommand{\argmax}{\mathop{\rm argmax}\limits}
\argmax_{w, b} \frac{1}{||w||} \min_i \{ t_i (w^Tx_i + b) \}
Maintenant, si vous mettez à l'échelle $ w, b $ de sorte que $ t_i (w ^ Tx + b) = 1 $, toutes les données d'apprentissage répondront aux contraintes suivantes.
t(w^Tx + b) \geq 1
plus loin,
\newcommand{\argmin}{\mathop{\rm argmin}\limits}
\argmin_{w, b} = \frac{1}{2}||w^2|| \\
t_i(w^Tx_i + b) \geq 1
Soutenir l'apprentissage automatique des vecteurs
Pour trouver les paramètres d'une machine à vecteurs de support, vous devez résoudre un problème d'optimisation contraint. Donc, si nous introduisons le multiplicateur de Lagrange $ a = (a_1, ..., a_n) $, qui est $ a \ geq 0 $,
L(w, b, a) = \frac{1}{2} ||w^2|| - \sum^n_{i=1} a_i \{ t_i(w^Tx_i + b) - 1 \}
Ce sera. Si ce $ L $ est différencié par rapport aux paramètres $ w et b $ et résolu comme 0,
\begin{align}
\frac{\partial L}{\partial w} &= w - \sum^n_{i=1}a_i t_i x_i = 0\\
w &= \sum^n_{i=1}a_i t_i x_i \\
\frac{\partial L}{\partial b} &= \sum^n_{i=1}a_i t_i = 0 \\
0 &= \sum^n_{i=1}a_i t_i
\end{align}
En les remplaçant par $ L (w, b, a) $ et en supprimant $ w, b $
\begin{align}
L(a) &= \frac{1}{2} w^T w - \sum^n_{i=1} a_i t_i w^T x_i - b \sum^n_{i=1} a_i t_i + \sum^n_{i=1} a_i \\
&= \frac{1}{2} w^T w - w^T w + \sum^n_{i=1} a_i \\
&= \sum^n_{i=1} a_i - \frac{1}{2} w^T w \\
&= \sum^n_{i=1} a_i - \frac{1}{2} \sum^n_{i,j=1} a_i a_j t_i t_j x^T_i x_j
\end{align}
Par conséquent, nous devons résoudre le problème de planification quadratique sous contraintes suivant, qui est appelé un problème double par rapport au problème principal. Puisqu'il existe une correspondance biunivoque entre le problème principal et le problème double, il suffit de résoudre le problème double au lieu du problème principal.
L(a) = \sum^n_{i=1} a_i - \frac{1}{2} \sum^n_{i,j = 1} a_i a_j t_i t_j k(x_i, x_j) \\
a_i \geq 0 \\
\sum^n_{i=1} a_n t_n = 0
Dans l'équation ci-dessus, $ k (x_i, x_j) = x ^ T_i x_j $ représente une fonction de noyau, qui est ici un noyau linéaire. Résoudre ceci donne une solution éparse telle que seule une petite quantité de données correspondant au vecteur de support est $ a_i \ neq 0 $, et les autres sont $ a_i = 0 $.
Si vous ajoutez le terme de pénalité $ \ frac {1} {2} \ lambda \ sum ^ n_ {i, j = 1} a_i a_j t_i t_j $ avec l'hyper paramètre comme $ \ lambda $ afin que la condition de contrainte du problème dual soit satisfaite,
L(a) = \sum^n_{i=1} a_i - \frac{1}{2} \sum^n_{i,j = 1} a_i a_j t_i t_j k(x_i, x_j) - \frac{1}{2} \lambda \sum^n_{i,j = 1} a_i a_j t_i t_j
Ce sera. Différenciation de $ L (a) $ par rapport à $ a_i $
\frac{\partial L}{\partial a_i} = 1 - \sum^n_{j=1} a_j t_i t_j k(x_i, x_j) - \lambda \sum^n_{j=1} a_j t_i t_j
Ce sera. Si vous résolvez le problème de maximisation par la méthode du gradient avec un taux d'apprentissage de $ \ eta $,
\begin{align}
\hat{a_i} &= a_i + \eta \frac{\partial L}{\partial \alpha_i} \\
&= a_i + \eta \left( 1 - \sum^n_{j=1} a_j t_i t_j k(x_i, x_j) - \lambda \sum^n_{j=1} a_j t_i t_j \right)
\end{align}
Ce sera. La convergence est garantie car ce problème est un problème d'optimisation quadratique convexe. En outre, la machine à vecteurs de support stocke $ n $ de données vectorielles de support et, lors de la prédiction, les classe en fonction de ce vecteur de support.
Puisque le paramètre $ w $ est dérivé de $ a $, nous dérivons finalement le biais $ b $. Compte tenu des nouvelles données $ x_j $, classez en utilisant la formule suivante:
y(x) = \sum^m_{j=1} a_j t_j k(x_i, x_j) + b
S'il peut être classé correctement, $ t_i y (x_i) = 1 $ sera satisfait.
t_i \left( \sum^m_{j=1} a_it_ik(x_i, x_j) + b \right) = 1
Ce sera. Ici, à partir de $ t ^ 2_i = 1 $,
\begin{align}
t_i \left( \sum^m_{j=1} a_j t_j k(x_i, x_j) + b \right) &= t^2_i \\
\sum^m_{j=1} a_j t_j k(x_i, x_j) + b &= t_i \\
\end{align}
Par conséquent, le biais $ b $ est
b = \frac{1}{n} \sum^n_{i=1} \left( t_i - \sum^m_{j=1} a_j t_j k(x_i, x_j) \right)
Ce sera. Si le nombre de données est égal ou supérieur à 100 000, l'argument loss de SGDClassifier est défini sur "hinge "et la machine à vecteur de support par la méthode de descente de gradient probabiliste est recommandée.
Marge douce
La machine à vecteurs de support dans la section précédente est appelée une marge ferme, et une marge souple qui permet un petit nombre d'erreurs de classification est proposée. Pour les marges douces, nous introduirions la variable slack $ \ xi $ et l'hyper paramètre $ C $ pour résoudre l'équation suivante:
\argmin_{w, b, \xi} \frac{1}{2} ||w||^2 + C \sum^n_{i=1} \xi_i \\
\xi_i \geq 0 \\
t_i (w^T x_i + b) \geq 1 - \xi_i \\
Astuce du noyau
Jusqu'à la section précédente, nous avons considéré le cas où l'identification linéaire est possible. Cependant, dans les problèmes réels, il existe peu de problèmes linéairement identifiables. Si vous souhaitez effectuer une discrimination non linéaire sur une machine à vecteurs de support, vous pouvez résoudre exactement le même problème d'optimisation que le problème de discrimination linéaire à partir de la fonction noyau $ K (x_i, x_j) $. Éviter de telles transformations non linéaires est appelé une astuce du noyau.
Les fonctions du noyau qui peuvent être utilisées sur la machine à vecteurs de support doivent remplir les conditions suivantes selon lesquelles ce sont des fonctions à valeur positive.
\sum_{i,j} a_i a_j K(x_i, x_j) > 0
Les fonctions typiques du noyau sont répertoriées ci-dessous.
Noyau linéaire
Le noyau linéaire est la machine à vecteurs de support linéaire jusqu'à la section précédente.
k(x_i, x_j) = x_i \cdot x_j
Noyau polygonal
Le noyau polymorphe se transforme en dimensions supérieures de degré $ p $. $ P, \ gamma, c $ sont incrémentés en hyperparamètres.
k(x_i, x_j) = (\gamma x_i \cdot x_j + c)^p
Noyau de fonction de base radiale (RBF)
Le noyau de la fonction de base radiative se transforme théoriquement en dimensions infinies. Le plus souvent utilisé comme noyau non linéaire. Vous devez ajuster l'hyper paramètre $ \ gamma $.
k(x_i, x_j) = \exp \left( -\gamma || x_i - x_j ||^2 \right)
Noyau Sigmaid
Le noyau sigmoïde est une fonction à valeur semi-fixe plutôt qu'une fonction à valeur positive, mais il présente des similitudes avec les réseaux de neurones.
k(x_i, x_j) = \tanh (\gamma x_i \cdot x_j + c)
la mise en oeuvre
Environnement d'exécution
Matériel
・ Processeur Intel (R) Core (TM) i7-6700K 4,00 GHz
Logiciel
・ Windows 10 Professionnel 1909 ・ Python 3.6.6 ・ Matplotlib 3.1.1 ・ Numpy 1.19.2 ・ Scikit-learn 0.23.2
Programme à exécuter
Le programme implémenté est publié sur GitHub.
svm_classification.py
svm_regression.py
svm_anomaly.py
résultat
Classification par machine à vecteurs de support
Classification par LinearSVC
J'ai utilisé l'ensemble de données sur le cancer du sein qui a également été utilisé dans Logistic Regression.
Accuracy 94.74%
Precision, Positive predictive value(PPV) 96.92%
Recall, Sensitivity, True positive rate(TPR) 94.03%
Specificity, True negative rate(TNR) 95.74%
Negative predictive value(NPV) 91.84%
F-Score 95.45%
Comparaison de l'hyperparamètre C
Diminuer l'hyperparamètre $ C $ augmente la marge à partir de la frontière discriminante, et l'augmenter réduit la marge.
Comparaison des fonctions du noyau
Les frontières discriminantes sont droites dans le noyau linéaire, mais circulaires dans le noyau polygonal, courbes dans le noyau sigmoïde, et plus complexes dans le noyau RBF.
Comparaison des hyperparamètres γ dans le noyau RBF
Des hyperparamètres du noyau RBF plus petits $ \ gamma $, qui sont souvent utilisés pour effectuer une discrimination non linéaire, desserrent les frontières discriminantes et les resserrent. L'hyperparamètre $ \ gamma $ est un résultat convaincant car il peut être considéré comme l'inverse de la distribution.
Classification multi-classes
Nous avons utilisé l'ensemble de données iris pour les données multiclassifiées.
Retour par machine à vecteur de support
Les données du problème de régression ont été exécutées en ajoutant un nombre aléatoire à la sinusoïde et en définissant $ k = 5 $.
Détection d'anomalies par la machine vectorielle de support
La détection des anomalies utilise une machine vectorielle de support de classe 1. Dans la figure ci-dessous, les zones autres que la zone bleue sont traitées comme des valeurs anormales.
référence
Christpher M. Bishop, "Pattern Recognition and Machine Learning", Springer, 2006.
Recommended Posts