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

Les étiquettes valent $y \in \{-1,+1\}$, avec un vecteur de poids $w \in \mathbb{R}^{n}$ et un biais $b$.

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.

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

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.

Le score brut est $z = w^T x - b$ et les étiquettes valent $y \in \{-1,+1\}$.

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.

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.

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

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

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) }$$

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.

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

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

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

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

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

---