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.

106_support_vector.png

À 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,||w||^{-1}Problème de maximisation||w||^2Si vous le remplacez par le problème de minimisation de, la formule à résoudre par la machine à vecteurs de support devient le problème de minimisation contraint suivant, appelé problème principal.

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

106_svc_margin.png

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.

106_svc_kernel.png

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.

106_svc_gamma.png

Classification multi-classes

Nous avons utilisé l'ensemble de données iris pour les données multiclassifiées.

106_svc_multiclass.png

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 $.

106_svr.png

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.

106_svm_anomaly.png

référence

1.4. Suppoer Vector Machines

Christpher M. Bishop, "Pattern Recognition and Machine Learning", Springer, 2006.

Recommended Posts

Machine Learning: Supervisé - Support Vector Machine
Machine de vecteur de support d'apprentissage automatique
Algorithme d'apprentissage automatique (machine vectorielle de support)
Algorithme d'apprentissage automatique (prise en charge de l'application de machine vectorielle)
Apprentissage automatique ① Résumé SVM (Support Vector Machine)
Apprentissage automatique: supervisé - AdaBoost
Machine Learning: Supervision - Régression linéaire
Apprentissage automatique: forêt supervisée - aléatoire
Machine learning supervisé (classification / régression)
Machine Learning: Supervisé - Arbre de décision
Apprentissage automatique
Apprentissage automatique: analyse discriminante linéaire supervisée
[Français] scikit-learn 0.18 Guide de l'utilisateur 1.4. Support Vector Machine
[Apprentissage automatique] Apprentissage supervisé utilisant l'estimation de la densité du noyau
Support Vector Machine (pour les débutants) -Code Edition-
Apprentissage supervisé (classification)
[Memo] Apprentissage automatique
Classification de l'apprentissage automatique
Exemple d'apprentissage automatique
[Apprentissage automatique] Apprentissage supervisé utilisant l'estimation de la densité du noyau Partie 2
[Apprentissage automatique] Apprentissage supervisé utilisant l'estimation de la densité du noyau Partie 3
Calcul de la machine à vecteurs de support (SVM) (en utilisant cvxopt)
Résumé du didacticiel d'apprentissage automatique
Apprentissage automatique sur le surapprentissage
Apprentissage automatique ⑤ Résumé AdaBoost
Régression logistique d'apprentissage automatique
Étudier l'apprentissage automatique ~ matplotlib ~
Mémo du cours d'apprentissage automatique
Bibliothèque d'apprentissage automatique dlib
Apprentissage automatique (TensorFlow) + Lotto 6
Apprenez en quelque sorte le machine learning
Apprendre avec un enseignant (retour) 1 Bases
Python: apprentissage supervisé (retour)
Bibliothèque d'apprentissage automatique Shogun
Défi de lapin d'apprentissage automatique
Introduction à l'apprentissage automatique
Python: apprentissage supervisé (classification)
Apprentissage automatique: k-voisins les plus proches
Qu'est-ce que l'apprentissage automatique?
Modèle d'apprentissage automatique prenant en compte la maintenabilité
L'apprentissage automatique appris avec Pokemon
Ensemble de données pour l'apprentissage automatique
Prétraitement japonais pour l'apprentissage automatique
Apprentissage automatique dans Delemas (s'entraîner)
Une introduction à l'apprentissage automatique
Bases de l'apprentissage automatique (mémoire)
Python: Apprentissage supervisé: Hyper Paramètres Partie 1
Un débutant en apprentissage automatique a essayé la RBM
[Apprentissage automatique] Comprendre la forêt aléatoire
Apprentissage automatique avec Python! Préparation
Bloc-notes de ressources d'étude d'apprentissage automatique
Apprentissage supervisé 3 hyper paramètres et réglage (2)
Comprendre l'apprentissage automatique ~ régression de crête ~.
Résumé de l'article sur l'apprentissage automatique (auto-écrit)
À propos de la matrice mixte d'apprentissage automatique
Apprendre avec l'enseignant 1 Principes de base de l'apprentissage avec l'enseignant (classification)
Mémo pratique du système d'apprentissage automatique
Démineur d'apprentissage automatique avec PyTorch
Créer un environnement d'apprentissage automatique
Programmation Python Machine Learning> Mots-clés