16 Méthode des moindres carrés
En régression linéaire, la méthode des moindres carrés permet d’estimer les paramètres \boldsymbol{w}\in\mathbb{R}^d du modèle f(\boldsymbol{x}) = \boldsymbol{w}^T\boldsymbol{x} directement par minimisation du risque empirique1 : \hat{\boldsymbol{w} } = \arg\min_{\boldsymbol{w}\in\mathbb{R}^{d}} \sum_{i=1}^m (y_i - \boldsymbol{w}^T\boldsymbol{x}_i)^2 .
En effet, la solution de ce problème d’optimisation est donnée explicitement par \hat{\boldsymbol{w}} = (\boldsymbol{X}^T\boldsymbol{X})^{-1} \boldsymbol{X}^T \boldsymbol{y} où les m exemples d’apprentissages (\boldsymbol{x}_i, y_i) sont concaténés dans \boldsymbol{X}=\begin{bmatrix}\boldsymbol{x}_1^T\\\vdots\\\boldsymbol{x}_m^T\end{bmatrix}\in\mathbb{R}^{m\times d},\qquad \boldsymbol{y} = \begin{bmatrix}y_1\\\vdots\\y_m\end{bmatrix}\in\mathbb{R}^m .
16.1 Démonstration de la formule des moindres carrés
Nous pouvons commencer par formuler le critère à minimiser en fonction des matrices \boldsymbol{X}, \boldsymbol{y} : J(\boldsymbol{w}) = \sum_{i=1}^m (y_i - \boldsymbol{w}^T\boldsymbol{x}_i)^2 = \|\boldsymbol{y} - \boldsymbol{X}\boldsymbol{w}\|^2
Soit le vecteur des erreurs \boldsymbol{e}=\begin{bmatrix}e_1\\\vdots\\e_m\end{bmatrix} avec e_i = y_i - \boldsymbol{w}^T \boldsymbol{x}_i. Par la symétrie du produit scalaire, nous avons aussi e_i = y_i - \boldsymbol{x}_i^T\boldsymbol{w}, et donc \boldsymbol{e} = \begin{bmatrix}y_1\\\vdots\\y_m\end{bmatrix} - \begin{bmatrix}\boldsymbol{x}_1^T\boldsymbol{w}\\\vdots\\\boldsymbol{w}^T\boldsymbol{x}_m\end{bmatrix} = \boldsymbol{y} - \boldsymbol{X} \boldsymbol{w}. D’un autre côté, par définition de la norme euclidienne, J(\boldsymbol{w}) = \sum_{i=1}^m e_i^2 = \|\boldsymbol{e}\|^2. ce qui conclut la preuve.
La fonction J(\boldsymbol{w}) est quadratique et convexe, ce qui signifie que son minimum se situe au(x) point(s) où la dérivée (le gradient si d>1) est nulle. Il suffit donc de résoudre \frac{\text{d} J(\hat{\boldsymbol{w}})}{\text{d} \boldsymbol{w}} = \boldsymbol{0} où, d’après le règle de dérivation en chaîne, avec \boldsymbol{e} = \boldsymbol{y}-\boldsymbol{X}\boldsymbol{w}, \frac{\text{d} J(\boldsymbol{w})}{\text{d} \boldsymbol{w}} = \left(\frac{\text{d} \boldsymbol{e}}{\text{d} \boldsymbol{w}}\right)^T \frac{\text{d} J(\boldsymbol{w})}{\text{d} \boldsymbol{e}} La règle de dérivation des fonctions linéaires donne \frac{\text{d} \boldsymbol{e}}{\text{d} \boldsymbol{w}} = -\boldsymbol{X} et la règle de dérivation des fonctions quadratiques \frac{\text{d} J(\boldsymbol{w})}{\text{d} \boldsymbol{e}} = 2 \boldsymbol{e} Cela conduit à \frac{\text{d} J(\boldsymbol{w})}{\text{d} \boldsymbol{w}} = -2 \boldsymbol{X}^T (\boldsymbol{y} - \boldsymbol{X} \boldsymbol{w}) et donc une dérivée nulle lorsque \boldsymbol{X}^T \boldsymbol{X} \hat{\boldsymbol{w}} = \boldsymbol{X}^T \boldsymbol{y}. Dans le cas où \boldsymbol{X}^T \boldsymbol{X} est inversible, la formule souhaitée est obtenue par multiplication à gauche par son inverse. Dans le cas contraire, la solution s’obtient par résolution du système d’équations linéaires ci-dessus par d’autres techniques (comme la factorisation QR, ou la pseudo-inverse par exemple). Mais en pratique, il est toujours préférable et plus efficace de résoudre le système linéaire ci-dessus plutôt que de calculer explicitement l’inverse de la matrice.
Minimiser la somme des erreurs est équivalent à minimiser la moyenne↩︎