L'apprentissage par l'erreur : régression et descente de gradient

Quiconque a appris un sport nouveau connaît, parfois douloureusement, l'apprentissage par l'erreur. Prenez le surf : couché trop en arrière sur la planche, elle s'enfonce et la vague vous échappe ; couché trop en avant, le nez plonge et vous projette dans les airs. Seul le point d'équilibre, au milieu, permet d'attraper la vague. L'apprenant surfeur teste, mesure l'ampleur de son échec, corrige, recommence — et converge vers la bonne position. Une famille entière d'algorithmes d'apprentissage automatique procède exactement ainsi : un modèle paramétré est initialisé avec des paramètres aléatoires, une fonction d'erreur (error function) juge la qualité de ses prédictions sur un jeu d'entraînement, puis les paramètres sont ajustés itérativement jusqu'à obtenir un modèle de plus en plus précis. C'est l'apprentissage par l'erreur (error-based learning).

La grande idée : minimiser l'erreur d'un modèle paramétré

Dans l'apprentissage par l'information (arbres de décision) ou par la similarité (k plus proches voisins), le modèle se déduisait directement de la structure des données. Ici le raisonnement s'inverse : on postule la forme du modèle — une combinaison pondérée des features descriptives — et l'apprentissage se réduit à trouver les bonnes valeurs des poids (weights). Chacune des innombrables combinaisons de poids définit un modèle qui s'ajuste plus ou moins bien à la relation présente dans les données. Les poids optimaux sont ceux qui produisent l'erreur de prédiction minimale.

Trois ingrédients suffisent donc : une forme de modèle paramétré, une fonction d'erreur pour mesurer l'écart entre prédictions et valeurs réelles, et un algorithme de recherche capable de trouver les poids qui minimisent cette erreur. Cet algorithme sera la descente de gradient (gradient descent), l'une des procédures les plus importantes non seulement de l'apprentissage automatique mais de toute l'informatique.

Les fondamentaux

La régression linéaire simple

Le jeu de données fil rouge enregistre le loyer mensuel (en euros) de bureaux du centre de Dublin, avec plusieurs features susceptibles d'influencer le prix : la surface (SIZE, en pieds carrés), l'étage (FLOOR), le débit internet (BROADBAND RATE, en Mb/s) et la classe énergétique (ENERGY RATING, de A à C). Commençons par une version simplifiée : prédire le loyer (RENTAL PRICE) à partir de la seule surface.

ID	SIZE	FLOOR	BROADBAND	ENERGY	RENTAL PRICE
1	500	4	8	C	320
2	550	7	50	A	380
3	620	9	7	A	400
4	630	5	24	B	390
5	665	8	100	C	385
6	700	4	8	B	410
7	770	10	7	B	480
8	880	12	50	A	600
9	920	14	8	C	570
10	1000	9	24	B	620

Un nuage de points de RENTAL PRICE contre SIZE révèle une relation linéaire nette : plus la surface croît, plus le loyer monte d'autant. Le modèle mathématique qui capture une telle relation est l'équation de la droite, y = m × x + b, où m est la pente et b l'ordonnée à l'origine (la valeur de y quand x vaut zéro). Avec une pente de 0,62 et une ordonnée à l'origine de 6,47, le modèle devient RENTAL PRICE = 6,47 + 0,62 × SIZE. Chaque pied carré supplémentaire ajoute 0,62 euro au loyer ; un bureau de 730 pieds carrés se louerait donc environ 6,47 + 0,62 × 730 ≈ 460 euros par mois.

Avec la notation du livre, on réécrit la régression linéaire simple (simple linear regression) ainsi :

Mw(d) = w[0] + w[1] × d[1]

où w = ⟨w[0], w[1]⟩ est le vecteur des poids, d une instance décrite par une seule feature d[1], et Mw(d) la prédiction du modèle. Tout l'enjeu est de déterminer les valeurs optimales des poids — celles qui font le mieux coller (fit) le modèle aux données. Pour les trouver, il faut d'abord savoir mesurer la qualité de l'ajustement.

Mesurer l'erreur

Plusieurs droites peuvent prétendre capturer la relation. En fixant w[0] à 6,47 et en faisant varier w[1] (0,4, 0,5, 0,62, 0,7, 0,8), on obtient des candidats différents. Visuellement, celui avec w[1] = 0,62 passe au plus près des points — mais comment le mesurer formellement ?

Il faut une fonction d'erreur qui capture l'écart entre les prédictions du modèle et les valeurs réelles du jeu d'entraînement. Les fonctions d'erreur sont aussi appelées fonctions de perte (loss functions), car elles représentent ce que l'on perd en réduisant les données à un simple modèle. Pour la régression linéaire, la plus courante est la somme des carrés des erreurs (sum of squared errors), notée L2. On calcule la prédiction pour chaque instance, puis l'erreur (ou résidu) entre prédiction et valeur réelle. Comme le modèle surestime parfois et sous-estime parfois, certaines erreurs sont positives, d'autres négatives ; les additionner telles quelles les ferait s'annuler. D'où l'élévation au carré, qui rend toutes les valeurs positives :

L2(Mw, D) = (1/2) × Σ (ti - Mw(di))²
            i = 1 à n

où le jeu d'entraînement D comporte n instances, chacune décrite par des features di et une cible ti. Appliquée au candidat w[0] = 6,47, w[1] = 0,62, la fonction donne :

ID	RENTAL	Prédiction	Erreur	Erreur²
1	320	316,47	3,53	12,46
2	380	347,47	32,53	1 058,20
3	400	390,87	9,13	83,36
4	390	397,07	-7,07	49,98
5	385	418,77	-33,77	1 140,41
6	410	440,47	-30,47	928,42
7	480	483,87	-3,87	14,98
8	600	552,07	47,93	2 297,28
9	570	576,87	-6,87	47,20
10	620	626,47	-6,47	41,86
			Somme	5 674,15
			L2 (÷2)	2 837,08

Les autres candidats donnent des sommes nettement plus élevées : 136 218 pour w[1] = 0,4, 42 712 pour 0,5, 20 092 pour 0,7, 90 978 pour 0,8. L'intuition visuelle était donc correcte — 0,62 minimise l'erreur.

La surface d'erreur

À chaque combinaison de poids ⟨w[0], w[1]⟩ correspond une valeur de L2. En joignant toutes ces valeurs, on forme une surface d'erreur (error surface) au-dessus du plan des poids, appelé espace des poids (weight space). Le meilleur modèle correspond au point le plus bas de cette surface.

       L2 (somme des carrés des erreurs)
        ^
        |                            /
        |                           /        surface convexe
        |                          /         (en forme de bol)
        |                         /
        |       _               _/
        |         _           _/
        |           __     __/
        |              ___/  <-- minimum global
        +----------------*--------------------> espace des poids
                     poids optimaux (w[0], w[1])

Pour des problèmes simples, on pourrait essayer toutes les combinaisons par force brute — mais c'est impraticable pour les problèmes réels. Heureusement, les surfaces d'erreur associées à la régression linéaire ont deux propriétés salvatrices : elles sont convexes (en forme de bol) et possèdent un minimum global unique. Ces propriétés tiennent à la linéarité du modèle, non aux données. Le minimum global se situe là où les dérivées partielles de la surface par rapport à w[0] et w[1] sont nulles — c'est le fond du bol, là où il n'y a plus de pente. Cette approche s'appelle l'optimisation des moindres carrés (least squares optimization).

L'approche standard : régression multivariée et descente de gradient

La régression linéaire multivariée

Les vrais problèmes sont multivariés (multivariable). Étendre le modèle est immédiat :

Mw(d) = w[0] + w[1] × d[1] + w[2] × d[2] + ... + w[m] × d[m]

En inventant une feature factice d[0] toujours égale à 1, on peut écrire de façon compacte Mw(d) = w · d, le produit scalaire (dot product) des vecteurs w et d — soit la somme des produits de leurs éléments correspondants. La fonction L2 s'adapte mécaniquement. Avec les features continues du jeu Dublin (surface, étage, débit), le modèle entraîné devient :

RENTAL PRICE = -0,1513 + 0,6270 × SIZE - 0,1781 × FLOOR + 0,0714 × BROADBAND

Un bureau de 690 pieds carrés au 11ᵉ étage avec 50 Mb/s se prédirait à environ 434 euros. Reste à savoir comment trouver ces poids.

La descente de gradient

Imaginez une randonneuse coincée à flanc de vallée dans un brouillard si dense qu'elle ne voit le sol que dans un rayon d'un mètre. Tout semble perdu — pourtant une stratégie fiable existe. Elle observe la pente sous ses pieds : dans certaines directions le sol monte, dans d'autres il descend. Si elle fait un petit pas dans la direction de plus forte descente (la direction du gradient), elle se rapproche du fond. En répétant ce geste, elle finit par atteindre le creux de la vallée. La descente de gradient fonctionne exactement ainsi.

L'algorithme part d'un point aléatoire de l'espace des poids et calcule la somme des carrés des erreurs en ce point. Il ne connaît rien d'autre de la surface — comme la randonneuse, il ne dispose que d'information locale. Mais en calculant la dérivée de la fonction d'erreur en ce point, il obtient la pente de la surface et donc la direction à suivre. Il ajuste alors légèrement les poids dans la direction qui descend, atteint un nouveau point plus proche du minimum, et recommence jusqu'à convergence.

Algorithme 7.1 — Descente de gradient pour la régression multivariée

Entrées : un jeu d'entraînement D
          un taux d'apprentissage alpha (vitesse de convergence)
          une fonction errorDelta (direction d'ajustement de chaque w[j])
          un critère de convergence

1: w <- point de départ aléatoire dans l'espace des poids
2: repeter
3:   pour chaque w[j] dans w faire
4:     w[j] <- w[j] + alpha × errorDelta(D, w[j])
5: jusqu'a convergence

Le cœur de l'algorithme est la ligne 4 : chaque poids reçoit un petit ajustement (un delta) qui doit faire descendre la surface. Ce delta provient du gradient de la surface d'erreur, c'est-à-dire de la dérivée partielle de L2 par rapport au poids considéré. En dérivant L2 (via la règle de dérivation en chaîne) et en sommant sur toutes les instances, on obtient la règle de mise à jour des poids (weight update rule) :

w[j] <- w[j] + alpha × Σ ( (ti - Mw(di)) × di[j] )
                       i = 1 à n

L'intuition est limpide. Si les prédictions sont en général trop hautes, w[j] doit diminuer quand di[j] est positif et augmenter quand il est négatif ; si elles sont trop basses, l'inverse. Comme un seul ajustement par poids est effectué à chaque itération, en sommant l'erreur de toutes les instances, on parle de descente de gradient par lots (batch gradient descent) — approche simple, précise et largement employée.

Choisir le taux d'apprentissage et les poids initiaux

Le taux d'apprentissage (learning rate) alpha détermine la taille du pas à chaque itération. Aucune théorie ne donne sa valeur optimale ; c'est affaire de règles empiriques et d'essais.

alpha trop petit       alpha bien choisi       alpha trop grand
                                              
  .                         .                    .       
   .                                            /|  /|  /|
    .                                          / | / | / |
     .                                        /  rebonds d'un
      .                                      /   bord à l'autre,
       . (1000 pas...)              *         risque de divergence
        *                    convergence
   converge mais            rapide ET sûre
   très lentement

Un taux trop petit converge sûrement mais très lentement (de minuscules pas). Un taux trop grand fait sauter d'un bord à l'autre de la surface : il peut manquer le minimum, rebondir indéfiniment autour, voire diverger (la somme des carrés augmente au lieu de baisser). Un taux bien choisi trouve l'équilibre. La plage typique est [0,00001, 10] ; les praticiens testent des valeurs élevées et observent la courbe d'apprentissage, abaissant la valeur jusqu'à obtenir une descente régulière.

Une approche plus systématique est la décroissance du taux (learning rate decay) : alpha démarre grand puis décroît selon alpha = alpha0 ÷ (1 + tau ÷ c), où tau est l'itération courante et c contrôle la vitesse de décroissance. On obtient une convergence rapide en début de parcours, sans le ballottement d'un grand taux fixe en fin de course ; cela peut même rattraper un taux initial trop grand qui aurait d'abord fait remonter l'erreur.

Extensions et variations

Interpréter le modèle et tester la significativité

Un atout majeur de la régression est l'interprétabilité des poids. Leur signe indique si une feature pousse la prédiction vers le haut ou le bas (le loyer monte avec la surface, baisse avec l'étage) ; leur magnitude dit de combien la cible change pour une unité de la feature. Mais comparer directement les magnitudes pour juger de l'importance est une erreur quand les features ont des échelles différentes (SIZE varie de 500 à 1000, FLOOR de 4 à 14). Pour évaluer correctement l'importance, on recourt à un test de significativité statistique — le test t — dont l'hypothèse nulle est que la feature n'a pas d'impact. On calcule une statistique t, on en déduit une p-value, et si celle-ci tombe sous le seuil (typiquement 0,05) on rejette l'hypothèse nulle. Sur le jeu Dublin, seule la feature SIZE s'avère statistiquement significative.

Gérer les features descriptives catégorielles

Multiplier une feature catégorielle comme ENERGY RATING par un poids numérique n'a aucun sens. La parade courante est de la transformer en plusieurs features continues binaires, une par niveau. ENERGY RATING (A, B, C) devient ENERGY RATING A, ENERGY RATING B, ENERGY RATING C : pour une instance de niveau A, la première vaut 1 et les autres 0. L'inconvénient est l'explosion du nombre de poids (sept poids pour quatre features). On peut en économiser un par feature catégorielle : avec seulement ENERGY RATING A et B, deux zéros impliquent implicitement le niveau C.

La régression logistique pour la classification

Pour prédire une cible catégorielle, considérons un jeu décrivant des générateurs de centrale par leur régime (RPM) et leur vibration (VIBRATION), avec un statut good ou faulty. Si les deux classes sont séparables par une droite, celle-ci est une frontière de décision (decision boundary) et les données sont dites linéairement séparables. La frontière s'écrit comme l'équation d'une droite, par exemple 830 - 0,667 × RPM - VIBRATION = 0. Comportement remarquable : toute instance au-dessus de la frontière donne une valeur négative, toute instance en dessous une valeur positive. On pourrait donc seuiller cette valeur à zéro pour classer.

Deux problèmes pourtant. Ce seuil dur est discontinu, donc non dérivable : impossible d'appliquer la descente de gradient. Et il produit toujours des prédictions catégoriques (0 ou 1), sans nuance entre une instance frôlant la frontière et une instance lointaine. La solution est un seuil continu et dérivable : la fonction logistique (logistic function), aussi appelée sigmoïde.

logistic(x) = 1 / (1 + e^(-x))

  1.0 |                          ___________
      |                     ____/
      |                  __/
  0.5 |- - - - - - - - -*
      |             __/
      |        ____/
  0.0 |_______/____________________________
     -10      0                          +10   x

La fonction pousse en douceur les valeurs au-dessus de zéro vers 1 et celles en dessous vers 0. Pour bâtir une régression logistique (logistic regression), on passe simplement le produit scalaire dans la sigmoïde : Mw(d) = logistic(w · d) = 1 ÷ (1 + e^(-(w · d))). La surface de décision présente alors une transition graduelle d'une classe à l'autre, et — bénéfice supplémentaire — la sortie s'interprète comme une probabilité : P(t = faulty | d) = Mw(d) et P(t = good | d) = 1 - Mw(d).

L'entraînement réutilise la descente de gradient à l'identique : seul l'errorDelta change. En dérivant L2 avec la sigmoïde (dont la dérivée vaut logistic(x) × (1 - logistic(x))), la règle de mise à jour devient :

w[j] <- w[j] + alpha × Σ ( (ti - Mw(di)) × Mw(di) × (1 - Mw(di)) × di[j] )
                       i = 1 à n

Modéliser des relations non linéaires

Que faire quand la relation n'est pas linéaire ? Un jeu agricole reliant la pluie (RAIN) à la croissance de l'herbe (GROWTH) montre que l'herbe pousse mal en cas de sécheresse comme d'excès d'eau, avec un optimum vers 2,5 mm/jour — une relation en cloche qu'aucune droite ne saurait capturer. La solution élégante est d'introduire des fonctions de base (basis functions) qui transforment les entrées brutes en représentations non linéaires, tout en gardant le modèle linéaire par rapport aux poids :

Mw(d) = w[0] × phi0(d) + w[1] × phi1(d) + ... + w[b] × phib(d)

où phi0 à phib sont des transformations diverses de l'entrée. Pour capturer une relation polynomiale du second ordre (quadratique, de forme a = bx + cx²), on prend par exemple phi0(RAIN) = 1, phi1(RAIN) = RAIN, phi2(RAIN) = RAIN². Le modèle entraîné GROWTH = 3,707 × phi0 + 8,475 × phi1 - 1,717 × phi2 épouse parfaitement la courbe — et reste entraînable par descente de gradient sans aucune modification de l'algorithme. Les fonctions de base s'appliquent aussi à la régression logistique : avec des termes cubiques et un terme d'interaction (phi = P20 × P45), on apprend des frontières de décision non linéaires séparant des classes qui ne le sont pas dans l'espace d'origine.

La régression logistique multinomiale

Pour une cible à plus de deux niveaux, on construit r modèles un-contre-tous (one-versus-all), chacun distinguant un niveau de tous les autres. Les sorties sont normalisées pour sommer à 1, et les r modèles sont entraînés en parallèle (leurs frontières sont donc interdépendantes). Pour une requête, on prédit le niveau du modèle dont la sortie normalisée est la plus élevée. C'est un cas d'ensemble qui multiplie les poids — un jeu par niveau —, raison pour laquelle d'autres approches lui sont souvent préférées au-delà de quelques niveaux.

Les machines à vecteurs de support

Les machines à vecteurs de support (support vector machines, SVM) abordent la classification sous un angle différent. Reprenons le jeu des générateurs : plusieurs frontières peuvent séparer les classes, mais elles ne se valent pas. La distance perpendiculaire de la frontière à l'instance la plus proche s'appelle la marge (margin). L'intuition des SVM : la frontière qui maximise la marge sépare les classes le plus fiablement.

       VIBRATION
        ^
        |  x   x          .  marge        marge maximale =
        |    x   x       . extents .       meilleure séparation
        |   x    x  +---/---------/------+
        |      x   x   / frontière de    |   x = good
        |  - - - - - -/- décision - - - -|   t (triangle) = faulty
        |            /         . t   t   |
        |           /  . t   t      t    |   o = vecteurs de support
        |      o---/---------------------+   (sur les bords de marge)
        |    t   t      t    t
        +----------------------------------> RPM

Les instances qui tombent sur les bords de la marge (margin extents) sont les vecteurs de support (support vectors) : ce sont les instances les plus importantes, car ce sont elles qui définissent la frontière. Il y en a toujours au moins une par classe. On fixe le niveau négatif à -1 et le positif à +1, et l'on entraîne le modèle pour que les instances négatives donnent une sortie ≤ -1 et les positives ≥ +1 ; l'espace entre -1 et +1 ménage la marge. Le modèle SVM s'écrit :

Mw(q) = (Σ ti × alpha[i] × (di · q)) + w0
        i = 1 à s

où q est la requête, (d1, t1), ..., (ds, ts) sont les s vecteurs de support, w0 le biais, et alpha un paramètre par vecteur de support (formellement des multiplicateurs de Lagrange). Sortie > 1 → classe positive ; < -1 → classe négative. Trouver ces composantes est un problème d'optimisation quadratique sous contraintes, résolu par des méthodes standard. Les contraintes garantissent que chaque instance est du bon côté (ti × (w0 + w · d) ≥ 1), et le critère d'optimisation maximise la marge 2 ÷ ||w||, où ||w|| est la norme euclidienne de w.

Comme pour la régression logistique, des fonctions de base permettent de traiter des données non linéairement séparables en les projetant dans un espace de plus grande dimension où une séparation linéaire existe. Mais le produit scalaire de vecteurs très grands est coûteux. L'astuce du noyau (kernel trick) l'évite : une fonction noyau (kernel function) appliquée aux features d'origine donne le même résultat que le produit scalaire après projection, à moindre coût. Quelques noyaux usuels :

Noyau linéaire        kernel(d, q) = d · q + c
Noyau polynomial      kernel(d, q) = (d · q + 1)^p
Noyau gaussien (RBF)  kernel(d, q) = exp(-gamma × ||d - q||²)

On commence par un noyau linéaire ou polynomial de bas degré, et l'on ne complexifie qu'en cas de performances insuffisantes. Une extension à marge souple (soft margin) tolère le chevauchement des classes.

En perspective

L'un des plus grands atouts des modèles de régression est leur ancrage dans un vaste corpus de recherche statistique — discipline bien plus ancienne que l'apprentissage automatique. Cette maturité les rend aisément acceptés dans les sciences biologiques, physiques et sociales, et offre tout un outillage d'analyse (tests de significativité, intervalles de confiance) dont peu d'autres approches disposent. Le chapitre ne couvre pas les réseaux de neurones artificiels (artificial neural networks), autre approche par l'erreur — l'un de leurs types se construit d'ailleurs en connectant des couches de régressions logistiques. C'est précisément cette filiation qui fait de la descente de gradient le pivot conceptuel reliant ces fondations classiques à l'apprentissage profond moderne.

À retenir

• L'apprentissage par l'erreur postule un modèle paramétré (une combinaison linéaire pondérée des features) et réduit l'apprentissage à trouver les poids qui minimisent une fonction d'erreur, le plus souvent la somme des carrés des erreurs (L2).
• Chaque combinaison de poids définit un point d'une surface d'erreur convexe à minimum global unique ; la descente de gradient part d'un point aléatoire et descend cette surface pas à pas, en suivant le gradient calculé par dérivation.
• Le taux d'apprentissage est décisif : trop petit, la convergence traîne ; trop grand, l'algorithme rebondit ou diverge. La normalisation des features et la décroissance du taux stabilisent et accélèrent l'entraînement.
• La régression logistique prédit des cibles catégorielles en seuillant la sortie linéaire par la fonction logistique (sigmoïde) continue et dérivable, dont la sortie s'interprète comme une probabilité ; seul l'errorDelta change dans l'algorithme.
• Les fonctions de base capturent des relations non linéaires tout en gardant le modèle linéaire en ses poids — donc entraînable par descente de gradient — au prix d'une conception manuelle et d'un espace de poids élargi.
• Les SVM cherchent la frontière de marge maximale, définie par les vecteurs de support ; l'astuce du noyau traite efficacement les données non linéairement séparables. Robustes au surapprentissage mais peu interprétables.
• Les poids d'une régression linéaire sont interprétables (signe et magnitude), mais leur importance relative se juge par un test t, pas par comparaison directe des magnitudes quand les échelles diffèrent.