La machine à vecteurs de support

add.png

\bullet Présentation:

La Machine à Vecteurs de Supports (SVM), également connue sous le nom de séparateurs à vaste marge, a été élaborée par Vladimir Vapnik en 1995. Elle est utilisée pour la classification d’une variable réponse binaire Y à partir d’une matrice \mathbf{X} = (X ^1, \cdots, X ^P) de P variables explicatives continues.

Les SVM s’appuient sur la notion de marge maximale et la notion de fonction noyau (kernel), permettant de traiter des problèmes de discrimination non-linéaire en reformulant le problème de classement comme un problème d’optimisation quadratique.

Les SVM font parties des techniques d’apprentissage supervisé et nécessitent le passage par une méthode de validation afin de généraliser leur résultat. En effet, il s’agit d’un outil très puissant permettant de modéliser avec une extrême précision un phénomène en fonction du noyau considéré, augmentant ainsi fortement le risque de surapprentissage.

\bullet Les machines à vecteurs de support:

Hypothèse préliminaire: Y binaire, \mathbf{X} continue.

L’Algorithme:

Le calcul des coefficients via les SVM est particulièrement coûteux étant donné qu’il se base sur la recherche d’une solution optimale au travers de noyau pouvant rallonger les ressources de calcul demandée, notamment pour le noyau polynomial. De plus, l’idée principale des SVM est d’estimer les vecteurs supports qui représentent les pondérations associées à chaque observation afin de déterminer leur influence sur l’élaboration de la frontière décisionnelle. En outre, plus il y a d’observations à considérer et plus le système associé à l’estimation de ces pondérations est important.

Quatre étapes sont à suivre pour estimer les coefficients \alpha_i ^*, i \in [1,n^*], qui ne correspondent donc pas aux P variables mais à nos n^* < n individus pour lesquels l’influence est significative (ceux associés à un vecteur support négligeable sont alors supprimés du modèle prédictif final).

– Étape 0: Définir le noyau et les paramètres qui lui sont associés.

– Étape 1: Déterminer l’équation des vecteurs de support à partir des paramètres définis en étape 0,

Q_{\alpha} = \sum_{i = 1} ^n \alpha_i - \frac{1}{2} \sum_{i_1 = 1} ^n \sum_{i_2 = 1} ^n \alpha_{i_1} \alpha_{i_2} Y_{i_1} Y_{i_2} K(X_{i_1}, X_{i_2})

– Étape 2: Déterminer la matrice à résoudre et dont la ième ligne est de la forme,

\alpha_i ^* = \frac{Q_{\alpha}}{\partial Q_{\alpha_i}} = \alpha_i - \frac{1}{2} \sum_{i_2 = 1} ^n \alpha_{i_2} Y_i Y_{i_2} K(X_i, X_{i_2}) = 1, \forall i \in [1,n]

, où \alpha = (\alpha_1, \cdots, \alpha_n) représente le vecteur des multiplicateurs de Lagrange.

– Étape 3: Rajouter à la matrice, conçue en étape 2, le vecteur en ligne et basé sur la contrainte de construction des \alpha, \sum_{i = 1} ^n Y_i \alpha_i = 0. Ce système est alors noté \blacksquare.

– Étape 4: Résoudre le système \blacksquare via les multiplicateurs de Lagrange afin d’obtenir les estimations (\alpha_1 ^*, \cdots, \alpha_n ^*).

Équation prédictive:

L’Algorithme permet de déterminer les Lagrangiens \alpha ^* soit les coefficients d’influence de nos vecteurs supports associés aux différentes observations. Cependant, les estimations \alpha ^* ne sont pas suffisants pour la prédiction d’une nouvelle observation. Définissons E ^* l’ensemble des observations associées à un vecteur support non nul et dont l’influence doit être considérée pour la prédiction. L’Équation de prédiction est alors,

f(x) = \sum_{i \in E ^*} \alpha_i ^* Y_i < X_i, x> + \beta_0

Où,

x est la notation utilisée pour désigner les valeurs caractéristiques associées aux variables explicatives considérées pour la nouvelle observation à prédire,

<.,.> le produit scalaire,

\beta_0 le coefficient constant obtenu par,

i; \beta_0 = Y_i - \sum_{p = 1} ^P X_i ^p \beta_p

, et dont la valeur ne varie pas quelque soit l’observation i utilisée.

\beta = (\beta_1, \cdots, \beta_P) les coefficients obtenus par,

\forall p \in [1,P], \beta_p = \sum_{i = 1} ^n \alpha_i ^* X_i ^p

Le choix du noyau:

Deux cas sont à distinguer lors de l’usage des SVM: le cas linéairement séparable et non linéairement séparable. Pour le premier, cela revient à construire une frontière linéaire optimale selon la notion de marge maximale. Le noyau est alors le noyau linéaire de formulation,

K(X_{i_1},X_{i_2}) = X{i_1} \cdot X_{i_2}

Pour le second cas, l’idée est de passer la construction d’une nouvelle dimension qui va envoyer les données dans un espace où la séparation est possible. Trois noyaux principaux existent parmi la longue liste disponible,

– le noyau polynomial K(X_{i_1},X_{i_2}) = (\gamma \cdot X_{i_1} ^T \cdot X_{i_2} + w_0) ^d,

– le noyau radial K(X_{i_1},X_{i_2}) = e^{- \gamma \cdot \Vert X_{i_1} - X_{i_2} \Vert ^2}, avec,

\Vert X_{i_1} - X_{i_2} \Vert = \sqrt{<X_{i_1},X_{i_1}> + <X_{i_2},X_{i_2}> - 2 <X_{i_1},X_{i_2}>}

– le noyau sigmoïdale K(X_{i_1},X_{i_2}) = tanh(\gamma \cdot X_{i_1} ^T \cdot X_{i_2} + w_0).

\gamma, w_0 et d sont les paramètres à figer.

La sélection de variable:

Le choix des variables à retenir dans le modèle final amène à l’introduction du principe de « marge ». La marge correspond à la distance entre la frontière construite par le modèle et ses vecteurs supports. En général, un modèle est de bonne qualité si la marge est suffisamment éloignée des vecteurs supports, permettant ainsi plus d’aisance dans sa généralisation.

La sélection des variables se fait en fonction de la marge associée et notamment de sa sensibilité. L’Idée est de s’orienter vers un modèle dont la marge est la plus robuste possible.

La marge se calcul selon la formule suivante,

m = \frac{2}{|| \beta ||} = \frac{2}{\sqrt{\sum_{i_1 = 1} ^n \sum_{i_2 = 1} ^n \alpha_{i_1} \alpha_{i_2} Y_{i_1} Y_{i_2} <X_{i_1},X_{i_2}>}}

En définissant un facteur échelle v qui est en fait le vecteur unitaire pondérant le noyau utilisé K, le système à résoudre pour définir la sensibilité de la marge est alors,

| \frac{\partial || w || ^2}{\partial v} | = | -2 \sum_{i_1, i_2} \alpha_{i_1} ^* \alpha_{i_2} ^* Y_{i_1} Y_{i_2} \frac{\partial K(v X_{i_1},v X_{i_2})}{\partial v} |

Généralisation au cas multiclasse:

Les SVM ne sont pas directement transposables au cas multiclasse du fait d’une formule d’estimation basée sur un principe binaire. Pour se faire, l’idée est d’appliquer une approche du type « 1-contre-1 » et qui consiste, pour K classes, à construire \frac{K \times (K - 1)}{2} classifieurs et d’avoir recours à un schéma de vote afin de décider de la classe de prédiction.

\bullet Annexe théorique:

Nous présentons ici une esquisse de la démarche méthodologique conduisant à l’algorithme d’estimation des coefficients \alpha d’un modèle basé sur les SVM.

Nous nous plaçons dans l’espace E munit du produit scalaire. L’objectif est de construire une fonction h qui sépare au mieux \mathbf{X}.

Le cas linéairement séparable:

Le plus simple, il s’écrit sous la forme suivante,

h(\mathbf{X}) = w ^t \cdot \mathbf{X} + w_0

Avec,

h(X_i) \geq 0 \Rightarrow Y_i = 1,

h(X_i) < 0 \Rightarrow Y_i = -1,

La frontière de décision h(\mathbf{X}) = 0 est un hyperplan, appelé hyperplan séparateur ou séparatrice. L’objectif est d’avoir,

\forall i \in [1,n], y_i \cdot h(X_i) \geq 0

Notion de marge maximale:

L’équation du séparateur linéaire montre que nous pouvons générer une infinité de classifieurs, la notion de marge prend alors toute son importance. Elle se définit comme étant la distance entre l’hyperplan et les observations les plus proches qui sont en fait nos vecteurs supports. L’hyperplan, à déterminer et qui maximise la marge, est donné par,

arg \hspace*{1mm} max_{w,w_0} min_i {\parallel \mathbf{X} - X_i \parallel : \mathbf{X} \in \mathbb{R} ^n / h(\mathbf{X}) = w^t \cdot \mathbf{X} + w_0 = 0}

Formulation primale:

La distance de X_i à l’hyperplan est donnée par sa projection orthogonale sur l’hyperplan,

\frac{y_i \cdot (w^T \cdot X_i + w_0)}{\parallel w \parallel}

La formule que nous recherchons se construit sous la contrainte:

arg \hspace*{1mm} max_{w,w_0} {\frac{1}{\parallel w \parallel} min_i [y_i \cdot (w^t \cdot X_i + w_0)]}

Afin de faciliter l’optimisation, nous choisissons de normaliser w et w_0, de telle manière à ce que les observations à la marge (\mathbf{X}_+ pour les vecteurs supports sur la frontière positive, et \mathbf{X}_- pour ceux situés sur la frontière opposée) satisfassent,

w^t \cdot \mathbf{X}_+ + w_0 = +1

w^t \cdot \mathbf{X}_- + w_0 = -1

La marge à maximiser vaut alors \frac{1}{\parallel w \parallel}. La formulation dite primale des SVM est ainsi,

Minimiser \frac{1}{2} \parallel w \parallel ^2 sous contraintes que y_i \cdot (w^t \cdot X_i + w_0) \geq 1

Ceci peut se résoudre par la méthode classique des multiplicateurs de Lagrange \alpha, où le lagrangien est donné par,

L(w,w_0,\alpha) = \frac{1}{2} \parallel w \parallel ^2 - \sum_{i = 1} ^n \alpha_i \cdot {y_i \cdot (w^t  \cdot X_i + w_0) - 1} \hspace*{10mm} (\blacksquare)

Formulation duale:

Le lagrangien doit être minimisé par rapport à w et w_0, et maximisé par rapport à \alpha. Pour cela nous posons notre problème sous forme duale. Nous cherchons ainsi à annuler les dérivées partielles du lagrangien, selon les conditions de Kuhn-Tucker, Nous obtenons,

\sum_{i = 1} ^n \alpha_i \cdot y_i \cdot X_i = w^*

\sum_{i = 1} ^n \alpha_i \cdot y_i = 0

En réinjectant ces valeurs dans l’équation (\blacksquare), nous avons la formulation duale suivante,

Maximiser L(\alpha) = \sum_{i = 1} ^n \alpha_i - \frac{1}{2} \sum_{i_1,i_2} ^n \alpha_{i_1} \cdot \alpha_{i_2} \cdot y_{i_1} \cdot y_{i_2} \cdot X_{i_1} ^t \cdot X_{i_2}

, sous les contraintes \alpha_i \geq 0, et \sum_{i = 1} ^n \alpha_i y_i.

Ce qui nous donne les multiplicateurs de Lagrange optimaux \alpha_i ^*. L’Equation de l’hyperplan solution devient alors,

h(x) = \sum_{i = 1} ^n \alpha_i ^* \cdot y_i \cdot (x \cdot X_i) + w_0

Le cas non linéairement séparable:

Finalement l’hyperplan solution ne dépend que du produit scalaire entre \mathbf{X} et les vecteurs supports. Cette remarque est à l’origine de la deuxième innovation majeure des SVM: l’utilisation de la fonction noyau pour projeter \mathbf{X} dans un espace dit de redescription.

Plus formellement, nous appliquons aux vecteurs d’entrée \mathbf{X}, une transformation non-linéaire notée \varphi.

Dans cet espace, nous cherchons alors l’hyperplan,

h(\mathbf{X}) = w^t \cdot \varphi(\mathbf{X}) + w_0

, qui vérifie \forall i \in [1,n], y_i \cdot h(X_i) > 0.

En utilisant la même procédure que dans le cas sans transformation, nous aboutissons au problème d’optimisation suivant,

Maximiser L(\alpha) = \sum_{i = 1} ^n \alpha_i - \frac{1}{2} \sum_{i_1,i_2} ^n \alpha_{i_1} \cdot \alpha_{i_2} \cdot y_{i_1} \cdot y_{i_2} \cdot \varphi(X_{i_1})^t \cdot \varphi(X_{i_2})

, sous contraintes \alpha_i \geq 0, et \sum_{i = 1} ^n \alpha_i \cdot y_i = 0.

La fonction noyau:

Le problème de la formulation ci-dessus est qu’elle implique un produit scalaire entre vecteurs dans l’espace de redescription et de dimension élevée, ce qui est couteux en termes de calculs. Pour résoudre ce problème, nous utilisons une astuce connue sous le nom de « Kernel trick » consistant à utiliser une fonction noyau vérifiant,

K(X_{i_1}, X_{i_2}) = \varphi(X_{i_1})^t \cdot \varphi(X_{i_2})

D’où l’expression de l’hyperplan séparateur en fonction de la fonction noyau,

h(x) = \sum_{i = 1} ^n \alpha_i ^* \cdot y_i \cdot K(X_i, x) + w_0

L’intérêt de la fonction noyau est double,

– le calcul se fait dans l’espace d’origine, ceci est beaucoup moins coûteux qu’un produit scalaire en grande dimension,

– la transformation \varphi n’a pas besoin d’être connue explicitement, seule la fonction noyau intervient dans les calculs, augmentant nettement les possibilités de discrimination.

Enfin, en accords avec le théorème de Mercer, \varphi doit être symétrique et semi-définie positive. L’approche par Kernel trick généralise ainsi l’approche linéaire.

Extension aux marges souples:

Cependant, il n’est pas non plus toujours possible de trouver une séparatrice linéaire dans l’espace de redescription. Il se peut aussi que des observations soient mal étiquetées et que l’hyperplan séparateur ne soit pas la meilleure solution au problème de classement.

Nous nous ramenons alors à la technique dite de marge souple, qui tolère les mauvais classements. La méthode cherche un hyperplan séparateur qui minimise le nombre d’erreurs grâce à l’introduction de variables ressorts \xi_i, qui permettent de relâcher les contraintes sur les vecteurs d’apprentissage:

\forall \xi_i \geq 0, i \in [1,n], y_i \cdot (w^t \cdot X_i + w_0) \geq 1 - \xi_i

Avec les contraintes précédentes, le problème d’optimisation est modifié par un terme de pénalité qui agit directement sur les variables ressorts élevées et de formulation:

Minimiser \frac{1}{2} \parallel w \parallel ^2 + C \cdot \sum_{i = 1} ^n \xi_i, C > 0

, où C est une constante qui permet de contrôler le compromis entre nombre d’erreurs de classement et la largeur de la marge.

\bullet Exemple:

Soit le jeu de données suivant,

add

Certains le reconnaîtront, il s’agit de la fonction XOR également appelée fonction OU exclusif. Essayons de résoudre le problème en fonction des trois fonctions noyaux décrites pour le cas non linéairement séparable. La matrice de données qui lui est associée est la suivante,

\mathbf{X} = \begin{pmatrix} Y & X1 & X2 \\ -1 & -1 & -1 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \\ -1 & 1 & 1 \\ \end{pmatrix}

Cas du noyau sigmoïdale:

Soit le noyau sigmoïdale de constante C = 1 et de paramètre \gamma = 1,

K(X_{i_1}, X_{i_2}) = tanh(1 + X_{i_1} ^1 X_{i_2} ^1 + X_{i_1} ^2 X_{i_2} ^2)

Nous calculons pour chaque combinaison d’observations le valeur du noyau,

\mathbf{Q} = \begin{pmatrix} i_1 & i_2 & Y_{i_1} \times Y_{i_2} \times K(X_{i_1}, X_{i_2}) \\ 1 & 1 & 0.9950548 \\ 1 & 2 & -0.7615942 \\ 1 & 3 & -0.76159421 \\ 1 & 4 & -0.7615942 \\ 2 & 1 & -0.7615942 \\ 2 & 2 & 0.9950548 \\ 2 & 3 & -0.7615942 \\ 2 & 4 & -0.7615942 \\ 3 & 1 & -0.7615942 \\ 3 & 2 & -0.7615942 \\ 3 & 3 & 0.9950548 \\ 3 & 4 & -0.7615942 \\ 4 & 1 & -0.7615942 \\ 4 & 2 & -0.7615942 \\ 4 & 3 & -0.7615942 \\ 4 & 4 & 0.9950548 \\ \end{pmatrix}

En rappelant la formule générale des Q_{\alpha},

Q_{\alpha} = \sum_{i = 1} ^n \alpha_i - \frac{1}{2} \cdot \sum_{i_1, i_2} ^n \alpha_{i_1} \alpha_{i_2} Q(i_1, i_2)

, nous obtenons la dérivation suivante,

\alpha_i ^* = \frac{\partial Q_{\alpha}}{\partial \alpha_i} = 1

\Rightarrow \alpha_i ^* = 1 - \sum_{i_2 = 1} ^n \alpha_{i_2} \times Q(i,i_2) = 1

\Rightarrow \alpha_i ^* = - \sum_{i_2 = 1} ^n \alpha_{i_2} \times Q(i,i_2)

Si nous raisonnons en termes de matrice afin de simplifier les calculs, cela revient à transposer les éléments de \mathbf{Q} en fonction de i_1. Nous obtenons alors la matrice,

\begin{pmatrix} \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 \\ -0.9950548 & 0.7615942 & 0.7615942 & 0.7615942 \\ 0.7615942 & -0.9950548 & 0.7615942 & 0.7615942 \\ 0.7615942 & 0.7615942 & -0.9950548 & 0.7615942 \\ 0.7615942 & 0.7615942 & 0.7615942 & -0.9950548 \\ \end{pmatrix}

Comme sous sommes sous contraintes que \sum_{i = 1} ^5 Y_i \times \alpha_i ^* = 0, nous rajoutons la condition au système à résoudre ainsi que la valeur de l’égalité (qui vaut -1 car, pour respecter le passage des équations à la forme matricielle du problème, nous faisons pivoter le coefficient constant associé à la somme des \alpha_i à droite),

\mathbf{S} = \begin{pmatrix} Y_t & \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 \\ -1 & -0.9950548 & 0.7615942 & 0.7615942 & 0.7615942 \\ -1 & 0.7615942 & -0.9950548 & 0.7615942 & 0.7615942 \\ -1 & 0.7615942 & 0.7615942 & -0.9950548 & 0.7615942 \\ -1 & 0.7615942 & 0.7615942 & 0.7615942 & -0.9950548 \\ 0 & 1 & -1 & -1 & 1 \end{pmatrix}

Nous résolvons ce système avec une régression linéaire et obtenons,

\alpha_1 ^* = \alpha_2 ^* = \alpha_3 ^* = \alpha_4 ^* = -0.7754

Tous nos coefficients sont différents de 0, nous en déduisons que pour ce noyau les quatre observations jouent un rôle de vecteur support.

Maintenant que les coefficients ont été estimés, nous pouvons déterminer la valeur de prédiction de X_1. Nous calculons dans un premier temps les coefficients \beta associés aux \alpha ^*,

\beta = (-0.7754 \times (-1) \times (-1) + (-0.7754) \times 1 \times (-1) + (-0.7754) \times 1 \times 1 + (-0.7754) \times (-1) \times 1, -0.7754 \times (-1) \times (-1) + (-0.7754) \times 1 \times 1 + (-0.7754) \times 1 \times (-1) + (-0.7754) \times (-1) \times 1)

= (0,0)

\Rightarrow \beta_0 = Y_1 - X_1 ^t \times \beta = Y_1 = -1

Nous pouvons maintenant déterminer la prédiction de X ^1 sur la base du modèle construit,

f(X_1) = \sum_{i = 1} ^4 \alpha_i ^* Y_i <X_i,X_1> + \beta_0

= -0.7754 \times (-1) \times ((-1) ^2 + (-1) ^2) + (-0.7754) \times 1 \times (-1 \times (-1) + (-1) \times 1) + (-0.7754) \times 1 \times ((-1) \times 1 + (-1) \times (-1)) + (-0.7754) \times (-1) \times ((-1) \times 1 + (-1) \times 1) + (-1)

= 0.7754 \times 2 - 0.7754 \times 0 -0.7754 \times 0 + 0.7754 \times (-2) - 1

= 1.5508 - 1.5508 - 1

\Rightarrow f(X_1) = - 1

Cas du noyau radial:

Soit le noyau radial de paramètre \gamma = 1,

K(X_{i_1}, X_{i_2}) = e ^{|| X_{i_1} - X_{i_2} || ^2}

Nous calculons pour chaque combinaison d’observations le valeur du noyau,

\mathbf{Q} = \begin{pmatrix} i_1 & i_2 & Y_{i_1} \times Y_{i_2} \times K(X_{i_1}, X_{i_2}) \\ 1 & 1 & 1 \\ 1 & 2 & -0.0183156389 \\ 1 & 3 & -0.0183156389 \\ 1 & 4 & 0.0003354626 \\ 2 & 1 & -0.0183156389 \\ 2 & 2 & 1 \\ 2 & 3 & 0.0003354626 \\ 2 & 4 & -0.0183156389 \\ 3 & 1 & -0.0183156389 \\ 3 & 2 & 0.0003354626 \\ 3 & 3 & 1 \\ 3 & 4 & -0.0183156389 \\ 4 & 1 & 0.0003354626 \\ 4 & 2 & -0.0183156389 \\ 4 & 3 & -0.0183156389 \\ 4 & 4 & 1 \\ \end{pmatrix}

En rappelant la formule générale des Q_{\alpha},

Q_{\alpha} = \sum_{i = 1} ^n \alpha_i - \frac{1}{2} \cdot \sum_{i_1, i_2} ^n \alpha_{i_1} \alpha_{i_2} Q(i_1, i_2)

, nous obtenons la dérivation suivante,

\alpha_i ^* = \frac{\partial Q_{\alpha}}{\partial \alpha_i} = 1

\Rightarrow \alpha_i ^* = 1 - \sum_{i_2 = 1} ^n \alpha_{i_2} \times Q(i,i_2) = 1

\Rightarrow \alpha_i ^* = - \sum_{i_2 = 1} ^n \alpha_{i_2} \times Q(i,i_2)

Si nous raisonnons en termes de matrice afin de simplifier les calculs, cela revient à transposer les éléments de \mathbf{Q} en fonction de i_1. Nous obtenons alors la matrice,

\begin{pmatrix} \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 \\ -1 & 0.0183156389 & 0.0183156389 & -0.0003354626 \\ 0.0183156389 & -1 & -0.00032354626 & 0.0183156389 \\ 0.0183156389 & -0.0003354626 & -1 & 0.0183156389 \\ -0.0003354626 & 0.0183156389 & 0.0183156389 & -1 \\ \end{pmatrix}

Comme sous sommes sous contraintes que \sum_{i = 1} ^5 Y_i \times \alpha_i ^* = 0, nous rajoutons la condition au système à résoudre ainsi que la valeur de l’égalité (qui vaut -1 car, pour respecter le passage des équations à la forme matricielle du problème, nous faisons pivoter le coefficient constant associé à la somme des \alpha_i à droite),

\mathbf{S} = \begin{pmatrix} Y_t & \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 \\ -1 & -1 & 0.0183156389 & 0.0183156389 & -0.0003354626 \\ -1 & 0.0183156389 & -1 & -0.00032354626 & 0.0183156389 \\ -1 & 0.0183156389 & -0.0003354626 & -1 & 0.0183156389 \\ -1 & -0.0003354626 & 0.0183156389 & 0.0183156389 & -1 \\ 0 & 1 & -1 & -1 & 1 \end{pmatrix}

Nous résolvons ce système avec une régression linéaire et obtenons,

\alpha_1 ^* = \alpha_2 ^* = \alpha_3 ^* = \alpha_4 ^* = 1.038

Tous nos coefficients sont différents de 0, nous en déduisons que pour ce noyau les quatre observations jouent un rôle de vecteur support.

Maintenant que les coefficients ont été estimés, nous pouvons déterminer la valeur de prédiction de X_1. Nous déterminons dans un premier temps les coefficients \beta associé aux \alpha ^*,

\beta = (1.038 \times (-1) \times (-1) + 1.038 \times 1 \times (-1) + 1.038 \times 1 \times 1 + 1.038 \times (-1) \times 1, 1.038 \times (-1) \times (-1) + 1.038 \times 1 \times 1 + 1.038 \times 1 \times (-1) + 1.038 \times (-1) \times 1)

= (0,0)

\Rightarrow \beta_0 = Y_1 - X_1 ^t \times \beta = Y_1 = -1

Nous pouvons maintenant déterminer la prédiction de X ^1 sur la base du modèle construit,

f(X_1) = \sum_{i = 1} ^4 \alpha_i ^* Y_i <X_i,X_1> + \beta_0

= 1.038 \times (-1) \times ((-1) ^2 + (-1) ^2) + 1.038 \times 1 \times (-1 \times (-1) + (-1) \times 1) + 1.038 \times 1 \times ((-1) \times 1 + (-1) \times (-1)) + 1.038 \times (-1) \times ((-1) \times 1 + (-1) \times 1) + (-1)

= - 1.038 \times 2 + 1.038 \times 0 + 1.038 \times 0 - 1.038 \times (-2) - 1

= -2.076 + 2.076 - 1

\Rightarrow f(X_1) = - 1

Cas du noyau polynomial:

Soit le noyau polynomial de degré 2, de constante C = 1 et de paramètre \gamma = 1,

K(X_{i_1}, X_{i_2}) = (1 + X_{i_1} ^1 X_{i_2} ^1 + X_{i_1} ^2 X_{i_2} ^2) ^2

Nous calculons pour chaque combinaison d’observations le valeur du noyau,

\mathbf{Q} = \begin{pmatrix} i_1 & i_2 & Y_{i_1} \times Y_{i_2} \times K(X_{i_1}, X_{i_2}) \\ 1 & 1 & 9 \\ 1 & 2 & -1 \\ 1 & 3 & -1 \\ 1 & 4 & 1 \\ 2 & 1 & -1 \\ 2 & 2 & 9 \\ 2 & 3 & 1 \\ 2 & 4 & -1 \\ 3 & 1 & -1 \\ 3 & 2 & 1 \\ 3 & 3 & 9 \\ 3 & 4 & -1 \\ 4 & 1 & 1 \\ 4 & 2 & -1 \\ 4 & 3 & -1 \\ 4 & 4 & 9 \\ \end{pmatrix}

En rappelant la formule générale des Q_{\alpha},

Q_{\alpha} = \sum_{i = 1} ^n \alpha_i - \frac{1}{2} \cdot \sum_{i_1, i_2} ^n \alpha_{i_1} \alpha_{i_2} Q(i_1, i_2)

, nous obtenons la dérivation suivante,

\alpha_i ^* = \frac{\partial Q_{\alpha}}{\partial \alpha_i} = 1

\Rightarrow \alpha_i ^* = 1 - \sum_{i_2 = 1} ^n \alpha_{i_2} \times Q(i,i_2) = 1

\Rightarrow \alpha_i ^* = - \sum_{i_2 = 1} ^n \alpha_{i_2} \times Q(i,i_2)

Si nous raisonnons en termes de matrice afin de simplifier les calculs, cela revient à transposer les éléments de \mathbf{Q} en fonction de i_1. Nous obtenons alors la matrice,

\begin{pmatrix} \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 \\ -9 & 1 & 1 & -1 \\ 1 & -9 & -1 & 1 \\ 1 & -1 & -9 & 1 \\ -1 & 1 & 1 & -9 \\ \end{pmatrix}

Comme sous sommes sous contraintes que \sum_{i = 1} ^5 Y_i \times \alpha_i ^* = 0, nous rajoutons la condition au système à résoudre ainsi que la valeur de l’égalité (qui vaut -1 car, pour respecter le passage des équations à la forme matricielle du problème, nous faisons pivoter le coefficient constant associé à la somme des \alpha_i à droite),

\mathbf{S} = \begin{pmatrix} Y_t & \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 \\ -1 & -9 & 1 & 1 & -1 \\ -1 & 1 & -9 & -1 & 1 \\ -1 & 1 & -1 & -9 & 1 \\ -1 & -1 & 1 & 1 & -9 \\ 0 & 1 & -1 & -1 & 1 \end{pmatrix}

Nous résolvons ce système avec une régression linéaire et obtenons,

\alpha_1 ^* = \alpha_2 ^* = \alpha_3 ^* = \alpha_4 ^* = 0.125

Tous nos coefficients sont différents de 0, nous en déduisons que pour ce noyau les quatre observations jouent un rôle de vecteur support.

Maintenant que les coefficients ont été estimés, nous pouvons déterminer la valeur de prédiction de X_1. Nous déterminons dans un premier temps les coefficients \beta associé aux \alpha ^*,

\beta = (0.125 \times (-1) \times (-1) + 0.125 \times 1 \times (-1) + 0.125 \times 1 \times 1 + 0.125 \times (-1) \times 1, 0.125 \times (-1) \times (-1) + 0.125 \times 1 \times 1 + 0.125 \times 1 \times (-1) + 0.125 \times (-1) \times 1)

=(0,0)

\Rightarrow \beta_0 = Y_1 - X_1 ^t \times \beta = Y_1 = -1

Nous pouvons maintenant déterminer la prédiction de X ^1 sur la base du modèle construit,

f(X_1) = \sum_{i = 1} ^4 \alpha_i ^* Y_i <X_i,X_1> + \beta_0

= 0.125 \times (-1) \times ((-1) ^2 + (-1) ^2) + 0.125 \times 1 \times (-1 \times (-1) + (-1) \times 1) + 0.125 \times 1 \times ((-1) \times 1 + (-1) \times (-1)) + 0.125 \times (-1) \times ((-1) \times 1 + (-1) \times 1) + (-1)

= - 0.125 \times 2 + 0.125 \times 0 + 0.125 \times 0 - 0.125 \times (-2) - 1

= -0.250 + 0.250 - 1

\Rightarrow f(X_1) = - 1

\bullet Application informatique:

Macro SAS:

%macro svm(DATA=,Y=,kernel=);

 /* Macro-programme pour le calcul des coefficients associés aux vecteurs supports.
       Les paramètres: – DATA, indique la base de données à traiter,
                       – Y, la variable réponse binaire ou multiclasse,
                       – kernel, le noyau (sigmoidale, radial, polynomial de degré 1-2-3-4).
       Sortie: la table coeffs_&kernel. des coefficients selon le noyau paramétré.

    /* Options nécessaires pour éviter de saturer le log et mettre en évidence les erreurs */
options nonotes spool;

   /* Sortie liste des variables explicatives */
proc contents data = &DATA. (drop =  &Y.) out = biblio noprint;
run;

    /* Listing variables explicatives et nombre */
proc sql noprint;
select distinct(name) into: list_vars separated by  »  » from biblio;
select count(*) into: nb_vars from biblio;
quit;

    /* Sortie effectif total */
proc sql noprint;
select count(*) into: nobs from &DATA.;
quit;

    /* Initialisation de la matrice des Y_i1 Y_i2 K(X_i1,X_i2) */
data Q;
run;

    /* Calcul par paire d’observations */
%do i1 = 1 %to &nobs.;

        /* Récupération 1ère observation */
data obs1;
set &DATA.;
if _n_ = &i1.;
rename &Y. = &Y.1;
%do p = 1 %to &nb_vars.;
rename %scan(&list_vars.,&p.) = %scan(&list_vars.,&p.)_1;
%end;
run;

%do i2 = 1 %to &nobs.;

            /* Récupération 2nde observation */
data obs2;
set &DATA.;
if _n_ = &i2.;
rename &Y. = &Y.2;
%do p = 1 %to &nb_vars.;
rename %scan(&list_vars.,&p.) = %scan(&list_vars.,&p.)_2;
%end;
run;

            /* Calcul de Y_i1 Y_i2 K(X_i1,X_i2) en fonction du noyau paramétré et de la paire d’observations considérées */
data pair;
merge obs1 obs2;
score = 0;
score1 = 0;
score2 = 0;
%do p = 1 %to &nb_vars.;
score = score + %scan(&list_vars.,&p.)_1*%scan(&list_vars.,&p.)_2;
score1 = score1 + %scan(&list_vars.,&p.)_1*%scan(&list_vars.,&p.)_1;
score2 = score2 + %scan(&list_vars.,&p.)_2*%scan(&list_vars.,&p.)_2;
%end;
%if &kernel. = sigmoidale %then %do;
score = &Y.1*&Y.2*tanh(1 + score);
%end;
%if &kernel. = radial %then %do;
score = &Y.1*&Y.2*exp(-sqrt((score1 + score2 – 2 * score)**2));
%end;
%if &kernel. = polynomial1 %then %do;
score = &Y.1*&Y.2*(1 + score);
%end;
%if &kernel. = polynomial2 %then %do;
score = &Y.1*&Y.2*(1 + score)**2;
%end;
%if &kernel. = polynomial3 %then %do;
score = &Y.1*&Y.2*(1 + score)**3;
%end;
%if &kernel. = polynomial4 %then %do;
score = &Y.1*&Y.2*(1 + score)**4;
%end;
run;

data Qadd;
set pair;
Obs1 = &i1.;
Obs2 = &i2.;
keep Obs1 Obs2 score;
run;

data Q;
set Q Qadd;
run;

%end;

%end;

    /* Finalisation de la liste des croisements et de leur score */
data Q;
set Q;
if Obs1 ne .;
score_deriv = – score;
run;

    /* Initialisation de la matrice des lagrangiens par la contrainte à respecter sum Y_i alpha_i = 0 */
proc transpose data = &DATA. (keep = &Y.) out = matsvm;
run;

data matsvm;
set matsvm;
score = 0;
drop _NAME_;
run;

    /* Pour chaque observation, on récupère la dérivée partielle pour le calcul des Lagrangiens */
%do i = 1 %to &nobs.;

data Qt;
set Q;
if Obs1 = &i.;
keep score_deriv;
run;

proc transpose data = Qt out = matsvm_add;
run;

data matsvm_add;
set matsvm_add;
score = -1;
drop _NAME_;
run;

data matsvm;
set matsvm matsvm_add;
run;

%end;

data matsvm;
set matsvm;
run;

    /* Sortie du dernier Lagrangien en guise de borne supérieur des Lagrangiens à considérer */
data _null_;
set &DATA.;
if _n_ = &nobs.;
lim_vars = compress(« COL »||_n_);
call symput (« lim_vars »,lim_vars);
run;

    /* Calcul des Lagrangiens par régression linéaire */
proc reg data = matsvm;
model score = COL1 — &lim_vars. / noint;
ods exclude NObs FitStatistics ParameterEstimates ANOVA;
ods output ParameterEstimates = coeffs;
run;

    /* Finalisation de la table des résultats finaux */
data Coeffs_&kernel.;
set coeffs;
Variable = tranwrd(Variable, »Alpha », »COL »);
Support = « N »;
if Estimate ne 0 then Support = « O »;
keep Variable Estimate Support;
run;

    /* Suppression des tables temporaires inutiles */
proc datasets lib = work nolist;
delete matsvm biblio Q Obs1 Obs2 pair Qadd Qt matsvm_add coeffs;
run;

    /* Reset des options */
options notes nospool;

%mend;

Package et fonction R: https://cran.r-project.org/web/packages/e1071/index.html

\bullet Bibliographie:

– The Elements of Statistical Learning de Trevor Hastie, Robert Tibshirani et Jerome Friedman.

– The Top Ten Algorithms in Data Minig de Xindong Wu et Vipin Kumar.

– Data Mining et statistique décisionnelle. L’intelligence des données de Stéphane Tufféry.

– Probabilité, analyse des données et statistique de Gilbert Saporta.

– SVM, Support Vector Machine. Machines à Vecteurs de Support – Séparateurs à Vaste Marge de Ricco Rakotomalala.

– Méthodes à noyaux – PART I de Alain Rakotomamonjy et Stéphane Canu.

– L’Article web: https://www.math.univ-toulouse.fr/~besse/Wikistat/pdf/st-m-app-svm.pdf

– Sélection de variables par SVM: application à la détection de piétons SVM Variable selection with application to pedestrian detection d’Alain Rakotomamonjy et de Frédéric Suard.