Descente de gradient pour les moindres carrés

La régression linéaire est une méthode statistique utilisée pour modéliser la relation entre une variable dépendante et une ou plusieurs variables indépendantes en ajustant une équation linéaire aux données observées. La forme la plus simple de l'équation linéaire avec une variable dépendante et une variable indépendante est représentée par $y = mx + b$, où $m$ est la pente de la droite et $b$ est l'ordonnée à l'origine. Cette méthode est largement utilisée en modélisation prédictive et en prévision quantitative.

Descente de gradient pour la régression linéaire

La descente de gradient est un algorithme d'optimisation utilisé pour minimiser une fonction en se déplaçant de manière itérative dans la direction de la plus grande pente, définie par l'opposé du gradient. Dans le contexte de la régression linéaire, la descente de gradient est utilisée pour trouver les valeurs de $m$ et $b$ qui minimisent la fonction de coût, qui est généralement la somme des différences au carré entre les valeurs observées et les valeurs prédites par le modèle.

Fonction de coût

La fonction de coût de régression linéaire, ici l’erreur quadratique moyenne, quantifie la différence entre les valeurs observées et les valeurs prédites par le modèle linéaire. Elle est donnée par :

$$E(m, b) = \frac{1}{n} \sum_{i=1}^{n} (y_i - (mx_i + b))^2$$

où :

• $n$ est le nombre d'observations,
• $y_i$ est la valeur observée,
• $x_i$ est la variable indépendante,
• $m$ est la pente, et
• $b$ est l'ordonnée à l'origine.

Algorithme de descente de gradient

L'algorithme de descente de gradient met à jour les paramètres $m$ et $b$ de manière itérative pour minimiser la fonction de coût $E(m, b)$. Les règles de mise à jour de $m$ et $b$ à chaque itération sont :

$$m_{k+1} = m_k - \alpha \frac{\partial E}{\partial m}$$ $$b_{k+1} = b_k - \alpha \frac{\partial E}{\partial b}$$

où $\alpha$ est le taux d'apprentissage, un hyperparamètre qui contrôle la taille des pas effectués vers le minimum de la fonction de coût.

Dérivées partielles de la fonction de coût

Les dérivées partielles de $E(m, b)$ par rapport à $m$ et $b$ sont :

$$\frac{\partial E}{\partial m} = -\frac{2}{n} \sum_{i=1}^{n} x_i(y_i - (mx_i + b))$$ $$\frac{\partial E}{\partial b} = -\frac{2}{n} \sum_{i=1}^{n} (y_i - (mx_i + b))$$

Ces gradients sont utilisés pour mettre à jour les valeurs de $m$ et $b$ de manière itérative dans la direction qui fait décroître la fonction de coût.

Étapes de mise en œuvre

1. Initialisation : commencer par des estimations initiales pour les valeurs de $m$ et $b$.
2. Calcul du gradient : calculer les gradients de la fonction de coût par rapport à $m$ et $b$.
3. Mise à jour des paramètres : mettre à jour les valeurs de $m$ et $b$ à l'aide des règles de mise à jour de la descente de gradient.
4. Itération : répéter les étapes 2 et 3 jusqu’à atteindre la tolérance sur le gradient ou épuiser le budget d’itérations, en indiquant le motif d’arrêt.

Solution exacte et mise à jour reproductible

Cette note traite du calcul d’optimisation ; les hypothèses et l’interprétation du modèle relèvent de Régression linéaire. Avec $r_i=mx_i+b-y_i$, la règle de la chaîne donne $\partial r_i^2/\partial m=2r_ix_i$ et $\partial r_i^2/\partial b=2r_i$, ce qui explique les signes et le facteur $2$. À cause de $1/n$, $E$ est une erreur quadratique moyenne, pas une somme de carrés. Redimensionner la perte conserve son minimiseur mais modifie le gradient et le taux d’apprentissage approprié.

Prenons trois observations $(1,2),(2,5),(3,3)$. Leur somme des carrés des résidus est exactement la quadratique de la note sur le gradient :

$$S=3E=14m^2+12mb+3b^2-42m-20b+38.$$

Ici $\sum x_i=6$, $\sum y_i=10$, $\sum x_i^2=14$ et $\sum x_iy_i=21$. Résoudre $28m+12b-42=0$ et $12m+6b-20=0$ donne $m=1/2$, $b=7/3$. Les résidus $y_i-(mx_i+b)$ valent $-5/6,5/3,-5/6$, d’où $S=25/6$ et $E=25/18$.

En $(m,b)=(0,0)$, $\nabla E=(-14,-20/3)$. Une mise à jour simultanée avec $\alpha=0.05$ donne $(7/10,1/3)$ et diminue $E$ de $38/3$ à $1789/450\approx3.975556$. À chaque itération, calculer les deux sommes du gradient avant de modifier un paramètre.

Regroupons les paramètres dans $\theta=(m,b)^T$ et les observations dans $y=(y_1,\ldots,y_n)^T$. La ligne $i$ de la matrice de conception $X$ est $(x_i,1)$ : la composante $i$ de $X\theta$ est donc la prédiction $mx_i+b$. Ainsi, $E=\|X\theta-y\|_2^2/n$, où le carré de la norme euclidienne additionne les carrés des résidus, et la matrice hessienne vaut $H=2X^TX/n$. Pour tout $v$, $v^THv=2\|Xv\|_2^2/n\ge0$, ce qui prouve la convexité. La solution n’est unique que si les colonnes de $X$ sont linéairement indépendantes, autrement dit si son rang égale le nombre de colonnes ; pour pente et intercept, il faut au moins deux $x_i$ distincts. Si tous les $x_i=c$, seul $mc+b$ est identifiable et plusieurs couples de paramètres s’ajustent aussi bien.

La borne du pas découle de la dynamique de l’erreur. Ici $H$ est symétrique définie positive et $\theta_*$ est l’unique minimiseur. Pour $e_k=\theta_k-\theta_*$, le gradient quadratique vaut $He_k$, donc

$$e_{k+1}=(I-\alpha H)e_k.$$

Selon un vecteur propre de $H$ associé à $\lambda>0$, l’erreur est multipliée par $1-\alpha\lambda$. Converger depuis tout point initial exige $|1-\alpha\lambda|<1$ pour chaque valeur propre, soit $0<\alpha<2/\lambda_{\max}(H)$. À la borne supérieure, la composante associée à la plus grande valeur propre oscille sans diminuer. La convexité caractérise les minima globaux ; elle ne garantit pas la convergence pour n’importe quel pas.

Pour ces données, $\lambda_{\max}(H)=(17+\sqrt{265})/3\approx11.092940$ ; la descente à pas fixe converge donc pour $0<\alpha<2/\lambda_{\max}\approx0.180295$. L’échelle des caractéristiques modifie cette borne. Utiliser une tolérance sur la norme du gradient et une limite d’itérations, puis comparer à la solution exacte ; une perte inchangée peut traduire une stagnation numérique. Pour de petits problèmes denses, les solveurs par QR ou SVD sont souvent préférables aux itérations manuelles ou à l’inversion explicite de $X^TX$.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.