Lasso (statistiques)

En statistiques, le lasso est une méthode de contraction des coefficients de la régression développée par Robert Tibshirani dans un article publié en 1996 intitulé Regression shrinkage and selection via the lasso[1].

Lasso

Nature	Analyse statistique (d)
Inventeur	Robert Tibshirani
Date d'invention	1996

Le nom est un acronyme anglais : Least Absolute Shrinkage and Selection Operator[1]^,[2].

Bien que cette méthode fut utilisée à l'origine pour des modèles utilisant l'estimateur usuel des moindres carrés, la pénalisation lasso s'étend facilement à de nombreux modèles statistiques tels que les modèles linéaires généralisés, les modèles à risque proportionnel, et les M-estimateurs. La capacité du lasso à sélectionner un sous-ensemble de variables est due à la nature de la contrainte exercée sur les coefficients et peut s'interpréter de manière géométrique, en statistique bayésienne ou analyse convexe.

Présentation formelle

Soit $x_{i}=(x_{i,1},\dots ,x_{i,p})^{T}$ , le vecteur contenant les variables explicatives associées à l'individu $i$ , $y_{i}$ la réponse associée et $\beta =(\beta _{1},\dots ,\beta _{p})^{T}$ les coefficients à estimer.

Modèle linéaire

Dans le cadre d'un modèle linéaire standard, les coefficients sont obtenus par minimisation de la somme des carrés des résidus.

Avec la méthode lasso, le vecteur de coefficients ${\widehat {\beta }}_{\lambda }^{L}$ est également obtenu en minimisant la somme des carrés des résidus mais sous une contrainte supplémentaire :

${\begin{aligned}\min _{\beta _{0},\beta _{1},\dots ,\beta _{p}}{\frac {1}{2}}\sum _{i=1}^{n}\left(y_{i}-\beta _{0}-\sum _{j=1}^{p}\beta _{j}x_{i,j}\right)^{2}{\text{ sous la contrainte }}\sum _{j=1}^{p}|\beta _{j}|\leq t.\end{aligned}}$

Le paramètre $t$ contrôle le niveau de régularisation des coefficients estimés.

Il s'agit d'une pénalisation de la norme $\ell _{1}$ des coefficients $\beta _{j},j=1,\dots ,p$ . Cette contrainte va contracter la valeur des coefficients (tout comme la régression ridge) mais la forme de la pénalité $\ell _{1}$ va permettre à certains coefficients de valoir exactement zéro (à l'inverse de la régression ridge).

En bleu, zones de contraintes de la pénalité lasso (à gauche) et de la pénalité ridge (à droite). En rouge, les contours de la fonction d'erreur des moindres carrés.

De plus, dans des cas où le nombre de variables est supérieur au nombre d'individus $n<p$ , le lasso en sélectionnera au plus $n$ [3].

On peut écrire aussi la version lagrangienne de ce problème :

$\min _{\beta _{0},\beta _{1},\dots ,\beta _{p}}{\frac {1}{2}}\sum _{i=1}^{n}\left(y_{i}-\beta _{0}-\sum _{j=1}^{p}\beta _{j}x_{i,j}\right)^{2}+\lambda \sum _{j=1}^{p}|\beta _{j}|$

avec $\lambda \geq 0$ le paramètre de régularisation. Ce paramètre $\lambda$ est relié au paramètre $t$ par une relation dépendante des données.

Écriture vectorielle

Soit $X$ la matrice contenant en ligne les individus, $X_{i,.}=(x_{i,1},\dots ,x_{i,p})$ . Le lasso s'écrit généralement sous forme vectorielle, en considérant les variables centrées afin d'enlever la constante $\beta _{0}$ du problème :

En rouge, la fonction de seuillage doux,

S(x;\lambda )

. En pointillés, la droite d'équation

y=x

.

${\begin{aligned}\min _{\beta \in \mathbb {R} ^{p}}{\frac {1}{2}}\|y-X\beta \|_{2}^{2}{\text{ sous la contrainte }}\|\beta \|_{1}\leq t\end{aligned}}$

avec $\|a\|_{q}=(\sum \limits _{i=1}^{n}|a_{i}|^{q})^{1/q}$ la norme $\ell _{q}.$

La version vectorielle pour le lagrangien, quant à elle, s'écrit :

$\min _{\beta \in \mathbb {R} ^{p}}{\frac {1}{2}}\|y-X\beta \|_{2}^{2}+\lambda \|\beta \|_{1}.$

Cas orthonormal

Dans le cas où la matrice $X$ est telle que $X^{T}X=I_{p}$ , le lasso a une solution explicite. L'estimateur lasso correspond alors à un seuillage doux de la solution des moindres carrées. Notons ${\hat {\beta }}^{LS}$ la solution des moindres carrées. La solution du lasso pour $j=1,\dots ,p$ est :

${\hat {\beta }}_{j}^{L}=\operatorname {sgn}({\hat {\beta }}_{j}^{LS})\cdot \max(0,|{\hat {\beta }}_{j}^{LS}|-\lambda )$

Démonstration

Soit ${\hat {\beta }}^{LS}$ la solution des moindres carrés. Comme $X^{T}X=I$ , on a :

${\hat {\beta }}^{LS}=(X^{T}X)^{-1}X^{T}y=X^{T}y$ .

La version lagrangienne du lasso est :

$\min _{\beta \in \mathbb {R} ^{p}}{\frac {1}{2}}\|y-X\beta \|_{2}^{2}+\lambda \|\beta \|_{1}$

En développant le premier terme du problème, on obtient ${\frac {1}{2}}y^{T}y-y^{T}X\beta +{\frac {1}{2}}\beta ^{T}X^{T}X\beta$ . Comme $y^{T}y$ est constant et $X^{T}X=I$ , le problème devient :

$\min _{\beta \in \mathbb {R} ^{p}}-y^{T}X\beta +{\frac {1}{2}}\|\beta \|_{2}^{2}+\lambda \|\beta \|_{1}$

En remarquant que $y^{T}X=({\hat {\beta }}^{LS})^{T}$ , on peut réécrire :

$\min _{\beta \in \mathbb {R} ^{p}}\sum \limits _{j=1}^{p}-{\hat {\beta }}_{j}^{LS}\beta _{j}+{\frac {1}{2}}\beta _{j}^{2}+\lambda |\beta _{j}|$

Notre fonction objectif s'écrit ainsi comme une somme de fonctions objectifs chacune associée à un $\beta _{j}$ différent. On peut donc optimiser le problème pour chaque $j$ . Ainsi, notre problème pour un $j$ donné est : $\min _{\beta _{j}\in \mathbb {R} }-{\hat {\beta }}_{j}^{LS}\beta _{j}+{\frac {1}{2}}\beta _{j}^{2}+\lambda |\beta _{j}|$ . Notons $f_{j}$ la fonction à minimiser.

Remarquons que si ${\hat {\beta }}_{j}^{LS}>0$ , alors $\beta _{j}\geq 0$ . De même si ${\hat {\beta }}_{j}^{LS}<0$ , alors $\beta _{j}\leq 0$ .

Comme la fonction valeur absolue n'est pas dérivable en $0$ , nous considérons plusieurs cas :

${\hat {\beta }}_{j}^{LS}>0$ , on a donc $\beta _{j}\geq 0$ et $f_{j}(\beta _{j})=-{\hat {\beta }}_{j}^{LS}\beta _{j}+{\frac {1}{2}}\beta _{j}^{2}+\lambda \beta _{j}$ .

En résolvant, $f_{j}^{'}(\beta _{j})=0$ , on obtient $\beta _{j}={\hat {\beta }}_{j}^{LS}-\lambda$ .

Comme on a forcément $\beta _{j}\geq 0$ , ce minimum est atteint seulement lorsque ${\hat {\beta }}_{j}^{LS}-\lambda \geq 0$ , si ce n'est pas le cas, le minimum est atteint pour $\beta _{j}=0$ . On a donc $\beta _{j}=\max(0,{\hat {\beta }}_{j}^{LS}-\lambda )$

${\hat {\beta }}_{j}^{LS}\leq 0$ , on a donc $\beta _{j}\leq 0$ .

En suivant le même raisonnement, on obtient $\beta _{j}=\max(0,-{\hat {\beta }}_{j}^{LS}-\lambda )$ .

Finalement, on a : $\beta _{j}=\left\{{\begin{array}{lll}\max(0,{\hat {\beta }}_{j}^{LS}-\lambda )&{\mbox{si}}&{\hat {\beta }}_{j}^{LS}>0\\-\max(0,-{\hat {\beta }}_{j}^{LS}-\lambda )&{\mbox{si}}&{\hat {\beta }}_{j}^{LS}\leq 0\end{array}}\right.$

que l'on peut simplifier sous la forme

$\beta _{j}=\operatorname {sgn}({\hat {\beta }}_{j}^{LS})\cdot \max(0,|{\hat {\beta }}_{j}^{LS}|-\lambda )$ .

Conditions de Karush-Kuhn-Tucker

Les conditions de Karush-Kuhn-Tucker sont des conditions qu'une solution d'un problème d'optimisation sous contraintes doit vérifier pour être optimale. Dans le cas de la version linéaire du lasso, les conditions du premier ordre sont pour $j=1,\dots ,p$ :

$X_{.,j}(y-X{\hat {\beta }}_{\lambda }^{L})=\lambda s_{j},$

$s_{j}\in \left\{{\begin{array}{lll}\operatorname {sgn}(({\hat {\beta }}_{\lambda }^{L})_{j})&{\mbox{si}}&({\hat {\beta }}_{\lambda }^{L})_{j}\not =0\\{[-1;1]}&{\mbox{si}}&({\hat {\beta }}_{\lambda }^{L})_{j}=0\end{array}}\right.$

avec $X_{.,j}$ la $j$ ^ieme colonne de la matrice $X$ et $s_{j}$ appartenant au sous-différentiel de la fonction $f(x)=|x|$ [3].

Cas général

Le lasso n'est pas uniquement restreint à la régression linéaire, il peut être également utilisé avec les modèles linéaires généralisés permettant ainsi de faire de la régression logistique pénalisée. L'écriture vectorielle de la forme lagrangienne est :

$\min _{\beta \in \mathbb {R} ^{p}}{\frac {1}{n}}\sum \limits _{i=1}^{n}f_{\beta }(X_{i,.},y_{i})+\lambda \|\beta \|_{1}$ avec $f_{\beta }$ une fonction objectif.

Par exemple, pour une régression logistique, on a :

$f_{\beta }(X_{i,.},y_{i})={\frac {1}{N}}\sum _{i=1}^{N}y_{i}(\beta _{0}+X_{i,.}^{T}\beta )-\log(1+e^{(\beta _{0}+X_{i,.}^{T}\beta )})$ .

Avantages et limites du lasso

Les principaux avantages du lasso sont :

Grande dimension : le lasso fonctionne dans les cas où le nombre d'individus est inférieur au nombre de variables $(n<p)$ , si toutefois un faible nombre de ces variables a une influence sur les observations (hypothèse de parcimonie). Cette propriété n'est pas vraie dans le cas de la régression linéaire classique avec un risque associé qui augmente comme la dimension de l'espace des variables même si l'hypothèse de parcimonie est vérifiée.
Sélection parcimonieuse : le lasso permet de sélectionner un sous-ensemble restreint de variables (dépendant du paramètre $\lambda$ ). Cette sélection restreinte permet souvent de mieux interpréter un modèle (rasoir d'Ockham).
Consistance de la sélection : lorsque le vrai vecteur solution $\beta$ est creux $(\|\beta \|_{0}=K<p)$ , c'est-à-dire que seul un sous-ensemble de variables est utilisé pour la prédiction, sous de bonnes conditions, le lasso sera en mesure de sélectionner ces variables d'intérêts avant toutes autres variables[4].

Par contre, certaines limites du lasso ont été démontrées :

Les fortes corrélations : si des variables sont fortement corrélées entre elles et qu'elles sont importantes pour la prédiction, le lasso en privilégiera une au détriment des autres. Un autre cas, où les corrélations posent problème, est quand les variables d'intérêts sont corrélées avec d'autres variables. Dans ce cas, la consistance de la sélection du lasso n'est plus assurée[4].
La très grande dimension : lorsque notamment la dimension est trop élevée ( $p$ très grand comparé à $n$ ) ou le vrai vecteur $\beta$ n'est pas suffisamment creux (trop de variables d'intérêts), le lasso ne pourra pas retrouver l'ensemble de ces variables d'intérêts[5].

Algorithmes de Résolution

Comme la fonction objectif du lasso n'est pas différentiable (car la norme $\ell _{1}$ n'est pas différentiable en 0), différents algorithmes ont été développés afin d'en trouver les solutions. Parmi ces algorithmes, on retrouve notamment le Least-Angle Regression (LARS)[6] et la descente de coordonnées circulaire [7].

Applications

Exemple de chemin solution du lasso. Chaque courbe représente la valeur d'un coefficients estimés par le lasso en fonction de

\lambda

.

Le lasso est utilisé dans des problèmes de grande dimension ( $n\ll p$ ), un cas où des méthodes plus classiques ne fonctionnent pas. Le lasso dispose d'algorithmes peu coûteux en temps de calcul et de stockage, ce qui le rend d'autant plus populaire, comme en génomique où l'on peut être amené à traiter des jeux de données avec plusieurs centaines de milliers de variables.

En pratique, le lasso est testé pour différentes valeurs de $\lambda$ . Un chemin solution représentant l'évolution des coefficients en fonction de $\lambda$ est ainsi obtenu. La courbe d'un coefficient estimé en fonction de $\lambda$ est linéaire par morceaux. Une fois ce chemin solution obtenu, une valeur de $\lambda$ est choisie par des méthodes comme la validation croisée ou un critère d'information (AIC par exemple).

Extensions

Un certain nombre de variantes du lasso ont été créées pour étendre la méthode à différents cas pratiques ou pour pallier certaines limitations du lasso. Sont présentées ici les variantes les plus courantes.

Elastic-Net

L'Elastic-net[8] a été introduit afin de surmonter deux "limitations" du lasso. Premièrement, le lasso ne peut sélectionner qu'au plus $n$ variables dans le cas où $n<p$ . Deuxièmement, en présence d'un groupe de variables fortement corrélées, le lasso ne sélectionne généralement qu'une seule variable du groupe. L'idée est donc d'ajouter au lasso une pénalité ridge. Ainsi l'objectif de l'Elastic-Net est :

$\min _{\beta \in \mathbb {R} ^{p}}{\frac {1}{2}}\|y-X\beta \|_{2}^{2}+\lambda _{1}\|\beta \|_{1}+\lambda _{2}\|\beta \|_{2}^{2}$

avec $\lambda _{1}\geq 0$ et $\lambda _{2}\geq 0$ .

Fused-lasso

Le Fused-Lasso[9] permet de prendre en compte la spatialité des variables. Le principe est que les variables "proches" aient des coefficients estimés "proches". Cela est possible en pénalisant la norme $\ell _{1}$ de la différence de deux coefficients successifs. De la même manière que pénaliser la norme $\ell _{1}$ d'un coefficient a tendance à produire des coefficients égaux à 0, pénaliser la différence va favoriser l'égalité de deux coefficients successifs. L'objectif du Fused-Lasso est alors :

$\min _{\beta \in \mathbb {R} ^{p}}{\frac {1}{2}}\|y-X\beta \|_{2}^{2}+\lambda _{1}\|\beta \|_{1}+\lambda _{2}\sum \limits _{j=2}^{p}|\beta _{j}-\beta _{j-1}|$

avec $\lambda _{1}\geq 0$ et $\lambda _{2}\geq 0$ .

Group-Lasso

L'idée du Group-Lasso[10] est d'avoir une méthode fournissant une sélection parcimonieuse de groupes (fournis a priori) et non de variables. Soit ${\mathcal {G}}=\{G_{1},\dots ,G_{K}\}$ , une partition des $p$ variables en $K$ groupes. On note $\beta _{G}$ , pour $G\in {\mathcal {G}}$ , le vecteur $\beta$ restreint aux éléments du groupe $G$ . L'objectif du Group-Lasso est :

$\min _{\beta \in \mathbb {R} ^{p}}{\frac {1}{2}}\|y-X\beta \|_{2}^{2}+\lambda \sum \limits _{j=1}^{K}w_{j}\|\beta _{G_{j}}\|_{2}$

avec $\lambda \geq 0$ , le paramètre de régularisation et $w_{j}>0$ , un poids associé au groupe $G_{j}$ (généralement ${\sqrt {\mathrm {Card} (G_{j})}}$ ).

Notes et références

(en) Robert Tibshirani, « Regression shrinkage and selection via the lasso », Journal of the Royal Statistical Society. Series B, vol. 58, n^o 1,‎ 1996, p. 267-288
Andrew Gelman, « Tibshirani announces new research result: A significance test for the lasso », sur Blog d'Andrew Gelman (consulté le 9 août 2015)
(en) Ryan Tibshirani, « The lasso problem and uniqueness », Electronic Journal of Statistics, vol. 7, n^o 0,‎ 2013, p. 1456-1490
(en) Peng Zhao et Bin Yu, « On Model Selection Consistency of Lasso », The Journal of Machine Learning Research, vol. 7,‎ 2006, p. 2541-2563
(en) Martin Wainwright et Bin Yu, « Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso) », IEEE Transactions on Information Theory, vol. 55, n^o 5,‎ 2009, p. 2183 - 2202
(en) Bradley Efron, Trevor Hastie, Iain Johnstone et Robert Tibshirani, « Least angle regression », The Annals of Statistics, vol. 32, n^o 2,‎ 2004, p. 407-499
(en) Jerome Friedman, Trevor Hastie et Robert Tibshirani, « Regularization Paths for Generalized Linear Models via Coordinate Descent », Journal of Statistical Software, vol. 33, n^o 1,‎ 2010, p. 1-22
(en) Hui Zou et Trevor Hastie, « Regularization and variable selection via the elastic net », Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol. 67, n^o 2,‎ 2005, p. 301-320
(en) Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu et Keith Knight, « Sparsity and smoothness via the fused lasso », Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol. 67, n^o 1,‎ 2005, p. 91-108
(en) Ming Yuan et Yi Lin, « Model Selection and Estimation in Regression with Grouped Variables », Journal of the Royal Statistical Society. Series B (statistical Methodology), vol. 68, n^o 1,‎ 2006, p. 49–67

Voir aussi

Lien interne

Acquisition comprimée

Liens externes

The Lasso Page sur le site web de Robert Tibshirani

Portail des probabilités et de la statistique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[tibshirani1996-1] (en) Robert Tibshirani, « Regression shrinkage and selection via the lasso », Journal of the Royal Statistical Society. Series B, vol. 58, n^o 1,‎ 1996, p. 267-288

[gelman-2] Andrew Gelman, « Tibshirani announces new research result: A significance test for the lasso », sur Blog d'Andrew Gelman (consulté le 9 août 2015)

[:0-3] (en) Ryan Tibshirani, « The lasso problem and uniqueness », Electronic Journal of Statistics, vol. 7, n^o 0,‎ 2013, p. 1456-1490

[cons-4] (en) Peng Zhao et Bin Yu, « On Model Selection Consistency of Lasso », The Journal of Machine Learning Research, vol. 7,‎ 2006, p. 2541-2563

[5] (en) Martin Wainwright et Bin Yu, « Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso) », IEEE Transactions on Information Theory, vol. 55, n^o 5,‎ 2009, p. 2183 - 2202

[6] (en) Bradley Efron, Trevor Hastie, Iain Johnstone et Robert Tibshirani, « Least angle regression », The Annals of Statistics, vol. 32, n^o 2,‎ 2004, p. 407-499

[7] (en) Jerome Friedman, Trevor Hastie et Robert Tibshirani, « Regularization Paths for Generalized Linear Models via Coordinate Descent », Journal of Statistical Software, vol. 33, n^o 1,‎ 2010, p. 1-22

[8] (en) Hui Zou et Trevor Hastie, « Regularization and variable selection via the elastic net », Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol. 67, n^o 2,‎ 2005, p. 301-320

[9] (en) Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu et Keith Knight, « Sparsity and smoothness via the fused lasso », Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol. 67, n^o 1,‎ 2005, p. 91-108

[10] (en) Ming Yuan et Yi Lin, « Model Selection and Estimation in Regression with Grouped Variables », Journal of the Royal Statistical Society. Series B (statistical Methodology), vol. 68, n^o 1,‎ 2006, p. 49–67