Introduction à Machine Learning-Hard Margin SVM Edition-
1. Qu'est-ce que Support Vector Machine (SVM)?
Dans la précédente Introduction to Machine Learning from Simple Perceptron, la méthode d'apprentissage de Simple Perceptron utilise le gradient de la fonction d'erreur pour rendre la fonction d'erreur de plus en plus petite. C'était ça. Cependant, cette méthode présente les deux problèmes suivants.
-La capacité de généralisation du modèle n'est pas garantie. -Non disponible en raison de problèmes séparables linéairement.
Ici, le modèle fait référence à l'expression de $ f (x) $ une fois l'entraînement terminé. En outre, la capacité de généralisation fait référence à la capacité de prédire correctement les étiquettes de classe et les valeurs de fonction non seulement pour les données d'entraînement données au moment de l'apprentissage, mais également pour les nouvelles données inconnues. En premier lieu, le but de l'utilisation de l'apprentissage automatique tel que Simple Perceptron est de classer si les e-mails qui ne sont pas utilisés dans l'apprentissage sont bien du spam dans le cas des e-mails de spam. En aucun cas, il ne suffit pas de classer uniquement les e-mails qui ont déjà été envoyés. C'est à cela que suffisent les signatures, pas le rôle de l'apprentissage automatique.
À propos, SVM est un algorithme qui résout les deux problèmes ci-dessus.
La solution à ces deux points a été l'introduction de la maximisation des marges et des astuces du noyau.
La marge fait référence à la distance entre la ligne _f (x) _ et les deux classes.
Cette maximisation de la marge est une tentative de maximiser la capacité de généralisation en maximisant la distance correspondant à M dans la figure ci-dessous.
L'astuce du noyau fait référence à la cartographie des données de l'espace de données d'origine vers un espace dimensionnel supérieur et à l'exécution d'une analyse de données linéaire sur cet espace dimensionnel supérieur.
C'est une histoire un peu difficile, mais vous pouvez penser que l'astuce du noyau fait quelque chose comme l'image ci-dessous.
"Pourquoi deux problèmes peuvent-ils être résolus en utilisant la maximisation des marges et les astuces du noyau?"
2. Formulation SVM
Dans la précédente Introduction to Machine Learning from Simple Perceptron et le contenu décrit jusqu'à présent, lorsqu'il y a du bruit dans les données lors de l'apprentissage des données Il n'a même pas mentionné quoi faire.
Dans l'implémentation de Simple Perceptron, l'apprentissage s'est poursuivi "jusqu'à ce que l'erreur devienne nulle".
Dans ce cas, par exemple, si les données ressemblent à la figure ci-dessous, l'implémentation précédente continuerait d'ajuster les paramètres pour toujours.
Bien sûr, des ajustements peuvent être faits pour arrêter l'apprentissage lorsqu'il est déterminé que l'erreur est minimisée, mais même dans ce cas, la précision de la classification diminuera en raison de la présence de bruit.
Même avec SVM, l'implémentation appelée SVM à marge dure a la faiblesse d'être faible lorsque les données sont mélangées avec du bruit.
Par conséquent, l'idée était une SVM à marge douce qui est forte dans une certaine mesure même lorsque les données sont mélangées avec du bruit.
Un modèle résistant au bruit, comme ce SVM à marge souple, est appelé modèle robuste.
Dans le monde réel, il y a beaucoup de données bruyantes et des SVM à marge souple sont utilisés pour la plupart des tâches.
Le SVM à marge rigide est plus facile à respecter que le SVM à marge souple, donc cette fois je n'expliquerai que le SVM à marge rigide.
2.1. Formule de Hesse
Comme vous le savez peut-être dans les manuels du secondaire numéro II, je vais expliquer la formule de Hesse, qui est la formule utilisée pour calculer la marge. Aucune preuve officielle n'est donnée ici, seulement comment il est utilisé. La formule de Hesse est une formule pour calculer la distance entre un point et une ligne droite, et est calculée par la formule suivante.
Point A(x_0,y_0)De, la longueur d de la perpendiculaire tracée à la droite ax + by + c = 0 est\\
d=\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}
Pour dériver le SVM, ce qui suit, qui est une extension multidimensionnelle de ceci, est utilisé.
Point de données A=(x_1,x_2,...,x_m)Du superplan f(x)=w^Tx+\La distance à thêta\\
d=\frac{|w^Tx+\theta|} {||w||}
2.2 La méthode du multiplicateur indécis de Lagrange
La méthode du multiplicateur indéterminé de Lagrange est utilisée lors de la maximisation de la marge sous les contraintes décrites ci-dessous. La méthode du multiplicateur indéterminé de Lagrange est une méthode d'optimisation d'un problème en tant que problème de valeur extrême ordinaire dans certaines conditions. Un exemple du cas bidimensionnel est présenté ci-dessous. Problème de trouver le point $ (a, b) $ où $ f (x, y) $ est la valeur maximale sous la condition de contrainte $ g (x, y) = 0 $
\left\{
\begin{array}{ll}
Maximiser& f(x,y) \\
Contraintes& g(x,y)=0
\end{array}
\right.
penser à.\\
À ce stade, la fonction suivante peut être définie en considérant le multiplicateur indécis $ \ lambda $ appelé multiplicateur de Lagrange.
L(x,y,\lambda)=f(x,y)-\lambda g(x,y) \\
point(a,b)alors\frac{\partial g}{\partial x}\neq0 et\frac{\partial g}{\partial y}\Lorsque neq 0\\
\frac{\partial L}{\partial x}=\frac{\partial L}{\partial y}=\frac{\partial L}{\partial \lambda}=0 \\
En trouvant le point $ (x, y) $ qui satisfait la condition comme point d'arrêt, la valeur maximale $ (x, y) $ peut être trouvée.
Ici aussi, le point d'arrêt fait référence au point où la différenciation devient 0. SVM est généralisé en utilisant ce qui suit, qui est une extension de ceci au multidimensionnel général. Sous contraintes $ M $ $ g_k (x_1, ..., x_n) = 0, (k = 1, ..., M) $ Problème de trouver un point à n dimensions $ x = (x_1, ..., x_n) $ où $ f (x_1, ..., x_n) $ est la valeur maximale
\left\{
\begin{array}{ll}
Maximiser& f(x_1,...,x_n) \\
Contraintes& g_k(x_1,...,x_n)=0,(k=1,...,M)
\end{array}
\right.
penser à.\\
A ce moment, un multiplicateur indécis appelé multiplicateur de Lagrange\lambda=(\lambda_1,...,\lambda_M)Considérant, la fonction suivante peut être définie.\\
L(x_1,...,x_n,\lambda)=f(x_1,...,x_n)-\sum_{k=1}^M\lambda_k g_k(x_1,...,x_n) \\
point(x_1,...,x_M)alors\nabla g_k=(\frac{\partial f}{\partial x_1},...,\frac{\partial f}{\partial x_n})\neq (0,...,0)Quand,\\
N+Conditions M:\frac{\partial L}{\partial \alpha}=0(\alpha=x_1,...,x_n,\lambda_1,...,\lambda_M)\\
Points à rencontrer(x_1,...,x_n)Le point qui devient la valeur maximale en trouvant comme point d'arrêt(x_1,...,x_n)Est recherché.
2.3. Conditions KKT (Karush-Kuhn-Tucker)
Considérons un problème de programmation mathématique avec les contraintes d'inégalité suivantes pour les fonctions différenciables $ f et g_i $.
\left\{
\begin{array}{ll}
Minimiser& f(x) \\
Contraintes& g_i(x) \leq 0 (i=1,...,m)
\end{array}
\right.
La formule suivante est la condition KKT pour ce qui précède.
\left\{
\begin{array}{l}
\nabla f(\hat{x})+\sum_{i=1}^m \hat{\lambda_i} \nabla g_i(\hat{x})=0 \\
\hat{\lambda_i} \geq 0,g_i(\hat{x})\leq 0,\hat{\lambda_i} g_i(\hat{x}) = 0 (i=1,...,m)
\end{array}
\right.
Ici avec la formule ci-dessus
\hat{\lambda_i} \geq 0,g_i(\hat{x})\leq 0,\hat{\lambda_i} g_i(\hat{x}) = 0 (i=1,...,m)
Indique qu'au moins un des $ \ hat {\ lambda_i} et g_i (\ hat {x}) $ est égal à 0 pour chaque $ i $, ce qui est généralement appelé condition de complémentarité.
2.4. Dérivation du SVM à marge ferme
Lorsque le nombre total de données d'apprentissage est n, la distance minimale d entre les données d'apprentissage et le superplan est donnée ci-dessous par "2.1. Formule de Hesse".
d=min_{i=1,...,n}\{\frac{|w^Tx_i+\theta|}{||w||}\} \\
Ici, $ min_ {i = 1, ..., n} $ est une fonction qui renvoie la valeur lorsque $ i $ prend la plus petite valeur parmi $ 1 à n $ dans le résultat du calcul.
Je veux trouver $ w $ et $ \ theta $ qui maximisent cette distance minimale $ d $. La formule pour cela est la suivante.
d_{max}=max_{w,\theta}[min_{i=1,...,n}\{\frac{|w^Tx_i+\theta|}{||w||}\}]
Ici, $ max_ {w, \ theta} $ est une fonction qui renvoie la valeur avec le plus grand résultat de calcul dans la fonction parmi les $ w $ et $ \ theta $ possibles.
En ce moment,
d_{max}=max_{w,\theta}[\frac{1}{||w||}min_{i=1,...,n}\{|w^Tx_i+\theta|\}] \\
Peut être exprimé comme.
min_{i=1,2,...,n}|w^Tx_i+\theta|=1
Cette volonté
max_{w,\theta}\frac{1}{||w||} \\
La fonction discriminante qui est\\
Du superplan aux données d'entraînement des deux côtés M=\frac{1}{||w||}Une façon
\frac{2}{||w||}Largeur de(Marge: marge)avoir.\\
max_{w,\theta}\frac{1}{||w||}Est min du côté informatique_{w,\theta}\frac{1}{2}||w||^Équivaut à 2.\\
En outre, l'étiquette de l'enseignant t_En utilisant i, la condition de contrainte min_{i=1,2,...,n}|w^Tx_i+\theta|=1 peut s'écrire comme suit.\\
t_i(w^Tx_i+\theta)\geq 1,(i=1,2,...,n) \\
Si les résultats du calcul des données de l'enseignant $ t_i $ et de la fonction d'identification $ w ^ Tx_i + \ theta $ sont incohérents, $ t_i (w ^ Tx_i + \ theta) <1
\left\{
\begin{array}{l}
min_{w,\theta}\frac{1}{2}||w||^2 \\
Contraintes:t_i(w^Tx_i+\theta)\geq 1,(i=1,2,...,n)
\end{array}
\right.
À ce stade, la fonction suivante peut être définie en considérant le multiplicateur indécis $ \ lambda (\ lambda_i \ geq 0) $ appelé multiplicateur de Lagrange. Il peut être remplacé par le problème de trouver la valeur minimale de cette fonction.
L(w,\theta,\lambda)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\lambda_i{t_i(w^Tx_i+\theta)-1} \\
À la valeur minimale, la pente de L(Pente)Devrait être 0\\
\frac{\partial L}{\partial b}=\sum_{i=1}^{N}\lambda_it_i=0 \\
\frac{\partial L}{\partial w}=w-\sum_{i=1}^{N}\lambda_i t_i x_i=0 \\
\frac{\partial L}{\partial w}Lorsque le côté droit de est transformé, il devient comme suit.\\
w=\sum_{i=1}^{N}\lambda_i t_i x_i \\
L(w,\theta,\lambda)Est élargi pour faciliter le calcul.\\
L(w,\theta,\lambda)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\lambda_it_iw^Tx_i+\lambda_it_i\theta-\lambda_i \\
L(w,\theta,\lambda)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\lambda_it_iw^Tx_i-\theta\sum_{i=1}^{N}\lambda_it_i+\sum_{i=1}^{N}\lambda_i \\
ici\thêta\sum_{i=1}^{N}C'est parce que c'est une constante.\\
L(w,\theta,\lambda)À\sum_{i=1}^{N}\lambda_it_i=0,w=\sum_{i=1}^{N}\lambda_i t_i x_Remplaçant i.\\
L(w,\theta,\lambda)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\lambda_it_ix_i\sum_{j=1}^{N}\lambda_j t_j x_j-\theta×0+\sum_{i=1}^{N}\lambda_i \\
L(w,\theta,\lambda)=\frac{1}{2}w\cdot w-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_i \\
L(w,\theta,\lambda)=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_i \\
L(w,\theta,\lambda)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_i \\
Cela peut être organisé comme un double format comme suit.\\
\left\{
\begin{array}{l}
max_{\lambda}-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_i \\
Contraintes:\sum_{i=1}^{N}\lambda_it_i=0,\lambda_i\geq 0
\end{array}
\right. \\
Un tel problème est appelé problème de planification secondaire convexe pour $ \ lambda_i $. Lorsque la solution $ \ hat {\ lambda_i} (> 0) $ de cette équation est trouvée, $ \ hat {w} $ est obtenu à partir de $ w = \ sum_ {i = 1} ^ {N} \ lambda_i t_i x_i $. .. Grâce à cette conception quadratique convexe, la solution optimale locale est toujours la solution optimale globale. La solution optimale $ \ hat {w}, \ hat {\ theta}, \ hat {\ lambda} $ doit satisfaire la condition complémentaire KKT $ \ hat {\ lambda_i} t_i (w ^ Tx_i + \ theta) -1 = 0 $ Doit être. Lorsque la contrainte d'inégalité $ t_i (w ^ Tx_i + \ theta) -1> 0 $ est satisfaite, $ \ lambda_i = 0 $ doit être satisfaite à partir de la condition complémentaire. Par conséquent, cette contrainte n'est plus valide. De plus, si $ t_i (w ^ Tx_i + \ theta) -1 = 0 $, alors $ \ lambda_i> 0 $, la contrainte est donc valide. A partir de là, seule la contrainte par le point (ci-après, vecteur de support) qui détermine la marge qui satisfait $ t_i (w ^ Tx_i + \ theta) -1 = 0 $ est activée. Étant donné que le nombre de vecteurs de support est considérablement plus petit que le nombre d'échantillons d'origine, il économise beaucoup de montant de calcul lors de l'identification.
Enfin, le SVM est dérivé comme suit.
f(x)=w^Tx+\theta,w=\sum_{i=1}^{N}\lambda_i t_i x_De moi\\
\hat{f}(x)=\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j +\theta
La valeur de $ \ theta $ est obtenue à partir de la condition de complémentation $ t_i (w ^ Tx_i + \ theta) -1 = 0 $ comme suit.
t_i(w^Tx_i+\theta)-1=0,w=\sum_{i=1}^{N}\lambda_i t_i x_De moi\\
t_i(\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j+\theta)-1=0 \\
T des deux côtés_Diviser par i\\
\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j+\theta - \frac{1}{t_i}=0\\
\Conditions de transfert autres que thêta\\
\theta=\frac{1}{t_i} -\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j\\
\frac{1}{t_i}Est t_i\in \{1,-1\}Parce que c'est t_Parce qu'il peut être dit équivalent à i\\
\theta=t_i -\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j
Lors de la recherche de $ \ theta $ dans une implémentation réelle, il arrive souvent que la moyenne soit prise en utilisant tous les vecteurs de support qui satisfont les conditions en considération de la stabilité dans le calcul numérique. Lors du calcul de la moyenne, $ \ theta $ est calculé par la formule suivante.
\theta = \frac{1}{N_S} \sum_{n \in S}(t_n - \sum_{m \in S}\hat{\lambda}_mt_m x_n^T x_m) \\
S:Ensemble de vecteurs de support(=\{s_1,s_2,...,s_{N_S}\}) \\
N_S:Nombre de vecteurs de support
Enfin, la frontière d'identification est tracée par la formule suivante.
\hat{f}(x)=\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j + \frac{1}{N_S} \sum_{n \in S}(t_n - \sum_{m \in S}\hat{\lambda}_mt_m x_n^T x_m)
3. Astuce du noyau
En optimisant la marge, on peut s'attendre à ce que la capacité de généralisation soit améliorée par rapport au simple Perceptron. Cependant, la mise en œuvre jusqu'à présent ne peut résoudre que des problèmes séparables linéairement. Une astuce du noyau a été conçue pour résoudre ce problème. Comme je l'ai expliqué au début de ce que fait l'astuce du noyau, il s'agit de "mapper les données de l'espace de données d'origine vers un espace dimensionnel supérieur et effectuer une analyse de données linéaire sur cet espace dimensionnel supérieur". Seule la façon de l'implémenter est décrite ici, et elle est trop avancée pour expliquer pourquoi elle n'affecte pas l'implémentation elle-même, je vais donc l'omettre. L'équation suivante finalement obtenue plus tôt est transformée.
\hat{f}(x)=\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i x_i^T x_j + \frac{1}{N_S} \sum_{n \in S}(t_n - \sum_{m\in S}\hat{\lambda}_mt_m x_n^T x_m)
Faites ceci.
\hat{f}(x)=\sum_{i=1}^{N}\sum_{j=1}^{N}\hat{\lambda_i}t_i K(x_i,x_j) + \frac{1}{N_S} \sum_{n \in S}(t_n - \sum_{m \in S}\hat{\lambda}_mt_m K(x_n,x_m)
$ K (\ cdot, \ cdot) $ est une fonction du noyau. Si vous voulez en savoir plus sur les astuces du noyau, découvrez la méthode du noyau. Plus précisément, il est nécessaire d'étudier l'espace nucléaire de Hilbert régénératif, le théorème de Représentant et le théorème de Mercer.
4. Algorithme d'apprentissage SVM
Il existe trois méthodes typiques pour optimiser $ \ lambda $.
4.1. Apprentissage par la méthode de descente la plus raide
La méthode de descente la plus raide est un algorithme qui recherche la valeur minimale d'une fonction à partir de la pente de la fonction. $ n $ Envisagez de trouver la valeur minimale de cette fonction avec $ f (x) $ comme fonction qui prend le vecteur suivant $ x = (x1, x2, ..., xn) $ comme argument. La méthode du gradient utilise une méthode itérative pour rapprocher $ x $ de la solution. Lorsque la solution est à la position $ x ^ (k) $ dans l'itération $ k $ ème, la méthode de descente la plus raide met à jour la valeur comme suit. Lors de la minimisation de la fonction
x^{(k+1)} = x^{(k)}-\alpha \nabla f(x^{(k)})
Lors de la maximisation d'une fonction
x^{(k+1)} = x^{(k)}+\alpha \nabla f(x^{(k)})
L'apprentissage se comporte comme indiqué dans la figure ci-dessous, qui est mise à jour de manière à descendre une pente.
La figure est unidimensionnelle pour la visualisation, mais il en va de même pour les cas multidimensionnels.
Utilisez n'importe quel nombre pour la valeur de $ \ alpha $. (Généralement un nombre entre 0 et 1)
Si $ \ alpha $ est trop grand, la distance en bas de la colline sera grande avec une mise à jour, et il ne sera pas possible de faire de petits virages, donc l'écart entre la valeur minimale réelle et la valeur approximative calculée sera grand.
Si $ \ alpha $ est trop petit, la quantité de calcul augmentera considérablement car la distance dans la pente sera courte avec une mise à jour.
Par conséquent, la définition appropriée de la valeur de $ \ alpha $ est également une vitrine pour les ingénieurs en apprentissage automatique.
Cette fois, nous mettrons en œuvre la méthode de descente la plus raide, qui est la plus simple à mettre en œuvre.
La formulation de la méthode de descente la plus raide vers SVM est indiquée ci-dessous. Considérez la variable $ \ lambda $ qui maximise $ L (w, \ theta, \ lambda) $.
\lambda_i^{(k+1)}=\lambda_i^{(k)}+\alpha \nabla L(w,\theta,\lambda) \\
\lambda_i^{(k+1)}=\lambda_i^{(k)}+\alpha \frac{\partial L(w,\theta,\lambda)}{\partial \lambda} \\
L(w,\theta,\lambda)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i\lambda_j t_it_j x_ix_j+\sum_{i=1}^{N}\lambda_De moi\\
\lambda_i^{(k+1)}=\lambda_i^{(k)}+\alpha (1-\sum_{j=1}^{N} \lambda_j t_i t_j x_i^T x_j) \\
\lambda_i^{(k+1)}=\lambda_i^{(k)}+\alpha (1-\sum_{j=1}^{N} \lambda_j t_i t_j K(x_i,x_j))
La variable $ \ lambda $ est mise à jour par la formule ci-dessus.
4.2. Apprentissage par l'algorithme SMO
L'algorithme SMO est une méthode d'optimisation qui sélectionne deux variables à optimiser et les met à jour de manière itérative. Il est également utilisé dans la célèbre bibliothèque SVM LIBSVM. L'implémentation elle-même est C ++ sur la page ci-dessous. http://web.cs.iastate.edu/~honavar/smo-svm.pdf http://www.cs.mcgill.ca/~hv/publications/99.04.McGill.thesis.gmak.pdf Je n'y reviendrai plus ici, mais je le publierai avec un commentaire.
4.3. Apprentissage par la méthode probabiliste de descente de gradient
La méthode de descente de gradient stochastique (SGD) est, en termes simples, une amélioration par rapport à la méthode de descente la plus raide, qui est l'apprentissage par lots, à l'apprentissage en ligne. Un article assez récent propose une implémentation appelée Pegosas ci-dessous. http://ttic.uchicago.edu/%7Enati/Publications/PegasosMPB.pdf En utilisant la méthode de descente de gradient probabiliste, il semble que l'apprentissage en ligne puisse être effectué avec SVM. Puisque nous ne connaissons pas ici les détails de l'algorithme, nous l'omettons. Je veux l'implémenter bientôt.
5. Exemple d'implémentation SVM à marge rigide par python
Il semble que c'était possible, mais le vecteur de support peut ne pas être calculé ou un vecteur de support étrange peut être calculé. Probablement, la cause est la partie implémentation de la méthode de descente la plus raide, qui détermine le nombre de mises à jour pour faire une erreur. Si la valeur du multiplicateur de Lagrange converge, il semble que le vecteur support puisse être trouvé correctement. Si vous connaissez la cause, faites-le moi savoir. Quand j'ai implémenté SVM une fois quand j'étais étudiant, je n'avais pas une pierre d'achoppement aussi étrange, donc c'est plutôt un mystère. (Le code source à ce moment-là a été perdu) Étant donné que le vecteur de support n'est pas calculé en cas de débordement avec la formule de mise à jour de la méthode de descente la plus raide, Si je suis motivé, je fixerai une limite supérieure à la valeur.
# -*- coding: utf-8 -*-
#Le nom du fichier est svm.py
import numpy as np
import random
from math import fabs
from scipy.linalg import norm
import matplotlib.pyplot as plt
#Classe SVM
class svm:
#Réglage de la valeur initiale
def __init__(self,kernel='linear',sigma=1.,degree=1.,threshold=1e-5,loop=500,LR=0.2):
self.kernel = kernel
#Dans le cas d'un noyau linéaire, cela revient à mettre à 1 tous les paramètres du noyau polymorphe.
if self.kernel == 'linear':
self.kernel = 'poly'
self.degree = 1.
#RBF et Poly(Polygone)Paramètres du noyau
self.sigma = sigma
self.degree = degree
#Seuil de recherche de vecteur de soutien
self.threshold = threshold
#Nombre de mises à jour
self.loop = loop
#Taux d'apprentissage
self.LR = LR
#Méthode pour calculer le noyau
def build_kernel(self,X):
self.K = np.dot(X,X.T)
if self.kernel == 'poly':
self.K = (1. + 1. / self.sigma * self.K)**self.degree
if self.kernel == 'rbf':
self.xsquared = (np.diag(self.K)*np.ones((1,self.N))).T
b = np.ones((self.N,1))
self.K -= 0.5*(np.dot(self.xsquared,b.T) + np.dot(b,self.xsquared.T))
self.K = np.exp(self.K/(2.*self.sigma**2))
#Méthodes de la partie apprentissage de SVM
def train_svm(self,X,t):
#La méthode de descente la plus raide a commencé
# self.Remplacez N par le nombre de lignes de X
self.N = np.shape(X)[0]
#Calculer le noyau
self.build_kernel(X)
count = 0
#Initialisation du multiplicateur de Lagrange
lam = np.ones((self.N,1))
#Boucle pour le nombre spécifié de mises à jour
while(count < self.loop):
for i in range(self.N):
ans = 0
for j in range(self.N):
#Une partie de la formule de renouvellement pour la méthode de descente la plus raide
ans += lam[j]*t[i]*t[j]*self.K[i,j]
#Formule de renouvellement de la méthode de descente la plus raide
lam[i] += self.LR * (1-ans)
#Puisque le multiplicateur de Lagrange est égal ou supérieur à 0, si une valeur négative est prise, 0 est remplacé.
if lam[i] < 0:
lam[i] = 0
count += 1
#La méthode de descente la plus raide se termine
#Extraire le multiplicateur de Lagrange qui dépasse la valeur de seuil en tant que vecteur de support
self.sv = np.where(lam>self.threshold)[0]
#Nombre de vecteurs de support
self.nsupport = len(self.sv)
print self.nsupport,"support vector found"
#Stocker uniquement les données de chaque vecteur de support
self.X = X[self.sv,:]
self.lam = lam[self.sv]
self.t = t[self.sv]
#formule pour w
self.w = np.array([0.,0.])
for i in range(self.nsupport):
self.w += self.lam[i]*self.t[i]*self.X[i]
#Formule de calcul de θ
self.b = np.sum(self.t)
for n in range(self.nsupport):
self.b -= np.sum(self.lam*self.t*np.reshape(self.K[self.sv[n],self.sv],(self.nsupport,1)))
self.b /= len(self.lam)
#Partie de classification pour noyaux linéaires ou polymorphes
if self.kernel == 'poly':
def classifier(Y):
K = (1. + 1./self.sigma*np.dot(Y,self.X.T))**self.degree
self.y = np.zeros((np.shape(Y)[0],1))
for j in range(np.shape(Y)[0]):
for i in range(self.nsupport):
self.y[j] += self.lam[i]*self.t[i]*K[j,i]
return self.y
#Partie de classification pour le noyau RBF
elif self.kernel == 'rbf':
def classifier(Y):
K = np.dot(Y,self.X.T)
c = (1./self.sigma * np.sum(Y**2,axis=1)*np.ones((1,np.shape(Y)[0]))).T
c = np.dot(c,np.ones((1,np.shape(K)[1])))
aa = np.dot(self.xsquared[self.sv],np.ones((1,np.shape(K)[0]))).T
K = K - 0.5*c - 0.5*aa
K = np.exp(K/(2.*self.sigma**2))
self.y = np.zeros((np.shape(Y)[0],1))
for j in range(np.shape(Y)[0]):
for i in range(self.nsupport):
self.y[j] += self.lam[i]*self.t[i]*K[j,i]
self.y[j] += self.b
return self.y
else:
print "[Error] There is not this Kernel --",self.kernel
return
self.classifier = classifier
if __name__ == "__main__":
from svm import svm
#Définir les données d'entraînement
cls1 = [] #Classe 1
cls2 = [] #Classe 2
mean1 = [-1, 2]
mean2 = [1, -1]
cov = [[1.0,0.8], [0.8, 1.0]]
N = 100
#Créez des données d'entraînement de classe 1 avec des nombres aléatoires
cls1.extend(np.random.multivariate_normal(mean1, cov, N/2))
#Créez des données d'entraînement de classe 2 avec des nombres aléatoires
cls2.extend(np.random.multivariate_normal(mean2, cov, N/2))
#Créer une matrice de données X
X = np.vstack((cls1, cls2))
#Créer une étiquette t
t = []
for i in range(N/2):
t.append(1.0) #Classe 1
for i in range(N/2):
t.append(-1.0) #Classe 2
t = np.array(t)
#Dessiner des données d'entraînement
x1, x2 = np.array(cls1).transpose()
plt.plot(x1, x2, 'rx')
x1, x2 = np.array(cls2).transpose()
plt.plot(x1, x2, 'bx')
sv = svm(kernel='linear',degree=3)
#Apprendre le svm
sv.train_svm(X,t)
#Dessiner un vecteur de support
for n in sv.sv:
plt.scatter(X[n,0], X[n,1], s=80, c='c', marker='o')
#Tracer des limites d'identification
step = 0.1
f0,f1 = np.meshgrid(np.arange(np.min(X[:,0])-0.5, np.max(X[:,0])+0.5, step), np.arange(np.min(X[:,1])-0.5, np.max(X[:,1])+0.5, step))
out = sv.classifier(np.c_[np.ravel(f0),np.ravel(f1)]).T
out = out.reshape(f0.shape)
plt.contour(f0,f1,out,1)
plt.show()
6. Références
6.1. Fonctionnaire de Hesse
Quand en 2 dimensions http://www004.upp.so-net.ne.jp/s_honma/urawaza/distance.htm En 3D http://yosshy.sansu.org/distance1.htm
6.2. Méthode du multiplicateur indéterminé de Lagrange
http://fd.kuaero.kyoto-u.ac.jp/sites/default/files/Lagrange1.pdf https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95
6.3. Conditions KKT
http://www.msi.co.jp/nuopt/glossary/term_da98193bc878eb73f1624989004cfa809e13590a.html 6.4. SVM Machine Learning: An Algorithmic Perspective, Second Edition (Chapman & Hall/Crc Machine Learning & Pattern Recognition) [Data Science 6 Machine Learning Learned with R](http://www.amazon.co.jp/%E3%83%9E%E3%82%B7%E3%83%B3%E3%83%A9%E3% 83% BC% E3% 83% 8B% E3% 83% B3% E3% 82% B0-R% E3% 81% A7% E5% AD% A6% E3% 81% B6% E3% 83% 87% E3% 83% BC% E3% 82% BF% E3% 82% B5% E3% 82% A4% E3% 82% A8% E3% 83% B3% E3% 82% B9-6-% E8% BE% BB% E8 % B0% B7-% E5% B0% 86% E6% 98% 8E / dp / 4320019261 / ref = sr_1_2? Ie = UTF8 & qid = 1453064931 & sr = 8-2 & mots-clés =% E3% 83% 9E% E3% 82% B7% E3 % 83% B3% E3% 83% A9% E3% 83% BC% E3% 83% 8B% E3% 83% B3% E3% 82% B0) Masaaki Tsujitani (Auteur), Kunio Takezawa (Auteur), Akitetsu Kim (Modifier) [Support Vector Machine](http://www.amazon.co.jp/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3 % 82% AF% E3% 83% 88% E3% 83% AB% E3% 83% 9E% E3% 82% B7% E3% 83% B3-% E6% A9% 9F% E6% A2% B0% E5% AD% A6% E7% BF% 92% E3% 83% 97% E3% 83% AD% E3% 83% 95% E3% 82% A7% E3% 83% 83% E3% 82% B7% E3% 83% A7% E3% 83% 8A% E3% 83% AB% E3% 82% B7% E3% 83% AA% E3% 83% BC% E3% 82% BA-% E7% AB% B9% E5% 86% 85 -% E4% B8% 80% E9% 83% 8E / dp / 4061529064 / ref = sr_1_1? Ie = UTF8 & qid = 1453064806 & sr = 8-1 & mots-clés =% E3% 82% B5% E3% 83% 9D% E3% 83% BC % E3% 83% 88% E3% 83% 99% E3% 82% AF% E3% 83% 88% E3% 83% AB% E3% 83% 9E% E3% 82% B7% E3% 83% B3) Ichiro Takeuchi (Auteur), Masayuki Karasuyama (Auteur) [Première reconnaissance de formes](http://www.amazon.co.jp/%E3%81%AF%E3%81%98%E3%82%81%E3%81%A6%E3%81%AE% E3% 83% 91% E3% 82% BF% E3% 83% BC% E3% 83% B3% E8% AA% 8D% E8% AD% 98-% E5% B9% B3% E4% BA% 95-% E6% 9C% 89% E4% B8% 89 / dp / 4627849710 / ref = sr_1_1? Ie = UTF8 & qid = 1453065064 & sr = 8-1 & mots-clés =% E3% 81% AF% E3% 81% 98% E3% 82% 81% E3 % 81% A6% E3% 81% AE% E3% 83% 91% E3% 82% BF% E3% 83% BC% E3% 83% B3% E8% AA% 8D% E8% AD% 98) Yuzo Hirai (Auteur) Pegasos: Primal Estimated sub-GrAdient SOlver for SVM Shai Shalev-Shwartz,Yoram Singer,Nathan Srebro
Recommended Posts