Régression pénalisée : le Lasso

Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Régression pénalisée : le Lasso
V. Viallon
M2 Maths Appli
Compléments
Introduction
Le Lasso
Sélection de modèle
1
Introduction
2
Le Lasso
3
Sélection de modèle
4
Estimation
5
Prédiction
6
Compléments
Estimation
Prédiction
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Cadre considéré dans ce cours
On supposera disposer d’un échantillon
(x1 , Y1 ), . . . , (xn , Yn ) tel que
Yi = xiT β∗ + ξi ,
i = 1, . . . , n,
où les ξi ∼ N(0, σ2 ) sont i.i.d., les Yi ∈ IR sont aléatoires
mais les xi ∈ IRp sont déterministes, et le paramètre
β∗ ∈ IRp est inconnu.
⇒ régression linéaire sur design fixe, avec erreurs gaussiennes
(sans intercept).
Exemple typique :
Yi : niveau d’expression du gène G chez l’individu i
xi = (xi 1 , . . . , xip )T : SNPs pour l’individu i (à valeurs dans
{0, 1, 2} généralement).
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Ecriture matricielle
Le modèle peut se réécrire sous forme matricielle
Y = Xβ∗ + ξ
où
Y = (Y1 , . . . , Yn )T ∈ IRn et ξ = (ξ1 , . . . , ξn )T ∈ IRn
X = (x1T , . . . , xnT )T ∈ IRn×p .
Rq: Dans ce cours, on considère que p = p(n) (typiquement,
fonction croissante de n).
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Cadre "standard"
n p, et rang(X) = p
alors l’estimateur des MCO
˜ = arg min kY − Xβk2
β
2
p
β∈IR
est donné par
˜ = (XT X)−1 XT Y.
β
On a
˜ − β∗ )k2
kX(β
2
∼ χ2p
σ2
et donc [exercice: pour (ii ), utilisez l’inégalité de
Chebyshev]
˜ − β∗ )k2 σ2 p
kX(β
2
(i ) IE
=
n
n
p ˜ − β∗ )k2
kX(β
2
(ii )
= OIP
.
n
n
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Cadre de la grande dimension
p > n (voire p n)
alors rang(X) < p (et donc XT X n’est pas inversible)
l’estimateur des MCO n’est plus unique (même formule
avec pseudo-inverse de Moore-Penrose)
et il "overfit" les données
notamment
˜ − β∗ )k2
kX(β
2
= OIP (1).
n
(Exemple avec n = p et X = In .)
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
"Solutions"
Hypothèse de parcimonie : β∗ est "creux", i.e.
s0 := ]{j : β∗j 6= 0} p
(et surtout n).
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
"Solutions"
Hypothèse de parcimonie : β∗ est "creux", i.e.
s0 := ]{j : β∗j 6= 0} p
(et surtout n).
Alors, si l’on connaissait l’ensemble J0 := {j : β∗j 6= 0}, on
s 0
→IP 0.
aurait une erreur de prédiction : OIP
n
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
"Solutions"
Hypothèse de parcimonie : β∗ est "creux", i.e.
s0 := ]{j : β∗j 6= 0} p
(et surtout n).
Alors, si l’on connaissait l’ensemble J0 := {j : β∗j 6= 0}, on
s 0
→IP 0.
aurait une erreur de prédiction : OIP
n
⇒ Sélection de variables
meilleure interprétabilité du modèle
meilleur pouvoir prédictif aussi
Autre hypothèse possible : peu de coefficients "grands"
(plutôt que peu de coefficients non nuls).
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Principe général de la régression pénalisée
Pour un λ > 0,
φP (λ) := minp
β∈IR
kY − Xβk22
+ λP(β).
2n
Si λ = 0 : MCO
Différents choix pour P(β) :
kβk0 = ]{j : βj 6= 0} : Théorie +++, Implémentation –
AIC : λ = σ2 /n
BIC : λ = σ2 log(n)/(2n)
Pb "combinatoire" : on doit énumérer les 2p modèles
possibles
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Principe général de la régression pénalisée
Pour un λ > 0,
φP (λ) := minp
β∈IR
kY − Xβk22
+ λP(β).
2n
Si λ = 0 : MCO
Différents choix pour P(β) :
kβk0 = ]{j : βj 6= 0} : Théorie +++, Implémentation –
P
kβk1 = j |βj | (Lasso) : Théorie : ++, Implémentation ++
P
kβk22 = j β2j (Ridge) : Théorie : +, Implémentation ++
...
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Least Absolute Shrinkage and Selection Operator
Pour λ > 0,
kY − Xβk22
ˆ
+ λkβk1 .
β(λ)
∈ Arg minp
β∈IR
2n
Problème convexe, mais la solution n’est pas
nécessairement unique
Si λ = 0 : MCO
la solution est typiquement creuse : plus λ est grand, et
ˆ
plus β(λ)
est creux (en "gros").
(1)
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Propriétés de sélection du Lasso: intuition
Le problème d’optimisation
φ(λ) := minp
β∈IR
kY − Xβk22
+ λkβk1 .
2n
est équivalent, pour une certaine valeur de T = T (λ), à
˜ ) :=
φ(T
min
kβk1 6T
kY − Xβk22
.
2n
Ex: dans le cas où n = p et xi = 1Ii : i -ème composante vaut 1,
les autres sont nulles. On cherche alors à résoudre
˜ ) :=
φ(T
min
kβk1 6T
n
1 X
(Yi − βi )2 .
2n
i =1
Introduction
Le Lasso
Sélection de modèle
Cône `1
Emprunté aux slides de J. Mairal
Estimation
Prédiction
Compléments
Introduction
Le Lasso
Sélection de modèle
Cône `2
Emprunté aux slides de J. Mairal
Estimation
Prédiction
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Propriétés du Lasso : que peut-on espérer ?
On peut espérer qu’avec grande probabilité, sous certaines
hypothèses et pour des choix appropriés de λ,
ˆ ≈ β∗
Estimation : β
ˆ j (λ) 6= 0}.
Sélection : Jb (λ) ≈ J0 , où Jb (λ) = {j : β
ˆ − β∗ )k2 ≈ s0 /n
Prédiction : n −1 kX(β
2
On précisera plus tard la signification de ≈ dans chacun des cas
précédents.
Remarque : "Difficulté" pour l’analyse des propriétés des
estimateurs Lasso (par rapport aux MCO): pas de forme
explicite (on va utiliser des conditions d’optimalité qui
caractérisent les solutions du problème (1)).
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Une première condition d’optimalité
Pour simplifier les notations, on suppose que λ est fixé et on
ˆ = β(λ),
ˆ
pose β
une solution de (1).
Lemme 2.1
Dénotons le gradient de (2n)−1 kY − Xβk22 par
ˆ soit
G(β) = −XT (Y − Xβ)/n. Alors une CNS pour que β
solution du problème (1) est
ˆ = −λ sign(β
ˆ k ) si β
ˆk =
Gk (β)
6 0
ˆ
ˆ
|Gj (β)| 6 λ si βj = 0
Cette caractérisation nous sera utile pour établir les propriétés
de sélection du Lasso.
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Lasso et soft-thresholding
Elle nous permet également de déduire le résultat suivant.
Si XT X/n = Ip (⇒ p 6 n), alors Lasso =
soft-thresholding :
ˆ j (λ) = sign(β
˜ j )(|β
˜ j | − λ)+ .
β
⇒ Rq : Le Lasso sélectionne.. mais shrinke aussi : les estimateurs
sont généralement biaisés (cf. regularization path).
Diverses extensions pour débiaiser les estimateurs Lasso
P
ˆ init | : on pénalise
Adaptive Lasso (Zou): kβk1 ⇒ j |βj |/|β
j
init
ˆ
plus βj si |βj | est petit.
Lasso-OLS Hybrid (= Relaxed Lasso de Meinshausen, avec
φ = 0)
On reviendra sur ces approches plus tard.
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Regularization path
Linear Lasso
0
7
15
26
37
0.2
7
0.1
3
0.0
30
32
17
36
14
13
23
26
24
10
29
19
20
11
33
37
2
18
25
31
21
34
27
12
38
35
28
9
−0.1
1
22
8
4
−0.2
Coefficients
15
5
6
0.0
0.5
1.0
L1 Norm
1.5
2.0
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Une seconde condition d’optimalité
Lemme 2.2
ˆ soit solution de (1) est que pour
Une autre CNS pour que β
tout β ∈ IRp
2
ˆ 2
kY − Xβk
2
ˆ 1 6 kY − Xβk2 + λkβk1
+ λkβk
2n
2n
En particulier, on a la CN suivante :
∗ 2
ˆ 2
kY − Xβk
2
ˆ 1 6 kY − Xβ k2 + λkβ∗ k1
+ λkβk
2n
2n
Cette caractérisation nous sera utile pour étudier les propriétés
d’estimation et d’erreur de prédiction du Lasso.
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
"Sparsistency" du Lasso
Une procédure de sélection de variables est dite consistante
en sélection de variables, ou "sparsistent", ssi le support du
vecteur estimé est identique au support du vecteur
théorique, Jb = J0 , avec grande probabilité.
Intuitivement, 2 types d’hypothèses sont nécessaires pour
la sparsistency.
conditions d’identifiabilité
beta-min conditions
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Hypothèses liées à l’identifiabilité
On supposera qu’il existe un paramètre de non-représentabilité
γ ∈ (0, 1] et une constante Cmin > 0 tels que
−1
maxc kXjT XJ0 (XT
J0 XJ0 ) k1 6 (1 − γ)
j ∈J0
Λmin
XT X J J0
n
0
> Cmin
(2)
(3)
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Interprétations de ces hypothèses
Hypothèse de valeur propre minimale (3) : identifiabilité
du problème restreint à J0 .
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Interprétations de ces hypothèses
Hypothèse de valeur propre minimale (3) : identifiabilité
du problème restreint à J0 .
Condition de non-représentabilité (2) :
−1
pour tout j ∈ J0c , kXjT XJ0 (XT
k1 : norme `1 du
J0 XJ0 )
paramètre de la régression linéaire de Xj sur XJ0 , estimé
par MCO.
un design idéal est tel que Xj est orthogonal aux colonnes
de la matrice XJ0 , auquel cas on aurait γ = 1.
En grande dimension, on ne peut pas avoir cette
orthogonalité stricte, mais on peut espérer être dans une
situation de "quasi-orthogonalité".
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Liens avec d’autres hypothèses "classiques"
Dans ce cours, on se contentera de présenter des résultats
obtenus sous la condition de non-représentabilité.
On peut aussi travailler sous les hypothèses suivantes
hypothèse d’incohérence mutuelle : le paramètre
d’incohérence de la matrice de design est "petit":
X T Xk j
ι(1) (X) = max 6 ν.
j 6=k
n
RIP (restricted isometry property) : la constante
d’isométrie restreinte est "petite"
XT X
S S
ι(2)
(X)
=
inf
:
∀S
:
|S
|
6
s,
−
I
6
.
s×s
s
2
n
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Résultat principal
−1 T
Soit ΠX⊥ := In×n − XJ0 (XT
J 0 X J 0 ) XJ 0 .
J0
Théorème 3.1
Sous les hypothèses (2) et (3) précédentes, l’estimateur
Lasso vérifie, pour λ > (2/γ)kXT
ξ/nk∞ ,
J0c ΠX⊥
J0
ˆ
1 Unicité : Le Lasso (1) a une solution unique β.
2
3
Absence de "faux positif" : Jb ⊆ J0 .
ˆ J − β∗ k∞ 6 B (λ, X) avec
Borne sur la norme `∞ : kβ
J0
0
XT X −1
XT X −1 ξ J0 J0
J0 J0
B (λ, X) = XT
+
λ
J0
∞
n
n ∞
n
4
Absence de "faux négatif" : le Lasso est sparsistent si
mink ∈J0 |β∗k | > B (λ, X).
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Corollaire 3.1
On suppose que les ξi ∼ N(0, σ2 ), et que la matrice de design
X est déterministe, vérifie les conditions (2) et (3), et a ses
colonnes normalisées, telles que
n −1/2 maxj =1,...,p kXj k2 6 C , pour une constante C > 0.
Pour le choix
s
2C σ 2 log(p − s0 ) + δ2
,
λ=
γ
n
pour une constante δ > 0, on a le résultat suivant, avec
2
2
probabilité supérieure à 1 − 2e −δ /2 − 2e −ε /2 : pour tout
ˆ est unique, de support Jb ⊆ J0
ε > 0, la solution optimale β
et telle que
r
√
σ
2 log s0 + ε2 λ s0
∗
ˆ
kβ − β k∞ 6 √
+
.
n
Cmin
Cmin
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Preuve
On doit premièrement montrer que ce choix de λ vérifie, avec
grande probabilité, la condition sur le λ du Théorème 3.1. Soit,
pour tout j ∈ J0c , Vj = XjT ΠX⊥ ξ/n. Ces variables aléatoires
J0
sont gaussiennes, centrées, et de variance bornée par
σ2 kΠX⊥ Xj /nk22 6 σ2 kXj /nk22 6 σ2 C 2 /n.
J0
On en déduit que
IP(maxc |Vj | > t ) 6 2(p − s0 )e −nt
2 /(2C 2 σ2 )
j ∈J0
et donc que
r
2
2 log(p − s0 ) + δ2 ξ
T
6 2e −δ /2
IP X ΠX⊥ > C σ
J0 n ∞
n
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Preuve (suite)
−1 XT ξ
T
J0
ek = e T XJ0 XJ0
Soit V
k
n
n , pour tout k ∈ J0 . On montre
ek sont gaussiennes, centrées de variance
facilement que les V
bornée par
T
σ2
σ2 XJ0 XJ0 −1 .
6
2
n
n
Cmin n
En procédant comme précédemment, il vient donc
r
2 log s + ε2 2
σ
0
ek | > √
IP
max |V
6 2e −ε /2 .
k =1,...,s0
n
Cmin
Comme enfin
√
T
XT X −1 √ s0
XJ0 XJ0 −1 J0 J0
,
6 s0 6
∞
2
n
n
Cmin
le résultat du Lemme est donc vérifié avec probabilité
2
2
supérieure à 1 − 2e −δ /2 − 2e −ε /2 .
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Corollaire 3.2
On suppose que la matrice de design X vérifie les
hypothèses du Théorème 3.1, que p = O(exp(n δ3 )),
s0 = O(n δ1 ), et que β2min > n −(1−δ2 ) avec
0 < δ1 + δ3 < δ2 < 1.
Si λn = n −(1−δ4 )/2 pour un δ4 ∈ (δ3 , δ2 − δ1 ), alors le Lasso
est sparsistent avec probabilité supérieure à 1 − exp(−c1 n δ4 ),
pour une certaine constante c1 .
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Corollaire 3.2
On suppose que la matrice de design X vérifie les
hypothèses du Théorème 3.1, que p = O(exp(n δ3 )),
s0 = O(n δ1 ), et que β2min > n −(1−δ2 ) avec
0 < δ1 + δ3 < δ2 < 1.
Si λn = n −(1−δ4 )/2 pour un δ4 ∈ (δ3 , δ2 − δ1 ), alors le Lasso
est sparsistent avec probabilité supérieure à 1 − exp(−c1 n δ4 ),
pour une certaine constante c1 .
p peut croître exponentiellement avec n
s0 /p ≈ n δ1 exp(−n δ3 ) décroît exponentiellement avec n.
Si p (et s0 ) fixe, λ = n −(1−δ)/2 et βmin > c2 n −(1−δ)/2
(pour δ > 0) assurent la sparsistency avec probabilité
> 1 − 2 exp(−c1 nδ), pour une constante c1 > 0.
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Une condition suffisante d’échec pour le Lasso
Théorème 3.2
On suppose que la condition sur la valeur propre minimale
(3) est vérifiée et que le vecteur de bruit ξ a une
distribution symétrique autour de 0.
1
Si la condition de non-représentabilité (2) n’est pas
vérifiée, en particulier si
∗
maxc |XjT XJ0 (XT
J0 XJ0 )sign(βJ0 )| = 1 + ν > 1,
j ∈J0
alors pour tout λn > 0 et n
ˆ = sign(β∗ )] 6 1/2.
IP[sign(β)
(4)
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Lemme 2.1 "étendu"
Lemme 3.1
1
ˆ ∈ IRp est optimal ssi ∃ˆ
ˆ 1 tel que
Un vecteur β
z ∈ ∂kβk
XT X ˆ
XT ξ
(β − β∗ ) −
+ λˆ
z=0
n
n
2
Pour tout j ∈ Jb c , si |ˆ
zj | < 1 alors toute solution
¯
¯ j = 0.
optimale β du Lasso est telle que β
(5)
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Lemme 2.1 "étendu"
Lemme 3.1
1
ˆ ∈ IRp est optimal ssi ∃ˆ
ˆ 1 tel que
Un vecteur β
z ∈ ∂kβk
XT X ˆ
XT ξ
(β − β∗ ) −
+ λˆ
z=0
n
n
2
(5)
Pour tout j ∈ Jb c , si |ˆ
zj | < 1 alors toute solution
¯
¯ j = 0.
optimale β du Lasso est telle que β
Preuve : D’après la règle de Fermat (cf. cours de N.P.),
ˆ ∈ Argminβ (2n)−1 kY − Xβk2 + λkβk1 est équivalent à :
β
2
ˆ − Y) + λˆ
ˆ 1 tel que 1 XT (Xβ
z = 0. La partie (1) du
∃ˆ
z ∈ ∂kβk
n
Lemme découle ensuite de l’égalité Y = Xβ∗ + ξ. On en déduit
ˆ = −λˆ
également le résultat du Lemme 2.1 puisque Gj (β)
zj .
Introduction
Le Lasso
Preuve
Sélection de modèle
Estimation
Prédiction
Compléments
(suite)
Pour le point (2), raisonnons par l’absurde.
´ une autre solution du problème Lasso (1) et j ∈ Jb c
Soit β
´ j 6= 0.
tel que |ˆ
zj | < 1 et β
Puisque le problème Lasso est convexe, l’ensemble de ses
solutions est convexe et donc, pour tout ρ ∈ [0, 1],
ˆ ρ = (1 − ρ)β
ˆ + ρβ
´
β
est également solution du Lasso.
ˆ ρ,j 6= 0 (par
Pour tout ρ ∈ (0, 1], on a par ailleurs β
construction), et donc, d’après le résultat du Lemme 2.1,
ˆ ρ )| = λ.
|Gj (β
ˆ ρ )|, on a donc
En définissant la fonction f (ρ) = |Gj (β
f (0) < λ et f (ρ) = λ, pour tout ρ ∈ (0, 1].
Ceci est en contradiction avec la continuité de la fonction f .
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Primal-Dual Witness construction
ˆ z
On va chercher à construire une paire (β,
ˆ) ∈ IRp × IRp de la
manière suivante :
ˆ J c = 0.
1 Soit β
0
2
ˆJ , z
ˆ J ∈ IRs0 une solution du problème
Soit (β
ˆJ0 ), avec β
0
0
Lasso oraculaire:
kY − X β k2
J0 J0 2
+ λkβJ0 k1
βJ0 ∈IRs0
2n
ˆ J ∈ Arg min
β
0
ˆ J k1 tel que GJ (β
ˆ J ) + λˆ
zJ0 = 0.
et z
ˆJ0 ∈ ∂kβ
0
0
0
3
On résout, en z
ˆJ0c ∈ IRp−s0 , l’équation (5), et on vérifie la
condition de faisabilité stricte, |ˆ
zj | < 1, est vérifiée pour
tout j ∈ J0c )
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
PDW et sparsistency du Lasso
6= méthode de résolution numérique pour le Lasso !!
Lemme 3.2
Si la construction PDW aboutit, alors sous l’hypothèse de
ˆ J , 0) est l’unique
valeur propre minimale (3), le vecteur (β
0
solution du Lasso.
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
PDW et sparsistency du Lasso
6= méthode de résolution numérique pour le Lasso !!
Lemme 3.2
Si la construction PDW aboutit, alors sous l’hypothèse de
ˆ J , 0) est l’unique
valeur propre minimale (3), le vecteur (β
0
solution du Lasso.
Preuve : Sous la condition de faisabilité stricte, le Lemme 3.1
¯ est telle que β
¯ j = 0 pour
assure que toute solution du Lasso β
c
¯
tout j ∈ J0 . Toute solution est donc de la forme (βJ0 , 0), et on
¯ J en résolvant le Lasso oraculaire.
peut donc obtenir β
0
D’autre part, sous l’hypothèse (3), le Lasso oraculaire est
strictement convexe, et admet donc une solution unique.
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Preuve du Théorème 3.1
Pour établir les points (1) et (2), au vu du Lemme 3.2, il
suffit de montrer que la faisabilité stricte est vérifiée dans
le PDW.
ˆJ , z
En réécrivant (5) par bloc, on a β
ˆJ et z
ˆJ qui vérifient:
0
1
n
"
XT
J0 X J0
XT
J c XJ 0
0
c
XT
J 0 XJ 0
T
XJ c XJ0c
#
0
ˆ J − β∗
β
J0
0
0
1
−
n
0
"
0
XT
J0 ξ
XT
Jc ξ
#
+λ
0
z
ˆ J0
z
ˆJ0c
= 0.
On a donc
ˆ J − β∗ =
β
J0
0
XT XJ −1 h XT ξ
J0
n
0
J0
n
− λˆ
zJ0
i
et
ξ J0
nλ
T
−1
z
ˆJ0c = XT
ˆ J 0 + XT
J0c XJ0 (XJ0 XJ0 ) z
J0c ΠX⊥
=: µ + V
(6)
Introduction
Le Lasso
Sélection de modèle
Preuve du Théorème 3.1
Estimation
Prédiction
Compléments
(suite)
Sous la condition de non-représentabilité, on a
kµk∞ 6 (1 − γ).
La condition sur λ assure pour sa part que kV k∞ 6 γ/2.
La faisabilité stricte suit facilement en utilisant
kˆ
zJ0c k∞ 6 kµk∞ + kV k∞ 6 (1 − γ/2) < 1.
Pour le point (3), il vient de (6) que
XT X −1 XT ξ XT X −1 J0 J0
J0 J0 J0
ˆ J − β∗ k∞ 6 kβ
+
λ
.
J0
0
∞
∞
n
n
n
La preuve du point (4) est directe.
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Restricted Eigenvalue condition
Définition 4.1
Soit, pour tout α > 0, le "cône" Cα (J0 ) de IRp défini par
Cα (J0 ) = {∆ ∈ IRp : k∆J0c k1 6 αk∆J0 k1 }
Définition 4.2
La matrice de design X vérifie la Restricted Eigenvalue
condition sur J0 , avec les paramètres (κ, α), avec κ > 0, si
1
kX∆k22 > κk∆k22
n
pour tout ∆ ∈ Cα (J0 ).
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Intuition pour la RE
Considérons la version contrainte avec T = kβ∗ k1 .
Soit Ln (β) = kY − Xβk22 /(2n).
ˆ ≈ Ln (β∗ ).
Si n → ∞, on peut espérer Ln (β)
ˆ ≈ β∗ ?
Sous quelles conditions cela implique-t-il que β
D’après Wainwright (unpublished)
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Intuition pour la RE (suite)
En multivarié, la courbure est liée au Hessien de Ln :
(XT X)/n : si cette matrice est définie positive, i.e.,
1
kX∆k22 > κk∆k22 > 0 pour tout ∆ ∈ IRp \ {0},
n
alors Ln aurait une courbure élevée dans toutes les
directions.
Impossible en grande dimension (p > n) : il y a forcément
au moins p − n directions selon lesquelles Ln est "plate".
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Résultat principal
Théorème 4.1
On suppose que X vérifie la condition RE sur J0 avec les
paramètres (κ, 3). Alors toute solution du Lasso avec
ˆ − β∗ k2 6 3λ√s0 /κ.
λ > 2kXT ξ/nk∞ est telle que kβ
Corollaire 4.1
Supposons que les conditions du Théorème 4.1 et les
hypothèses de normalité des résidus ξi ∼ N(0, σ2 ) et de
standardisation des variables, n −1/2 maxj =1,...,p kXj k2 6 C
(pour une constante C 6 0) sont vérifiées. Alors, pour le
choix
r
2 log p + δ2
λ = 2C σ
n
le résultat du Théorème 4.1 est vérifié avec probabilité
2
supérieure à 1 − 2e −δ /2 .
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Preuve du corollaire
Sous les conditions du corollaire, la quantité kXT ξ/nk∞
correspond au maximum de la valeur absolue de p variables
gaussiennes, centrées et de variance bornée par C 2 σ2 /n.
En procédant comme précédemment, on obtient alors que pour
tout δ > 0,
r
2
2 log p + δ2 6 2e −δ /2 .
IP kXT ξ/nk∞ > C σ
n
Le résultat du Théorème 4.1 permet donc de conclure qu’avec
2
une probabilité supérieure à 1 − 2e −δ /2 , on a
r
6C σ 2s0 log p + s0 δ2
∗
ˆ
kβ − β k2 6
.
κ
n
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Preuve du Théorème 4.1
b = (β
ˆ − β∗ ) ∈ C3 (J0 )
1 Si λ > 2kXT ξ/nk , alors ∆
∞
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Preuve du Théorème 4.1
b = (β
ˆ − β∗ ) ∈ C3 (J0 )
1 Si λ > 2kXT ξ/nk , alors ∆
∞
ˆ est optimal, on a les propriétés suivantes
Puisque β
∗ 2
ˆ 2
kY − Xβk
2
ˆ 1 6 kY − Xβ k2 + λkβ∗ k1
+ λkβk
2n
2n
2
ˆ 2
kY − Xβk
kξk
2
2
ˆ 16
+ λkβk
+ λkβ∗ k1
2n
2n
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Preuve du Théorème 4.1
b = (β
ˆ − β∗ ) ∈ C3 (J0 )
1 Si λ > 2kXT ξ/nk , alors ∆
∞
ˆ est optimal, on a les propriétés suivantes
Puisque β
∗ 2
ˆ 2
kY − Xβk
2
ˆ 1 6 kY − Xβ k2 + λkβ∗ k1
+ λkβk
2n
2n
2
ˆ 2
kY − Xβk
kξk
2
2
ˆ 16
+ λkβk
+ λkβ∗ k1
2n
2n
T
b 2
b
kX∆k
2
b J c k1 ) 6 2 ξ X∆ + 2λkβ∗ k1
b J k1 + k∆
+ 2λ(kβ∗J0 + ∆
J0
0
0
n
n
ξT X b 2
kX∆k
2
b J c k1 6 2k∆k
b 1
b J k1
+ 2λk∆
+2λk∆
0
0
n
n ∞
b 2
kX∆k
2
b J k1 − k∆
b J c k1 }.
6 λ{3k∆
06
0
0
n
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Preuve du Théorème 4.1
b = (β
ˆ − β∗ ) ∈ C3 (J0 )
1 Si λ > 2kXT ξ/nk , alors ∆
∞
ˆ est optimal, on a les propriétés suivantes
Puisque β
∗ 2
ˆ 2
kY − Xβk
2
ˆ 1 6 kY − Xβ k2 + λkβ∗ k1
+ λkβk
2n
2n
2
ˆ 2
kY − Xβk
kξk
2
2
ˆ 16
+ λkβk
+ λkβ∗ k1
2n
2n
T
b 2
b
kX∆k
2
b J c k1 ) 6 2 ξ X∆ + 2λkβ∗ k1
b J k1 + k∆
+ 2λ(kβ∗J0 + ∆
J0
0
0
n
n
ξT X b 2
kX∆k
2
b J c k1 6 2k∆k
b 1
b J k1
+ 2λk∆
+2λk∆
0
0
n
n ∞
b 2
kX∆k
2
b J k1 − k∆
b J c k1 }.
6 λ{3k∆
06
0
0
n
2
On conclut la preuve du Théorème 4.1 en appliquant la RE
b 2 6 3λk∆
b J k1 6 3λ√s0 k∆k
b 2.
pour obtenir κk∆k
0
2
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Résultat principal
Théorème 5.1
ˆ une solution optimale du problème Lasso (1) avec le
Soit β
choix λ > 2kXT ξ/nk∞ .
1
On a toujours la vitesse lente suivante:
ˆ − β∗ )k2
kX(β
2
6 12kβ∗ k1 λ.
n
2
Si le support de β∗ , J0 , est tel que |J0 | = s0 et que la
matrice de design X vérifie la condition RE avec
paramètres (κ, 3) sur J0 , on a alors la vitesse rapide
suivante
ˆ − β∗ )k2
kX(β
9
2
6 s0 λ2 .
n
κ
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Corollaire
En procédant comme précédemment, on montre que si les
ξj ∼ N(0, σ2 ), et sous l’hypothèse de variables p
normalisées,
−1/2
n
maxj kXj k 6 C , alors le choix λ = 2C σ (2 log p + δ2 )/n
est "valide" avec probabilité supérieure à 1 − exp(−δ2 /2), et
alors :
1 la partie (1) du Théorème implique que
r
ˆ − β∗ )k2
kX(β
2 log p + δ2
∗
2
6 24kβ k1 C σ
.
n
n
sous la seule contrainte kβ∗ k1 6 T , cette borne ne peut pas
être améliorée.
2
sous les hypothèses de sparsité et RE, alors on obtient la
borne
ˆ − β∗ )k2 72C 2 σ2 2s0 log p + s0 δ2
kX(β
2
6
.
n
κ
n
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Preuve du point (2) du Théorème 5.1
En procédant comme dans la preuve du Théorème 4.1, il vient
b 2
kX∆k
2
b J k1 6 3λ√s0 k∆
b J k2 .
6 3λk∆
0
0
n
b ∈ C3 (J0 ), on peut
D’autre part, comme on a toujours ∆
appliquer une nouvelle fois la condition RE−(κ, 3) :
b 26
k∆k
2
b 2
kX∆k
2
,
nκ
ce qui, combiné à l’inégalité précédente, conduit à
√
b
3λ s0
kX∆k
√ 2 6 √
n
κ
Introduction
Le Lasso
Sélection de modèle
Estimation
Preuve du point (1) du Théorème 5.1
1
b 1 6 4kβ∗ k1 .
Montrons que k∆k
Prédiction
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Preuve du point (1) du Théorème 5.1
1
b 1 6 4kβ∗ k1 .
Montrons que k∆k
En procédant comme précédemment on obtient aisément
06
b 2
b
kX∆k
ξT X ∆
2
ˆ 1 }.
6
+ λ{kβ∗ k1 − kβk
2n
n
(7)
D’après l’inégalité d’Hölder, le choix de λ, puis l’inégalité
triangulaire, il vient
ξ T X∆
b λ
XT ξ b
ˆ 1 ).
6
k∆k1 6 (kβ∗ k1 + kβk
n
n ∞
2
(8)
ˆ 1 6 3kβ∗ k1 ,
En combinant ces deux inégalités, il vient kβk
et donc, via l’inégalité triangulaire,
b 1 6 kβk
ˆ 1 + kβ∗ k1 6 4kβ∗ k1 .
k∆k
Introduction
Le Lasso
Sélection de modèle
Estimation
Preuve du point (1) du Théorème 5.1
2
Prédiction
Compléments
(suite)
En combinant les résultats obtenus dans les dérivations des
équations (7) et (8), il vient également
b 2
λ b
kX∆k
∗
∗
2
b
6 k∆k
1 + λ{kβ k1 − kβ + ∆k1 }
2n
2
3λ b
6
k∆k1
2
6 6λkβ∗ k1
où la 2ème ligne vient de l’inégalité triangulaire
b 1 > kβ∗ k1 − k∆k
b 1,
kβ∗ + ∆k
b 1 6 4kβ∗ k1 .
et la 3ème ligne de la borne k∆k
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Sur les conditions RE, MI, etc.
Table : Récapitulatif des liens "Résultats-conditions"
Propriétés
Prédiction Vitesse Lente
Prédiction Vitesse Rapide
J0 ⊆ Jb
J0 = Jb
conditions sur X
"Rien"
RE
RE
Non-Repres.
beta-min
Non
Non
Oui
Oui
Pour les méthodes `0 (ou assimilées, telle qu’exponential
screening, etc.), RE n’est pas nécessaire pour vitesse rapide
en prédiction.
Pour sparsistency (et estimation), il faut des conditions,
liées à l’identifiabilité.
Cas de design aléatoire
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Qq conditions proposées, et leurs inter-relations....
D’après van de Geer et Bühlmann, EJS, 2009.
Compléments
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Modèles Linéaires généralisés
Pour ces modèles,
P la vraisemblance s’exprime généralement
sous la forme i L(Yi , XT
i β)
Régression logistique : L(y, η) = yη − log(1 + e η )
Le Lasso se généralise alors :
φ(λ) := minp −
β∈IR
ou
φ(λ) := maxp
β∈IR
n
X
L(Yi , xT
i β) + λkβk1 .
i =1
n
X
i =1
L(Yi , xT
i β) − λkβk1 .
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
En pratique
On travaille généralement sur variables "standardisées"
Différentes approches ont été proposées, à partir du Lasso,
pour l’améliorer
Adaptive Lasso
Thresholded Lasso
Relaxed Lasso
BoLasso
...
Introduction
Le Lasso
Sélection de modèle
Estimation
Prédiction
Compléments
Biblio
1 Wainwright. Sharp thresholds for high-dimensional ...,
IEEE Trans. Inform. Theory, 2009.
2 Wainwright. Livre en cours d’écriture.
3 Lounici. Sup-norm convergence rate and sign
concentration property of Lasso and Dantzig
estimators. EJS, 2008.
4 Bickel, Ritov, Tsybakov. Simultaneous analysis of Lasso
and Dantzig Selector, AoS, 2009.
5 van de Geer et Bühlmann. Statistics for
high-dimensional data, (Chap. 2, 6, 7), Springer, 2011.
6 van de Geer et Bühlmann. On the conditions used to
prove oracle results for the Lasso, EJS, 2009.
7 Giraud. High-dimensional statistics, 2013.
http://www.cmap.polytechnique.fr/~giraud/MSV/
LectureNotes.pdf
8 Horn et Johnson. Matrix Analysis, 2nd Ed., Cambridge
Univ. Press, 2013.

Download Report