Machines à vecteurs de supportSupport Vector Machines — Constrained Optimization · Cours 6 & 7 (9/29, 10/1)

Slides 4-svms (44 p.) PRML §7.1 p.326–344 PRML §6.1–6.2 kernels p.293–299 PRML annexe E (Lagrange) p.707

Ce chapitre répond à une seule question : parmi tous les hyperplans qui séparent deux classes, lequel choisir, et comment le calculer ? La réponse — laisser la rue la plus large entre les classes — donne un problème d'optimisation sous contraintes ; on apprend l'outil pour le résoudre (Lagrangien, dualité), puis on étend la méthode aux données non séparables et aux frontières non linéaires. Au début de chaque section, un encadré Où on en est fait le point.

Feuille de route

Slides p.2 (plan)

Les slides découpent le cours en quatre blocs : (Modèle) le classifieur à marge maximale (§1–2) ; (Préliminaires) l'optimisation sous contraintes (§3) ; (Apprentissage) la SVM par le primal et le dual, puis la marge souple (§4–5) ; (Modèle) du linéaire au non linéaire avec les noyaux (§6). La chaîne complète, cliquable :

① Critère · §1la marge géométrique $\rho_f = \min_i\frac{|f(\bx_i)|}{\|\bw\|}$distance du point le plus proche

→

② Problème · §2$\min\frac12\|\bw\|^2$ s.c. $y_i(\bw\T\bx_i+b)\ge1$grâce à l'invariance d'échelle

→

③ Outil · §3Lagrangien et dualitécontraintes → jeu $\min\max$

→

④ Résolution · §4dual en $\boldsymbol\alpha$, $\bw = \sum_i\alpha_iy_i\bx_i$seuls les vecteurs de support comptent

→

⑤ Non séparable · §5marge souple $\xi_i$, constante $C$= hinge loss + régularisation

→

⑥ Non linéaire · §6$\bx_i\T\bx_j\ \to\ \kappa(\bx_i,\bx_j)$kernel trick

Le raisonnement, maillon par maillon

①Définir ce qu'est un « bon » séparateur. Si les données sont séparables, une infinité d'hyperplans les séparent. On préfère celui qui est le plus loin des points les plus proches : la marge géométrique. Il faut d'abord savoir calculer une distance à un hyperplan : $|\bw\T\bx+b|/\|\bw\|$.
②Écrire le problème. « Maximiser la plus petite distance » est un max-min peu pratique. Comme $(\lambda\bw,\lambda b)$ décrit le même hyperplan, on peut fixer l'échelle pour que le point le plus proche ait $y_i(\bw\T\bx_i+b) = 1$ ; la marge vaut alors $1/\|\bw\|$, et le problème devient : minimiser $\frac12\|\bw\|^2$ sous $N$ contraintes. → Un problème avec contraintes : la descente de gradient ne suffit plus.
③Apprendre l'outil. Le Lagrangien remplace chaque contrainte par une pénalité $\lambda_ig_i(\bx)$ avec $\lambda_i\ge0$. Le problème contraint devient un jeu $\min_\bx\max_{\boldsymbol\lambda}$ ; en échangeant l'ordre on obtient le problème dual, toujours une borne inférieure (dualité faible), égal à l'optimum sous des conditions qui sont vérifiées pour la SVM (dualité forte, KKT).
④Résoudre la SVM par le dual. On minimise d'abord en $(\bw,b)$ (formule close), on réinjecte, on obtient un problème en $\boldsymbol\alpha$ seulement. Résultats : $\bw^* = \sum_i\alpha_i^*y_i\bx_i$ ; seuls les points avec $\alpha_i^*>0$, sur le bord de la rue, comptent (vecteurs de support) ; et les données n'apparaissent que par des produits scalaires $\bx_i\T\bx_j$.
⑤Relâcher la séparabilité. Si aucun hyperplan ne sépare, le problème du §2 n'a pas de solution. On autorise chaque point à violer la marge de $\xi_i\ge0$, payé $C\xi_i$. Le dual change à peine ($0\le\alpha_i\le C$), et le problème équivaut à minimiser $\frac12\|\bw\|^2 + C\sum_i\max\{0,1-y_if(\bx_i)\}$ : la hinge loss, une perte de substitution comme la cross-entropy du chapitre 2.
⑥Passer au non linéaire. Comme au chapitre 1, on remplace $\bx$ par des features $\bphi(\bx)$. Le dual ne demande que les produits $\bphi(\bx_i)\T\bphi(\bx_j)$ : on les remplace par un noyau $\kappa(\bx_i,\bx_j)$ calculé directement, même si $\bphi$ est de dimension infinie (noyau gaussien).

À la fin du chapitre, tu dois savoir…

prouver que $\bw$ est normal à l'hyperplan et que la distance vaut $|f(\bx)|/\|\bw\|$ ;
passer du max-min au problème canonique $\min\frac12\|\bw\|^2$ s.c. $y_i(\bw\T\bx_i+b)\ge1$ ;
écrire un Lagrangien, la fonction duale, et prouver la dualité faible par l'inégalité minimax ;
dériver le dual de la SVM, retrouver $\bw^*$, $b^*$ et reconnaître les vecteurs de support (complémentarité) ;
écrire la SVM à marge souple, son dual ($0\le\alpha_i\le C$) et sa forme hinge ;
expliquer le kernel trick et évaluer un noyau polynomial ou RBF.

Où se trouve chaque question du HW3 dans ce chapitre

P1.(1) marge et normalisation → §1, §2 · P1.(2) dual → §4 · P1.(3) complémentarité et $b^\star$ → KKT, vecteurs de support · P2.(1) marge souple → §5 · P2.(2) comparaison → §5. Indices et corrigés : page Devoirs.

Notations du chapitre

Toutes les lettres utilisées dans la page (et dans les slides), au même endroit. Attention, plusieurs lettres changent de sens en cours de route : voir l'encadré qui suit le tableau.

Symbole	Se lit / signifie	Nature	Où
Données
$N,\ D$	nombre d'exemples ; dimension des entrées	entiers	partout
$\bx_i$	$i$-ième exemple (aussi indicé $j$ ou $n$)	$\R^D$	§1, §2, §4 →
$y_i$	étiquette, obligatoirement $\pm1$ : « bien classé » s'écrit $y_if(\bx_i)>0$	$\{-1,+1\}$	partout
Classifieur et marge (§1–2)
$\bw,\ b$	vecteur normal à l'hyperplan ; biais	$\R^D$, $\R$	partout
$f(\bx) = \bw\T\bx+b$	score ; la prédiction est son signe	réel	partout
$\{\bx : f(\bx) = 0\}$	l'hyperplan séparateur (une droite en 2D)	sous-ensemble de $\R^D$	§1 →
$\rho_f(\bx)$	marge géométrique d'un point : sa distance à l'hyperplan, $\|f(\bx)\|/\\|\bw\\|$	réel $\ge0$	§1
$\rho_f,\ \rho$	marge sur l'échantillon $\min_i\rho_f(\bx_i)$ ; la marge maximale sur tous les $f$	réels $\ge0$	§1, §2
$y_if(\bx_i)$	marge fonctionnelle (le $m$ du chapitre 2), qui dépend de l'échelle de $\bw$	réel	§2
$\bx_p,\ \tau$	projection orthogonale de $\bx$ sur l'hyperplan ; déplacement signé	$\R^D$ ; réel	§1 (preuve)
$\lambda$ (§2)	facteur d'échelle $>0$ : $(\lambda\bw,\lambda b)$ décrit le même hyperplan	réel $>0$	§2
Optimisation sous contraintes (§3 — cadre général)
$\bx$ (§3)	la variable qu'on optimise (pas un exemple !)	$\R^D$	§3
$L(\bx)$	la fonction objectif à minimiser	$\R^D\to\R$	§3
$g_i(\bx)\le0,\ h_j(\bx) = 0$	contraintes d'inégalité ($i = 1..m$, ou $M$) ; d'égalité ($j = 1..P$)	fonctions $\R^D\to\R$	§3
$\delta_{\R_-},\ J(\bx)$	indicatrice « 0 si $\le0$, $+\infty$ sinon » ; objectif + indicatrices des contraintes	$\{0,+\infty\}$ ; réel ou $+\infty$	§3
$\mathfrak L(\bx,\boldsymbol\lambda)$	Lagrangien $L(\bx)+\sum_i\lambda_ig_i(\bx)$ (les slides l'écrivent $\mathcal L$)	réel	§3 →
$\lambda_i,\ \nu_j$ (§3)	multiplicateurs de Lagrange : $\lambda_i\ge0$ (inégalités), $\nu_j\in\R$ (égalités)	réels	§3
$D(\boldsymbol\lambda)$	fonction duale $\min_\bx\mathfrak L(\bx,\boldsymbol\lambda)$	réel	§3, §4
$p^,\ d^$	valeur optimale du primal ; du dual. Dualité faible : $d^\le p^$	réels	§3
$\rho(x,y)$ (§3)	une fonction quelconque de deux variables, dans l'inégalité minimax	réel	§3
SVM primal / dual (§4–5)
$\alpha_i$	multiplicateur de la contrainte du point $i$ (= les $\lambda_i$ du §3, renommés)	réel $\ge0$	§4 →
$\bw^,\ b^,\ \boldsymbol\alpha^*$	solutions optimales	—	§4
vecteur de support	point $\bx_i$ avec $\alpha_i^*>0$ ; il est sur le bord de la rue ($y_if(\bx_i) = 1$)	exemple	§4
$K_{ij}$	matrice de Gram $\bx_i\T\bx_j$ (puis $\kappa(\bx_i,\bx_j)$)	$\R^{N\times N}$	§4, §6
$\xi_i$	variable d'écart (slack) : de combien le point $i$ viole la marge	réel $\ge0$	§5
$C$	prix d'une unité d'écart ; grand $C$ = peu de régularisation	réel $>0$	§5 →
$\beta_i$	multiplicateur de la contrainte $\xi_i\ge0$	réel $\ge0$	§5
$t_i,\ \ell_{\text{hinge}}(t)$	$t_i = y_i(\bw\T\bx_i+b)$ ; hinge loss $\max\{0,1-t\}$	réels	§5
Noyaux (§6)
$\bphi(\bx)$	vecteur de features (comme au chapitre 1), éventuellement de dimension infinie	vecteur	§6
$\kappa(\bx,\bx')$	noyau : remplace $\bphi(\bx)\T\bphi(\bx')$, mesure de similarité	réel	§6
$\sigma$	largeur du noyau gaussien (RBF)	réel $>0$	§6

Pièges de notation (ils viennent des slides)

$\lambda$ a deux sens : au §2 c'est un facteur d'échelle ($\lambda\bw,\lambda b$) ; au §3 ce sont les multiplicateurs de Lagrange $\lambda_i\ge0$. Pour la SVM (§4), les multiplicateurs s'appellent $\alpha_i$.
Au §3, $\bx$ n'est pas un exemple : c'est la variable d'optimisation générique (les slides suivent le livre MML). Au §4, ce rôle est tenu par $(\bw,b)$ et $\bx_i$ redevient un exemple.
$L$ et $\mathfrak L$ : $L(\bx)$ est l'objectif, $\mathfrak L$ (écrit $\mathcal L$ dans les slides) le Lagrangien. Au chapitre 2, $L$ était la log-vraisemblance négative.
$D$ a trois sens : le jeu de données $\mathcal D$, la dimension $D$, la fonction duale $D(\boldsymbol\lambda)$ ou $D(\boldsymbol\alpha)$.
$\rho$ : la marge (§1–2), mais $\rho(x,y)$ est une fonction quelconque dans l'inégalité minimax (§3).
$\sigma$ : largeur du noyau RBF. Au chapitre 1 c'était l'écart-type du bruit, au chapitre 2 la sigmoïde.
Étiquettes $\pm1$, alors que la vraisemblance du chapitre 2 utilisait $\{0,1\}$.
$C$ multiplie la perte, alors que $\lambda$ multipliait la pénalité dans le ridge : grand $C$ ⇔ petit $\lambda$.
$J(\bx)$ (objectif + indicatrices, §3) n'a rien à voir avec le $J(\bw)$ de la slide 33 du chapitre 2. Les indices $i$, $j$, $n$ et les nombres de contraintes $m$, $M$ sont aussi mélangés d'une slide à l'autre.

1Quel hyperplan séparateur choisir ? La marge

Slides p.3–6 PRML §7.1 p.326–327

Où on en est

Acquis

Chapitre 2 : un classifieur linéaire $\operatorname{sign}(\bw\T\bx+b)$ ; la régression logistique en trouve un en minimisant la cross-entropy.

Il manque

Si les données sont séparables, une infinité d'hyperplans les séparent. Lequel est le « meilleur », et comment le mesurer ?

Cette partie

On définit la marge géométrique (distance du point le plus proche à l'hyperplan) et on prouve la formule de distance $|f(\bx)|/\|\bw\|$.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Visually ExplainedSupport Vector Machine (SVM) in 2 minutesL'idée de la marge maximale en 2 minutes, très visuelle.▶

StatQuestSupport Vector Machines Part 1 (of 3): Main Ideas!!!Marge, classifieur à marge souple et vecteurs de support, sans équations.▶

MIT OCW — Patrick Winston16. Learning: Support Vector MachinesLe cours classique du MIT : de la « rue la plus large » au dual, à la main au tableau.

Pour des données linéairement séparables, il existe une infinité d'hyperplans séparateurs (le perceptron ou la régression logistique en rendent un parmi d'autres). Intuition : préférer celui qui est le plus loin des points les plus proches. Un petit bruit sur un point (ou un nouveau point de test proche des données) ne le fera pas basculer du mauvais côté : c'est une forme de robustesse, et la théorie de l'apprentissage montre qu'une grande marge contrôle l'erreur de généralisation.

Marge géométrique (geometric margin)

Pour un classifieur linéaire $f(\bx) = \bw\T\bx + b$, la marge géométrique en $\bx$ est sa distance euclidienne à l'hyperplan $f(\bx) = 0$ : $$\rho_f(\bx) := \frac{|f(\bx)|}{\|\bw\|}.$$ Sur un ensemble d'exemples : $\rho_f := \min_i\rho_f(\bx_i)$ — la distance du point le plus proche.

Les objets en jeu

$\mathcal D = ((\bx_i,y_i))_{i=1}^N$: jeu de donnéesExemples $\bx_i\in\R^D$ et étiquettes $y_i\in\{-1,+1\}$ (convention $\pm1$ obligatoire ici : elle permet d'écrire « bien classé » comme $y_if(\bx_i)>0$).
$f(\bx) = \bw\T\bx + b$: fonction affine $\R^D\to\R$Le score du classifieur ; la prédiction est $\operatorname{sign}(f(\bx))$.
$\{\bx : f(\bx) = 0\}$: hyperplan de $\R^D$La frontière de décision (droite en 2D, plan en 3D) : dimension $D-1$.
$\|\bw\|$: réel $>0$Norme du vecteur normal. Diviser par $\|\bw\|$ convertit un « score » en une distance.
$\rho_f(\bx)$: distance $\ge0$Marge géométrique d'un point. À comparer avec la marge fonctionnelle $y f(\bx)$ du chapitre 2, qui dépend de l'échelle de $\bw$.
$\rho_f$: distance $\ge0$Marge sur l'échantillon = demi-largeur de la « rue » vide autour de la frontière.

Géométrie : $\bw$ est normal à l'hyperplan, et la formule de distance

Slides p.4–5 PRML §4.1.1 p.181–182 (Fig. 4.1)

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

3Blue1BrownDot products and duality (Essence of linear algebra, ch. 9)Le produit scalaire comme projection : la clé de la formule de distance à l'hyperplan.

En 3D ci-dessous : $f(\bx) = \bw\T\bx + b$ est un plan incliné au-dessus de l'espace d'entrée. La frontière est l'endroit où ce plan coupe le sol. La hauteur $f(\bx)$ d'un point n'est pas une distance : si on double $\bw$ et $b$, le plan est deux fois plus pentu, les hauteurs doublent, mais la frontière et les distances ne bougent pas. Diviser par $\|\bw\|$ (la pente du plan) corrige exactement cela.

Ne pas confondre : l'hyperplan et le plan incliné

L'hyperplan de décision $\{\bx\in\R^D : \bw\T\bx+b = 0\}$ vit dans l'espace des entrées $\R^D$ et est de dimension $D-1$. Ici $D = 2$ : c'est une droite — la droite blanche, au sol dans la vue 3D et dans le plan de gauche.
Le plan incliné est le graphe de la fonction score, $\{(\bx, f(\bx))\}\subset\R^{D+1}$ : un objet auxiliaire qu'on dessine au-dessus des entrées pour voir les valeurs de $f$. Il est de dimension $D$ (un vrai plan quand $D = 2$).
Lien : l'hyperplan est l'intersection du graphe avec le sol $z = 0$ (la « ligne de niveau 0 » de $f$) ; les droites $f = \pm1$ sont ses intersections avec les hauteurs $z = \pm1$.

Le mot « hyperplan » est réservé au premier objet. Dans chaque figure, le bouton ◉ Affichage (en haut à droite) permet de masquer le plan incliné, les hauteurs, les étiquettes… pour ne garder que ce qui t'intéresse.

Preuve — $\bw\perp$ hyperplan et $\rho_f(\bx) = |f(\bx)|/\|\bw\|$ (slides p.4–5)

$\bw$ est normal. Soient $\bx_1,\bx_2$ sur l'hyperplan : $\bw\T\bx_1 + b = 0$ et $\bw\T\bx_2 + b = 0$. En soustrayant : $\bw\T(\bx_1-\bx_2) = 0$. Tout vecteur « dans » l'hyperplan est orthogonal à $\bw$.

Décomposition. Soit $\bx$ quelconque et $\bx_p$ sa projection orthogonale sur l'hyperplan. Comme $\bx - \bx_p$ est orthogonal à l'hyperplan, il est colinéaire à $\bw$ : $\bx = \bx_p + \tau\frac{\bw}{\|\bw\|}$ pour un réel $\tau$ (déplacement signé).

$\bx_p$ est sur l'hyperplan : $0 = f(\bx_p) = \bw\T\big(\bx - \tau\frac{\bw}{\|\bw\|}\big) + b = f(\bx) - \tau\frac{\bw\T\bw}{\|\bw\|} = f(\bx) - \tau\|\bw\|$.

Donc $\tau = \frac{f(\bx)}{\|\bw\|}$ et la distance est $\rho_f(\bx) = \|\bx-\bx_p\| = |\tau| = \frac{|f(\bx)|}{\|\bw\|}$. Le signe de $\tau$ dit de quel côté on est.

∎

2Maximisation de la marge

Slides p.7–11 PRML éq. 7.3–7.6 p.327–328

Où on en est

Acquis

La marge $\rho_f = \min_i|f(\bx_i)|/\|\bw\|$ d'un classifieur.

Il manque

Transformer « choisir l'hyperplan de marge maximale » en un problème d'optimisation qu'on sait écrire proprement.

Cette partie

Grâce à l'invariance d'échelle, le max-min devient : minimiser $\frac12\|\bw\|^2$ sous les contraintes $y_i(\bw\T\bx_i+b)\ge1$. C'est la SVM (marge dure).

On suppose les données linéairement séparables (relâché au §5). On cherche l'hyperplan séparateur de marge maximale :

$$\rho = \max_{f:\ \forall i,\ y_if(\bx_i)\ge0}\ \rho_f = \max_{f:\ \forall i,\ y_if(\bx_i)\ge0}\ \min_j\ \rho_f(\bx_j).$$

Problème de maximisation de la marge (forme canonique)

$$\min_{\bw,b}\ \frac12\|\bw\|^2\qquad\text{s.c.}\qquad y_i(\bw\T\bx_i + b)\ge1,\quad i = 1,\dots,N.$$ Le classifieur obtenu est la machine à vecteurs de support (SVM). À l'optimum, la marge vaut $\rho = 1/\|\bw^*\|$ et les deux « bords de la rue » sont les hyperplans $\bw\T\bx + b = \pm1$.

Les objets en jeu

$\max_f\min_j$: problème max-min« Choisir $f$ pour que le pire point soit le plus loin possible. » Non lisse (le min change de point actif), d'où la reformulation.
$y_if(\bx_i)\ge0$: contrainte« Le point $i$ est du bon côté ». Pour $y_i=+1$ : $f(\bx_i)\ge0$ ; pour $y_i=-1$ : $f(\bx_i)\le0$.
$(\lambda\bw,\lambda b)$: même hyperplanInvariance d'échelle : pour $\lambda>0$, $\{\bx:\bw\T\bx+b = 0\} = \{\bx:\lambda(\bw\T\bx+b)=0\}$. On a un degré de liberté « gratuit » qu'on fixe par une normalisation.
hyperplan canonique: normalisationChoisir l'échelle telle que $\min_jy_j(\bw\T\bx_j+b) = 1$ : les points les plus proches ont un score exactement $\pm1$.
$\frac12\|\bw\|^2$: objectif quadratique convexeMaximiser $1/\|\bw\|$ ⇔ minimiser $\|\bw\|$ ⇔ minimiser $\frac12\|\bw\|^2$ (même minimiseur, mais différentiable et quadratique ; le $\frac12$ simplifie les dérivées).

Preuve — les égalités « ? » de la slide 7, étape par étape

(a) Retirer la valeur absolue. Sous les contraintes $y_if(\bx_i)\ge0$, on a $|f(\bx_j)| = y_jf(\bx_j)$ (car $|y_j| = 1$ et $y_jf(\bx_j)\ge0$). Donc $\rho = \max_f\min_j\frac{y_jf(\bx_j)}{\|\bw\|}$. On peut ensuite retirer les contraintes du max : pour un $f$ qui classe mal un point, $\min_jy_jf(\bx_j)<0$, ce qui ne peut pas battre un séparateur (données séparables ⇒ il existe $f$ avec valeur $>0$).

(b) Invariance d'échelle. $\frac{y_j(\lambda\bw\T\bx_j+\lambda b)}{\|\lambda\bw\|} = \frac{y_j(\bw\T\bx_j+b)}{\|\bw\|}$ pour $\lambda>0$ : l'objectif ne dépend que de l'hyperplan, pas de l'échelle. On peut donc imposer $\min_jy_j(\bw\T\bx_j+b) = 1$ sans perte : $\rho = \max_{f:\ \min_jy_jf(\bx_j) = 1}\frac1{\|\bw\|}$. Concrètement : si $(\bw,b)$ sépare les données, $m := \min_jy_j(\bw\T\bx_j+b)>0$ ; en prenant $\lambda^* = 1/m$, on obtient $\min_jy_j(\lambda^*\bw\T\bx_j+\lambda^*b) = \lambda^*m = 1$. Voir la scène juste après la preuve.

(c) Relâcher « $\min = 1$ » en « $\ge1$ pour tout $j$ ». Le nouvel ensemble admissible est plus grand, donc le max est $\ge$. Réciproquement, si $(\bw,b)$ vérifie toutes les contraintes $\ge1$ avec $m := \min_jy_jf(\bx_j) > 1$, alors $(\bw/m, b/m)$ est aussi admissible avec $\min = 1$ et une valeur $\frac{m}{\|\bw\|}$ plus grande. À l'optimum le min vaut donc exactement 1 : les deux problèmes ont la même valeur.

(d) De max à min. $\max\frac1{\|\bw\|}\iff\min\|\bw\|\iff\min\frac12\|\bw\|^2$ ($t\mapsto\frac12t^2$ est croissante sur $\R_+$).

∎

Voir l'invariance d'échelle et le $\lambda^*$ qui normalise

Slides p.7 (étape « ? »)PRML p.327 (éq. 7.4–7.5)

Multiplier $(\bw,b)$ par $\lambda>0$ ne change pas l'ensemble $\{\bx : \bw\T\bx+b = 0\}$ : c'est le même hyperplan. Mais toutes les marges fonctionnelles $y_jf(\bx_j)$ sont multipliées par $\lambda$ (le plan incliné $z = \lambda f(\bx)$ devient plus ou moins pentu), et $\|\bw\|$ aussi — si bien que la marge géométrique $\frac{y_jf(\bx_j)}{\|\bw\|}$ ne bouge pas. On a donc un bouton de réglage « gratuit » : on s'en sert pour fixer l'échelle.

Le facteur qui met le minimum à 1

Si $(\bw,b)$ sépare les données, posons $m := \min_jy_j(\bw\T\bx_j+b)>0$ (atteint au point le plus proche $j^*$). Alors $$\min_jy_j\big((\lambda\bw)\T\bx_j+\lambda b\big) = \lambda\,m\qquad\Longrightarrow\qquad\lambda^* = \frac1m = \frac{1}{\min_jy_j(\bw\T\bx_j+b)}.$$ Après normalisation, les droites $\lambda^*f(\bx) = \pm1$ passent par le(s) point(s) le(s) plus proche(s), et $\frac1{\|\lambda^*\bw\|} = \frac{m}{\|\bw\|} = \rho_f$ : dans la forme canonique, la marge est exactement $1/\|\bw\|$.

Les objets en jeu

$\lambda>0$: réel (facteur d'échelle)Multiplie $\bw$ et $b$ en même temps. $\lambda<0$ est exclu : il retournerait l'orientation (les classes échangeraient leur côté).
$y_jf(\bx_j)$: marge fonctionnelle« Hauteur signée » du point $j$ sur le plan incliné ; dépend de l'échelle : $\times\lambda$.
$m$: réel $>0$La plus petite marge fonctionnelle, pour l'échelle de départ. $m\le0$ ⇔ l'hyperplan ne sépare pas les données : aucun $\lambda>0$ ne peut rendre le min égal à 1.
$j^*$: indiceLe point le plus proche de l'hyperplan (celui qui deviendra un vecteur de support si l'hyperplan est optimal).
$\rho_f = m/\|\bw\|$: distanceLa marge géométrique : invariante, car numérateur et dénominateur sont tous deux multipliés par $\lambda$.

Dans la scène : fais glisser $\lambda$ (ou la poignée du 3^e panneau). La droite blanche ne bouge pas ; les droites jaunes $\lambda f = \pm1$ se rapprochent quand $\lambda$ grandit ; la courbe rose $\lambda m$ croise le niveau 1 exactement en $\lambda^* = 1/m$, pendant que la marge géométrique (verte) reste plate. En 3D, regarde le triangle posé sur le point le plus proche : sa base au sol (verte) est la marge géométrique $\rho$, sa hauteur (rose) est $\lambda f(\bx_{j^*}) = \lambda m$, et son hypoténuse (jaune) suit le plan incliné, de pente $\|\lambda\bw\|$. Quand $\lambda$ change, le triangle s'étire verticalement mais sa base ne bouge pas : $\rho = \frac{\text{hauteur}}{\text{pente}} = \frac{\lambda m}{\lambda\|\bw\|}$. Change aussi la « norme de départ » : $m$ et $\lambda^*$ changent, mais le produit $\lambda^*\bw$ (la forme canonique) est toujours le même.

3Optimisation sous contraintes : Lagrangien et dualité

Slides p.10–18 PRML annexe E p.707–710

Où on en est

Acquis

Le problème de la SVM : un objectif simple, mais $N$ contraintes.

Il manque

La descente de gradient ne sait pas gérer des contraintes. Il faut un outil général.

Cette partie

Le Lagrangien (une pénalité $\lambda_ig_i$ par contrainte), la fonction duale, la dualité faible (par l'inégalité minimax) et forte, et les conditions KKT. Ici les notations sont génériques : $\bx$ est la variable optimisée, pas un exemple.

Problème primal

$$\min_{\bx}\ L(\bx)\qquad\text{s.c.}\qquad g_i(\bx)\le0,\quad i = 1,\dots,m.$$

Les objets en jeu

$L:\R^D\to\R$: fonction objectifCe qu'on minimise (pour la SVM : $\frac12\|\bw\|^2$). Attention, rien à voir avec une loss d'apprentissage ici : notation générique.
$g_i:\R^D\to\R$: fonctions contraintesChaque contrainte est écrite « $\le0$ ». Pour la SVM : $g_i(\bw,b) = 1 - y_i(\bw\T\bx_i+b)$.
ensemble admissible: sous-ensemble de $\R^D$$\{\bx : g_i(\bx)\le0\ \forall i\}$ (feasible set). Contrainte active en $\bx$ si $g_i(\bx) = 0$ (on est sur son bord).
$p^*$: réelLa valeur optimale du primal.

Du contraint au non contraint : fonction indicatrice et Lagrangien

Slides p.14–16

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Khan Academy (Grant Sanderson)Lagrange multipliers, using tangency to solve constrained optimizationMultiplicateurs de Lagrange par la tangence des lignes de niveau.▶

Khan Academy (Grant Sanderson)The LagrangianLe Lagrangien : tout regrouper en une seule fonction.

On sait bien optimiser sans contraintes (GD, SGD). Première idée : mettre une pénalité infinie sur les points interdits,

$$J(\bx) = L(\bx) + \sum_{i=1}^m\delta_{\R_-}\big(g_i(\bx)\big),\qquad\delta_{\R_-}(z) = \begin{cases}0 & z\le0\\+\infty & z>0.\end{cases}$$

Exact mais inutilisable : ce « mur » est discontinu et ne dit rien du degré de violation. La relaxation lagrangienne remplace le mur par une pente linéaire $\lambda_ig_i(\bx)$, et le mur est retrouvé en maximisant sur les pentes.

Lagrangien · fonction duale · problème dual

$$\mathfrak L(\bx,\boldsymbol\lambda) = L(\bx) + \sum_{i=1}^m\lambda_ig_i(\bx),\quad\lambda_i\ge0;\qquad J(\bx) = \max_{\boldsymbol\lambda\ge0}\mathfrak L(\bx,\boldsymbol\lambda)\ \Rightarrow\ J(\bx)\ge\mathfrak L(\bx,\boldsymbol\lambda)\ \ \forall\boldsymbol\lambda\ge0.$$ $$\text{Dual : }\ \max_{\boldsymbol\lambda\ge0}D(\boldsymbol\lambda),\qquad D(\boldsymbol\lambda) := \min_{\bx\in\R^D}\mathfrak L(\bx,\boldsymbol\lambda).$$

Les objets en jeu

$\lambda_i\ge0$: multiplicateur de LagrangeLe « prix » d'une unité de violation de la contrainte $i$. Positivité obligatoire : on ne doit pas récompenser la violation.
$\mathfrak L(\bx,\boldsymbol\lambda)$: fonction de $\R^D\times\R^m_+$Le Lagrangien (les slides le notent aussi $\mathcal L$). Pour $\boldsymbol\lambda$ fixé, c'est un problème sans contrainte en $\bx$.
$J(\bx)$: $\R^D\to\R\cup\{+\infty\}$La fonction « objectif + mur ». $\max_\lambda\lambda g$ vaut 0 si $g\le0$ (prendre $\lambda=0$) et $+\infty$ si $g>0$ ($\lambda\to\infty$) : on retrouve exactement l'indicatrice.
$D(\boldsymbol\lambda)$: fonction concave de $\boldsymbol\lambda$La fonction duale : pour chaque prix, le meilleur $\bx$ sans contrainte. Toujours concave (min de fonctions affines en $\boldsymbol\lambda$), même si $L$ ne l'est pas.
$d^*$: réel$\max_{\boldsymbol\lambda\ge0}D$, la valeur optimale du dual.

Scène : $\min_x (x-a)^2$ s.c. $x\le c$. À gauche l'espace de $x$ : pour chaque $\lambda$, la parabole $\mathfrak L(\cdot,\lambda)$ est « penchée » par la pente $\lambda(x - c)$ et son minimum donne $D(\lambda)$. Au milieu, $D(\lambda)$ reste toujours sous $p^*$ (dualité faible) et le touche au $\lambda^*$ optimal (dualité forte). À droite, la surface $\mathfrak L(x,\lambda)$ est une selle : min en $x$, max en $\lambda$, et l'optimum est le point-selle.

Preuve — $J(\bx) = \max_{\boldsymbol\lambda\ge0}\mathfrak L(\bx,\boldsymbol\lambda)$

$\max_{\boldsymbol\lambda\ge0}\mathfrak L(\bx,\boldsymbol\lambda) = L(\bx) + \sum_i\max_{\lambda_i\ge0}\lambda_ig_i(\bx)$ (les $\lambda_i$ sont indépendants).

Si $g_i(\bx)\le0$ : $\lambda_ig_i(\bx)\le0$, maximum atteint en $\lambda_i = 0$, valeur $0 = \delta_{\R_-}(g_i(\bx))$.

Si $g_i(\bx)>0$ : $\lambda_ig_i(\bx)\to+\infty$ quand $\lambda_i\to\infty$, valeur $+\infty = \delta_{\R_-}(g_i(\bx))$.

Donc $\max_{\boldsymbol\lambda}\mathfrak L = J$, et pour tout $\boldsymbol\lambda\ge0$ fixé, $J(\bx)\ge\mathfrak L(\bx,\boldsymbol\lambda)$ : le Lagrangien est un minorant (relaxation) de l'objectif pénalisé.

∎

Inégalité minimax, dualité faible et forte

Slides p.18–20

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Inside Bloomberg — David Rosenberg9. Lagrangian Duality and Convex OptimizationDualité faible et forte, condition de Slater : le cadre complet (niveau master).

Inégalité minimax · Dualité faible

$$\max_y\min_x\rho(x,y)\ \le\ \min_x\max_y\rho(x,y)\qquad\Longrightarrow\qquad \underbrace{\min_{\bx}\max_{\boldsymbol\lambda\ge0}\mathfrak L(\bx,\boldsymbol\lambda)}_{\text{primal } = p^*}\ \ge\ \underbrace{\max_{\boldsymbol\lambda\ge0}\min_{\bx}\mathfrak L(\bx,\boldsymbol\lambda)}_{\text{dual } = d^*}.$$ Dualité faible : l'inégalité est toujours vraie — tout $D(\boldsymbol\lambda)$ est une borne inférieure de $p^*$. Dualité forte : égalité $p^* = d^*$ sous conditions (convexité + Slater, cf. plus bas). $p^* - d^*$ s'appelle le duality gap.

Preuve — inégalité minimax (slide 18)

Posons $\psi(y) := \min_x\rho(x,y)$. Par définition du min : $\psi(y)\le\rho(x,y)$ pour tous $x,y$.

Fixons $x$ et prenons le max en $y$ des deux côtés (l'inégalité est préservée) : $\max_y\psi(y)\le\max_y\rho(x,y)$ pour tout $x$.

Le membre de gauche ne dépend pas de $x$ ; c'est donc un minorant de $x\mapsto\max_y\rho(x,y)$, en particulier de son min : $\max_y\psi(y)\le\min_x\max_y\rho(x,y)$.

C'est-à-dire $\max_y\min_x\rho\le\min_x\max_y\rho$. Avec $\rho = \mathfrak L$, $x = \bx$, $y = \boldsymbol\lambda$ et $\min_{\bx}\max_{\boldsymbol\lambda}\mathfrak L = \min_{\bx} J(\bx) = p^*$ : dualité faible. Intuition : « celui qui joue en second a l'avantage ».

∎

Pourquoi le dual ? (slide 20) Attaquer directement le « min-max » est difficile : $\max_\lambda$ puis $\min_x$ ne fournit pas de gradient utile (on retombe sur le mur) ; une descente–montée simultanée peut osciller. Le dual est plus facile quand le min intérieur en $\bx$ a une forme close en fonction de $\boldsymbol\lambda$ — c'est exactement le cas de la SVM. Et $D$ est toujours concave : maximiser $D$ sous $\boldsymbol\lambda\ge0$ est un problème convexe.

Contraintes d'égalité

Slides p.21–22

Lagrangien avec égalités

$h(\bx) = 0\iff h(\bx)\le0$ et $-h(\bx)\le0$ ; les deux multiplicateurs $\lambda_1,\lambda_2\ge0$ se combinent : $\lambda_1h - \lambda_2h = \nu h$ avec $\nu = \lambda_1-\lambda_2\in\R$ non signé. Pour $\min L$ s.c. $g_i\le0$ ($i\le M$) et $h_j = 0$ ($j\le P$) : $$\mathfrak L(\bx,\boldsymbol\lambda,\boldsymbol\nu) = L(\bx) + \sum_{i=1}^M\lambda_ig_i(\bx) + \sum_{j=1}^P\nu_jh_j(\bx),\qquad\lambda_i\ge0,\ \nu_j\in\R.$$ Et oui : $\min_{\bx}\max_{\boldsymbol\lambda\ge0,\boldsymbol\nu}\mathfrak L$ est équivalent au problème contraint (question slide 22), car $\max_\nu\nu h(\bx) = 0$ si $h(\bx) = 0$ et $+\infty$ sinon.

Conditions KKT et point-selle en 2D Hors slides PRML annexe E, éq. E.9–E.11

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Visually ExplainedThe KKT Conditions and the Interior Point Method for Convex OptimizationLes conditions KKT et la dualité, avec des animations géométriques.

Pour un problème convexe (L et $g_i$ convexes, $h_j$ affines) vérifiant la condition de Slater (il existe un point strictement admissible, $g_i(\bx)<0$ pour tout $i$), la dualité est forte et $(\bx^*,\boldsymbol\lambda^*)$ est optimal si et seulement si les conditions de Karush–Kuhn–Tucker sont vérifiées :

$$\underbrace{\nabla L(\bx^*) + \sum_i\lambda_i^*\nabla g_i(\bx^*) = 0}_{\text{stationnarité}},\quad\underbrace{g_i(\bx^*)\le0}_{\text{admissibilité primale}},\quad\underbrace{\lambda_i^*\ge0}_{\text{admissibilité duale}},\quad\underbrace{\lambda_i^*g_i(\bx^*) = 0}_{\text{complémentarité}}.$$

Géométrie : à l'optimum sur le bord, le gradient de l'objectif et celui de la contrainte sont opposés (l'objectif voudrait sortir, la contrainte l'en empêche) et $\lambda^*$ est le rapport de leurs longueurs. Si l'optimum libre est déjà admissible, la contrainte est inactive et $\lambda^* = 0$ : c'est la complémentarité, qui donnera les vecteurs de support.

4La SVM par le dual

Slides p.24–30 PRML éq. 7.7–7.19 p.328–330

Où on en est

Acquis

Le primal de la SVM (§2) et l'outil Lagrangien / dual (§3).

Il manque

Appliquer l'outil à la SVM et en tirer le classifieur $\bw^*$, $b^*$.

Cette partie

On dérive le problème dual en $\boldsymbol\alpha$, on reconstruit $\bw^*$ et $b^*$, et on comprend pourquoi seuls quelques points (les vecteurs de support) déterminent la solution.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Stanford CS229 — Andrew NgLecture 6: Support Vector MachinesCours complet : marge géométrique, problème primal, dual de la SVM.

Ce qu'on cherche, précisément

Ce qu'on a (§2) : le problème primal $\ \min_{\bw,b}\frac12\|\bw\|^2$ s.c. $y_i(\bw\T\bx_i+b)\ge1$ pour tout $i$. Ses inconnues sont $\bw\in\R^D$ et $b$ ; il a $N$ contraintes, une par point.

Ce qu'on veut à la fin : le classifieur $f(\bx) = \bw^{*\top}\bx + b^*$, c'est-à-dire les deux nombres/vecteurs $\bw^*$ et $b^*$.

L'idée du dual : au lieu de chercher $\bw$ directement, on cherche un poids $\alpha_i\ge0$ par point (le « prix » de sa contrainte). On obtient un problème en $\boldsymbol\alpha$ seulement, aux contraintes très simples, où les données n'apparaissent que par des produits scalaires $\bx_i\T\bx_j$. On le résout, puis on reconstruit $\bw^*$ et $b^*$ à partir de $\boldsymbol\alpha^*$.

Pourquoi se donner ce mal (slide 24) : (1) si $N\ll D$ il y a moins d'inconnues ; (2) la solution ne dépend que de quelques points (les vecteurs de support) ; (3) surtout, les produits scalaires pourront être remplacés par un noyau (§6) pour obtenir des frontières non linéaires. Si $N\gg D$ et qu'on reste linéaire, on peut aussi résoudre le primal directement (programme quadratique, points intérieurs).

Primal$\min_{\bw,b}\tfrac12\|\bw\|^2$
s.c. $N$ contraintes

→

① Lagrangienun $\alpha_i\ge0$ par contrainte : $\min_{\bw,b}\max_{\boldsymbol\alpha}\mathfrak L$

→

② min en $(\bw,b)$formule close : $\bw = \sum_i\alpha_iy_i\bx_i$, $\sum_i\alpha_iy_i = 0$

→

③ réinjecter$D(\boldsymbol\alpha)$ ne dépend que de $\boldsymbol\alpha$ et des $\bx_i\T\bx_j$

→

④ max en $\boldsymbol\alpha$solveur QP (SMO) → $\boldsymbol\alpha^*$

→

⑤ reconstruire$\bw^*$, $b^*$, puis $f(\bx)$

Le plan, étape par étape

①Écrire le Lagrangien. On remplace chaque contrainte « $1-y_i(\bw\T\bx_i+b)\le0$ » par une pénalité $\alpha_i\big(1-y_i(\bw\T\bx_i+b)\big)$ avec $\alpha_i\ge0$ (§3). Pourquoi : un problème contraint devient un jeu $\min_{\bw,b}\max_{\boldsymbol\alpha}$ ; par dualité forte on peut échanger l'ordre et faire d'abord le $\min$.
②Minimiser en $(\bw,b)$ à $\boldsymbol\alpha$ fixé. Pour des prix $\alpha_i$ donnés, $\mathfrak L$ est une parabole (bol) en $\bw$ et une droite en $b$ : on annule les dérivées. Pourquoi c'est possible : c'est exactement le cas « le min intérieur a une forme close » de la slide 20. On obtient $\bw$ comme combinaison des points, et une condition d'équilibre $\sum_i\alpha_iy_i = 0$.
③Réinjecter $\bw = \sum_j\alpha_jy_j\bx_j$ dans $\mathfrak L$. Il ne reste qu'une fonction de $\boldsymbol\alpha$ : la fonction duale $D(\boldsymbol\alpha)$. Pourquoi : c'est la meilleure borne inférieure de $p^*$ qu'on puisse obtenir avec ces prix (dualité faible) ; on va la rendre la plus haute possible.
④Maximiser $D(\boldsymbol\alpha)$ sous $\alpha_i\ge0$ et $\sum_i\alpha_iy_i = 0$. C'est un programme quadratique concave : pas de minimum local parasite ; on le confie à un solveur (la scène ci-dessous utilise SMO, qui améliore deux $\alpha$ à la fois).
⑤Reconstruire le classifieur. $\bw^* = \sum_i\alpha_i^*y_i\bx_i$ (seuls les $\alpha_i^*>0$ contribuent) ; $b^*$ se lit sur un vecteur de support, qui vérifie $y_i(\bw^{*\top}\bx_i+b^*) = 1$ ; puis on prédit avec $\operatorname{sign}(f(\bx))$. Pourquoi $b$ se lit ainsi : complémentarité, $\alpha_i^*>0\Rightarrow$ la contrainte $i$ est active (le point est sur le bord de la rue).

Lagrangien primal de la SVM

$$\mathfrak L(\bw,b,\boldsymbol\alpha) = \frac12\|\bw\|^2 + \sum_{i=1}^N\alpha_i\Big(1 - y_i(\bw\T\bx_i + b)\Big),\qquad\alpha_i\ge0.$$ On suppose la dualité forte (vraie ici : problème convexe + Slater si les données sont séparables) : $\min_{\bw,b}\max_{\boldsymbol\alpha\ge0}\mathfrak L = \max_{\boldsymbol\alpha\ge0}\min_{\bw,b}\mathfrak L$.

Les objets en jeu

$\alpha_i\ge0$: multiplicateur du point $i$Un multiplicateur par exemple d'entraînement (la contrainte $i$ est « le point $i$ est hors de la rue »). Le dual a donc $N$ variables, quelle que soit la dimension $D$.
$1 - y_i(\bw\T\bx_i+b)$: $g_i(\bw,b)$La contrainte du point $i$ écrite « $\le0$ ».
$\bw^*,\ b^*,\ \boldsymbol\alpha^*$: optimum primal-dualLa solution ; $\rho = 1/\|\bw^*\|$.
$\bx_i\T\bx_j$: réelProduit scalaire entre deux exemples : la seule façon dont les données entrent dans le dual (clé du kernel trick). La matrice $[\bx_i\T\bx_j]_{ij}$ est la matrice de Gram.
vecteur de support: exemple avec $\alpha_i^*>0$Un point posé exactement sur le bord de la rue, $y_i(\bw^{*\top}\bx_i+b^*) = 1$ ; seuls eux déterminent $\bw^*$.

Résultat des étapes ②–③ : le problème dual (marge dure)

$$\max_{\boldsymbol\alpha\ge0}\ -\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\,\bx_i\T\bx_j + \sum_{i=1}^N\alpha_i\qquad\text{s.c.}\qquad\sum_{i=1}^N\alpha_iy_i = 0.$$ Puis $\bw^* = \sum_i\alpha_i^*y_i\bx_i$ et, pour tout vecteur de support $\bx_i$ ($\alpha_i^*>0$) : $b^* = y_i - \bw^{*\top}\bx_i = y_i - \sum_j\alpha_j^*y_j\bx_j\T\bx_i$.

Dérivation détaillée des étapes ②–⑤ (slides p.27–29), avec le « pourquoi » de chaque ligne

② Ce qu'on fait : fixer $\boldsymbol\alpha\ge0$ et chercher $\min_{\bw,b}\mathfrak L(\bw,b,\boldsymbol\alpha)$. $\mathfrak L = \frac12\bw\T\bw - \sum_i\alpha_iy_i\bw\T\bx_i - b\sum_i\alpha_iy_i + \sum_i\alpha_i$ : quadratique convexe en $\bw$ (terme $\frac12\|\bw\|^2$), affine en $b$. Le minimum est là où les dérivées s'annulent.

② (suite) Dérivée en $\bw$ : $\frac{\partial\mathfrak L}{\partial\bw} = \bw - \sum_i\alpha_iy_i\bx_i = 0\ \Rightarrow\ \boxed{\bw = \sum_i\alpha_iy_i\bx_i}$. Lecture : le meilleur $\bw$ pour ces prix est une somme de flèches $\pm\bx_i$ pondérées par $\alpha_i$ (la chaîne de flèches de la scène).

② (suite) Dérivée en $b$ : $\frac{\partial\mathfrak L}{\partial b} = -\sum_i\alpha_iy_i = 0\ \Rightarrow\ \boxed{\sum_i\alpha_iy_i = 0}$. Si ce n'était pas nul, $\mathfrak L$ serait une droite non horizontale en $b$ : son minimum vaudrait $-\infty$, borne inutile. Seuls les $\boldsymbol\alpha$ « équilibrés » (autant de poids total côté $+1$ que côté $-1$) donnent une borne finie : c'est la contrainte du dual.

③ Ce qu'on fait : remplacer $\bw$ par $\sum_j\alpha_jy_j\bx_j$ dans $\mathfrak L$. Notons $S = \sum_{i,j}\alpha_i\alpha_jy_iy_j\bx_i\T\bx_j$. Alors $\frac12\bw\T\bw = \frac12S$, $\sum_i\alpha_iy_i\bw\T\bx_i = S$, et $b\sum_i\alpha_iy_i = 0$. Chaque terme devient une double somme de produits scalaires $\bx_i\T\bx_j$ : $\bw$ a disparu.

③ Résultat : $D(\boldsymbol\alpha) = \frac12S - S + \sum_i\alpha_i = \boxed{-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,\bx_i\T\bx_j + \sum_i\alpha_i}$. Concave car $S = \|\sum_i\alpha_iy_i\bx_i\|^2\ge0$ : on maximise une « parabole retournée ».

④ Ce qu'on fait : $\boldsymbol\alpha^* = \argmax_{\boldsymbol\alpha\ge0,\ \sum\alpha_iy_i = 0}D(\boldsymbol\alpha)$ (numériquement). Par dualité forte, $D(\boldsymbol\alpha^*) = p^* = \frac12\|\bw^*\|^2$.

⑤ Ce qu'on fait : $\bw^* = \sum_i\alpha_i^*y_i\bx_i$ ; pour un $i$ avec $\alpha_i^*>0$, la complémentarité $\alpha_i^*\big(1 - y_i(\bw^{*\top}\bx_i+b^*)\big) = 0$ impose $y_i(\bw^{*\top}\bx_i + b^*) = 1$ ; en multipliant par $y_i$ ($y_i^2 = 1$) : $\boxed{b^* = y_i - \bw^{*\top}\bx_i}$. En pratique on moyenne sur tous les vecteurs de support.

Bonus — la marge Hors slides : en sommant la complémentarité sur $i$, $\sum_i\alpha_i^* = \sum_i\alpha_i^*y_i\bw^{*\top}\bx_i + b^*\sum_i\alpha_i^*y_i = \|\bw^*\|^2$, d'où $\rho = 1/\|\bw^*\| = 1/\sqrt{\sum_i\alpha_i^*}$.

∎

Application : la recette pour entraîner et utiliser une SVM

Recette (sans dérivation)

Entraînement, à partir des données $(\bx_i,y_i)_{i=1}^N$, $y_i\in\{-1,+1\}$ :

Calculer la matrice de Gram $K_{ij} = \bx_i\T\bx_j$ (taille $N\times N$).
Résoudre le dual : $\max_{\boldsymbol\alpha}\ \sum_i\alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jK_{ij}$ s.c. $\alpha_i\ge0$ (ou $0\le\alpha_i\le C$ en marge souple), $\sum_i\alpha_iy_i = 0$ → $\boldsymbol\alpha^*$.
Repérer les vecteurs de support : $\mathcal S = \{i : \alpha_i^*>0\}$ (en pratique, souvent peu nombreux).
$\bw^* = \sum_{i\in\mathcal S}\alpha_i^*y_i\bx_i$ et $b^* = \frac1{|\mathcal S|}\sum_{i\in\mathcal S}\big(y_i - \bw^{*\top}\bx_i\big)$.
(Optionnel) marge $\rho = 1/\|\bw^*\|$.

Prédiction d'un nouveau point $\bx$ : $\ f(\bx) = \sum_{i\in\mathcal S}\alpha_i^*y_i\,\bx_i\T\bx + b^*$, classe $= \operatorname{sign}f(\bx)$. On n'a besoin que des vecteurs de support et de produits scalaires — d'où le kernel trick du §6.

Exemple complet à la main (2 points)

Données : $\bx_1 = (1,1)$ avec $y_1 = +1$, et $\bx_2 = (-1,-1)$ avec $y_2 = -1$. On devine la réponse (la médiatrice $x_1 + x_2 = 0$) ; vérifions que la recette la retrouve.

Déroulé de la recette

1. Gram. $K_{11} = \bx_1\T\bx_1 = 2$, $K_{22} = 2$, $K_{12} = \bx_1\T\bx_2 = -2$.

2. Dual. Contrainte $\alpha_1y_1 + \alpha_2y_2 = \alpha_1 - \alpha_2 = 0$, donc $\alpha_1 = \alpha_2 =: a$. La double somme vaut $\sum_{i,j}\alpha_i\alpha_jy_iy_jK_{ij} = a^2(2) + a^2(2) + 2a^2(y_1y_2K_{12}) = 4a^2 + 2a^2\cdot(-1)(-2) = 8a^2$. Donc $D(a) = 2a - \frac12\cdot8a^2 = 2a - 4a^2$, maximale en $D'(a) = 2 - 8a = 0$ : $\boxed{a = \tfrac14}$.

3. Vecteurs de support. $\alpha_1^* = \alpha_2^* = \frac14>0$ : les deux points (évidemment, il n'y en a que deux).

4. $\bw^*$ et $b^*$. $\bw^* = \frac14(+1)(1,1) + \frac14(-1)(-1,-1) = (\frac12,\frac12)$. $b^* = y_1 - \bw^{*\top}\bx_1 = 1 - (\frac12+\frac12) = 0$. Frontière : $\frac12x_1 + \frac12x_2 = 0$, la médiatrice attendue.

5. Marge. $\|\bw^*\| = \frac{\sqrt2}2$, donc $\rho = \frac{2}{\sqrt2} = \sqrt2$ : c'est bien la distance de $(1,1)$ à la droite $x_1+x_2 = 0$. Vérifications : $\sum\alpha_i^* = \frac12 = \|\bw^*\|^2$ ✓ ; $D(\frac14) = \frac14 = \frac12\|\bw^*\|^2$ ✓ (dualité forte).

Prédiction pour $\bx = (2,-1)$ : $f(\bx) = \frac14(+1)\,\bx_1\T\bx + \frac14(-1)\,\bx_2\T\bx + 0 = \frac14(1) - \frac14(-1) = \frac12>0$ → classe $+1$ (avec $\bw^*$ : $\frac12\cdot2 - \frac12 = \frac12$ ✓).

∎

Pour le voir en grand : dans la scène ci-dessous (section suivante), le solveur applique exactement cette recette à chaque déplacement de point, et affiche les $\alpha_i$, $\sum_i\alpha_iy_i$, $\sum\alpha_i = \|\bw^*\|^2$ et $D(\boldsymbol\alpha^*) = \frac12\|\bw^*\|^2$.

Pourquoi « vecteurs de support » ?

Slides p.29–30

$\bw^* = \sum_i\alpha_i^*y_i\bx_i$ est une combinaison des points ; par complémentarité, $\alpha_i^*\big(1 - y_i(\bw^{*\top}\bx_i + b^*)\big) = 0$, donc deux cas :

$\alpha_i^*>0\Rightarrow y_i(\bw^{*\top}\bx_i+b^*) = 1$ : $\bx_i$ est sur le bord de la rue, c'est un vecteur de support ;
$y_i(\bw^{*\top}\bx_i+b^*)>1\Rightarrow\alpha_i^* = 0$ : $\bx_i$ n'est pas un vecteur de support, il ne compte pas.

Seuls les vecteurs de support « soutiennent » la solution : déplacer ou supprimer un point loin de la rue ne change rien. Dans la scène, le solveur (SMO) calcule les $\alpha_i$ ; la chaîne de flèches montre $\bw = \sum_i\alpha_iy_i\bx_i$ construit bout à bout à partir des seuls vecteurs de support.

5Marge souple : variables d'écart et hinge loss

Slides p.31–37 PRML §7.1.1 p.331–336

Où on en est

Acquis

La SVM à marge dure, résolue par le dual.

Il manque

Elle suppose les données séparables. Sinon, aucun $(\bw,b)$ ne vérifie les contraintes : pas de solution.

Cette partie

On autorise des violations $\xi_i\ge0$, payées $C\xi_i$ (marge souple). Le dual change à peine, et on voit que c'est la même chose que minimiser la hinge loss + une régularisation, comme les pertes de substitution du chapitre 2.

Données non séparables : aucune solution admissible. On autorise chaque point à violer la marge d'une quantité $\xi_i\ge0$ (slack) : $y_n(\bw\T\bx_n + b)\ge1-\xi_n$. $\xi_n$ mesure (en unités de $1/\|\bw\|$) de combien le point a franchi le bord de son côté de la rue.

SVM à marge souple (soft margin) — primal

$$\min_{\bw,b,\boldsymbol\xi}\ \frac12\|\bw\|^2 + C\sum_{i=1}^N\xi_i\qquad\text{s.c.}\qquad y_i(\bw\T\bx_i+b)\ge1-\xi_i,\quad\xi_i\ge0.$$

Les objets en jeu

$\xi_i\ge0$: variable d'écart0 si le point est hors de la rue du bon côté ; $0\lt \xi_i\le1$ s'il est dans la rue mais bien classé ; $\xi_i>1$ s'il est mal classé. Donc $\sum_i\xi_i$ majore le nombre d'erreurs d'entraînement.
$C>0$: hyperparamètreCompromis largeur de rue / violations. $C$ grand ⇒ violations chères ⇒ rue étroite, proche de la marge dure (risque de sur-apprentissage) ; $C$ petit ⇒ rue large, plus de violations tolérées (régularisation forte). $\frac12\|\bw\|^2$ joue le rôle du régulariseur, $C$ celui de $1/\lambda$.
$\beta_i\ge0$: multiplicateurAssocié à la contrainte $\xi_i\ge0$ (i.e. $-\xi_i\le0$).

Preuve — dual de la marge souple (slides p.33–34)

Lagrangien : $\mathfrak L = \frac12\|\bw\|^2 + C\sum_i\xi_i + \sum_i\alpha_i\big(1-\xi_i-y_i(\bw\T\bx_i+b)\big) - \sum_i\beta_i\xi_i$, avec $\alpha_i,\beta_i\ge0$.

Stationnarité : $\partial_{\bw} = 0\Rightarrow\bw = \sum_i\alpha_iy_i\bx_i$ ; $\partial_b = 0\Rightarrow\sum_i\alpha_iy_i = 0$ ; $\partial_{\xi_i} = 0\Rightarrow C - \alpha_i - \beta_i = 0$.

En substituant, les termes en $\xi_i$ disparaissent : leur coefficient est $C - \alpha_i - \beta_i = 0$. On retombe sur exactement la même fonction duale qu'au §4 : $-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\bx_i\T\bx_j + \sum_i\alpha_i$.

Contraintes restantes : $\beta_i = C - \alpha_i\ge0$ et $\alpha_i\ge0$ ⇔ $0\le\alpha_i\le C$ (contrainte de boîte, box constraint), plus $\sum_i\alpha_iy_i = 0$. La seule différence avec la marge dure est le plafond $C$ sur les $\alpha_i$.

Hors slides Complémentarité : $\alpha_i = 0\Rightarrow y_if(\bx_i)\ge1$ (hors de la rue) ; $0\lt \alpha_i\lt C\Rightarrow\beta_i>0\Rightarrow\xi_i = 0$ et $y_if(\bx_i) = 1$ (sur le bord) ; $\alpha_i = C\Rightarrow y_if(\bx_i) = 1-\xi_i\le1$ (dans la rue ou mal classé). $b^*$ se calcule avec les points $0\lt \alpha_i\lt C$.

∎

Vue « perte » : la hinge loss

Slides p.36–37 PRML §7.1.2 p.336 (Fig. 7.5)

Primal sans contrainte avec hinge loss

$$\min_{\bw,b}\ \frac12\|\bw\|^2 + C\sum_{i=1}^N\ell_{\text{hinge}}\big(y_i(\bw\T\bx_i+b)\big),\qquad\ell_{\text{hinge}}(t) = \max\{0,\,1-t\}.$$ Équivalent au primal contraint : à $(\bw,b)$ fixés, le meilleur écart est $\xi_i^* = \max\{0,1-t_i\}$ avec $t_i := y_i(\bw\T\bx_i+b)$.

Les objets en jeu

$t_i = y_i(\bw\T\bx_i+b)$: marge fonctionnelleLe même $m$ qu'au chapitre 2.
$\ell_{\text{hinge}}$: $\R\to\R_+$, convexe, non dérivable en $t=1$« Charnière » : nulle dès que $t\ge1$ (hors de la rue du bon côté), linéaire sinon. Majore la perte 0-1. Si $0\lt t<1$ le point est bien classé mais paie quand même : cela pousse vers $t\ge1$.

Preuve — $\xi_i^* = \max\{0, 1-t_i\}$ (slides p.36–37)

Pour $(\bw,b)$ fixés, les contraintes sur $\xi_i$ sont $\xi_i\ge1-t_i$ et $\xi_i\ge0$, soit $\xi_i\ge\max\{0,1-t_i\}$. Elles sont découplées entre les $i$.

L'objectif contient $+C\xi_i$ avec $C>0$ : il est croissant en chaque $\xi_i$, donc on prend le plus petit $\xi_i$ admissible : $\xi_i^* = \max\{0,1-t_i\}$.

En réinjectant, $\min_{\boldsymbol\xi}\big[\frac12\|\bw\|^2 + C\sum\xi_i\big] = \frac12\|\bw\|^2 + C\sum_i\max\{0,1-t_i\}$ : on minimise ensuite en $(\bw,b)$ sans contrainte (sous-gradient possible). « Maximiser la marge » = « régulariser en $\ell_2$ ».

∎

La scène montre les trois catégories de points pour chaque $C$ : hors de la rue ($\alpha = 0$), sur le bord ($0\lt \alpha\lt C$), dans la rue ou mal classés ($\alpha = C$, $\xi>0$). À droite, chaque point placé sur la courbe hinge selon sa marge $t_i$. Compare aussi les pertes dans la scène des pertes du chapitre 2 (coche « hinge »).

6Du linéaire au non linéaire : le kernel trick

Slides p.39–43 PRML §6.1–6.2 p.293–299

Où on en est

Acquis

La SVM à marge souple, dont le dual ne dépend des données que par les produits $\bx_i\T\bx_j$.

Il manque

Des frontières non linéaires, sans payer le coût de features de très grande dimension.

Cette partie

Remplacer $\bx$ par $\bphi(\bx)$ (comme au chapitre 1), puis remplacer directement $\bphi(\bx_i)\T\bphi(\bx_j)$ par un noyau $\kappa(\bx_i,\bx_j)$ : le kernel trick, et le noyau gaussien (RBF).

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Visually ExplainedThe Kernel Trick in Support Vector Machine (SVM)Le kernel trick en animation : relever les données pour les séparer.▶

StatQuestSupport Vector Machines Part 2: The Polynomial KernelLe noyau polynomial et les produits scalaires dans l'espace relevé.▶

Stanford CS229 — Andrew NgLecture 7: KernelsCours complet sur les noyaux (feature maps, kernel trick, noyaux valides).

Comme au chapitre 1, on peut remplacer $\bx$ par des features $\bphi(\bx)$. Le dual à marge souple devient :

$$\max_{\boldsymbol\alpha}\ -\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,\bphi(\bx_i)\T\bphi(\bx_j) + \sum_i\alpha_i\qquad\text{s.c.}\qquad\sum_i\alpha_iy_i = 0,\ \ 0\le\alpha_i\le C.$$

Le problème — et la prédiction $f(\bx) = \sum_i\alpha_iy_i\bphi(\bx_i)\T\bphi(\bx) + b$ — ne dépendent des features qu'à travers des produits scalaires. Or calculer $\bphi$ explicitement peut coûter très cher : tous les monômes de degré $\le3$ de $\bx\in\R^{100}$ font déjà ~176 000 features.

Kernel trick

Remplacer $\bphi(\bx)\T\bphi(\bx')$ par une fonction noyau $\kappa(\bx,\bx')$ calculable directement : $$\min_{\boldsymbol\alpha}\ \frac12\sum_{i,j}y_iy_j\alpha_i\alpha_j\kappa(\bx_i,\bx_j) - \sum_i\alpha_i\quad\text{s.c.}\quad\sum_iy_i\alpha_i = 0,\ 0\le\alpha_i\le C,\qquad f(\bx) = \sum_i\alpha_iy_i\kappa(\bx_i,\bx) + b.$$ On n'évalue jamais $\bphi$ pendant l'entraînement ; le nombre de multiplicateurs ($N$) ne dépend pas de la dimension de $\bphi$ — qui peut être infinie.

Les objets en jeu

$\bphi:\R^D\to\mathcal H$: feature mapRelèvement vers un espace de features $\mathcal H$ (dimension finie ou infinie) où les classes deviennent linéairement séparables.
$\kappa(\bx,\bx')$: $\R^D\times\R^D\to\R$Le noyau : un produit scalaire dans $\mathcal H$ calculé sans passer par $\mathcal H$. Mesure de similarité : grand si $\bphi(\bx)$ et $\bphi(\bx')$ sont proches/alignés, petit s'ils sont presque orthogonaux.
matrice de Gram $\mathbf K$: $N\times N$ symétrique, $\succeq0$$K_{ij} = \kappa(\bx_i,\bx_j)$ : tout ce dont l'entraînement a besoin. Hors slides Mercer : $\kappa$ est un vrai noyau (il existe $\bphi$) ssi toutes ses matrices de Gram sont semi-définies positives.
$\sigma$ (RBF): réel $>0$Largeur du noyau gaussien : échelle à laquelle deux points sont « similaires ».

Voir le relèvement en 3D

Des données en anneaux ne sont pas séparables par une droite. Relevons chaque point avec $\bphi(\bx) = (x_1, x_2, x_1^2+x_2^2)$ : le disque intérieur reste en bas, l'anneau extérieur monte — un plan horizontal les sépare. Son intersection avec le paraboloïde, projetée au sol, est un cercle : la frontière non linéaire dans l'espace d'origine. (Même idée que le relèvement $x\mapsto(x,x^2)$ du chapitre 1.)

Preuve — le noyau polynomial $(\bx\T\bx')^2$ est un produit scalaire de features explicites

En 2D : $(\bx\T\bx')^2 = (x_1x_1' + x_2x_2')^2 = x_1^2x_1'^2 + 2x_1x_2x_1'x_2' + x_2^2x_2'^2$.

$= (x_1^2,\ \sqrt2x_1x_2,\ x_2^2)\cdot(x_1'^2,\ \sqrt2x_1'x_2',\ x_2'^2) = \bphi(\bx)\T\bphi(\bx')$ avec $\bphi(\bx) = (x_1^2,\sqrt2x_1x_2,x_2^2)\in\R^3$.

En dimension $D$ et degré $d$, $\bphi$ contient $\binom{D+d-1}{d}$ monômes, mais $\kappa$ se calcule en $O(D)$ : un produit scalaire puis une puissance. C'est tout le gain du kernel trick.

∎

Le noyau gaussien (RBF)

Slides p.42–43 PRML éq. 6.23 p.296

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestSupport Vector Machines Part 3: The Radial (RBF) KernelLe noyau RBF, sa dimension infinie (série de Taylor) et son rôle de similarité.

Noyau RBF (radial basis function)

$$\kappa(\bx_i,\bx_j) = \exp\!\Big(-\frac{\|\bx_i-\bx_j\|^2}{2\sigma^2}\Big).$$ Vaut 1 si $\bx_i = \bx_j$, décroît vers 0 avec la distance. Sa feature map est de dimension infinie : on peut évaluer le noyau mais pas construire $\bphi$.

Géométrie de la décision : $f(\bx) = \sum_i\alpha_iy_i\,\kappa(\bx_i,\bx) + b$ est une somme de bosses gaussiennes centrées sur les vecteurs de support — positives pour la classe $+1$, négatives pour $-1$ — posées sur un niveau $b$. La frontière est la courbe de niveau 0 de ce paysage (vue 3D). $\sigma$ petit : bosses étroites, frontière très tortueuse (sur-apprentissage) ; $\sigma$ grand : bosses larges, frontière presque linéaire.

Preuve — la feature map du noyau RBF en 1D est de dimension infinie (slide 43)

$\exp\!\big(-\frac{(x-x')^2}{2\sigma^2}\big) = e^{-x^2/2\sigma^2}\,e^{-x'^2/2\sigma^2}\,e^{xx'/\sigma^2}$ (développer $(x-x')^2 = x^2 - 2xx' + x'^2$).

Série de Taylor de l'exponentielle : $e^{xx'/\sigma^2} = \sum_{k=0}^\infty\frac{(xx')^k}{k!\,\sigma^{2k}} = \sum_{k=0}^\infty\Big(\frac{x^k}{\sqrt{k!}\,\sigma^k}\Big)\Big(\frac{x'^k}{\sqrt{k!}\,\sigma^k}\Big)$.

Donc $\kappa(x,x') = \bphi(x)\T\bphi(x')$ avec $\bphi(x) = e^{-x^2/2\sigma^2}\Big[1,\ \sqrt{\tfrac{1}{1!\sigma^2}}\,x,\ \sqrt{\tfrac{1}{2!\sigma^4}}\,x^2,\ \sqrt{\tfrac1{3!\sigma^6}}\,x^3,\ \dots\Big]$ : une infinité de coordonnées.

La scène ci-dessous tronque cette série à $K$ termes : l'approximation converge vers le noyau exact, mais il faut d'autant plus de termes que $|xx'|/\sigma^2$ est grand.

∎

7Résumé & questions de la slide 44

Tout le chapitre en une chaîne

$$\underbrace{\max_f\min_i\frac{y_if(\bx_i)}{\|\bw\|}}_{\text{§1 : marge}}\ \xrightarrow{\text{échelle}}\ \underbrace{\min_{\bw,b}\tfrac12\|\bw\|^2\ \text{s.c.}\ y_i(\bw\T\bx_i+b)\ge1}_{\text{§2 : primal}}\ \xrightarrow{\text{Lagrangien (§3)}}\ \underbrace{\max_{\boldsymbol\alpha\ge0,\ \sum_i\alpha_iy_i = 0}\ \sum_i\alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\bx_i\T\bx_j}_{\text{§4 : dual}}$$ $$\xrightarrow{}\ \underbrace{\bw^* = \sum_i\alpha_i^*y_i\bx_i}_{\text{vecteurs de support}}\ \xrightarrow{\text{non séparable}}\ \underbrace{0\le\alpha_i\le C\ \Leftrightarrow\ \tfrac12\|\bw\|^2+C\sum_i\max\{0,1-y_if(\bx_i)\}}_{\text{§5 : marge souple = hinge}}\ \xrightarrow{\text{non linéaire}}\ \underbrace{\bx_i\T\bx_j\to\kappa(\bx_i,\bx_j)}_{\text{§6 : noyaux}}$$

Comment formuler l'apprentissage à marge maximale ?

Réponse

Maximiser la distance du point le plus proche à l'hyperplan, $\max_f\min_j\frac{y_jf(\bx_j)}{\|\bw\|}$ ; par invariance d'échelle on fixe $\min_jy_jf(\bx_j) = 1$, ce qui donne $\min\frac12\|\bw\|^2$ s.c. $y_i(\bw\T\bx_i+b)\ge1$ — un programme quadratique convexe. Version non séparable : ajouter les écarts $\xi_i$ et $C\sum\xi_i$, soit hinge loss + régularisation $\ell_2$.

Quel lien entre le primal et le dual ?

Réponse

Le dual maximise la borne inférieure $D(\boldsymbol\alpha) = \min_{\bw,b}\mathfrak L$ ; dualité faible toujours ($d^*\le p^*$), forte ici (convexe + Slater). Les solutions sont liées par $\bw^* = \sum\alpha_i^*y_i\bx_i$, et la complémentarité fait que seuls les vecteurs de support ont $\alpha_i^*>0$. Le dual a $N$ variables et ne voit les données qu'à travers des produits scalaires.

Pourquoi le dual permet-il des features non linéaires ?

Réponse

Parce que les données n'apparaissent que via $\bphi(\bx_i)\T\bphi(\bx_j)$, remplaçable par un noyau $\kappa(\bx_i,\bx_j)$ calculable sans construire $\bphi$ — même de dimension infinie (RBF). Le coût dépend de $N$, pas de la dimension des features.

Pour s'entraîner : page d'exercices à trous.