9. Machines à vecteurs de support
Les machines à vecteurs de support sont des classifieurs linéaires à grande marge. Elles choisissent la frontière qui maximise la distance aux points les plus proches, contrôlent le surapprentissage avec la perte charnière et une pénalité \(C\), et utilisent des noyaux pour ajuster des frontières non linéaires sans jamais former l'application de caractéristiques. Partout, les étiquettes valent \(y \in \{-1,+1\}\) et la décision utilise un score brut \(z = w^T x - b\).
Objectifs
- Définir l'hypothèse SVM, son hyperplan séparateur et la marge géométrique.
- Formuler le primal à marge dure et le primal à marge souple avec perte charnière et pénalité \(C\).
- Définir les noyaux, l'astuce du noyau et la condition de Mercer.
- Former le lagrangien, dériver le dual et les conditions KKT, et définir les vecteurs de support.
9.1 Classifieur à marge optimale
Les étiquettes valent \(y \in \{-1,+1\}\), avec un vecteur de poids \(w \in \mathbb{R}^{n}\) et un biais \(b\).
9.1.1 Hypothèse et frontière
L'hypothèse est définie comme le signe du score brut \(z = w^T x - b\) :
\[\boxed{ h(x) = \operatorname{sign}(w^T x - b) }\]La frontière de décision est l'ensemble des points de score nul :
\[\boxed{ w^T x - b = 0 }\]Remarque : \(w\) est orthogonal à la frontière, il en fixe donc l'orientation, et \(b\) fixe le décalage.
9.1.2 Marge géométrique
La marge géométrique de l'exemple \(i\) est définie comme sa distance signée à la frontière, rendue positive par l'étiquette :
\[\boxed{ \gamma^{(i)} = y^{(i)} \, \frac{w^T x^{(i)} - b}{\lVert w \rVert} }\]Un point correctement classé vérifie \(\gamma^{(i)} > 0\). La marge du jeu de données est la plus petite \(\gamma^{(i)}\) sur tous les exemples.
Remarque : diviser par \(\lVert w \rVert\) rend la marge invariante au rééchelonnement de \((w,b)\), contrairement au score brut \(z\).
9.1.3 Primal à marge dure
En fixant l'échelle pour que les points les plus proches vérifient \(y^{(i)}(w^T x^{(i)} - b) = 1\), maximiser la marge équivaut à minimiser \(\lVert w \rVert^2\) sous une marge fonctionnelle unitaire :
\[\boxed{ \min_{w,b} \tfrac{1}{2}\lVert w \rVert^2 \quad \text{s.c.} \quad y^{(i)}(w^T x^{(i)} - b) \ge 1 \ \ \forall i }\]C'est un programme quadratique convexe à contraintes linéaires, il admet donc un optimum unique.
Remarque : il exige des données linéairement séparables. La leçon suivante assouplit cela avec des variables d'écart.
L'hyperplan optimal (trait plein) maximise la marge (pointillés). Les points entourés sont les vecteurs de support.
9.2 Perte charnière
Le score brut est \(z = w^T x - b\) et les étiquettes valent \(y \in \{-1,+1\}\).
9.2.1 Perte charnière
La perte charnière est définie comme l'écart par lequel la marge \(yz\) tombe sous \(1\), tronqué à zéro :
\[\boxed{ L(z,y) = \max(0,\, 1 - yz), \quad z = w^T x - b }\]Elle est nulle dès que \(yz \ge 1\) (le point est correct et au-delà de la marge) et croît linéairement à l'intérieur ou au-delà de la marge.
Remarque : la perte charnière est convexe mais non dérivable en \(yz = 1\), on l'optimise donc avec des sous-gradients.
9.2.2 Primal à marge souple
On introduit un écart \(\xi_i \ge 0\) par exemple pour autoriser les violations de marge, pénalisé par \(C > 0\) :
\[\boxed{ \min_{w,b,\xi} \tfrac{1}{2}\lVert w \rVert^2 + C\sum_{i=1}^{m}\xi_i \quad \text{s.c.} \quad y^{(i)}(w^T x^{(i)} - b) \ge 1 - \xi_i, \ \ \xi_i \ge 0 }\]À l'optimum \(\xi_i = \max(0,\, 1 - y^{(i)}(w^T x^{(i)} - b))\), donc éliminer les écarts donne la forme régularisée sans contrainte :
\[\boxed{ \min_{w,b} \tfrac{1}{2}\lVert w \rVert^2 + C\sum_{i=1}^{m}\max\!\big(0,\, 1 - y^{(i)}(w^T x^{(i)} - b)\big) }\]C'est de la régularisation plus une perte charnière : le terme \(\tfrac{1}{2}\lVert w \rVert^2\) élargit la marge et la somme pénalise les violations.
9.2.3 Rôle de \(C\)
| \(C\) | Pénalité des violations | Marge | Comportement |
|---|---|---|---|
| petit | faible | large | plus de violations tolérées, variance plus faible |
| grand | forte | étroite | moins de violations, ajuste davantage les données |
Remarque : quand \(C \to \infty\) aucune violation n'est tolérée, ce qui redonne le classifieur à marge dure.
9.3 Noyaux
9.3.1 Définition d'un noyau
Un noyau est défini comme le produit scalaire d'une application de caractéristiques \(\phi\) appliquée à deux entrées :
\[\boxed{ K(x,z) = \phi(x)^T \phi(z) }\]Un noyau valide calcule ce produit scalaire directement, donc \(\phi\) n'a jamais à être formée (elle peut même être de dimension infinie).
9.3.2 Astuce du noyau
Le dual du SVM ne dépend des données qu'à travers des produits scalaires \(\langle x^{(i)}, x^{(j)} \rangle\). L'astuce du noyau remplace chaque produit scalaire par un noyau :
\[\boxed{ \langle x^{(i)}, x^{(j)} \rangle \ \longrightarrow \ K(x^{(i)}, x^{(j)}) }\]Cela ajuste une frontière linéaire dans l'espace de caractéristiques, donc non linéaire dans l'espace d'origine, au prix d'évaluer \(K\) au lieu de \(\phi\).
Un choix très répandu est le noyau gaussien (RBF) :
\[\boxed{ K(x,z) = \exp\!\left( -\frac{\lVert x - z \rVert^2}{2\sigma^2} \right) }\]9.3.3 Condition de Mercer
Une fonction \(K\) est un noyau valide si et seulement si, pour tout échantillon fini, sa matrice de Gram est symétrique semi-définie positive :
\[\boxed{ K = K^T, \qquad K \succeq 0 }\]Remarque : c'est la condition de Mercer. Elle garantit l'existence d'une application \(\phi\), donc le dual reste convexe.
9.3.4 Noyaux usuels
| Noyau | \(K(x,z)\) | Note |
|---|---|---|
| Linéaire | \(x^T z\) | pas d'application, redonne le SVM linéaire |
| Polynomial | \((x^T z + c)^d\) | degré \(d\), décalage \(c\) |
| Gaussien (RBF) | \(\exp\!\big(-\tfrac{\lVert x - z \rVert^2}{2\sigma^2}\big)\) | dimension infinie, local |
Remarque : un petit \(\sigma\) rend le noyau RBF très local, ce qui peut surapprendre. Il se règle en compromis avec \(C\).
Un noyau RBF sépare des classes non linéairement séparables, par une frontière non linéaire dans l'espace d'entrée.
9.4 Lagrangien et dualité
9.4.1 Lagrangien
Pour un objectif primal \(f(w)\) avec contraintes d'inégalité \(g_i(w) \le 0\) et multiplicateurs \(\beta_i \ge 0\), le lagrangien est défini comme :
\[\boxed{ \mathcal{L}(w,\beta) = f(w) + \sum_{i=1}^{m} \beta_i \, g_i(w) }\]Appliqué au primal SVM \(\tfrac{1}{2}\lVert w \rVert^2\) avec contraintes \(1 - y^{(i)}(w^T x^{(i)} - b) \le 0\), les conditions de stationnarité \(\nabla_w \mathcal{L} = 0\) et \(\partial_b \mathcal{L} = 0\) donnent :
\[\boxed{ w = \sum_{i=1}^{m} \beta_i\, y^{(i)} x^{(i)}, \qquad \sum_{i=1}^{m} \beta_i\, y^{(i)} = 0 }\]Le \(w\) optimal est donc une combinaison linéaire des entrées d'apprentissage pondérées par \(\beta_i y^{(i)}\).
9.4.2 Problème dual
En réinjectant ces relations, on élimine \(w\) et \(b\), ce qui laisse un problème en \(\beta\) ne dépendant des données qu'à travers des produits scalaires :
\[\boxed{ \max_{\beta} \ \sum_{i=1}^{m}\beta_i - \tfrac{1}{2}\sum_{i,j}\beta_i \beta_j\, y^{(i)} y^{(j)} \langle x^{(i)}, x^{(j)} \rangle \quad \text{s.c.} \quad \beta_i \ge 0, \ \ \sum_{i}\beta_i y^{(i)} = 0 }\]Les produits scalaires sont exactement l'endroit où l'on substitue un noyau \(K\) (voir Noyaux).
9.4.3 KKT et vecteurs de support
À l'optimum, l'écart complémentaire lie chaque multiplicateur à sa contrainte :
\[\boxed{ \beta_i \big[\, y^{(i)}(w^T x^{(i)} - b) - 1 \,\big] = 0 }\]Les vecteurs de support sont définis comme les exemples à multiplicateur non nul :
\[\boxed{ \text{vecteurs de support} = \{\, i : \beta_i > 0 \,\} }\]Ce sont les points exactement sur la marge. Tous les autres ont \(\beta_i = 0\) et n'influencent pas \(w\).
9.4.4 Décision à noyau
Remplacer le produit scalaire par un noyau donne une règle de décision exprimée uniquement à travers les vecteurs de support :
\[\boxed{ h(x) = \operatorname{sign}\!\left( \sum_{i=1}^{m} \beta_i\, y^{(i)}\, K(x^{(i)}, x) - b \right) }\]Remarque : seuls les vecteurs de support (\(\beta_i > 0\)) contribuent, donc le coût de prédiction croît avec leur nombre, pas avec \(m\).
9.4.5 Du primal à la décision
flowchart TD A["QP primal : minimiser demi norme au carre"] B["lagrangien avec multiplicateurs"] C["probleme dual en beta"] D["conditions KKT"] E["vecteurs de support : beta superieur a zero"] F["regle de decision a noyau"] A --> B B --> C C --> D D --> E E --> F
Les machines à vecteurs de support tracent une seule frontière, éventuellement à noyau. La dernière partie suit une autre voie : découper l'espace des variables par des règles simples et combiner de nombreux modèles en un ensemble.
Suivant : Arbres de décision et méthodes d'ensemble · Vue d'ensemble du cours