Apprentissage 1516 Lasso

Apprentissage Statistique : Partie III
Magalie Fromont (Université Rennes 2)
Ensai, 2015 - 2016
Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 1 / 46

Plan du cours
1 Régression linéaire : rappels
2 Régression linéaire régularisée : régressions ridge, LASSO, Elastic Net
3 Variantes du LASSO
4 Méthodes à noyaux pour la régression non linéaire

Plan du cours

Modèle de régression linéaire
Estimation des paramètres par MCO
Sélection de variables

Rappel des notations
Données observées de type entrée-sortie : d1n = {(x1 , y1 ), . . . , (xn , yn )}

avec xi ∈ Rp ), yi ∈ R pour i = 1 . . . n.
Objectif : prédire la sortie y associée à une nouvelle entrée x,

sur la base de d1n (problème de régression réelle).
Modèle non paramétrique :

On suppose que d1n est l’observation d’un n-échantillon
D1n = {(X1 , Y1 ), . . . , (Xn , Yn )} d’une loi conjointe P sur Rp × R,
totalement inconnue.
On suppose que x est une observation de la variable X , (X , Y ) étant un
couple aléatoire de loi conjointe P indépendant de D1n .

Modèle de régression linéaire : xi = (xi1 , . . . , xip )0 . On suppose que :
Yi = β0 + β1 xi1 + β2 xi2 + . . . + βp xip + εi , 1 ≤ i ≤ n,
où
β0 , β1 , . . . , βp sont les paramètres du modèle (à estimer),
les variables εi vérifient :
E[εi ] = 0, cov(εi , εj ) = 0 ∀i 6= j, var(εi ) = σ 2 ,
les variables sont supposées gaussiennes pour l’inférence statistique
(intervalles de confiance, tests, p valeurs...)

Modèle de régression linéaire sous forme matricielle :
Y = Xβ + ε,
où   
β0 ε1
x10 x11 x12 x1p
 
. β1   ε2 
 x20 . x21 x22 x2p   
, β =  . , ε =  . ,
 
X=
 . . . . .   
.
 
.
xn0 xn1 xn2 . xnp
βp εn
 0    j
x1 1 x1
x20  1  j
x2 
x0 =  x j =  .  (j = 1 . . . p).
   
 .  = . ,
    
 .  . .
 
xn0 1 xnj

Estimation des paramètres par MCO
β est estimé par la méthode des moindres carrés ordinaires : l’estimateur
p+1 le critère empirique :
Pn β ∈ R
β̂ minimise pour
1 2 p 2
i=1 Yi − β0 − β1 xi − β2 xi − . . . − βp xi .
,→ minimisation de risque empirique pour la perte quadratique, sur

l’ensemble des règles de régression linéaires, de la forme
f (x) = β0 + β1 x 1 + β2 x 2 + . . . + βp x p .
Estimation des paramètres : β̂ = (X0 X)−1 X0 Y
Vecteur des valeurs ajustées : Ŷ = Xβ̂ = X(X0 X)−1 X0 Y
Vecteur des résidus : ε̂ = Y − Ŷ
Somme des carrés résiduelle : SCR = ni=1 ε̂2i
P
Somme des carrés totale : SCT = ni=1 (Yi − Ȳ )2

P
Somme des carrés expliquée : SCE = ni=1 (Ŷi − Ȳ )2

P
Équation d’analyse de la variance : SCT = SCE + SCR

Coefficient de détermination : R 2 = 1 − SCR/SCT
Une question :
Quel choix pour la matrice de plan d’expérience X ?
Multicolinéarité des variables explicatives, principe de parcimonie
⇒ critères de sélection de variables.
Impossibilité d’étudier TOUS les modèles linéaires possibles
⇒ méthodes algorithmiques de sélection.
Notations :
Pour un sous-ensemble ξ de {0, 1, . . . , p}, on note |ξ| son cardinal,
Xξ la matrice dont les vecteurs colonnes sont les x j pour j ∈ ξ,
βξ le vecteur composé des βj , pour j ∈ ξ,
[β̂]ξ le vecteur composé des β̂j pour j ∈ ξ,
βbξ = (X0ξ Xξ )−1 X0ξ Y l’estimateur des MCO de βξ dans
(Mξ ) Y = Xξ βξ + η.

Qualité de l’estimation, erreur quadratique moyenne (EQM)
En général, βbξ (6= [β̂]ξ ) est un estimateur biaisé de βξ .
Mais Var([β̂]ξ ) − Var(βbξ ) et Var(Xβ̂) − Var(Xξ βbξ ) semi-déf. ≥ 0
Définition
L’erreur quadratique
h moyenne iassociée à (Mξ ) est définie par
EQM(ξ) = E kX β − Xξ βbξ k2 .
Proposition
h i
EQM(ξ) = kX β − E[Xξ βbξ ]k2 + E kXξ βbξ − E[Xξ βbξ ]k2
= k(I − ΠXξ )X βk2 + |ξ|σ 2 .
Compromis biais-variance idéal ⇒ ξ ∗ idéal (oracle) inconnu !

Qualité de la prédiction, erreur quadratique moyenne de prédiction

(EQMP)
Soit xn+1,ξ une nouvelle valeur des variables explicatives de (Mξ ).
Définition
L’erreur quadratique
h moyenne de prédiction
i associée à (Mξ ) est définie par
EQMP(ξ) = E (Yn+1 − xn+1,ξ βξ ) .
b 2
Problème : EQM(ξ) et EQMP(ξ) sont inconnues ⇒ Nécessité de

construire des critères de sélection de ξ accessibles, ou d’estimer EQM(ξ)
ou EQMP(ξ).

Cadre général (conditions standards)
Somme des carrés résiduelle, cœfficient de détermination R 2

SCR(ξ)
Notation : R 2 (ξ) = 1 − SCT associé à (Mξ )
Proposition
Si ξ − ⊂ ξ, tous deux contenant ou pas l’indice de la constante, alors
R 2 (ξ) ≥ R 2 (ξ − )
,→ Minimiser la SCR ou maximiser le R 2 conduit à choisir le modèle le plus

complexe : la SCR et le R 2 sont de mauvais critères de sélection de
variables (mais ils restent utiles pour choisir entre deux modèles avec le
même nombre de variables explicatives).
,→ Deux possibilités : corriger le R 2 ou décider si l’augmentation du R 2 est
statistiquement significative (tests sous hypothèse gaussienne).

Cœfficient de détermination ajusté Ra2
Définition
Le cœfficient de détermination ajusté de (Mξ ) est défini par
Ra2 (ξ) = 1 − SCR(ξ)/(n−|ξ|) n−1 2

SCT /(n−1) = 1 − n−|ξ| 1 − R (ξ) .
Remarque : Ra2 (ξ) < R 2 (ξ) dès que |ξ| ≥ 2 (Ra2 (ξ) peut même être
négatif).

Critère du Cp de Mallows
EQM(ξ) = E[SCR(ξ)] − nσ 2 + 2|ξ|σ 2 .
Définition (Mallows, 1973)

c2 − n + 2|ξ|.
Le critère du Cp est défini par Cp (ξ) = SCR(ξ)/σ
Proposition
c2 Cp (ξ) estime sans biais EQM(ξ).
Si ξ ne dépend pas de Y , σ
,→ À utiliser sur un jeu de données "isolé".

,→ Règle usuelle : on retient (Mξ ) si Cp (ξ) ≤ |ξ|.
,→ Défaut : biais de sélection

Estimation de l’EQMP par validation croisée ou bootstrap
Définition
L’estimateur de EQMP(ξ) par validation Leave One Out est défini par
P 2
PRESS= ni=1 Yi − xi,ξ βbξ (i) , où βbξ (i) est l’estimateur des MCO de βξ
obtenu après suppression de la ième donnée.
Autres estimations possibles :

bootstrap par paires
(wild) bootstrap des résidus.

Cadre gaussien
Tests de validité de sous-modèles

Choix entre deux sous-modèles emboîtés l’un dans l’autre, l’un (Mξ ) défini
par ξ de cardinal |ξ| ≥ 2, validé, et l’autre, (Mξ− ), défini par ξ − tel que
ξ − ⊂ ξ et |ξ − | = |ξ| − 1.
SCR(ξ − )−SCR(ξ)
Statistique de test : F (Y ) = SCR(ξ)/(n−|ξ|) .
Sous l’hypothèse de validité de (Mξ− ), F (Y ) ∼ F(1, n − |ξ|).

On rejette donc (Mξ− ) au profit de (Mξ ) au niveau α si
F (y ) ≥ f1,n−|ξ|,(1−α)
Variante : réduction par la variance estimée dans le modèle complet (plus
pratique pour une méthode ascendante !).

Cadre gaussien
Critères de vraisemblance pénalisée

Sous l’hypothèse gaussienne, la log-vraisemblance est donnée par
ln L(Y , β, σ 2 ) = − n2 ln σ 2 − n2 ln(2π) − 2σ1 2 kY − Xβk2 .
Estimateurs du maximum de vraisemblance dans (Mξ ) :
f2 ξ = SCR(ξ)/n.
β̃ξ = βbξ et σ
f2 ξ ) = − n ln SCR(ξ) − n (1 + ln(2π)).
ln L(Y , βbξ , σ
2 n 2
Choisir un modèle maximisant la vraisemblance reviendrait donc à choisir
un modèle (Mξ ) ayant la plus petite SCR(ξ) donc ayant le plus de variables
⇒ nécessité de pénaliser les modèles ayant un grand nombre de variables

Cadre gaussien
On cherche un modèle (Mξ ) minimisant un critère de la forme :
f2 ξ ) + |ξ|f (n) = n ln SCR(ξ) + n(1 + ln(2π)) + |ξ|f (n),
−2 ln L(Y , βbξ , σ
n
où (|ξ| + 1)f (n) est un terme de pénalité positif (croissant avec n).
Définitions (Akaike,1973) (Schwarz, 1978)
Le critère AIC (Akaike’s Information Criterion) correspond à f (n) = 2 :
AIC (ξ) = n ln SCR(ξ)
n + n(1 + ln(2π)) + 2|ξ|.
Le critère BIC (Bayesian Information Criterion) correspond à f (n) = ln n :
BIC (ξ) = n ln SCR(ξ)
n + n(1 + ln(2π)) + |ξ| ln n.
Si n ≥ 8, la pénalité du critère BIC est plus lourde que celle de l’AIC :

les modèles choisis par le BIC ont moins de variables explicatives.
Lorsque n → +∞, la probabilité de sélectionner un modèle exact par
minimisation du critère BIC tend vers 1.
Cadre gaussien
Liens avec les tests de validité de sous-modèles

Critère du Ra2
−
Ra2 (ξ − ) < Ra2 (ξ) ⇔ (n − |ξ|) SCR(ξSCR(ξ)
)−SCR(ξ)
> 1 ⇔ F (Y ) > 1.
,→ Test avec valeur critique 1 au lieu de f1,n−|ξ|,(1−α) (qui est > 3.84).
Critère du Cp
Si F̃ (Y ) est la statistique de test de validité de sous-modèle variante
(réduction par σ c2 ), Cp (ξ − ) > Cp (ξ) ⇔ F̃ (Y ) > 2.

f2 − ) + |ξ − |f (n) > −2 ln L(Y , β̂ξ σ
−2 ln L(Y , β̂ξ− σ f2 ξ ) + |ξ|f (n) ⇔ F (Y ) >
ξ
(n − |ξ|) e 2f (n)/n − 1 .


Méthodes algorithmiques de sélection
Méthode de recherche exhaustive

Nombre de sous-modèles possibles pour p + 1 variables explicatives :
2p+1 ⇒ coût algorithmique prohibitif pour p grand, même modéré.
Aucun sens pour l’utilisation des tests de validité de sous-modèles.
Méthode de recherche ascendante (forward) On part du modèle
constant (aucune variable explicative), et on ajoute de manière séquentielle
les variables qui permettent d’optimiser le critère (maximiser le Ra2 ,
minimiser les autres critères), ou d’accepter la validité du modèle (test).
Méthode de recherche descendante (backward) Même principe, mais
on part du modèle complet et on élimine une à une les variables.
Méthode de recherche progressive (stepwise) Algorithme mixte qui
ajoute ou supprime une variable du modèle à chaque étape.
,→ Sélection et donc estimation finalement peu satisfaisantes, instables,
surtout inadaptées au cas p ≥ n...
Plan du cours

Régression linéaire régularisée
Régression ridge
Régression LASSO
Elastic-Net

Régression linéaire régularisée
Préambule : les variables explicatives x j sont standardisées, puis on suppose
que β = 0 et Ȳ = 0 (modèle sans constante). Concrètement, β0 est estimé
par Ȳ et Yi remplacé par Yi − Ȳ .
Un estimateur par minimisation du risque empirique régularisé (pour la

perte quadratique) est, dans le cadre de la régression linéaire, défini par :
n p
βp xip )2
X X
β̂λ ∈ argminβ∈Rp (Yi − β1 xi1 − β2 xi2 − ... − +λ |βj |q
i=1 j=1
∈ argminβ∈Rp kY − Xβk22 + λkβkqq ,
λ étant un paramètre positif, appelé paramètre de régularisation.
q = 2 ⇒ régression ridge
q = 1 ⇒ régression LASSO

Régression ridge
Définition et premières propriétés
L’estimateur ridge est défini pour λ > 0 par
β̂λridge ∈ argminβ∈Rp kY − Xβk22 + λkβk22 .
Proposition
Minimiser kY − Xβk22 + λkβk22 en β ∈ Rp est équivalent à minimiser
kY − Xβk22 sous la contrainte kβk22 ≤ r (λ), où r est bijective.
La matrice (X0 X + λIp ) est toujours définie positive, donc inversible,
et β̂λridge = (X0 X + λIp )−1 X0 Y .
L’estimateur ridge est biaisé, son biais est égal à −λ(X0 X + λIp )−1 β, sa
variance à σ 2 (X0 X + λIp )−1 X0 X(X0 X + λIp )−1 .
Noter que les valeurs propres de (X0 X + λIp ) sont plus élevées que celles de
X0 X, donc la variance de β̂λridge sera plus faible que celle de β̂.
Régression ridge
Ajustement du paramètre de régularisation
Lorsque λ = 0, β̂λridge = β̂.

Lorsque λ → +∞, β̂λridge = 0.
Lorsque λ augmente, le biais de β̂λridge a tendance à augmenter et la
variance à diminuer ⇒ compromis ?
Ajustement de λ
On appelle chemin de régularisation de la régression ridge l’ensemble des

fonctions λ 7→ (β̂λridge )j pour j = 1, . . . , p.
En pratique, on constate que le chemin de régularisation de la régression

ridge est continu, ne permettant pas un ajustement aisé de λ.
,→ Choix usuel par validation croisée V fold sur une grille finie de valeurs
de λ > 0.

Régression ridge
Rétrécissement
Décomposition en valeurs singulières (SVD) de X (p ≥ n) : X = UDV 0 , où

U de taille n × n, de vecteurs colonnes u 1 , . . . , u n ,
D est une matrice "diagonale" de taille n × p dont tous les éléments
vérifient d1 ≥ . . . ≥ dp ≥ 0,
V est de taille p × p, de vecteurs colonnes v 1 , . . . , v p ,
U et V sont orthogonales : UU 0 = U 0 U = In , VV 0 = V 0 V = Ip .
2
ridge 0 −1 0 0
Pp dj
On a alors Xβ̂λ = UD(D D + λIp ) D U Y = j=1 d 2 +λ hu j , Y iu j .
j
Pour l’estimateur des MCO (λ = 0) : Xβ̂ = pj=1 u j hu j , Y i.

P
,→ hu j , Y i correspond à la jième composante de Y dans la base des u j .

,→ La
régression
ridge multiplie cette composante par
2 2
dj / dj + λ ∈]0, 1[ : on dit qu’elle est "rétrécie" (shrinked).

Régression ridge
Rétrécissement et ACP
Les x j étant centrées, X0 X/n = VD 0 DV 0 /n en est la matrice de

variance-covariance empirique.
Rappel : si v est un vecteur de Rp de norme 1, Var(Xv ) = v 0 X0 Xv est
maximale pour v = v 1 et vaut d12 ⇒ z 1 = Xv 1 est la première composante
principale de X.
Les vecteurs propres orthogonaux v 1 , . . . , v p sont les directions principales
(ou directions de Karhunen Loeve) de X.
Les z j = Xv j = UDV 0 v j = dj u j sont les composantes principales de X.
,→ La régression ridge rétrécit peu les premières composantes principales

(pour lesquelles dj est grand), et davantage les dernières.

Régression LASSO
Définition et premières propriétés
L’estimateur LASSO (Least Absolute Selection and Shrinkage Operator)

(Tibshirani 1996) est défini pour λ > 0 par
β̂λlasso ∈ argminβ∈Rp kY − Xβk22 + λkβk1 .
La fonction L : β 7→ kY − Xβk22 + λkβk1 est convexe, non différentiable.

La solution du problème de minimisation peut ne pas être unique.
Le vecteur des valeurs ajustées en résultant Xβ̂λlasso , lui, est toujours unique.
Proposition
Minimiser kY − Xβk22 + λkβk1 en β ∈ Rp est équivalent à minimiser
kY − Xβk22 sous une contrainte de la forme kβk1 ≤ R̂λ
(R̂λ = kβ̂λlasso k1 ).

Régression LASSO
Parcimonie et rétrécissement
L’estimateur LASSO a l’avantage d’avoir un certain nombre de cœfficients

nuls lorsque λ est suffisamment grand
⇒ Estimateur parcimonieux / sélection de variables induite.
Explication graphique

Régression LASSO
Parcimonie et rétrécissement
Proposition : condition d’optimalité du premier ordre

β̂λlasso vérifie X0 Xβ̂λlasso = X0 Y − λẐ /2 avec
Ẑj ∈ [−1, 1] et Ẑj = signe β̂λlasso j si β̂λlasso j 6= 0.

Cas orthonormal :x j orthonormés, X0 X = Ip (et

plasso≤ n).
0
lasso lasso
j

Pour β̂λ j
6
= 0, β̂ λ j
= (x ) Y − λsigne β̂ λ j
/2, d’où
0 = (x ) Y − λsigne (x j )0 Y /2.
0
lasso j
lasso j

signe β̂λ j
= signe (x ) Y et β̂λ j
⇒ Si (x j )0 Y ≤ λ/2, β̂ lasso = 0.

λ j
Proposition

Si les x j sont orthonormés, β̂λlasso j = (x j )0 Y 1 − λ/ 2(x j )0 Y

.
+
,→ parcimonie et rétrécissement des MCO dans le cas orthogonal, mais

attention : pas de formule explicite dans le cas non orthogonal !
Régression LASSO
Sélection de modèles
Pour β ∈ Rpn , Sn (β) = {j ∈ {1, . . . , pn } / βj 6= 0} de cardinal qn .
XS = matrice composée des x j , j ∈ S.
On suppose que kX0Sn (β)c XSn (β) (X0Sn (β) XSn (β) )−1 sign(βSn (β) )k∞ ≤ 1 − γ
pour γ ∈]0, 1[ (irreprésentabilité), que η 0 X0Sn (β) XSn (β) η ≥ M1 ∀kηk2 = 1,
1−c2
qn = O(nc1 ), n 2 mini∈Sn (β) |βi | ≥ M2 , et E[ε2k
i ] < +∞, pour
0 ≤ c1 < c2 ≤ 1, M1 , M2 > 0, k ∈ N∗ .
Théorème (Zhao and Yu, 2006)
√ c2 −c1 √
Si les x j sont normés et λn / n = o(n 2 ) et (λn / n)2k /pn → +∞,
alors P(sign(β̂λlasso
n
) = sign(β)) ≥ 1 − O(pn nk /λ2k
n ) → 1.
,→ Condition d’irreprésentabilité = les variables non influentes (βj = 0) ne

sont pas trop corrélées à celles qui le sont.
,→ Sélection en général d’un trop grand nombre de variables ⇒ Bolasso ?

,→ Attention : si qnn ln pqnn > 12 , aucune sélection pertinente possible.
Régression LASSO
Borne de risque / inégalité oracle
Théorème
j sont normés, et ε ∼ N (0, σ 2 I ). Pour tout L > 0, si
Si les x p n
λ = 3σ 2 ln p + 2L, avec probabilité au moins égale à 1 − e −L ,
 
2 p
X β̂ lasso − β 2 ≤ infβ 0 6=0 kX β 0 − β 2 + 18σ (L + ln p)
 
1
X
λ β 0 6=0 ,
2  2 κ2 (β 0 ) j 
j=1
où κ(β 0 ) est ce qu’on appelle une constante de compatibilité, mesurant le

manque d’orthogonalité des x j , dépendant de β 0 .

Régression LASSO
Ajustement du paramètre de régularisation
Lorsque λ = 0, β̂λlasso = β̂.
Lorsque λ → +∞, β̂λlasso = 0.
On appelle chemin de régularisation de la régression lasso l’ensemble des

fonctions λ 7→ (β̂λlasso )j pour j = 1, . . . , p.
Ajustement de λ
Le chemin de régularisation de la régression lasso est linéaire par morceaux
(c.f. Condition d’optimalité du premier ordre), avec changements en un
nombre fini de points : les points de transition.
,→ Choix pour un nombre donné de cœfficients non nuls souhaités.
,→ Prédiction : choix sur les points de transition ? Choix usuel par
validation croisée V fold sur une grille finie de valeurs de λ > 0.
,→ Base de l’algorithme LARS (package R lars), qui calcule les
estimateurs LASSO en les points de transition et qui interpole linéairement
ensuite.
Régression LASSO
Algorithmes de calcul
Descente de coordonnées
Algorithme Coordinates descent
Variable
X, Y , λ:matrice n × p, vecteur de taille n, réel > 0
Début
Initialiser β = βin
Répéter
Pour j variant de 1 à p
Calculer Rj = (x j )0 (Y − k6=j βk x k )
P

Calculer βj = Rj 1 − λ/(2|Rj |) +
FinPour
Jusque Convergence de β
Retourner β
Fin

Régression LASSO
Algorithmes de calcul
Descente de coordonnées
Proposition

La fonction βj 7→ L(β) est minimum en βj = Rj 1 − λ/(2|Rj |) +
avec
Rj = (x j )0 (Y − k6=j βk x k ).
P
Pour une évaluation sur une grille Λ = {λ1 , . . . , λT } de valeurs rangées par
ordre décroissant, calculer β̂λlasso
1
avec βin = 0, puis β̂λlasso
2
avec
lasso
βin = β̂λ1 ...
Le coin du UseR : package glmnet
fit=glmnet(x,y)
plot(fit)
coef(fit,s=1) # affiche les coefficients pour un λ
predict(fit,newx=x[1:10,],s=1) # prédiction
Elastic Net
La méthode Elastic-Net combine les atouts des méthodes ridge et LASSO.

En particulier, elle pallie le défaut de l’estimation LASSO lorsque les X j
sont fortement corrélées.
L’estimateur Elastic-Net (Zou, Hastie 2005) est défini pour λ1 , λ2 > 0 par
β̂λEN
1 ,λ2
∈ argminβ∈Rp kY − Xβk22 + λ1 kβk1 + λ2 kβk22 .
Le coin du UseR : packages glmnet, elasticnet.

Plan du cours
Dantzig Selector
Adaptive LASSO
Group LASSO
Sparse-Group LASSO
Fused LASSO
Régression logistique (Group) LASSO

Dantzig Selector
Le Dantzig Selector (Candès, Tao 2007) est défini pour λ > 0 par
β̂λDS ∈ argminβ∈Rp kβk1 s.c. kX0 (Y − Xβ)k∞ ≤ λ.
Si {β ∈ Rp , kX0 (Y − Xβ)k∞ ≤ λ} n’est pas "parallèle" à la boule unité

pour la norme L1 , la solution est unique.
Propriétés similaires à celles de l’estimateur LASSO

(Bickel, Ritov, Tsybakov 2007)
Le coin du UseR : package flare

Adaptive LASSO
Problème :
estimateur LASSO biaisé ⇒ pondération "data-driven" de la pénalité ?
L’estimateur adaptive LASSO (Zou 2006) est défini pour λ, ν > 0 par
p
X |βj |
β̂λa−lasso ∈ argminβ∈Rp kY − Xβk22 +λ Gauss−lasso ,
β̂ν
j=1 j
où β̂νGauss−lasso = Πvect(X j , lasso )) Y .

j∈S(β̂λ
L’estimateur adaptive LASSO - le plus populaire sans doute - permet de

retrouver le support du vrai modèle sous des conditions plus faibles que
celles de l’estimateur LASSO.
Calcul par les algorithmes LARS et descente de coordonnées possible.
Le coin du UseR : packages lqa, parcor, lassogrp
Group LASSO
Sélection de groupes de variables / Group sparsity
Groupes de variables pré-définis par des sous-matrices Xl de X, pour
l = 1 . . . L, dont les colonnes correspondent à un groupe donné de colonnes
de X, et les vecteurs βl de longueur nl associés.
L’estimateur Group LASSO (Yuan, Lin 2007) est défini pour λ > 0 et
K1 , . . . , KL matrices définies positives nl × nl , par
L q
β̂λgrp−lasso ∈ argminβ∈Rp kY − Xβk22 + λ
X
βl0 Kl βl .
l=1
√
βl0 Kl βl =
p
Cas particulier : Kl = nl Inl , nl kβl k2 .
Pour appliquer l’algorithme de descente de coordonnées, les Xl doivent être
orthonormales : condition restrictive.
Le coin du UseR : algorithme LARS implémenté dans lassogrp,
algorithme Blockwise-Majorization-Descent implémenté dans gglasso.
Sparse-Group LASSO
Sparse-Group sparsity
Groupes de variables pré-définis par des sous-matrices Xl de X, pour

l = 1 . . . L, dont les colonnes correspondent à un groupe donné de colonnes
de X, et les vecteurs βl de longueur nl associés.
L’estimateur Sparse-Group LASSO (Simon et al. 2013) est défini pour

λ, µ > 0 et K1 , . . . , KL matrices définies positives nl × nl , par
L q
X
β̂λSGL ∈ argminβ∈Rp kY − Xβk22 + λ βl0 Kl βl + µkβk1 .
l=1
Le coin du UseR : package SGL.

Fused LASSO
Variation sparsity
Situation où peu d’incréments βj+1 − βj sont non nuls.
L’estimateur Fused LASSO (Tibshirani et al. 2005) est défini pour λ > 0
par
p−1
X
f −lasso 2
β̂λ ∈ argminβ∈Rp kY − Xβk2 + λ |βj+1 − βj |.
j=1
Pp
,→ Idem au LASSO après un changement de variables : Z j = k=j Xk.

Rappel des notations
Données observées de type entrée-sortie : d1n = {(x1 , y1 ), . . . , (xn , yn )}

avec xi ∈ Rp ), yi ∈ {−1, 1} pour i = 1 . . . n.
Objectif : prédire la sortie y associée à une nouvelle entrée x,

sur la base de d1n (problème de discrimination binaire).
Modèle non paramétrique :

On suppose que d1n est l’observation d’un n-échantillon
D1n = {(X1 , Y1 ), . . . , (Xn , Yn )} d’une loi conjointe P sur Rp ×{−1, 1},
totalement inconnue.
On suppose que x est une observation de la variable X , (X , Y ) étant un
couple aléatoire de loi conjointe P indépendant de D1n .

Modèle de régression logistique :
xi = (xi1 , . . . , xip )0 , π(xi ) = P(Yi = 1|Xi = xi )

On suppose que :
π(xi )
ln = β0 + β1 xi1 + . . . + βp xip , 1 ≤ i ≤ n.
1 − π(xi )
Pn vraisemblance :1 Ln (Y1 , . . . , Ypn , β0 , β) =

Log
1 p
i=1 Yi (β0 + β1 xi + . . . + βp xi ) − ln 1 + exp(β0 + β1 xi + . . . + βp xi )
Les variables qualitatives sont transformées en variables indicatrices

(dummy variables).

Des groupes de variables sont créés de la façon suivante : toutes les
modalités d’une variable qualitative sont regroupées dans un même groupe,
les variables quantitatives sont considérées individuellement.
Notations idem à la régression Group LASSO : Xl de taille n × nl , pour
l = 1 . . . L, βl de longueur nl .
L’estimateur (Group) LASSO logistique (Lokhorst 1999, Meier, van de

Geer, Bühlmann 2008) est défini pour λ > 0 par
L
√
β̂λlogGL ∈ argminβ0 ∈R,β∈Rp − Ln (Y1 , . . . , Yn , β0 , β) + λ
X
nl kβl k2 .
l=1
Algorithme de descente de coordonnées par blocs.

Le coin du UseR : package grplasso.

Plan du cours

Apprentissage de dictionnaire
Kernel Ridge regression

Apprentissage de dictionnaire
On considère un dictionnaire de fonctions D = {ηj , j = 1 . . . p},

ηj : X → R d’un espace de Hilbert (H, k.kH ) et on se restreint aux
fonctions de régression de la forme :
η(x) = β1 η1 (x) + . . . + βp ηp (x).
Ce dictionnaire peut être choisi pour permettre à la fonction de régression

de s’adapter à une certaine structure de parcimonie de X.
Un estimateur de minimisation de risque empirique régularisé, pour la

fonction de perte l, basé sur le dictionnaire D, est défini pour λ > 0 par
n
X
β̂λ ∈ argminβ∈Rp l(Yi , β1 η1 (xi )+. . .+βp ηp (xi ))+λkβ1 η1 +. . .+βp ηp k2H .
i=1

Kernel Ridge regression
Cas particulier :
D = {k(xj , .), j = 1 . . . n}, où k est un noyau symétrique
auto-reproduisant ou noyau de Mercer, et H est un espace
auto-reproduisant (Reproducing Kernel Hilbert Space).
Propriété d’auto-reproduction : hk(xj , .), k(xi , .)iH = k(xi , xj ).
Notations : K matrice des k(xi , xj ) i,j∈{1,...,n} , β = (β1 , . . . , βn )0 .
Pn 2 2
i=1 (Yi − β1 k(x1 , xi ) − . . . − βn k(xn , xi )) = kY − K βk2
kβ1 k(x1 , .) + . . . + βn k(xn , .)k2H = β 0 K β
L’estimateur Kernel Ridge est défini pour λ > 0 par
β̂λkridge ∈ argminβ∈Rn kY − K βk22 + λ(β 0 K β).
Solution explicite : β̂λkridge = (K + λIn )−1 Y .

Apprentissage 1516 Lasso

Transféré par

Droits d'auteur :

Formats disponibles

Apprentissage 1516 Lasso

Transféré par

Informations du document

Description originale:

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Apprentissage 1516 Lasso

Transféré par

Droits d'auteur :

Formats disponibles

Apprentissage Statistique : Partie III

Magalie Fromont (Université Rennes 2)

Ensai, 2015 - 2016

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 1 / 46

1 Régression linéaire : rappels

2 Régression linéaire régularisée : régressions ridge, LASSO, Elastic Net

4 Méthodes à noyaux pour la régression non linéaire

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 2 / 46

1 Régression linéaire : rappels

2 Régression linéaire régularisée : régressions ridge, LASSO, Elastic Net

4 Méthodes à noyaux pour la régression non linéaire

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 3 / 46

Rappel des notations

Données observées de type entrée-sortie : d1n = {(x1 , y1 ), . . . , (xn , yn )}

Objectif : prédire la sortie y associée à une nouvelle entrée x,

Modèle non paramétrique :

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 4 / 46

Modèle de régression linéaire : xi = (xi1 , . . . , xip )0 . On suppose que :

Yi = β0 + β1 xi1 + β2 xi2 + . . . + βp xip + εi , 1 ≤ i ≤ n,

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 5 / 46

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 6 / 46

,→ minimisation de risque empirique pour la perte quadratique, sur

Somme des carrés totale : SCT = ni=1 (Yi − Ȳ )2

Somme des carrés expliquée : SCE = ni=1 (Ŷi − Ȳ )2

Équation d’analyse de la variance : SCT = SCE + SCR

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 8 / 46

Compromis biais-variance idéal ⇒ ξ ∗ idéal (oracle) inconnu !

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 9 / 46

Qualité de la prédiction, erreur quadratique moyenne de prédiction

Problème : EQM(ξ) et EQMP(ξ) sont inconnues ⇒ Nécessité de

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 10 / 46

Somme des carrés résiduelle, cœfficient de détermination R 2

,→ Minimiser la SCR ou maximiser le R 2 conduit à choisir le modèle le plus

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 11 / 46

Cœfficient de détermination ajusté Ra2

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 12 / 46

Définition (Mallows, 1973)

,→ À utiliser sur un jeu de données "isolé".

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 13 / 46

Estimation de l’EQMP par validation croisée ou bootstrap

Autres estimations possibles :

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 14 / 46

Tests de validité de sous-modèles

Sous l’hypothèse de validité de (Mξ− ), F (Y ) ∼ F(1, n − |ξ|).

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 15 / 46

Critères de vraisemblance pénalisée

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 16 / 46

Si n ≥ 8, la pénalité du critère BIC est plus lourde que celle de l’AIC :

Liens avec les tests de validité de sous-modèles

Critères de vraisemblance pénalisée

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 18 / 46

Méthode de recherche exhaustive

1 Régression linéaire : rappels

2 Régression linéaire régularisée : régressions ridge, LASSO, Elastic Net

4 Méthodes à noyaux pour la régression non linéaire

Magalie Fromont (Université Rennes 2) Apprentissage Statistique - Partie III 20 / 46

Un estimateur par minimisation du risque empirique régularisé (pour la

∈ argminβ∈Rp kY − Xβk22 + λkβkqq ,

λ étant un paramètre positif, appelé paramètre de régularisation.