MS IAMDI 720 : Lasso

François PortierTélécom Paristech

Some of the contents were provided by Joseph Salmon http://josephsalmon.eu

1 / 49

Plan

Rappels

Sélection de variables et parcimonieLa pénalisation `0 et ses limitesLa pénalisation `1Sous-gradient / sous-différentielle

Améliorations et extensions du LassoLSLasso / Elastic-NetPénalités non-convexes / Adaptive LassoStructure sur le supportStabilisationExtensions des moindres carrés / Lasso

2 / 49

Retour sur le modèle

y “ Xθ‹ ` ε P Rn

X “ rx1, . . . ,xps “

¨

˚

˝

x1,1 . . . x1,p... . . . ...

xn,1 . . . xn,p

˛

‹

‚

P Rnˆp,θ‹ P Rp

3 / 49

Motivation

Utilité des estimateurs θ avec beaucoup de coefficients nuls :§ pour l’interprétation§ pour l’efficacité computationnelle si p est énorme

Idée sous-jacente : sélectionner des variables

Rem: aussi utile si θ‹ a peu de coefficients non nuls

4 / 49

Méthodes de sélection de variables§ Méthodes de dépistage par corrélation ( : correlationscreening) : supprimer les xj de faible corrélation avec y‚ avantages : rapide (+++), coût : p produits scalaires detaille n, intuitive (+++)‚ défauts : néglige les interactions entre variables xj , résultatsthéoriques faibles (- - -)

§ Méthodes gloutonnes ( : greedy) / pas à pas( : stage/step-wise)‚ avantages : rapide (++), coût : p produits scalaires de taillen par variable active, intuitive (++)‚ défauts : propagation de mauvaises sélections de variablesaux étapes suivantes ; résultats théoriques faibles (-)

§ Méthodes pénalisées favorisant la parcimonie (e.g.,Lasso)‚ avantages : résultats théoriques bons (++)‚ défauts : encore lent (on y travaille Fercoq et al.(2015)) (-)

5 / 49

Méthodes de sélection de variables§ Méthodes de dépistage par corrélation ( : correlationscreening) : supprimer les xj de faible corrélation avec y‚ avantages : rapide (+++), coût : p produits scalaires detaille n, intuitive (+++)‚ défauts : néglige les interactions entre variables xj , résultatsthéoriques faibles (- - -)

§ Méthodes gloutonnes ( : greedy) / pas à pas( : stage/step-wise)‚ avantages : rapide (++), coût : p produits scalaires de taillen par variable active, intuitive (++)‚ défauts : propagation de mauvaises sélections de variablesaux étapes suivantes ; résultats théoriques faibles (-)

§ Méthodes pénalisées favorisant la parcimonie (e.g.,Lasso)‚ avantages : résultats théoriques bons (++)‚ défauts : encore lent (on y travaille Fercoq et al.(2015)) (-)

5 / 49

Méthodes de sélection de variables§ Méthodes de dépistage par corrélation ( : correlationscreening) : supprimer les xj de faible corrélation avec y‚ avantages : rapide (+++), coût : p produits scalaires detaille n, intuitive (+++)‚ défauts : néglige les interactions entre variables xj , résultatsthéoriques faibles (- - -)

§ Méthodes gloutonnes ( : greedy) / pas à pas( : stage/step-wise)‚ avantages : rapide (++), coût : p produits scalaires de taillen par variable active, intuitive (++)‚ défauts : propagation de mauvaises sélections de variablesaux étapes suivantes ; résultats théoriques faibles (-)

§ Méthodes pénalisées favorisant la parcimonie (e.g.,Lasso)‚ avantages : résultats théoriques bons (++)‚ défauts : encore lent (on y travaille Fercoq et al.(2015)) (-)

5 / 49

La pseudo-norme `0

DéfinitionsLe support du vecteur θ est l’ensemble des indices descoordonnées non nulles :

supppθq “ tj P J1, pK, θj ‰ 0u

La pseudo-norme `0 d’un vecteur θ P Rp est son nombre decoordonnées non-nulles :

θ0 “ cardtj P J1, pK, θj ‰ 0u

Rem: ¨ 0 n’est pas une norme, @t P R˚, tθ0 “ θ0Rem: ¨ 0 n’est pas non plus convexe, θ1 “ p1, 0, 1, . . . , 0qθ2 “ p0, 1, 1, . . . , 0q et 3 “ θ1`θ2

2 0 ěθ10`θ20

2 “ 2

6 / 49

Sommaire

Rappels

Sélection de variables et parcimonieLa pénalisation `0 et ses limitesLa pénalisation `1Sous-gradient / sous-différentielle

Améliorations et extensions du LassoLSLasso / Elastic-NetPénalités non-convexes / Adaptive LassoStructure sur le supportStabilisationExtensions des moindres carrés / Lasso

7 / 49

La pénalisation `0

Première tentative de méthode pénalisée pour introduire de laparcimonie : utiliser `0 pour la pénalisation / régularisation

θλ “ arg minθPRp

ˆ

12y´Xθ

22

loooooomoooooon

attache aux données

` λθ0loomoon

régularisation

˙

Problème combinatoire ! ! ! (problème “NP-dur”)

Résolution exacte : nécessite de considérer tous les sous-modèles,i.e.,calculer les estimateurs pour tous les supports possibles ; il y ena 2p, ce qui requiert le calcul de 2p moindres carrés !

Exemples :p “ 10 possible : « 103 moindres carrésp “ 30 impossible : « 1010 moindres carrés

Rem: avancées récentes Bertsimas et al.168 / 49

Sommaire

Rappels

Sélection de variables et parcimonieLa pénalisation `0 et ses limitesLa pénalisation `1Sous-gradient / sous-différentielle

Améliorations et extensions du LassoLSLasso / Elastic-NetPénalités non-convexes / Adaptive LassoStructure sur le supportStabilisationExtensions des moindres carrés / Lasso

9 / 49

Le Lasso : la définition pénaliséeLasso : Least Absolute Shrinkage and Selection OperatorTibshirani (1996)

θLassoλ “ arg min

θPRp

ˆ

12y´Xθ

22

loooooomoooooon

attache aux données

` λθ1loomoon

régularisation

˙

où θ1 “pÿ

j“1|θj | (somme des valeurs absolues des coefficients)

§ On retrouve de nouveau les cas limites :

limλÑ0

θLassoλ “θ

MCO

limλÑ`8

θLassoλ “0 P Rp

Attention : l’estimateur Lasso n’est pas toujours unique pour unλ fixé ; prendre par exemple deux colonnes identiques

10 / 49

Moindre carrees / Ridge et Lasso

Figure: OLS, Ridge, Lasso

11 / 49

Moindre carrees / Ridge et Lasso

Figure: OLS, Ridge, Lasso

11 / 49

Moindre carrees / Ridge et Lasso

Figure: OLS, Ridge, Lasso

11 / 49

Moindre carrees / Ridge et Lasso

Figure: OLS, Ridge, Lasso

11 / 49

Moindre carrees / Ridge et Lasso

Figure: OLS, Ridge, Lasso

11 / 49

Interprétation contrainteUn problème de la forme :

θLassoλ “ arg min

θPRp

ˆ

12y´Xθ

22

loooooomoooooon

attache aux données

` λθ1loomoon

régularisation

˙

admet la même solution qu’une version contrainte :$

&

%

arg minθPRp

y´Xθ22

t.q. θ1 ď T

pour un certain T ą 0.

Rem: le lien T Ø λ n’est pas explicite§ Si T Ñ 0 on retrouve comme solution le vecteur nul : 0 P Rp

§ Si T Ñ8 on retrouve θMCO (non contraint)

12 / 49

Mise à zéro de certains coefficients

Optimisation sous contrainte `2 : solution non parcimonieuse13 / 49

Mise à zéro de certains coefficients

Optimisation sous contrainte `1 : solution parcimonieuse13 / 49

Sommaire

Rappels

Sélection de variables et parcimonieLa pénalisation `0 et ses limitesLa pénalisation `1Sous-gradient / sous-différentielle

Améliorations et extensions du LassoLSLasso / Elastic-NetPénalités non-convexes / Adaptive LassoStructure sur le supportStabilisationExtensions des moindres carrés / Lasso

14 / 49

Sous-gradients / sous-différentiellesDéfinitionsPour f : Rn Ñ R une fonction convexe, u P Rn est unsous-gradient de f en x˚, si pour tout x P Rn on a

fpxq ě fpx˚q ` xu, x´ x˚y

La sous-différentielle est l’ensemble des sous-gradients :Bfpx˚q “ tu P Rn : @x P Rn, fpxq ě fpx˚q ` xu, x´ x˚yu.

Rem: si le sous-gradient est unique, on retrouve le gradient

15 / 49

Sous-gradients / sous-différentiellesDéfinitionsPour f : Rn Ñ R une fonction convexe, u P Rn est unsous-gradient de f en x˚, si pour tout x P Rn on a

fpxq ě fpx˚q ` xu, x´ x˚y

La sous-différentielle est l’ensemble des sous-gradients :Bfpx˚q “ tu P Rn : @x P Rn, fpxq ě fpx˚q ` xu, x´ x˚yu.

Rem: si le sous-gradient est unique, on retrouve le gradient

15 / 49

Sous-gradients / sous-différentiellesDéfinitionsPour f : Rn Ñ R une fonction convexe, u P Rn est unsous-gradient de f en x˚, si pour tout x P Rn on a

fpxq ě fpx˚q ` xu, x´ x˚y

La sous-différentielle est l’ensemble des sous-gradients :Bfpx˚q “ tu P Rn : @x P Rn, fpxq ě fpx˚q ` xu, x´ x˚yu.

Rem: si le sous-gradient est unique, on retrouve le gradient

15 / 49

Sous-gradients / sous-différentiellesDéfinitionsPour f : Rn Ñ R une fonction convexe, u P Rn est unsous-gradient de f en x˚, si pour tout x P Rn on a

fpxq ě fpx˚q ` xu, x´ x˚y

La sous-différentielle est l’ensemble des sous-gradients :Bfpx˚q “ tu P Rn : @x P Rn, fpxq ě fpx˚q ` xu, x´ x˚yu.

Rem: si le sous-gradient est unique, on retrouve le gradient

15 / 49

Règle de Fermat

ThéorèmeUn point x˚ est un minimum d’une fonction convexe f : Rn Ñ Rsi et seulement si 0 P Bfpx˚q

Preuve : utiliser la définition des sous-gradients :§ 0 est un sous-gradient de f en x˚ si et seulement si@x P Rn, fpxq ě fpx˚q ` x0, x´ x˚y

16 / 49

Règle de Fermat

ThéorèmeUn point x˚ est un minimum d’une fonction convexe f : Rn Ñ Rsi et seulement si 0 P Bfpx˚q

Preuve : utiliser la définition des sous-gradients :§ 0 est un sous-gradient de f en x˚ si et seulement si@x P Rn, fpxq ě fpx˚q ` x0, x´ x˚y

Rem:visuellement cela correspond à une tangente horizontale

16 / 49

Sous-différentielle de la valeur absolue

Fonction (abs) :

f :#

R Ñ Rx ÞÑ |x|

Sous-différentielle (sign)

Bfpx˚q “

$

’

&

’

%

t´1u si x˚ Ps ´8, 0rt1u si x˚ Ps0,8rr´1, 1s si x˚ “ 0

17 / 49

Sous-différentielle de la valeur absolue

Fonction (abs) :

f :#

R Ñ Rx ÞÑ |x|

Sous-différentielle (sign)

Bfpx˚q “

$

’

&

’

%

t´1u si x˚ Ps ´8, 0rt1u si x˚ Ps0,8rr´1, 1s si x˚ “ 0

17 / 49

Sous-différentielle de la valeur absolue

Fonction (abs) :

f :#

R Ñ Rx ÞÑ |x|

Sous-différentielle (sign)

Bfpx˚q “

$

’

&

’

%

t´1u si x˚ Ps ´8, 0rt1u si x˚ Ps0,8rr´1, 1s si x˚ “ 0

17 / 49

Sous-différentielle de la valeur absolue

Fonction (abs) :

f :#

R Ñ Rx ÞÑ |x|

Sous-différentielle (sign)

Bfpx˚q “

$

’

&

’

%

t´1u si x˚ Ps ´8, 0rt1u si x˚ Ps0,8rr´1, 1s si x˚ “ 0

17 / 49

Sous-différentielle de la valeur absolue

Fonction (abs) :

f :#

R Ñ Rx ÞÑ |x|

Sous-différentielle (sign)

Bfpx˚q “

$

’

&

’

%

t´1u si x˚ Ps ´8, 0rt1u si x˚ Ps0,8rr´1, 1s si x˚ “ 0

17 / 49

Sous-différentielle de la valeur absolue

Fonction (abs) :

f :#

R Ñ Rx ÞÑ |x|

Sous-différentielle (sign)

Bfpx˚q “

$

’

&

’

%

t´1u si x˚ Ps ´8, 0rt1u si x˚ Ps0,8rr´1, 1s si x˚ “ 0

17 / 49

Sous-différentielle de la valeur absolue

Fonction (abs) :

f :#

R Ñ Rx ÞÑ |x|

Sous-différentielle (sign)

Bfpx˚q “

$

’

&

’

%

t´1u si x˚ Ps ´8, 0rt1u si x˚ Ps0,8rr´1, 1s si x˚ “ 0

17 / 49

Sous-différentielle de la valeur absolue

Fonction (abs) :

f :#

R Ñ Rx ÞÑ |x|

Sous-différentielle (sign)

Bfpx˚q “

$

’

&

’

%

t´1u si x˚ Ps ´8, 0rt1u si x˚ Ps0,8rr´1, 1s si x˚ “ 0

17 / 49

Condition de Fermat pour le Lasso

θLassoλ “ arg min

θPRp

ˆ

12y´Xθ

22

loooooomoooooon

attache aux données

` λθ1loomoon

régularisation

˙

Conditions nécessaires et suffisantes d’optimalité (Fermat) :

@j P rps, xJj

˜

y ´XθLassoλ

λ

¸

P

#

tsignpθLassoλ qju si pθ

Lassoλ qj ‰ 0,

r´1, 1s si pθLassoλ qj “ 0.

18 / 49

Régularisation en 1D : RidgeRésoudre : ηλpzq “ arg min

xPRx ÞÑ

12pz ´ xq

2 `λ

2x2

ηλpzq “z

1` λ

ηRidge,λ

Contraction `2 : Ridge

19 / 49

Régularisation en 1D : LassoRésoudre : ηλpzq “ arg min

xPRx ÞÑ

12pz ´ xq

2 ` λ|x|

ηλpzq “ signpzqp|z| ´ λq`(Exercice)

ηST,λ

Contraction `1 : Seuillage doux ( : soft thresholding)

19 / 49

Régularisation en 1D : `0

Résoudre : ηλpzq “ arg minxPR

x ÞÑ12pz ´ xq

2 ` λ1x‰0

ηλpzq “ z1|z|ě

?2λ

ηHT,λ

Contraction `0 : Seuillage dur ( : hard thresholding)

19 / 49

Régularisation en 1D : Elastic NetRésoudre : ηλpzq “ arg min

xPRx ÞÑ

12pz ´ xq

2 ` λpγ|x| ` p1´ γqx2

2 q

ηλpzq “ Exercice

ηEnet,λ,γ

Contraction `1`219 / 49

Seuillage doux : forme explicite

ηLasso,λpzq “

$

’

&

’

%

z ` λ si z ă ´λ0 si |z| ď λ

z ´ λ si z ą λ

Exercise: Prouver le résultat précédent en utilisant lessous-gradients

20 / 49

Exemple numérique : simulation

§ θ‹ “ p1, 1, 1, 1, 1, 0, . . . , 0q P Rp (5 coefficients non-nuls)§ X P Rnˆp a des colonnes tirées selon une loi gaussienne§ y “ Xθ‹ ` ε P Rn avec ε „ N p0, σ2 Idnq§ On utilise une grille de 50 valeurs de λ

Pour cet exemple les tailles sont : n “ 60, p “ 40, σ “ 1

21 / 49

Lasso vs Ridge

10−5 10−4 10−3 10−2 10−1 100 101 102 103 104

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Coe

ffici

ent

valu

e

Ridge path: p = 40, n = 60

22 / 49

Lasso vs Ridge

10−5 10−4 10−3 10−2 10−1 100 101 102 103 104

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Coe

ffici

ent

valu

e

CV = 5

Ridge path: p = 40, n = 60

22 / 49

Lasso vs Ridge

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Coe

ffici

ent

valu

e

Lasso path: p = 40, n = 60

22 / 49

Lasso vs Ridge

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Coe

ffici

ent

valu

e CV = 5

Lasso path: p = 40, n = 60

22 / 49

Intérêt du Lasso

§ Enjeu numérique : le Lasso est un problème convexe§ Sélection de variables/ solutions parcimonieuses (sparse) :θ

Lassoλ a potentiellement de nombreux coefficients nuls. Le

paramètre λ contrôle le niveau de parcimonie : si λ est grand,les solutions sont très creuses.

Exemple : on obtient 17 coefficients non nuls pour LassoCVdans la simulation précédente

Rem: RidgeCV n’avait aucun coefficient nul

23 / 49

Analyse de l’estimateur dans le cas général

Analyse théorique : (nettement) plus poussée que pour lesmoindres carrées ou que pour Ridge ; peut être trouvée dans desréférences récentes, cf.Buhlmann et van de Geer (2011) pour desrésultats théoriques

En résumé : on biaise l’estimateur des moindres carrés pour réduirela variance

24 / 49

Sommaire

Rappels

Sélection de variables et parcimonieLa pénalisation `0 et ses limitesLa pénalisation `1Sous-gradient / sous-différentielle

Améliorations et extensions du LassoLSLasso / Elastic-NetPénalités non-convexes / Adaptive LassoStructure sur le supportStabilisationExtensions des moindres carrés / Lasso

25 / 49

Le biais du LassoLe lasso est biaisé : il contracte les grands coefficients vers 0

0 5 10 15 20 25 30 35 400.0

0.2

0.4

0.6

0.8

1.0

1.2

1.4Signal estimation: p = 40, n = 60

True signal

Lasso

Illustration sur l’exemple26 / 49

Le biais du LassoLe lasso est biaisé : il contracte les grands coefficients vers 0

0 5 10 15 20 25 30 35 400.0

0.2

0.4

0.6

0.8

1.0

1.2

1.4Signal estimation: p = 40, n = 60

True signal

Lasso

LSLasso

Illustration sur l’exemple26 / 49

Le biais du Lasso : un remède simple

Comme les grands coefficients sont parfois contractés vers zéro, ilest possible d’utiliser une procédure en deux étapes

LSLasso (Least Square Lasso)

1. Lasso : obtenir θLassoλ

2. Moindres-carrés sur les variables actives supppθLassoλ q

θLSLassoλ “ arg min

θPRpsupppθq“supppθLasso

λ q

12y´Xθ

22

Attention : il faut faire la CV sur la procédure entière ; choisir λ duLasso par CV puis faire les moindres carrés garde trop de variables

Rem: LSLasso pas forcément codé dans les packages usuels

27 / 49

Débiasage

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Coe

ffici

ent

valu

e

LSLasso path: p = 40, n = 60

28 / 49

Débiasage

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Coe

ffici

ent

valu

e

CV = 5

LSLasso path: p = 40, n = 60

28 / 49

Prédiction : Lasso vs. LSLasso

10−2 10−1 100 101

λ

10−2

10−1

100

101

102

Pre

dict

ion

Err

or

CV-Lasso

CV-LSLasso

CV-Ridge

Prediction Error: p = 40, n = 60

29 / 49

Bilan du LSLasso

Avantages§ les “vrais” grands coefficients sont moins atténués§ en faisant la CV on récupère moins de variables parasites(amélioration de l’interprétabilité)e.g.,sur l’exemple précédent le LSLassoCV retrouve les 5“vraies” variables non nulles, et un faux positif

LSLasso : utile pour l’estimation

Limites§ la différence en prédiction n’est pas toujours flagrante§ nécessite plus de calcul : re-calculer autant de moindres carrésque de paramètres λ (de dimension la taille des supports, caron néglige les autres variables)

§ non packagé

30 / 49

Elastic Net : régularisation `1`2

L’Elastic Net introduit par Zou et Hastie (2005) est solution de

θλ “ arg minθPRp

„

12y´Xθ

22 ` λ

ˆ

γθ1 ` p1´ γqθ22

2

˙

Rem: deux paramètres de régularisation, un pour la régularisationglobale, un qui contrôle l’influence Ridge vs. Lasso

Rem: la solution est unique et la taille du support de l’Elastic Netest plus petite que minpn, pq

31 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 1.0032 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.9932 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.9532 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.9032 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.7532 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.5032 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.2532 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.132 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.0532 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.0132 / 49

Elastic-Net : γθ1 ` p1´ γqθ222

10−2 10−1 100 101

λ

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0C

oeffi

cien

tva

lue

Enet path: p = 40, n = 60

γ “ 0.0032 / 49

Sommaire

Rappels

Sélection de variables et parcimonieLa pénalisation `0 et ses limitesLa pénalisation `1Sous-gradient / sous-différentielle

Améliorations et extensions du LassoLSLasso / Elastic-NetPénalités non-convexes / Adaptive LassoStructure sur le supportStabilisationExtensions des moindres carrés / Lasso

33 / 49

Pénalités non-convexesUtiliser une pénalité non-convexe approchant mieux ¨ 0, enchoisissant tÑ penλ,γptq non-convexe

θpenλ,γ “ arg min

θPRp

ˆ

12y´Xθ

22

loooooomoooooon

attache aux données

`

pÿ

j“1penλ,γp|θj |q

looooooooomooooooooon

régularisation

˙

34 / 49

Pénalités non-convexesUtiliser une pénalité non-convexe approchant mieux ¨ 0, enchoisissant tÑ penλ,γptq non-convexe

θpenλ,γ “ arg min

θPRp

ˆ

12y´Xθ

22

loooooomoooooon

attache aux données

`

pÿ

j“1penλ,γp|θj |q

looooooooomooooooooon

régularisation

˙

§ Adaptive-Lasso Zou (2006) / `1 re-pondérés Candès etal.(2008)

penλ,γptq “ λ|t|q avec 0 ă q ă 1

34 / 49

Pénalités non-convexesUtiliser une pénalité non-convexe approchant mieux ¨ 0, enchoisissant tÑ penλ,γptq non-convexe

θpenλ,γ “ arg min

θPRp

ˆ

12y´Xθ

22

loooooomoooooon

attache aux données

`

pÿ

j“1penλ,γp|θj |q

looooooooomooooooooon

régularisation

˙

§ MCP (minimax concave penalty) Zhang (2010) pour λ ą 0 etγ ą 1

penλ,γptq “#

λ|t| ´ t2

2γ , si |t| ď γλ12γλ

2, si |t| ą γλ

34 / 49

Pénalités non-convexesUtiliser une pénalité non-convexe approchant mieux ¨ 0, enchoisissant tÑ penλ,γptq non-convexe

θpenλ,γ “ arg min

θPRp

ˆ

12y´Xθ

22

loooooomoooooon

attache aux données

`

pÿ

j“1penλ,γp|θj |q

looooooooomooooooooon

régularisation

˙

§ SCAD (Smoothly Clipped Absolute Deviation) Fan et Li(2001) pour λ ą 0 et γ ą 2

penλ,γptq “

$

’

’

&

’

’

%

λ|t|, si |t| ď λγλ|t|´pt2`λ2q2

γ´1 , si λ ă |t| ď γλλ2pγ2´1q2pγ´1q , si |t| ą γλ

Rem: difficultés algorithmiques (arrêt, minima locaux, etc.)

34 / 49

Forme des pénalités classiques

l1 35 / 49

Forme des pénalités classiques

l0 35 / 49

Forme des pénalités classiques

l22 35 / 49

Forme des pénalités classiques

enet 35 / 49

Forme des pénalités classiques

sqrt 35 / 49

Forme des pénalités classiques

log 35 / 49

Forme des pénalités classiques

mcp 35 / 49

Forme des pénalités classiques

scad 35 / 49

Forme des pénalités classiques

l0

sqrt

l22

enet

log

mcp

scad

l1

35 / 49

Adaptive-Lasso

Plusieurs noms pour une même idée :§ Adaptive-Lasso Zou (2006)§ `1 re-pondérés Candès et al.(2008)§ approche DC-programming (pour Difference of ConvexProgramming) Gasso et al.(2008)

36 / 49

Adaptive-Lasso

Exemple : prendre penλ,γptq “ λ|t|q avec q “ 12

Algorithme : Adaptive Lasso (cas q “ 12)Entrées : X,y, nombre d’itérations K, régularisation λInitialisation : w Ð p1, . . . , 1qJ

pour k “ 1, . . . ,K faire

θ Ð arg minθPRp

˜

y´Xθ222 ` λ

pÿ

j“1wj |θj |

¸

wj Ð1

|θj |12, @j P J1, pK

Rem: en pratique pas besoin d’itérer beaucoup (5 itérations)

Rem: utiliser un solveur Lasso pour mettre à jour θ

37 / 49

Adaptive-Lasso

Exemple : prendre penλ,γptq “ λ|t|q avec q “ 12

Algorithme : Adaptive Lasso (cas q “ 12)Entrées : X,y, nombre d’itérations K, régularisation λInitialisation : w Ð p1, . . . , 1qJpour k “ 1, . . . ,K faire

θ Ð arg minθPRp

˜

y´Xθ222 ` λ

pÿ

j“1wj |θj |

¸

wj Ð1

|θj |12, @j P J1, pK

Rem: en pratique pas besoin d’itérer beaucoup (5 itérations)

Rem: utiliser un solveur Lasso pour mettre à jour θ

37 / 49

Adaptive-Lasso

Exemple : prendre penλ,γptq “ λ|t|q avec q “ 12

Algorithme : Adaptive Lasso (cas q “ 12)Entrées : X,y, nombre d’itérations K, régularisation λInitialisation : w Ð p1, . . . , 1qJpour k “ 1, . . . ,K faire

θ Ð arg minθPRp

˜

y´Xθ222 ` λ

pÿ

j“1wj |θj |

¸

wj Ð1

|θj |12, @j P J1, pK

Rem: en pratique pas besoin d’itérer beaucoup (5 itérations)

Rem: utiliser un solveur Lasso pour mettre à jour θ

37 / 49

Adaptive-Lasso

Exemple : prendre penλ,γptq “ λ|t|q avec q “ 12

Algorithme : Adaptive Lasso (cas q “ 12)Entrées : X,y, nombre d’itérations K, régularisation λInitialisation : w Ð p1, . . . , 1qJpour k “ 1, . . . ,K faire

θ Ð arg minθPRp

˜

y´Xθ222 ` λ

pÿ

j“1wj |θj |

¸

wj Ð1

|θj |12, @j P J1, pK

Rem: en pratique pas besoin d’itérer beaucoup (5 itérations)

Rem: utiliser un solveur Lasso pour mettre à jour θ

37 / 49

Adaptive-Lasso

Exemple : prendre penλ,γptq “ λ|t|q avec q “ 12

Algorithme : Adaptive Lasso (cas q “ 12)Entrées : X,y, nombre d’itérations K, régularisation λInitialisation : w Ð p1, . . . , 1qJpour k “ 1, . . . ,K faire

θ Ð arg minθPRp

˜

y´Xθ222 ` λ

pÿ

j“1wj |θj |

¸

wj Ð1

|θj |12, @j P J1, pK

Rem: en pratique pas besoin d’itérer beaucoup (5 itérations)

Rem: utiliser un solveur Lasso pour mettre à jour θ

37 / 49

Adaptive-Lasso

Exemple : prendre penλ,γptq “ λ|t|q avec q “ 12

Algorithme : Adaptive Lasso (cas q “ 12)Entrées : X,y, nombre d’itérations K, régularisation λInitialisation : w Ð p1, . . . , 1qJpour k “ 1, . . . ,K faire

θ Ð arg minθPRp

˜

y´Xθ222 ` λ

pÿ

j“1wj |θj |

¸

wj Ð1

|θj |12, @j P J1, pK

Rem: en pratique pas besoin d’itérer beaucoup (5 itérations)

Rem: utiliser un solveur Lasso pour mettre à jour θ

37 / 49

Sommaire

Rappels

Sélection de variables et parcimonieLa pénalisation `0 et ses limitesLa pénalisation `1Sous-gradient / sous-différentielle

Améliorations et extensions du LassoLSLasso / Elastic-NetPénalités non-convexes / Adaptive LassoStructure sur le supportStabilisationExtensions des moindres carrés / Lasso

38 / 49

Structure du support

On suppose ici que l’on connaît une structure de groupes sur lesvariables au préalable de l’étude : J1, pK “

Ť

gPG g

Vecteur et ses coordonnées actives (en orange) :

Support creux : quelconque

Pénalité envisagée : Lasso

θ1 “pÿ

j“1|θj |

39 / 49

Structure du support

On suppose ici que l’on connaît une structure de groupes sur lesvariables au préalable de l’étude : J1, pK “

Ť

gPG g

Vecteur et ses coordonnées actives (en orange) :

Support creux : groupes

Pénalité envisagée : Groupe-Lasso

θ2,1 “ÿ

gPG

θg2

39 / 49

Structure du support

On suppose ici que l’on connaît une structure de groupes sur lesvariables au préalable de l’étude : J1, pK “

Ť

gPG g

Vecteur et ses coordonnées actives (en orange) :

Support creux : groupes + sous groupes

Pénalité envisagée : Sparse-Groupe-Lasso

αθ1 ` p1´ αqθ2,1 “ αpÿ

j“1|θj | ` p1´ αq

ÿ

gPG

θg2

39 / 49

Groupe-Lasso

La pénalisation par la norme `1 assure que peu de coefficients sontactifs, mais aucune autre structure sur le support n’est utilisée

Structures additionnelles classiques :§ Parcimonie par groupe/bloc : Groupe-Lasso Yuan et Lin(2006)

§ Parcimonie individuelle et par groupe : Sparse Groupe-LassoSimon, Friedman, Hastie et Tibshirani (2012)

§ Structures hiérarchiques (par exemple avec les interactionsd’ordre supérieur) Bien,Taylor et Tibshirani (2013)

§ Structures sur des graphes, des gradients, etc.

40 / 49

Sommaire

Rappels

Sélection de variables et parcimonieLa pénalisation `0 et ses limitesLa pénalisation `1Sous-gradient / sous-différentielle

Améliorations et extensions du LassoLSLasso / Elastic-NetPénalités non-convexes / Adaptive LassoStructure sur le supportStabilisationExtensions des moindres carrés / Lasso

41 / 49

Exemple

42 / 49

Régression multi-tâchesOn veut résoudre m régressions linéaires conjointement : Y « XΘ

avec§ Y P Rnˆm : matrice des observations§ X P Rnˆp : matrice de design (commune)§ Θ P Rpˆm : matrice des coefficients

Exemple : plusieurs signaux sont observés au cours du temps(e.g.,divers capteurs d’un même phénomène)

Rem:cf.MultiTaskLasso dans sklearn pour le numérique43 / 49

Moindre carres pénalisées

Dans le contexte de la régression multi-tâches on peut résoudre lesmoindres carrés pénalisés :

Θλ “ arg minΘPRpˆm

ˆ

12Y ´XΘ2Flooooooomooooooon

attache aux données

` λΩpΘqlooomooon

régularisation

˙

où Ω est une pénalité / régularisation à préciser

Rem: la norme de Frobenius ¨ F est définie pour toute matriceA P Rn1ˆn2 par

A2F “n1ÿ

j1“1

n2ÿ

j2“1A2j1,j2

44 / 49

Références I

§ F. Bach.Bolasso : model consistent Lasso estimation through the bootstrap.In ICML, 2008.

§ D. Bertsimas, A. King, and R. Mazumder.Best subset selection via a modern optimization lens.Ann. Statist., 44(2) :813–852, 2016.

§ P. Bühlmann and S. van de Geer.Statistics for high-dimensional data.Springer Series in Statistics. Springer, Heidelberg, 2011.Methods, theory and applications.

§ E. J. Candès, M. B. Wakin, and S. P. Boyd.Enhancing sparsity by reweighted l1 minimization.J. Fourier Anal. Applicat., 14(5-6) :877–905, 2008.

45 / 49

Références II

§ O. Fercoq, A. Gramfort, and J. Salmon.Mind the duality gap : safer rules for the lasso.In ICML, pages 333–342, 2015.

§ J. Fan and R. Li.Variable selection via nonconcave penalized likelihood and its oracleproperties.J. Amer. Statist. Assoc., 96(456) :1348–1360, 2001.

§ G. Gasso, A. Rakotomamonjy, and S. Canu.Recovering sparse signals with non-convex penalties and DC programming.IEEE Trans. Sig. Process., 57(12) :4686–4698, 2009.

§ Bien J, J. Taylor, and R. Tibshirani.A lasso for hierarchical interactions.Ann. Statist., 41(3) :1111–1141, 2013.

46 / 49

Références III§ N. Meinshausen and P. Bühlmann.

Stability selection.Journal of the Royal Statistical Society : Series B (Statistical Methodology),72(4) :417–473, 2010.

§ N. Parikh, S. Boyd, E. Chu, B. Peleato, and J. Eckstein.Proximal algorithms.Foundations and Trends in Machine Learning, 1(3) :1–108, 2013.

§ N. Simon, J. Friedman, T. Hastie, and R. Tibshirani.A sparse-group lasso.J. Comput. Graph. Statist., 22(2) :231–245, 2013.

§ R. Tibshirani.Regression shrinkage and selection via the lasso.J. Roy. Statist. Soc. Ser. B, 58(1) :267–288, 1996.

§ M. Yuan and Y. Lin.Model selection and estimation in regression with grouped variables.J. Roy. Statist. Soc. Ser. B, 68(1) :49–67, 2006.

47 / 49

Références IV

§ H. Zou and T. Hastie.Regularization and variable selection via the elastic net.J. Roy. Statist. Soc. Ser. B, 67(2) :301–320, 2005.

§ C.-H. Zhang.Nearly unbiased variable selection under minimax concave penalty.Ann. Statist., 38(2) :894–942, 2010.

§ H. Zou.The adaptive lasso and its oracle properties.J. Am. Statist. Assoc., 101(476) :1418–1429, 2006.

48 / 49