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} \tag{18.1} directement par minimisation du risque empirique, et donc de trouver le modèle linéaire qui « colle » le plus possible aux données. Cependant, lorsque la dimension d des données est trop grande par rapport au nombre m d’exemples, cela peut conduire au surapprentissage.
Pour éviter cela, la régularisation consiste à ajouter un terme pénalisant la complexité du modèle dans la minimisation. La régression ridge propose de mesurer cette complexité par la norme euclidienne du vecteur des paramètres.
La méthode LASSO propose quant-à elle de mesurer cette complexité par la norme \ell_1 des paramètres, c’est-à-dire la somme des valeurs absolues des paramètres w_k. Cela conduit à formuler l’apprentissage ainsi : \hat{\boldsymbol{w}} = \arg\min_{\boldsymbol{w}\in\mathbb{R}^d} \sum_{i=1}^m (y_i-\boldsymbol{w}^T\boldsymbol{x}_i)^2 + \lambda \|\boldsymbol{w}\|_1 où l’hyperparamètre \lambda>0 règle le compromis entre l’attache aux données et la régularisation.
Contrairement aux moindres carrés classiques et la régression ridge, ce problème d’optimisation ne possède une solution explicite que dans certains cas particuliers. Dans le cas général, le problème se reformule comme un problème de programmation quadratique :
\begin{align*}
\hat{\boldsymbol{w}} = \arg\min_{\boldsymbol{w}\in\mathbb{R}^d, a_k\geq 0} &\ \sum_{i=1}^m (y_i-\boldsymbol{w}^T\boldsymbol{x}_i)^2 + \lambda \sum_{k=1}^d t_k \\
s.c.\ &\ -t_k \leq w_k \leq t_k,\quad k=1,\dots, d
\end{align*} où les variables auxiliaires t_k représentent les valeurs absolues des w_k au travers de contraintes linéaires.
La régularisation par la norme \ell_1 du LASSO conduit en général à des modèles plus parcimonieux, c’est-à-dire avec beaucoup de paramètres nuls. Cette parcimonie peut se mesurer par la pseudo-norme \ell_0 : \|\boldsymbol{w}\|_0 = \left|\{ k : w_k\neq 0\}\right| avec typiquement \|\boldsymbol{w}\|_0 < d/3 pour un modèle parcimonieux.
L’intérêt d’un modèle parcimonieux est multiple :
Pour comprendre pourquoi minimiser la somme des valeurs absolues conduit plus souvent à des solutions parcimonieuses comparativement à la minimisation d’une norme euclidienne (comme en régression ridge), nous prendrons un exemple plus simple à étudier.
Soit un problème de résolution d’équation linéaire sous-déterminée : \boldsymbol{a}^T \boldsymbol{w} = b avec \boldsymbol{a}, \boldsymbol{w}\in\mathbb{R}^2. Ici, nous avons deux variables w_1 et w_2 (les composantes de \boldsymbol{w}) et une seule équation. Il existe donc une infinité de solutions. Pour retrouver l’unicité, nous allons régulariser en cherchant la solution de norme minimale.
Pour la norme euclidienne, cela donne \min_{\boldsymbol{w}\in\mathbb{R}^2} \|\boldsymbol{w}\|,\quad s.c.\ \boldsymbol{a}^T \boldsymbol{w} = b Dans l’espace des variables, la contrainte linéaire correspondant à une droite sur laquelle toutes les solutions se trouvent. Dans cet espace, nous pouvons dessiner les courbes de niveau de \|\boldsymbol{w}\|, c’est-à-dire les lieux des points où cette norme est constante. Les solutions du problème de minimisation se trouvent donc à l’intersection de ces courbes avec la droite, pour la courbe correspondant à la plus petite norme. Les courbes de niveau d’une norme euclidienne sont des cercles où le rayon égale \|\boldsymbol{w}\|, et le cercle de plus petit rayon qui intersecte la droite donne la solution. Celui-ci est le cercle tangent à la droite.
a = np.array([1, 1])
b = 1
x = np.array([-2,2])
plt.plot(x, (-a[0]*x + b) / a[1] )
t = np.linspace( 0 , 2 * np.pi , 150 )
plt.plot(1.5*np.cos(t), 1.5*np.sin(t), "--")
plt.plot(np.cos(t), np.sin(t), "--")
plt.plot(np.sqrt(0.5)*np.cos(t), np.sqrt(0.5)*np.sin(t), "-")
plt.plot(0.5,0.5, "*r", markersize=10)
plt.grid()
plt.axis([-2.2, 2.2, -2.2, 2.2])
Sur cette illustration, il est clair que la solution n’est pas parcimonieuse : w_1\neq 0 et w_2\neq 0. De plus, la plupart des droites possibles (pour d’autres valeurs de \boldsymbol{a} et b) donnent le même type de solutions. Seules les 4 droites parallèles aux axes donneraient des solutions avec un composante à 0.
Considérons maintenant la minimisation de la norme \ell_1 : \min_{\boldsymbol{w}\in\mathbb{R}^2} \|\boldsymbol{w}\|_1,\quad s.c.\ \boldsymbol{a}^T \boldsymbol{w} = b Ce problème peut être illustré de la même manière mais avec des « boules \ell_1 » pour les courbes de niveau, c’est-à-dire des carré dont les pointes se situent sur les axes.
a = np.array([2, 1])
b = 1
x = np.array([-2,2])
plt.plot(x, (-a[0]*x + b) / a[1] )
plt.plot([-1.5, 0, 1.5, 0, -1.5], [0 , 1.5, 0 , -1.5, 0], "--")
plt.plot([-1, 0, 1, 0, -1], [0 , 1, 0 , -1, 0], "--")
plt.plot([-0.5, 0, 0.5, 0, -0.5], [0 , 0.5, 0 , -0.5, 0], "--")
plt.plot(0.5,0, "*r", markersize=10)
plt.grid()
plt.axis([-2.2, 2.2, -2.2, 2.2])
Ici, la solution au point tangent est bien parcimonieuse : w_2=0. De plus, la plupart des autres droites auraient donné le même type de solution, sauf pour les cas très particuliers de droites à 45 degrés parallèles à une face du carré.