Predicteurs Conformes Sparses
Universite Paris-Est – Marne-la-Vallee
Groupe de travail previsionCrest, 8 Avril 2011
M. Hebiri (UMLV) SCP 8 Avril 2011 1 / 21
Outline
1 Cadre de travail
2 Pre-requis
3 Predicteurs Conformes SparsesLasso Conformal PredictorFamille de predicteurs conformes
4 Experiences numeriquesMethodes et comparaisonPerformances
M. Hebiri (UMLV) SCP 8 Avril 2011 2 / 21
Cadre Transductif
References:Vapnik ’98
Joachims ’99
M. Hebiri (UMLV) SCP 8 Avril 2011 3 / 21
Modele de regression lineaire
Observations: En = {(x1, y1), . . . , (xn, yn), xnew}
yi = xiβ∗ + ξi
Vecteur des variables : xi = (xi,1, . . . , xi,p) ∈ Rp, i ≥ 1
Nouvelle observation : xnew ∈ Rp
Response : yi ∈ R, i ≥ 1
Parametre inconnu : β∗ = (β∗1 , . . . , β∗p)′ ∈ Rp
Bruit : ξi ∼ N (0, σ2), σ2 connu.
M. Hebiri (UMLV) SCP 8 Avril 2011 4 / 21
Objectifs
Objectif I : Etant donne En et ε > 0, construire un predicteur conforme(intervalle de confiance) Γε de niveau 1− ε pour ynew
Outil : Mesure de conformite entre xnew et les xi deja observesdistance (geometrique, voisinage, etc.)
distance de similarite : a definir par la suite
Objectif II : Exploiter la sparsite du modele (beaucoup de composantesdans β∗ sont egale a zero) si necessaire
Outil : Recourrir a une procedure de selection de variables (LASSO, etc.)
Remarque : ce deuxieme objectif est particulierement interessant lorsque↪→ le nombre de variables est tres grand (comparativement au nombre
d’observations)↪→ le nombre de variables vraiment pertinentes est petit
M. Hebiri (UMLV) SCP 8 Avril 2011 5 / 21
Prediction Conforme : Vovk et al. ’05
Notations :y ∈ R : valeur possible de ynew
|A| : cardinal de l’ensemble AScore de Non-conformite α(y) = (α1(y), . . . , αn(y), αnew(y))′
αi(y) : similarite entre (xnew, y) et (xi, yi)
information relative : p-value
p(y) =1
n+ 1| {i ∈ {1, . . . , n, new} : αnew(y) ≤ αi(y)} |
p(y) ∈ [ 1n+1 ; 1]
plus p(y) est petite, moins la paire testee (xnew, y) est vraisemblable(ce choix fait de y une valeur aberrante lorsqu’elle est combinee avecxnew)
Predicteur Conforme Γε : valeurs y ∈ R telle que p(y) > ε.
M. Hebiri (UMLV) SCP 8 Avril 2011 6 / 21
Estimateur LASSO : Tibshirani ’96
LASSO
β = Argminβ∈Rp
1
n
n∑i=1
(yi − xiβ)2 + λ
p∑j=1
|βj |
Parametre de regularisation : λ
Motivation :
Solution sparse β (i.e., beaucoup de coefficients reduits a 0)
Resultats interpretables quand le modele est sparse
M. Hebiri (UMLV) SCP 8 Avril 2011 7 / 21
Algorithmique
Solution approchee : LARS algorithme (Efron et al. ’04)
0 0.2 0.4 0.6 0.8 1
−600
−400
−200
0
200
400
600
Algorithme LARS : données de diabètes
( Σ | βj | ) / ( Σ | β
j
mc | )
Coeffic
ients
βj
↪→ βλ1 , . . . , βλK : approximations de la solution LASSO aux points detransition λ = λ1, . . . , λK
M. Hebiri (UMLV) SCP 8 Avril 2011 8 / 21
Suite...
Etape k : µk = xkβλk = xk(x′kxk)
−1(x′ky −λk2 sk)
vecteur des reponses : y = (y1, . . . , yn)′
matrice des donnees : x = (x′1, . . . , x′n)′
vecteur signe : skxk est la restriction de x aux colonnes correspondant aux variablesselectionnees
Ne prend pas en compte xnew dans la construction de β !
M. Hebiri (UMLV) SCP 8 Avril 2011 9 / 21
Predicteurs Conformes Sparses
On considere les donnees augmentees : x = (x′1, . . . , x′n, x′new)′ et
y = (y1, . . . , yn, y)′
Pour tout point de transition λk, on definit l’estimateur LASSO µksur la base de xk et y
On definit le score de Non-conformite
αk(y) := |y − µk| = |Ak + Ck +Bk y|
ou | · | s’interprete composante par composante etAk = (ak1, . . . , a
kn, a
knew)′ := (I−Hk) (y1, . . . , yn, 0)′
Bk = (bk1, . . . , bkn, b
knew)′ := (I−Hk) (0, . . . , 0, 1)′
Ck = (ck1, . . . , ckn, c
knew)′ := λk
2 xk (x′kxk)−1 sk
Les αk(y) sont lineaires par morceaux
M. Hebiri (UMLV) SCP 8 Avril 2011 10 / 21
Predicteurs Conformes Sparses
p-value: pk(y) = 1n+1 |
{i : αki (y) ≤ αknew(y)
}|
Predicteur a l’etape k : Γεk = {y ∈ R : pk(y) > ε}
Proposition
Les points y tels que αki (y) = αknew(y) existenti) si bki 6= bknew : quand y est egal a
−aki − aknew + cki − cknew
bki − bknewet − aki + aknew + cki + cknew
bki + bknew.
ii) si bki = bknew 6= 0 : lorsque y est egal a
−aki + aknew + cki + cknew
2bki
Conformal Lasso Predictor Γεopt : le plus petit ΓεkM. Hebiri (UMLV) SCP 8 Avril 2011 11 / 21
Exemple de predicteurs conformes
0 10 20 30 40 50−80
−60
−40
−20
0
20
40
60
80
Conformal predictors when n=300
iteration
Γkε
ynew
CoLP
↪→ Le Conformal Lasso Predictor est le plus petit intervalle↪→ Dans cet exemple, il contient la vraie valeur de ynew↪→ En general : ∀λ fixe P(ynew ∈ Γλ) ≥ 1− ε
M. Hebiri (UMLV) SCP 8 Avril 2011 12 / 21
Extension
Estimateur de la forme :
µ = u(x, s)y + v(x, s)
ou u(·) et v(·) sont des fonctions constantes par morceaux par rapport a y
On s’interesse aCoLP: u(x, s) = xk(x
′kxk)
−1x′kv(x, s) = −λkxk(x′kxk)−1sk
CoRP: u(x, s) = x(x′x + µIp)−1x′ et v = 0
CENeP: u(x, s) = xk(x′kxk + µkIk)
−1x′kv(x, s) = −λkxk(x′kxk)−1sk
M. Hebiri (UMLV) SCP 8 Avril 2011 13 / 21
Cadre experimental
Tous les intervalles de confiance construits sont de niveau1− ε = 90%
Toutes les experiences de simulations sont repetees M = 1000 fois
Mesures de performance :
Precision : taille de l’intervalle
Validite : VALε = M−1M∑
m=1
I(ynew ∈ (Γεopt)m)
Selection de variable : reconstitution du support de β∗
Methodes de reference :
Selection de variables : LASSO original (Tibshirani ’96) etl’Elastic-Net original (Zou & Hastie ’05) (base sur le critere BIC)
Precision et validite : CoRP (Vovk et al. ’05)
M. Hebiri (UMLV) SCP 8 Avril 2011 14 / 21
Donnees simulees avec p = 50
A∗ = {j : β∗j 6= 0} : ensemble des variables pertinentesExemple(a): A∗ = {1}; decroissance exponentielle des correlationsentre les variables successives {15, . . . , 35}Exemple(b): A∗ = {1, . . . , 5} ∪ {10, . . . , 25} ; les correlations sontcomme dans l’Exemple(a)
Exemple(c): A∗ = {1, . . . , 15}; trois groupes de variables trescorrelees : G1 = {1, . . . , 5}, G2 = {6, . . . , 10} and G1 = {11, . . . , 15}Exemple(d): A∗ = {1, . . . , p}; decroissance exponentielle descorrelations entre les variables successives {1, . . . , p}
M. Hebiri (UMLV) SCP 8 Avril 2011 15 / 21
Validite
Table: Controle de VALε
Exemple[n/σ] CoRP CoLP CoLaRP CENePEx (a)[300/1] 0.90± 0.02 0.88± 0.02 0.85± 0.02 0.88± 0.02Ex (a)[300/7] 0.89± 0.02 0.91± 0.02 0.89± 0.02 0.90± 0.02Ex (a)[300/15] 0.89± 0.02 0.89 ± 0.02 0.88± 0.02 0.89± 0.02
Ex (b)[300/1] 0.90± 0.02 0.88± 0.02 0.87± 0.02 0.87± 0.02Ex (c)[300/1] 0.90± 0.02 0.90± 0.02 0.89± 0.02 0.90± 0.02Ex (d)[300/1] 0.89± 0.02 0.90± 0.02 0.90± 0.02 0.90± 0.02
Ex (a)[50/3] 0.89± 0.02 0.67± 0.03 0.41± 0.03 0.79± 0.02Ex (a)[20/3] 0.86± 0.02 0.60± 0.03 0.30± 0.03 0.69± 0.03
Exemple[n/σ] CoRP CoLP Stopped-CoLP 2-PN-CoLPEx (a)[50/7] 0.85± 0.02 0.62± 0.03 0.82± 0.02 0.88± 0.02Ex (b)[50/1] 0.88± 0.02 0.56± 0.03 0.82± 0.02 0.91 ± 0.02Ex (c)[20/15] 0.88± 0.02 0.61± 0.03 0.77± 0.03 0.90± 0.02Ex (d)[20/1] 0.90± 0.02 0.60± 0.03 0.79± 0.02 0.89± 0.02
M. Hebiri (UMLV) SCP 8 Avril 2011 16 / 21
Selection de variables : Exemple(b)[300/5]
0 5 10 15 20 25 30 35 40 45 500
5
10
15
20
25
30
35
40
45
50
Variable index
Itera
tion
CoLP
CoRLaP
Lasso
0 5 10 15 20 25 30 35 40 45 500
5
10
15
20
25
30
35
40
45
50
Variable indexItera
tion
CENeP
Elastic−Net
M. Hebiri (UMLV) SCP 8 Avril 2011 17 / 21
Precision : Exemple(b)[n/5]
0 5 10 15 20 25 30 35 40 45 500
10
20
30
40
50
60
70
80
90
Iteration
Inte
rvals
siz
es
Selected predictor
0 50 100 150 200 250 300 350 4000
0.5
1
1.5
2
2.5x 10
4
IterationIn
terv
als
siz
es
Selected predictorFailed predictor
M. Hebiri (UMLV) SCP 8 Avril 2011 18 / 21
Donnees Reelles
On utilise les donnees “House Boston” (506 observations et 13 variables)On ajoute artificiellement 483 variables bruits ↪→ p = 500
On effectue 150 permutations des lignes de la matrice des donnees etdu vecteur reponse↪→ on selectionne n = 50 couples (xi, yi)↪→ on choisit une lignes au hasard comme etant (xnew, ynew)
Table: controle de VALε et du numbre de variables bruits selectionnees (variablesX14 a X500) (p = 500 et n = 50).
CoRP CoLP CENeP Stopped-CoLP 2-PN-CoLPVALε 0.93± 0.01 0.43± 0.04 0.85± 0.02 0.85± 0.02 0.93± 0.01
Noise 100 % 20.3 % 4.0 % 5.9 % 5.9 %
M. Hebiri (UMLV) SCP 8 Avril 2011 19 / 21
Conclusion
Predicteurs Conformes Sparses↪→ critere naturelle de selection de l’intervalle optimal↪→ bonne performance dans le cas p ≤ n↪→ correction dans le cas p > n : permet d’egaler (ou d’amelorer)
les performances du CoRP (avec une precisioin toujours meilleure)
Validite theorique (Vovk et al. ’05)
Perspective : consistance en selection de variables (theorique) lorsquela selection est basee sur le critere de precision !
M. Hebiri (UMLV) SCP 8 Avril 2011 20 / 21
Merci de votre attention
M. Hebiri (UMLV) SCP 8 Avril 2011 21 / 21