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.
© Copyright 2024 ExpyDoc