De la méthode des moindres carrés à la descente de gradient

Hors piste Le 14 août 2018  - Ecrit par  Aurélien Alvarez Voir les commentaires (2)

Dans l’article Galileo aurait adoré la carte Arduino, nous avons construit un dispositif expérimental relativement simple nous permettant de mesurer la hauteur de chute, le temps de chute libre et la vitesse en fin de chute pour une bille lâchée sans vitesse initiale. L’expérience étant très simple à mettre en œuvre, en faisant varier la hauteur de chute, il est facile d’acquérir rapidement un grand nombre de mesures. Nous avons ensuite vu dans l’article Si Galilée avait été un data scientist... comment inférer des modèles mathématiques des lois de la chute libre uniquement à partir de telles données mesurées. Pour cela, nous avons utilisé des modèles de régression linéaire que nous avons estimés par la méthode des moindres carrés.
Nous proposons d’expliquer dans cet article, qui peut être lu indépendamment des deux susmentionnés, les mathématiques que nous avons utilisées.

Problème

On dispose d’un ensemble de données $X = \{(x_i, y_i)\}_{1 \leq i \leq N}$ de couples de nombres réels.
Par exemple il peut s’agir de mesures provenant de $N$ réalisations d’une expérience.
On cherche la « meilleure » droite qui représente ces données, c’est-à-dire une fonction affine
\[h_w(x) = w_1 x + w_0\]
telle que, pour tout $i$, $h_w(x_i)$ soit « aussi proche que possible » de $y_i$.

Les inconnues du problème sont $w_0$ et $w_1$ (géométriquement ce sont la pente de la droite et son ordonnée à l’origine) et il s’agit donc de trouver une façon d’estimer ces poids.

Plusieurs approches pour estimer les poids $w_0$ et $w_1$ sont possibles (maximum de vraisemblance, inférence bayésienne...) et, parmi elles, la méthode des moindres carrés est à la fois relativement simple et le « meilleur » estimateur, sous certaines hypothèses souvent vérifiées par les données en pratique.

PNG - 26.3 ko

Estimation par la méthode des moindres carrés

PNG - 75.7 ko

L’idée principale est de chercher à minimiser une fonction $L(h_w)$ dite de « perte empirique » calculée à partir des données.
De nombreux choix sont possibles pour la fonction $L$ de $h_w$ qui est donc une fonction des deux variables $w_0$ et $w_1$.
Pour de bonnes raisons dont nous dirons quelques mots ci-dessous, Gauss nous suggère de considérer une somme quadratique, c’est-à-dire une fonction $L$ de la forme
\[L(h_w) = \sum_{i=1}^N (y_i - h_w(x_i))^2 = \sum_{i=1}^N (y_i - (w_1 x_i + w_0))^2.\]

Ainsi, pour chaque couple de données, on calcule le carré de la différence entre la valeur prédite $h_w(x_i)$ et la valeur observée $y_i$, et on fait la somme sur tous les couples de données.
Le graphe de cette fonction est une surface comme celle ci-contre, une surface qui a la propriété d’avoir un unique minimum global $w^\star=(w_0^\star, w_1^\star)$.
Le calcul différentiel de Leibniz et Newton nous enseigne qu’un tel minimum est un point critique, c’est-à-dire un point où le gradient de la fonction s’annule, soit
\[\frac{\partial}{\partial w_0} L(h_w) = 0 \quad \text{et} \quad \frac{\partial}{\partial w_1} L(h_w) = 0,\]
ou encore
\[\sum_{i=1}^{N}(y_i-(w_1^\star x_i + w_0^\star))=0 \quad \text{et} \quad \sum_{i=1}^{N}x_i(y_i-(w_1^\star x_i + w_0^\star))=0.\]
Il ne reste plus qu’à résoudre ce système d’équations pour obtenir

\[w_1^\star = \frac{N\sum_{i=1}^N x_i y_i - (\sum_{i=1}^N x_i) \cdot (\sum_{i=1}^N y_i)}{N\sum_{i=1}^N {x_i}^2 - (\sum_{i=1}^N x_i)^2} \quad \text{et} \quad w_0^\star = \frac{1}{N}\sum_{i=1}^N (y_i - w_1^\star x_i).\]

Nous avons donc résolu notre problème : nous avons trouvé les poids $w_0^\star$ et $w_1^\star$ « les meilleurs » dans le sens que la perte quadratique est ainsi la plus petite possible.
Le problème de trouver un modèle de régression linéaire estimé par la méthode des moindres carrés présente un petit miracle : il existe toujours une unique solution donnée par les formules ci-dessus car la convexité de la fonction perte empirique assure qu’il n’y pas de minima locaux autres que l’unique minimum global.

Exercice

Notons tout de même que la formule donnée pour $w_1^\star$ n’a pas grand sens lorsque son dénominateur est nul. Montrer que cela correspond au cas où tous les $x_i$ sont égaux, et que dans ce cas les données se retrouvent réparties sur une droite verticale.

On peut bien sûr généraliser et résoudre le problème précédent en dimension plus grande.
Chaque donnée est désormais un couple $(\mathbf{x}_i, y_i)$, où $\mathbf{x}_i$ désigne un $k$-uplet $\mathbf{x}_i=(x_i^1, \cdots, x_i^k)$ de nombres réels.
On cherche alors le « meilleur » hyperplan affine qui représente ces données, c’est-à-dire une fonction affine de la forme
\[h_{\mathbf{w}}(\mathbf{x}) = w_k x_k + \cdots + w_1 x_1 + w_0,\]
où les inconnues du problème sont les poids $w_0, \cdots, w_k$.
Là encore, il est possible d’expliciter sans ambiguïté une unique solution avec des formules d’algèbre linéaire généralisant le cas $k=1$.

Une justification théorique à la méthode des moindres carrés

Dans l’article Si Galilée avait été un data scientist..., le premier modèle mathématique que l’on cherche à décrire est une loi reliant la vitesse $v$ en fin de chute au temps de chute $t$ pour une bille en chute libre lâchée sans vitesse initiale.
En faisant varier la hauteur de chute, on enregistre autant de mesures de couples $(t,v)$ que l’on souhaite.
Chaque mesure est entachée d’erreurs du fait de notre dispositif expérimental relativement élémentaire.
Donnons deux exemples de sources d’erreurs dans les mesures, parmi bien d’autres :

  • l’usage de simples photorésistances rend le dispositif sensible aux variations de lumière dans la pièce ;
  • selon que la bille tombe parfaitement verticalement ou pas, les faisceaux lasers ne sont pas coupés exactement aux mêmes instants.

Cependant, en première approximation, ces erreurs sont assez indépendantes d’une mesure à l’autre : il n’y a pas de raison que si la bille a été mal positionnée sur l’électroaimant, l’expérimentateur ne la positionne pas bien la fois suivante [1] et, en moyenne, on peut raisonnablement penser que les erreurs se compensent.
De même, on n’a pas vraiment de raison de penser que les dispersions des mesures du couple $(t,v)$ pour des billes lâchées à une certaine hauteur soient significativement différentes des dispersions pour des mesures de billes lâchées à une hauteur différente.

Sous ces hypothèses, le théorème suivant nous assure que l’estimateur des moindres carrés est le meilleur possible.

Théorème de Gauss-Markov

Pour un modèle linéaire, si les erreurs sont non corrélées et si elles ont une espérance nulle en même temps que des variances égales, alors l’estimateur des moindres carrés est le meilleur estimateur linéaire non biaisé des coefficients.

La descente de gradient

Comme nous l’avons vu, pour tout problème de régression linéaire estimée par une méthode des moindres carrés, il est possible de donner une formule explicite pour les poids.
En dehors de ce cas particulier, il n’y a guère d’espoir de pouvoir résoudre aussi facilement en général un tel problème de minimisation d’une fonction de perte empirique.
Mais l’intuition géométrique suggère tout de même un angle d’attaque...

PNG - 422.2 ko

Le graphe d’une fonction de perte empirique dessine une hyper-surface au-dessus de l’espace des poids (les inconnus du problème) et ce graphe n’a pas de raison a priori d’être convexe.
En dimension 1, on obtient un graphe comme celui dessiné en logo de cet article et, en dimension quelconque, un graphe analogue avec des bosses et des creux.
À ce propos, on pourra lire l’article Des sommets, des creux, des cols et une théorie indomptable qui est une invitation aux liens entre topologie et allure qualitative des fonctions, et dont sont extraits le logo de cet article et l’image ci-dessus.
En général, une fonction présente de nombreux minima locaux et, à défaut de pouvoir trouver facilement un ou le minimum global, on aimerait au moins avoir une méthode suffisamment robuste pour nous assurer de trouver un minimum local.

Principe de la descente de gradient

C’est la méthode que l’on suivrait intuitivement si on se retrouvait soudainement pris dans du mauvais temps lors d’une sortie en ski.
Pour descendre le plus rapidement possible, il est naturel de chercher à glisser dans la direction de pente descendante la plus forte et continuer ainsi jusqu’à atteindre une cuvette où l’on espère pouvoir se mettre à l’abri.

Concrètement, on choisit un point au hasard dans l’espace des poids et on suit l’opposé du gradient de la fonction perte empirique.
De proche en proche, on se déplace en faisant diminuer comme souhaité la valeur de la fonction jusqu’à atteindre un certain critère d’arrêt fixé à l’avance.

  • Choisir un point $\mathbf{w}$ au hasard dans l’espace des poids.
  • Jusqu’à atteindre un certain critère d’arrêt :
    \[\mathbf{w} \longleftarrow \mathbf{w} - \alpha \, \text{grad}_\mathbf{w} \, L(h_w),\]
    où $\alpha$ est le taux d’apprentissage, un paramètre qui peut être choisi constant ou décroître au fil de l’apprentissage.

Reprenons l’exemple que nous avons développé dans le cas de la méthode des moindres carrés.
On obtient dans ce cas
\[w_0 \longleftarrow w_0 + 2\alpha \sum_{i=1}^N (y_i-h_{\mathbf{w}}(x_i)) \quad \text{et} \quad w_1 \longleftarrow w_1 + 2\alpha \sum_{i=1}^N x_i (y_i-h_{\mathbf{w}}(x_i)).\]
À condition de choisir $\alpha$ suffisamment petit mais au prix de devoir itérer un nombre grandissant de fois la procédure, un théorème assure la convergence de cet algorithme vers l’unique minimum global.

Variante de la méthode : la descente de gradient stochastique

Afin de réduire le nombre de calculs, particulièrement dans le cas où $N$ est grand, une variante de cette méthode est la descente de gradient stochastique.
À chaque itération, plutôt que de considérer la somme sur tous les couples dans l’ensemble de données, on se contente d’un seul couple, ce qui réduit considérablement les calculs, et on change de couple de données à chaque itération.
Cette approche est particulièrement précieuse dans un contexte où les données arrivent en temps réel puisque la descente de gradient peut elle aussi être calculée en temps réel.

Par contre, avec un taux d’apprentissage $\alpha$ fixé, rien ne garantit la convergence de l’algorithme qui peut osciller autour du minimum indéfiniment comme l’illustrent les images ci-dessous extraites du chapitre 5 du film Chaos à propos d’une bille dans une cuvette.

Dans certains cas cependant, avec un taux d’apprentissage $\alpha$ décroissant progressivement, des théorèmes assurent à nouveau la convergence de l’algorithme.

En guise de conclusion

Ainsi s’achève, à la suite des articles Galileo aurait adoré la carte Arduino et Si Galilée avait été un data scientist..., cette introduction à quelques idées sous-jacentes à l’apprentissage statistique, un champ d’étude à l’interface entre mathématiques et informatique qui suscite un très vif engouement ces dernières années suite à des avancées spectaculaires comme celles du logiciel AlphaGo.
Pour celles et ceux qui voudraient en savoir plus, de très nombreuses ressources circulent sur le web.
Pour une introduction au sujet, on peut citer la récente conférence La théorie de l’apprentissage de Vapnik et les progrès récents de l’intelligence artificielle de Yann LeCun dans le cadre du cycle de conférences Un texte, un mathématicien.
Pour aller plus loin, on pourra suivre le récent cours L’apprentissage face à la malédiction de la grande dimension de Stéphane Mallat au Collège de France.

Post-scriptum :

La rédaction d’Images des mathématiques ainsi que l’auteur remercient Gabriel Sarrazin pour sa relecture attentive des deux derniers articles de la série sur Galilée et pour ses suggestions.

Article édité par Christian Mercat

Notes

[1En pratique, l’expérimentateur va à chaque fois mal positionner la bille, mais toujours différemment.

Partager cet article

Pour citer cet article :

Aurélien Alvarez — «De la méthode des moindres carrés à la descente de gradient» — Images des Mathématiques, CNRS, 2018

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • exercice

    le 16 août à 11:03, par nicolas

    Concernant l’exercice proposé : le dénominateur de w1* est nul lorsque la variance des xi est nulle, c’est-à-dire lorsque tous les xi sont égaux. Dans ce cas, les points sont tous alignés sur une droite verticale, et il n’est pas possible d’ajuster une relation y=ax+b.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM