Machines à vecteurs de support et noyaux

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• calculer la distance d'un point à un hyperplan et la marge géométrique d'un séparateur linéaire, et démontrer que la bande de marge d'un séparateur normalisé a une largeur $2/\Vert \mathbf{w}\Vert$;
• écrire le séparateur à marge maximale comme un problème d'optimisation convexe, le résoudre exactement sur un petit exemple et vérifier sa solution par les conditions KKT, en reconnaissant les vecteurs de support;
• passer à la marge souple, relier le paramètre $C$ à la perte charnière et à la minimisation régularisée du risque empirique des chapitres 4 et 6, et entraîner le modèle par descente de sous-gradient;
• expliquer l'astuce du noyau: remplacer un produit scalaire de caractéristiques $\phi (\mathbf{x}{)}^{\top }\phi ({\mathbf{x}}^{\prime })$ par un noyau $k(\mathbf{x},{\mathbf{x}}^{\prime })$, avec les noyaux polynomial et gaussien, et rendre le problème du XOR séparable;
• calculer une régression ridge à noyau $\mathbf{\alpha }=(K+\lambda I{)}^{-1}\mathbf{y}$, choisir la largeur de bande du noyau gaussien comme un réglage biais–variance, et estimer le coût de la matrice de Gram.

Une autre idée de la meilleure droite

Le chapitre 4 s'achevait sur une difficulté. Quand une droite sépare parfaitement les deux classes, la régression logistique n'a pas de solution: ses poids grandissent sans limite, parce que la vraisemblance peut toujours être améliorée en rendant le modèle plus sûr de lui. Et une droite qui sépare, il y en a alors une infinité. Le chapitre 4 annonçait trois remèdes: arrêter tôt, pénaliser les poids, ou changer de critère. Ce chapitre suit la troisième voie, et elle mène plus loin qu'on ne pourrait le croire.

Le critère est géométrique. Parmi toutes les droites qui séparent les exemples, choisissons celle qui s'en tient le plus loin possible: celle dont le point le plus proche est le plus éloigné. L'intuition est celle d'une route tracée entre deux villages: la plus sûre passe au milieu de l'espace libre, pas en frôlant la première maison. Un nouvel exemple qui ressemble aux exemples d'entraînement, mais qui en diffère un peu, a alors le plus de chances de tomber du bon côté.

Ce critère donne la machine à vecteurs de support (support vector machine, SVM), le modèle qui a dominé l'apprentissage supervisé pendant une bonne partie des années 1990 et 2000, avant les réseaux de neurones profonds. Il a trois propriétés qui en font un objet d'étude à part entière, même à l'époque de l'apprentissage profond. Son entraînement est un problème convexe, sans minimum local. Sa solution ne dépend que de quelques exemples, les vecteurs de support, qui donnent leur nom à la méthode. Et sa formulation ne fait intervenir les données que par des produits scalaires, ce qui permet de remplacer ces produits scalaires par un noyau et de travailler, sans jamais les calculer, avec des caractéristiques en nombre arbitrairement grand — voire infini. Cette dernière idée dépasse les SVM: la fin du chapitre l'applique à la régression ridge du chapitre 6.

Un classifieur linéaire calcule un score affine et décide selon son signe.

La frontière ne détermine pas $(\mathbf{w},b)$: multiplier les deux par $c>0$ ne change ni l'hyperplan $H$ ni les décisions, mais multiplie toutes les marges $m_i$ par $c$. La marge fonctionnelle mesure donc la confiance de façon arbitraire, puisqu'on peut la rendre aussi grande qu'on veut en dilatant $\mathbf{w}$. C'est d'ailleurs exactement ce que fait la régression logistique sur des données séparables. Pour une mesure qui ait un sens, il faut une distance.

La marge géométrique

On mesure la distance d'un point à un hyperplan le long de la normale à l'hyperplan, qui est la direction $\mathbf{w}$.

Démonstration. Posons $f(\mathbf{x})={\mathbf{w}}^{\top }\mathbf{x}+b$ et $\mathbf{p}={\mathbf{x}}_0-t\mathbf{w}$ avec $t=f({\mathbf{x}}_0)/\Vert \mathbf{w}{\Vert }^2$. Alors : le point est sur , et . Montrons qu'aucun point de n'est plus proche. Pour tout , on a : le vecteur est orthogonal à , donc à . Par le théorème de Pythagore (Algèbre linéaire, chapitre 7),

avec égalité si et seulement si $\mathbf{h}=\mathbf{p}$. La distance de ${\mathbf{x}}_0$ à $H$ est donc $|f({\mathbf{x}}_0)|/\Vert \mathbf{w}\Vert$, atteinte en $\mathbf{p}$ seulement. $\square$

En dimension 2, c'est la formule bien connue de la distance d'un point $(x_0,y_0)$ à la droite $ax+by+c=0$, $|a{x}_0+b{y}_0+c|/\sqrt{a^2+b^2}$. La formule (9.2) dit aussi que le score est une distance à la frontière, mesurée dans l'unité . Si l'exemple est bien classé, , et la distance s'écrit sans valeur absolue.

L'invariance par changement d'échelle laisse une liberté: on peut choisir l'échelle de $(\mathbf{w},b)$ comme on veut. Le choix commode, pour un séparateur, est celui qui donne une marge fonctionnelle égale à 1 à l'exemple le plus proche: ${\min }_i{y}_{i}f({\mathbf{x}}_i)=1$. On dit alors que le séparateur est sous forme canonique. Ce n'est qu'une convention de normalisation, mais elle simplifie tout le reste.

Démonstration. Par le théorème 9.1, la marge géométrique de l'exemple $i$ vaut $y_{i}f({\mathbf{x}}_i)/\Vert \mathbf{w}\Vert \ge 1/\Vert \mathbf{w}\Vert$, avec égalité pour l'exemple qui réalise le minimum; donc $\gamma =1/\Vert \mathbf{w}\Vert$. Les hyperplans $H_{+}$, et ont la même normale : ils sont parallèles. Un exemple strictement entre et vérifierait , donc , ce qui contredit la forme canonique. Enfin, prenons un point , de sorte que . Le point vérifie , donc , et le segment est dirigé selon la normale commune; sa longueur est la distance entre les deux hyperplans parallèles. On peut aussi l'obtenir par (9.2): la distance de à vaut .

Dans la littérature, «la marge» désigne tantôt $\gamma$, la distance du point le plus proche à la frontière, tantôt $2\gamma$, la largeur de la bande. Ce chapitre réserve marge géométrique à $\gamma$ et dit largeur de la bande pour $2/\Vert \mathbf{w}\Vert$. Les deux notions donnent le même séparateur optimal, puisque l'une est le double de l'autre.

Le séparateur à marge maximale

Nous pouvons maintenant écrire le critère annoncé. On cherche le séparateur de plus grande marge géométrique. Sous forme canonique, cette marge vaut $1/\Vert \mathbf{w}\Vert$; la maximiser revient à minimiser $\Vert \mathbf{w}\Vert$, ou, ce qui est équivalent et plus commode, $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$.

Le problème (9.3) est un problème d'optimisation convexe: l'objectif est une fonction quadratique convexe, et chaque contrainte est affine en $(\mathbf{w},b)$, de sorte que l'ensemble des $(\mathbf{w},b)$ admissibles est une intersection de demi-espaces, donc un convexe. C'est un programme quadratique (quadratic program). Deux conséquences importent ici. D'abord, il n'a pas de minimum local qui ne soit global: un algorithme qui descend ne peut pas se laisser piéger, contrairement à ce que nous verrons pour les réseaux de neurones au chapitre 10. Ensuite, sa solution en $\mathbf{w}$ est unique: si ${\mathbf{w}}_1\ne {\mathbf{w}}_2$ étaient deux solutions de même norme minimale, leur milieu serait admissible (les contraintes sont affines) et de norme strictement plus petite, par la stricte convexité de — contradiction. Le biais est alors unique lui aussi dès qu'un exemple de chaque classe touche la bande.

Pourquoi le minimum existe-t-il? Si les données sont séparables, il existe un séparateur, que l'on peut mettre sous forme canonique: l'ensemble admissible n'est pas vide. Le reste est un argument de compacité standard, que nous admettons. Si les données ne sont pas séparables, l'ensemble admissible est vide et (9.3) n'a pas de solution: c'est la limite de la marge dure, et la section suivante la lève.

Les vecteurs de support sont les exemples qui «portent» la solution: on verra que les autres pourraient être retirés, ou déplacés tant qu'ils restent hors de la bande, sans que le séparateur change d'un iota. C'est une différence profonde avec la régression logistique, où chaque exemple, même très loin de la frontière, tire un peu sur les poids.

La figure 9.1 montre ce que les calculs disent. La bande est aussi large que possible: on ne peut ni la tourner ni la décaler sans qu'elle heurte $A$, $B$ ou $D$. Trois points suffisent ici à bloquer une bande dans le plan — deux d'un côté, un de l'autre. Ce n'est pas un hasard: en dimension $d$, une bande en position générale est bloquée par au plus $d+1$ points.

Le problème dual

Le certificat de l'exemple 9.1 n'est pas une astuce isolée. Il vient de la théorie de la dualité lagrangienne, qui associe à tout problème d'optimisation sous contraintes un second problème, dit dual, dont les variables sont des multiplicateurs, un par contrainte. Pour (9.3), on introduit un multiplicateur ${\alpha }_i\ge 0$ par exemple et le lagrangien

Pour $\mathbf{\alpha }$ fixé, $\mathcal{L}$ est une fonction quadratique convexe de $(\mathbf{w},b)$. Annuler ses dérivées partielles donne $\mathbf{w}-{\sum }_i{\alpha }_i{y}_i{\mathbf{x}}_i=0$ et . En reportant dans , les termes en disparaissent et il reste une fonction des seuls . C'est elle que maximise le problème dual.

Nous admettons ce théorème. Sa démonstration repose sur le théorème de dualité forte de l'optimisation convexe, valable ici parce que l'objectif est convexe et les contraintes affines (c'est une condition de qualification des contraintes, dite de Slater dans sa version générale). Le démontrer demanderait un cours d'optimisation — un théorème de séparation des convexes, puis la théorie des multiplicateurs — qui sort du cadre de ce cours. Ce que nous pouvons vérifier, en revanche, c'est la condition suffisante que nous avons utilisée dans l'exemple 9.1, et elle se démontre en quelques lignes: si $(\mathbf{w},b,\mathbf{\alpha })$ satisfait les trois conditions, alors pour tout séparateur canonique $(\mathbf{v},c)$ admissible,

La première inégalité est la convexité de $\frac{1}{2}\Vert \cdot {\Vert }^2$; l'égalité utilise les deux conditions de stationnarité (on peut ajouter $c-b$ fois ${\sum }_i{\alpha }_i{y}_i=0$); la dernière inégalité vient de ce que, par complémentarité, seuls les avec ont , et pour eux . Aucun séparateur admissible ne fait donc mieux que .

Quatre conséquences du théorème 9.3 structurent la suite du chapitre.

La solution est une combinaison des vecteurs de support. La complémentarité impose ${\alpha }_i=0$ dès que la contrainte n'est pas active, c'est-à-dire dès que l'exemple n'est pas un vecteur de support. La relation de stationnarité devient

une somme sur les vecteurs de support seulement. C'est ce qui justifie la réponse à la question 9.2.

Le biais se lit sur n'importe quel vecteur de support. Si ${\alpha }_s>0$, alors $y_s({\mathbf{w}}^{\top }{\mathbf{x}}_s+b)=1$, et comme , . Dans l'exemple 9.1, avec : .

Le dual ne voit les données qu'à travers leurs produits scalaires. Dans (9.4), les exemples n'apparaissent que dans les nombres ${\mathbf{x}}_i^{\top }{\mathbf{x}}_j$, qui forment une matrice $n\times n$. Et la décision sur un nouveau point aussi: par (9.5), $f(\mathbf{x})={\sum }_i{\alpha }_i{y}_i{\mathbf{x}}_i^{\top }\mathbf{x}+b$. Ni ni les coordonnées des ne sont nécessaires, seulement des produits scalaires. Toute la section sur les noyaux repose sur cette observation.

Le dual a $n$ variables, le primal $d+1$. Quand il y a peu d'exemples et beaucoup de caractéristiques, le dual est le plus petit des deux problèmes; quand $n$ est grand, c'est l'inverse. Les bibliothèques résolvent généralement le dual par des méthodes de décomposition, dont la plus connue est l'algorithme SMO (sequential minimal optimization) de John Platt, qui ne modifie que deux ${\alpha }_i$ à la fois.

Sur l'exemple 9.1, la matrice des produits scalaires entre les vecteurs de support $A$, $B$, $D$ vaut

et la valeur de (9.4) en $\mathbf{\alpha }=(\frac{1}{20},\frac{1}{20},\frac{1}{10})$ est , égale à la valeur du primal: les deux problèmes ont bien le même optimum. Vous démontrerez à l'exercice 9.5 que à l'optimum, ce qui donne une formule pour la marge géométrique, ; ici .

La marge souple et la perte charnière

La marge dure a deux défauts. Le premier est rédhibitoire: si les données ne sont pas séparables, le problème (9.3) n'a pas de solution. C'est le cas du jeu B, où E8 et E15 sont du mauvais côté de toute droite raisonnable — et c'est le cas de presque tous les jeux de données réels. Le second est plus sournois: même sur des données séparables, un seul exemple bruité près de la frontière peut imposer une bande très étroite, et la solution en dépend entièrement. Les vecteurs de support sont peu nombreux, ce qui fait la force de la méthode; mais s'ils sont aberrants, c'est sa faiblesse.

Le remède consiste à autoriser des violations de la marge, en les faisant payer. À chaque exemple on associe une variable d'écart ${\xi }_i\ge 0$ (slack variable), qui mesure de combien il manque à sa marge pour atteindre 1.

Le problème (9.6) est toujours admissible — il suffit de prendre des ${\xi }_i$ assez grands — et il reste un programme quadratique convexe. Le paramètre $C$ arbitre entre deux souhaits contradictoires: une bande large (petit $\Vert \mathbf{w}\Vert$) et peu de violations (petits ${\xi }_i$). Avec un $C$ grand, chaque violation coûte cher et l'on se rapproche de la marge dure; avec un $C$ petit, on accepte beaucoup de violations pour une bande large. C'est un hyperparamètre, et il se choisit par validation croisée (chapitre 5), jamais sur l'ensemble de test.

Le dual de (9.6) a exactement la forme (9.4), à une différence près: les multiplicateurs sont bornés, $0\le {\alpha }_i\le C$. Les conditions KKT disent alors que ${\alpha }_i=0$ pour les exemples strictement hors de la bande ($m_i>1$), pour ceux qui sont dedans ou du mauvais côté (), et seulement pour ceux qui sont exactement sur son bord (): pour ces derniers, les conditions ne fixent pas la valeur, et l'exemple 9.2 montre qu'elle peut même ne pas être unique. Réciproquement, force . Nous admettons ces faits pour la même raison que le théorème 9.3.

Les variables d'écart peuvent être éliminées, et ce que l'on obtient éclaire la méthode d'un jour nouveau.

Démonstration. Fixons $(\mathbf{w},b)$ et notons $m_i=y_i({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)$. Les contraintes de (9.6) sur s'écrivent et , soit . Comme l'objectif est croissant en chaque (le coefficient est positif), la meilleure valeur de à fixé est la plus petite permise, , et toute autre valeur admissible donne un objectif strictement plus grand. Minimiser (9.6) en revient donc à minimiser en la fonction obtenue en remplaçant par , qui est (9.7), et les solutions se correspondent comme annoncé. Enfin, diviser une fonction par la constante ne change pas ses minimiseurs, et .

Ce résultat range la SVM dans le cadre général du cours: minimiser un risque empirique régularisé. La régression ridge du chapitre 6 minimise une perte carrée plus $\lambda \Vert \mathbf{w}{\Vert }^2$; la régression logistique régularisée, une entropie croisée plus $\lambda \Vert \mathbf{w}{\Vert }^2$; la SVM, une perte charnière plus $\lambda \Vert \mathbf{w}{\Vert }^2$. Le paramètre $C$ est, à un facteur $2n$ près, l'inverse de — comme le chapitre 6 l'annonçait: un grand est une régularisation faible.

La comparaison avec la régression logistique va plus loin. Avec $y\in \{-1,+1\}$ et $\hat{p}=\sigma (f(\mathbf{x}))$, l'entropie croisée (4.6) du chapitre 4 s'écrit $\ln (1+{\mathrm{e}}^{-yf(\mathbf{x})})$. En effet, pour elle vaut , et pour elle vaut , puisque . Les trois pertes de classification du cours sont donc des fonctions de la seule :

La figure 9.2 met côte à côte les trois pertes. La perte 0–1 est celle qu'on voudrait minimiser — le taux d'erreur —, mais elle est constante par morceaux et ne guide aucune optimisation (chapitre 1). La perte charnière et la perte logistique en sont deux substituts convexes (convex surrogates). La charnière majore la perte 0–1 partout. Elles se ressemblent beaucoup pour $m$ très négatif, où toutes deux croissent comme $-m$: une erreur grossière coûte proportionnellement à sa gravité, et non à son carré comme avec la perte carrée de l'exemple 4.1, ce qui évite qu'un exemple aberrant fasse pivoter toute la frontière. Elles diffèrent pour $m\ge 1$: la perte logistique continue de récompenser un exemple de plus en plus sûr, alors que la charnière s'en désintéresse complètement. C'est cette indifférence qui rend la solution parcimonieuse — seuls les exemples de marge au plus 1 ont un ${\alpha }_i$ non nul — et qui fait qu'une SVM ne produit pas de probabilité.

La marge souple sur les courriels

Remarquez combien la solution est parcimonieuse: sur seize courriels, neuf n'interviennent pas du tout dans $\mathbf{w}$ pour $C=1$. On pourrait les déplacer, tant qu'ils restent hors de la bande, ou les retirer, sans changer le modèle. La régression logistique, elle, utilise les seize.

Entraîner par descente de sous-gradient

Le dual se résout par des algorithmes spécialisés. Mais la forme (9.7) suggère une approche plus simple, dans l'esprit du chapitre 3: descendre le gradient. L'obstacle est que la perte charnière n'est pas dérivable en $m=1$, où elle fait un coude. On contourne l'obstacle avec la notion de sous-gradient: pour une fonction convexe, un vecteur $\mathbf{g}$ est un sous-gradient en $\mathbf{\theta }$ si $J({\mathbf{\theta }}^{\prime })\ge J(\mathbf{\theta })+{\mathbf{g}}^{\top }({\mathbf{\theta }}^{\prime }-\mathbf{\theta })$ pour tout — la droite (ou l'hyperplan) de pente reste sous la courbe. Là où est dérivable, le seul sous-gradient est le gradient. Au coude de , toute pente entre et convient, et l'on choisit . Pour l'objectif (9.7), noté , un sous-gradient est donc

où la somme porte sur les exemples actifs, ceux dont la marge est strictement inférieure à 1. Les autres ne contribuent pas: un exemple sûr ne tire plus sur la frontière.

La descente de sous-gradient répète ${\mathbf{\theta }}^{(k+1)}={\mathbf{\theta }}^{(k)}-{\eta }_k{\mathbf{g}}^{(k)}$. Contrairement à la descente de gradient du chapitre 3, un pas fixe ne converge pas: au voisinage du coude, le sous-gradient ne tend pas vers zéro, et l'itéré oscille. Il faut un pas ; comme est fortement convexe en (le terme a une hessienne égale à l'identité), le pas convient. Le biais, qui n'est pas pénalisé, converge plus lentement; les caractéristiques avant la descente, puis corriger le biais à la fin, accélère nettement les choses, pour la même raison que la standardisation au chapitre 3. L'exercice suivant met tout cela en œuvre.

Le rôle de $C$

L'explorateur suivant résout la marge souple sur un petit jeu synthétique de vingt points, tirés une fois pour toutes par un générateur pseudo-aléatoire de graine 24: deux nuages qui se chevauchent, de sorte qu'aucune droite ne les sépare. La solution est calculée dans la page, par 6 000 pas de la descente de sous-gradient que vous venez d'écrire.

En faisant glisser $C$ de $0,01$ à $10$, vous voyez la bande se resserrer: sa largeur passe de $6,99$ à $1,76$, et le nombre de vecteurs de support tombe de 18 à 6. Avec un $C$ minuscule, la pénalité $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$ domine, est petit, la bande est immense, et presque tous les points sont dedans: le modèle est très , son orientation est une sorte de moyenne de tout le nuage. Avec un grand, la frontière se laisse dicter par les quelques points qui la bordent. Le nombre d'erreurs d'entraînement, lui, reste à 3 presque partout: ce sont les mêmes trois points, enfoncés dans le nuage adverse, qu'aucune droite raisonnable ne récupère. C'est le compromis biais–variance du chapitre 6, réglé par au lieu de .

L'astuce du noyau

Une SVM linéaire ne sait tracer que des frontières droites. Le chapitre 2 a montré comment s'affranchir de cette limite sans changer d'algorithme: remplacer les caractéristiques brutes $\mathbf{x}$ par des caractéristiques transformées $\phi (\mathbf{x})$ (définition 2.5) — des puissances, des produits, des indicateurs — et appliquer la méthode linéaire dans le nouvel espace. Une frontière droite dans l'espace des $\phi (\mathbf{x})$ est une courbe dans l'espace des $\mathbf{x}$.

L'obstacle est le nombre de caractéristiques. Tous les monômes de degré au plus $m$ en $d$ variables sont au nombre de $\left(\genfrac{}{}{0ex}{}{d+m}{m}\right)$ (question 2.10): $6$ pour $d=2$ et $m=2$, mais $176851$ pour et , et pour une image de pixels au degré 3. Calculer et stocker ces vecteurs pour chaque exemple devient vite impossible. C'est ici que l'observation faite sur le dual prend tout son sens: . Si l'on sait calculer ces produits scalaires directement, sans passer par les vecteurs, on n'a jamais besoin de .

L'astuce du noyau (kernel trick) consiste à prendre un algorithme qui n'utilise les données qu'à travers des produits scalaires, et à remplacer chaque produit scalaire ${\mathbf{x}}_i^{\top }{\mathbf{x}}_j$ par $k({\mathbf{x}}_i,{\mathbf{x}}_j)$. Pour la SVM, le dual (9.4) devient

et la décision sur un nouveau point, par (9.5),

Le vecteur $\mathbf{w}={\sum }_i{\alpha }_i{y}_i\phi ({\mathbf{x}}_i)$ existe dans l'espace des caractéristiques, mais on ne le calcule jamais. Le prix à payer est que la prédiction doit parcourir les vecteurs de support: un modèle à noyau garde une partie des données d'entraînement, comme les plus proches voisins du chapitre 7.

Le noyau gaussien est le poids gaussien déjà rencontré pour les votes pondérés des plus proches voisins (chapitre 7), avec la même largeur de bande $h$. Il vaut 1 quand $\mathbf{x}={\mathbf{x}}^{\prime }$ et décroît vers 0 quand les points s'éloignent, à l'échelle $h$: c'est une similarité. Les bibliothèques l'écrivent souvent $\exp (-\gamma \Vert \mathbf{x}-{\mathbf{x}}^{\prime }{\Vert }^2)$ avec , une lettre qui n'a rien à voir avec la marge géométrique.

Le noyau polynomial correspond à un nombre fini de caractéristiques, même grand. Le noyau gaussien va plus loin, et c'est la promesse du chapitre 2: il correspond à une transformation qui a une infinité de composantes.

Démonstration. Développons le carré: $(x-x^{\prime }{)}^2=x^2+x^{\prime 2}-2x{x}^{\prime }$, donc

La série de l'exponentielle (Analyse I) donne, pour tout réel $u$, ${\mathrm{e}}^u={\sum }_{j\ge 0}{u}^j/j!$, avec convergence absolue. Avec $u=x{x}^{\prime }/h^2$,

En multipliant chaque terme par les deux facteurs ${\mathrm{e}}^{-x^2/(2h^2)}$ et ${\mathrm{e}}^{-x^{\prime 2}/(2h^2)}$, qui ne dépendent pas de , on obtient la formule annoncée, et la série reste absolument convergente. Pour , chaque est le produit de nombres non nuls.

En dimension $d$, le noyau gaussien est le produit des noyaux gaussiens de chaque coordonnée, puisque $\Vert \mathbf{x}-{\mathbf{x}}^{\prime }{\Vert }^2={\sum }_j(x_j-x_j^{\prime }{)}^2$; ses caractéristiques sont tous les produits , une infinité dénombrable. Une SVM à noyau gaussien est donc une SVM dans un espace de dimension infinie, que l'on entraîne et que l'on évalue avec une matrice et quelques exponentielles. Les sont, au facteur gaussien près, les monômes de la régression polynomiale du chapitre 2, pondérés par : les degrés élevés sont fortement amortis, ce qui est une forme de régularisation intégrée au noyau.

Toute fonction de deux variables n'est pas un noyau. La définition 9.7 exige une transformation $\phi$, et cette exigence a une conséquence que l'on peut tester sur des données.

Démonstration. La symétrie vient de celle du produit scalaire: $K_{ij}=\phi ({\mathbf{x}}_i{)}^{\top }\phi ({\mathbf{x}}_j)=\phi ({\mathbf{x}}_j{)}^{\top }\phi ({\mathbf{x}}_i)=K_{ji}$. Pour , par bilinéarité du produit scalaire,

La réciproque est vraie aussi, et c'est un théorème profond (théorème de Mercer, ou de Moore–Aronszajn dans sa forme moderne): une fonction symétrique dont toutes les matrices de Gram sont semi-définies positives est un noyau, pour un $\phi$ convenable. Nous l'admettons; il garantit que le dual de la SVM reste un problème concave à maximiser, donc sans optimum local parasite, quel que soit le noyau. L'exercice 9.4 montre qu'une fonction aussi naturelle que $\Vert \mathbf{x}-{\mathbf{x}}^{\prime }{\Vert }^2$ n'est pas un noyau.

Les méthodes à noyau au-delà des SVM

L'astuce du noyau s'applique à tout algorithme qui ne voit les données qu'à travers des produits scalaires — et il y en a beaucoup plus qu'on ne le croirait. Pour s'en convaincre, il faut une raison générale pour laquelle la solution d'un problème d'apprentissage s'écrit comme une combinaison des exemples, comme (9.5) pour la SVM. Cette raison existe, et elle porte un nom: le théorème du représentant (representer theorem). Sous une forme simple, il dit que si l'on minimise, sur les $\mathbf{w}$ de l'espace des caractéristiques, un critère de la forme «somme de pertes sur les scores ${\mathbf{w}}^{\top }\phi ({\mathbf{x}}_i)$ plus $\lambda \Vert \mathbf{w}{\Vert }^2$», alors la solution est une combinaison $\mathbf{w}={\sum }_i{\alpha }_i\phi ({\mathbf{x}}_i)$ des seuls exemples d'entraînement. L'idée de la preuve est géométrique: on décompose en sa projection sur le sous-espace engendré par les et un reste orthogonal; le reste ne change aucun score , donc aucune perte, mais il augmente — l'optimum le met à zéro. Nous ne l'énonçons pas en toute généralité, mais nous allons l'établir directement pour la ridge.

La régression ridge à noyau

La régression ridge du chapitre 6 minimise $\Vert \mathbf{y}-\tilde{X}\mathbf{\theta }{\Vert }^2+\lambda \Vert \mathbf{w}{\Vert }^2$, et sa solution (6.4) fait intervenir ${\tilde{X}}^{\top }\tilde{X}$, une matrice de produits scalaires entre , de taille . Ce n'est pas encore la forme voulue. Pour passer aux produits scalaires entre , on travaille sans biais, avec des étiquettes (on soustrait leur moyenne d'entraînement avant l'ajustement, et on la rajoute aux prédictions), ce qui remplace le biais non pénalisé. Notons la matrice dont la -ème ligne est ; alors , la matrice de Gram.

Démonstration. La première égalité est la forme close de la ridge, théorème 6.3, appliquée sans biais à la matrice $\Phi$: ici toutes les coordonnées sont pénalisées, $I^{\prime }$ devient $I_p$, et ${\Phi }^{\top }\Phi +\lambda I_p$ est définie positive par le même argument. La matrice est elle aussi définie positive: est semi-définie positive (théorème 9.6) et pour ; elle est donc inversible. Partons de l'identité évidente

Multiplions-la à gauche par $({\Phi }^{\top }\Phi +\lambda I_p{)}^{-1}$ et à droite par $(\Phi {\Phi }^{\top }+\lambda I_n{)}^{-1}$: il vient , et en appliquant les deux membres à , la deuxième égalité. Enfin, , puisque les colonnes de sont les . La prédiction vaut alors .

La démonstration suppose $p$ fini, mais la formule finale n'en dépend plus: elle ne contient que $K$ et $k$. Elle reste valable pour le noyau gaussien, à caractéristiques infinies — c'est le contenu du théorème du représentant, que nous admettons dans ce cas. C'est là que se trouve l'économie: avec $p$ caractéristiques, la forme primale inverse une matrice $p\times p$, la forme à noyau une matrice $n\times n$. Quand $p$ est beaucoup plus grand que $n$ — et a fortiori quand il est infini —, c'est la seconde qu'on veut. Et c'est bien la formule (6.4) du chapitre 6, écrite dans un espace de caractéristiques que l'on ne voit jamais.

Remarquez la différence avec la SVM: les coefficients ${\alpha }_i$ de la ridge à noyau sont tous non nuls en général. La perte carrée ne s'annule jamais tant que la prédiction n'est pas exacte, et chaque exemple contribue. La parcimonie des SVM vient de la perte charnière, pas du noyau.

La largeur de bande est donc un réglage biais–variance, au même titre que le degré d'un polynôme ou le nombre $k$ de voisins. Ses deux limites se calculent. Quand $h\to 0$, $k({\mathbf{x}}_i,{\mathbf{x}}_j)\to 0$ pour $i\ne j$: tend vers l'identité, , la prédiction en un point d'entraînement tend vers et la prédiction partout ailleurs vers . C'est une mémoire pure, sans aucune généralisation: variance maximale. Quand , tous les coefficients de tendent vers 1, et le modèle ne distingue plus les points: biais maximal. Entre les deux, et se choisissent ensemble, par validation croisée. La figure 9.3 montre aussi un défaut commun aux noyaux gaussiens: loin de toutes les données, la prédiction retombe vers , c'est-à-dire vers la moyenne, quelle que soit la tendance observée au bord. Une extrapolation à noyau gaussien n'extrapole pas: elle oublie.

Le coût de la matrice de Gram

Les méthodes à noyau échangent la dimension des caractéristiques contre le nombre d'exemples. C'est un excellent marché quand $n$ est modeste, et un très mauvais quand il est grand. La matrice de Gram a $n^2$ coefficients: pour $n=10000$, cela fait $10^8$ nombres, soit 800 Mo en double précision (8 octets par nombre); pour $n=100000$, $10^{10}$ nombres et 80 Go, plus que la mémoire de la plupart des ordinateurs. Résoudre le système (9.12) par une décomposition de Cholesky demande de l'ordre de opérations, soit environ pour . Doubler les données multiplie la mémoire par quatre et le temps par huit.

La SVM s'en tire un peu mieux, parce que le dual peut se résoudre par morceaux (SMO) sans stocker toute la matrice, et que la prédiction (9.10) ne parcourt que les vecteurs de support. Mais leur nombre croît en général avec $n$ sur des données bruitées, puisque chaque exemple mal classé en est un. Au-delà de quelques dizaines de milliers d'exemples, on recourt à des approximations du noyau — la méthode de Nyström, qui n'utilise qu'un sous-ensemble des colonnes de $K$, ou les caractéristiques aléatoires de Fourier, qui construisent un $\phi$ de dimension finie dont le produit scalaire approche le noyau gaussien —, ou l'on change de méthode. Les réseaux de neurones des chapitres 10 et 11, entraînés par descente de gradient stochastique, ont un coût par époque proportionnel à $n$; c'est l'une des raisons pour lesquelles ils ont supplanté les méthodes à noyau sur les très grands jeux de données.

Synthèse

• Avec des étiquettes $y\in \{-1,+1\}$, la marge $m_i=y_{i}f({\mathbf{x}}_i)$ est positive pour un exemple bien classé. La distance d'un point à l'hyperplan vaut ; sous forme canonique (), la marge géométrique vaut et la bande de marge a une largeur .

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• James, G., Witten, D., Hastie, T. et Tibshirani, R., An Introduction to Statistical Learning, Springer, 2ᵉ éd., 2021, chap. 9 (séparateur à marge maximale, classifieur à marge souple, SVM à noyau, lien avec la régression logistique).
• Hastie, T., Tibshirani, R. et Friedman, J., The Elements of Statistical Learning, Springer, 2ᵉ éd., 2009, chap. 12 (SVM et perte charnière comme minimisation d'un risque régularisé).
• Bishop, C. M., Pattern Recognition and Machine Learning, Springer, 2006, chap. 6 (méthodes à noyau, régression ridge à noyau, construction de noyaux) et chap. 7 (SVM, dual et conditions KKT).
• Shalev-Shwartz, S. et Ben-David, S., Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, chap. 15 (SVM, descente de sous-gradient) et chap. 16 (noyaux, théorème du représentant).
• Azencott, C.-A., Introduction au Machine Learning, Dunod, 2ᵉ éd., 2022 (les SVM et les méthodes à noyau, en français).
• Cortes, C. et Vapnik, V., «Support-vector networks», Machine Learning, 1995 (l'article qui introduit la marge souple).