Verfahren zur Modellschrumpfung und Variablenselektion

Jona Cederbaum

Institut für Statistik

Ludwig-Maximilians-Universität

10. Juni 2009

Der LASSO-Schätzer

2

Übersicht

1.1. Spezialfall orthonormales Design

1.2. Schätzung des Standardfehlers

1.3. Bestimmung des Lasso-Parameters

2 Beispiel Prostatakrebs

3 Zusammenfassung

4 Grenzen des Lasso-Schätzers

5 Ausblick

6 Einleitung

6.1. Das Modell

6.2. KQ-Schätzer und Motivation

für neue Schätzerverfahren

6.3. Ridge-Regression

6.4. Subset Selection

7 Der Lasso-Schätzer

7.1. Definition und Herleitung

7.2. Allgemeine Eigenschaften

7.3. Geometrie im 2

3

Das Modell

Betrachtet wird das lineare Regressionsmodell

y X ! " #

$ % &T

1 2 ny y , y ,..., y , y | X unabhängig, zentriert n

ii 1

1y y 0

n

'

$ X ist eine n p( Designmatrix, standardisiert n n

ij iji 1 i 1

1 1x 0, x ² 1

n n

' '

$ # : Fehlerterme, für die gilt: % &N 0, ²I# )!

4

Kleinste-Quadrate-Schätzer

Residuenquadratsumme

% & % & % &n 2 TT

i ii 1

RSS y x y X y X

* ! * ! * !'

Falls X vollen Rang hat, definiert sich der Kleinste-Quadrate-Schätzer als

" % & % & % & 1T T TKQ arg min y X y X X X X y

RSS

*

+ ,- -- -

! * ! * ! . /! - -

- - 0 1

#$$$%$$$&

5

Eigenschaften des KQ-Schätzers (1)

$ Erwartungstreuer Schätzer für !, d.h.

"% & "% &KQ KQBias E 0! ! *!

!

#%&

$ Minimale Varianz und somit minimaler Mean-Squared-Error unter den

unverzerrten Schätzern (BLUE)

"% & "% & "% &% & "% &% &T

KQ KQ KQ KQMSE Var Bias * Bias

0

! ! " ! !

#$$$$%$$$$&

"% & % & 12 TKQVar X X

* ! )

6

Eigenschaften des KQ-Schätzers (2)

$ Tendenziell zu groß geschätzte Länge des Schätzers, d.h. "KQ! 2 !' ' ' '

$ Keine Variablenselektion, sehr geringe Effekte bleiben im Modell

Eingeschränkte Interpretierbarkeit

$ Existiert nur für vollen Rang der Designmatrix ( Multikollinearität)

Idee: Suche in Länge beschränkten Schätzer, der 2 Aspekte

$ Prädiktionsgenauigkeit

$ Interpretierbarkeit

7

Ridge-Regression

$ Ausweitung der Suche auf die Klasse der verzerrten Schätzer

$ Minimierung der RSS unter linearer Nebenbedingung, die die Länge des

Schätzers beschränkt

" 3 4Ridge arg min RSS!

! unter der Nebenbedingung p

2j

j 1

0t, t

! 5 2'

% & % &T Targ min y X y X , 0

RSS

!

+ ,- -- -

* ! * ! " 6 2. /- -- -

6!

0 1

!#$$$%$$$&

% & 1T TX X I X y*

" 6 , I: Einheitsmatrix

8

Eigenschaften des Ridge-Schätzers (1)

$ Lineare Lösung in " % & 1TRidgey. Hy, mit H X X I

*! " 6

$ Kein erwartungstreuer Schätzer

$ Für geeignete Wahl von 6 gilt:

"% & "% &Ridge KQMMSE SE5! !

Bias-Quadrat

MSE

KQ-Schätzer

Varianz

Ridge-Schätzer

6

9

Eigenschaften des Ridge-Schätzers (2)

$ Je größer 6, desto stärker der Schrumpfungseffekt

$ Designmatrix X muss nicht den vollen Rang haben

löst Multikollinearitäts-Problematik

$ Keine Variablenselektion

$ Wahl von 6 zum Beispiel mit Kreuzvalidierung (siehe Vortrag L0)

Fazit: Einer der beiden Aspekte bzgl. des KQ-Schätzers verbessert

$ Verbesserung der Prädiktionsgenauigkeit durch geeignete Wahl von 6

möglich

$ ABER: Keine Verbesserung der Interpretierbarkeit

13

Least Absolute Shrinkage and Selection Operator (LASSO)

$ Ziel: Simultane Schrumpfung und Variablenselektion

$ Minimierung der RSS unter linearer Nebenbedingung

" 3 4Lasso arg min RSS!

! unter der Nebenbedingung p

jj 1

0t, t

! 5 2'

% & % & jj

Tp

1

arg min y X y X , 0

RSS

!

+ ,- -- -

* ! * ! " 6 2. /- -

-

!

0

6

- 1

'#$$$%$$$&

Im Allgemeinen nicht explizit darstellbar, da keine lineare Lösung in y

14

Allgemeine Eigenschaften des Lasso-Schätzers

$ Mit "p

KQ, jKQ j 1t :

!' gilt: für alle Werte

7 KQt t Schrumpfung, einige Koeffizienten exakt auf Null

2 KQt t " "Lasso KQ! ! (sofern existent)

$ 6 hat genau entgegen gerichtete Wirkung auf den Schätzer

$ Designmatrix X muss nicht den vollen Rang haben

$ " Lasso! ist unabhängig vom KQ-Schätzer

15

Geometrische Aspekte im 2 (1)

Betrachtet wird der Fall p 2

$ Sowohl Ridge- als auch Lasso-Schätzer minimieren die RSS unter

Nebenbedingungen

Ridge: 2-Penalisierung ! Lasso: 1-Penalisierung

$ "% & "% & % &T

1 2

TT

KQ KQRSS const, wobeiX ,X " !!* !! * !! !

RSS c , für c8 beliebig hat elliptische, um "KQ! zentrierte, Konturlinien

Hauptachsen der Ellipsen in 45° mit Koordinatenachsen des

1 2! *! - Koordinatensystems

16

-4 -2 0 2 4 6

-4-2

02

46

!2

!1

!^

-4 -2 0 2 4 6-4

-20

24

6

!2

!1

!^"KQ! "

KQ!

Geometrische Aspekte im 2 (2)

Elliptische Konturlinien

RIDGE

LASSO

2im2p 2 2j 1 2j 1

t ! ! "! 5'

2im

p

j 1 2j 1t

! ! " ! 5'

Graphische Darstellung der Schätzer im 2 für verschiedene Wahl von t

17

Spezialfall orthonormales Design (1)

$ X hat orthonormale Einträge, d.h. es gilt TX X I , I: Einheitsmatrix

$ Lasso-Schätzer geschlossener Form darstellbar ( "98 , + : positiver Teil)

Schätzer Formel

Ridge-Schätzer " " % &KQ, jRidge Rid, gej 1 , " 9 9 6! !

Best Subset der Größe k " " "

KQ, jSubset , j KQ, j, falls! !! 9(

Lasso-Schätzer " "% & "% &K LQLa , jsso, KQ assoj , jsign , 2

"

! ! * 9 9 6!

18

Spezialfall orthonormales Design (2)

RIDGE BEST SUBSET SELECTION LASSO

! ! !

Linear, Proportionale Schrumpfung

Sprungstelle bei 29 Variablenselektion

Schätzfunktionen im Vergleich zur KQ-Schätzung im orthonormalen Design, für 29

Teilweise linear Schrumpfung &

Selektion

"!

19

LASSO

Geometrie im 2 im orthomalen Design

$ Konturlinien von "% & "% &TT

KQ KQX X!*! !*! sind kreisförmig

-4 -2 0 2 4 6

-4-2

02

46

!2

!1

!^

-4 -2 0 2 4 6

-4-2

02

46

!2

!1

!^

Kreisförmige Konturlinien

RIDGE

"KQ! "

KQ!

Graphische Darstellung der Schätzer im 2 für verschiedene Wahl von t im Spezialfall des orthonormalen Designs

20

Schätzung des Standardfehlers des Lasso-Schätzers

$ Lasso-Schätzer ist nichtlineare, nichtdifferenzierbare Funktion

Schätzung des Standardfehlers )% & % &j jse Var , j 1,...,p ! schwierig

$ Vergleich:

- KQ-Schätzer: "% & % & 12 TKQVar X X

*! )

- Ridge-Schätzer: "% & % & % &1 12 T T TRidgeVar X X I X X X X I

* *! ) " 6 " 6

$ Ein Ansatz: Approximation durch Ridge-Schätzer

21

Schätzung des Standardfehlers durch Ridge-Approximation (1)

$ Transformation der Lasso-Nebenbedingung

p

jj 1

t

! 5' zu % &p

2j j

j 1

t

! ! 5'

Approximation des Lasso-Schätzers % & 1T T

Verallgem. Ridge-Schätzer

X X W X y*: *! " 6

#$$$%$$$&,

mit "% &Lasso, jW diag , j 1,...,p ! ,

W*: verallgem. Inverse von W , d.h. WW*W=W

6 derart gewählt, dass p

jj 1

t:

! ' erfüllt ist

22

Schätzung des Standardfehlers durch Ridge-Approximation (2)

* % & " % & % &21 1T T TVar X X W X X X X W* *: * *! ) " 6 " 6 ,

" 2) : Schätzer für Fehlervarianz

Diagonalelemente als Schätzer für Varianz des jeweiligen " Lasso, j! , j 1,...,p

$ Nachteil: Für " Lasso, j 0! ; Varianz wird automatisch Null

Vernachlässigung der Unsicherheit

23

Wahl des Lasso-Parameters t (1)

$ Anhand Generalisierter Kreuzvalidierung (GCV)

$ Ziel: Minimierung des Vorhersagefehlers "% &2

PE E y X * !

$ Wieder: Transformation der Lasso-Nebenbedingung

p

jj 1

t

! 5' zu % &p

2j j

j 1

t

! ! 5'

und Approximation durch verallgemeinerten Ridge-Schätzer (vgl. Folie 21)

% & 1T TX X W X y*: *! " 6

24

Wahl des Lasso-Parameters t (2)

$ Zu minimierendes Generalisiertes Kreuzvalidierungskriterium allgemein

in Abhängigkeit vom Parameter 6

% & % &% &

2n

i i

i 1

y f x1GCV

n 1 tr H n

6

< =*6 > ?> ?*@ A

'"

- % &if x6"

: Schätzwert an der Stelle i in Abhängigkeit von 6

- tr: Spur der Matrix

- H: Hatmatrix, d.h. "y Hy

25

Wahl des Lasso-Parameters t (3)

$ Im unrestringierten Fall des KQ-Schätzers mit % & 1T TH X X X X*

gilt:

% &tr H = p

$ Für die Ridge-Regression mit % & 1T TH X X X I X*

" 6 gilt

im orthonormalen Design % & % &tr H p 1 " 6 (effektive Parameteranzahl)

$ Für die Approximation % & 1T TX X W X y*: *! " 6 des Lasso-Schätzers gilt:

% & 1T TH X X X W X** " 6 % & % &tr H p t+ (effektive Parameteranzahl)

% &% &

% &% &3 4

2*n

2i 1

RSS t1 y X 1GCV t

n 1 p t n n 1 p t n

+ ,* !- - . /

*- - *0 1' ,

mit % &RSS t als RSS für Schätzung unter Nebenbedingung mit Restriktion t

26

Beispiel Prostatakrebs (1)

$ Datensatz Prostate aus dem R-Paket lasso2

$ Beschreibung der Daten:

- Zusammenhang zwischen dem Level eines prostataspezifischen Antigens

und mehreren klinischen Messungen bei Männern, die kurz vor der

operativen Entfernung der Prostata standen

- Response: logarithmiertes Level des prostataspezifschen Antigens (lpsa)

- Einflussgrößen: lcavol, lweight, age, lbph, svi, lcp, gleason, pgg45

$ Zunächst Standardisieren: n n

ij iji 1 i 1

1 1x 0, x ² 1

n n

' ' , y unzentriert

27

Beispiel Prostatakrebs (2)

$ KQ-, Ridge- und Lasso-Schätzer im Vergleich

$ Wahl des Lasso-Parameters anhand von Leave-One-Out Kreuzvalidierung (vgl. Vortrag (L0))

Ergebnis:

KQ

tt 0.69 s [0,1]

t ; 8

"" "

Leave-One-Out CV

CV

t

28

Beispiel Prostatakrebs (3)

Farbig: signifikant zum Niveau 0.05

Name KQ Ridge Ridge 57,876 Lasso

Lasso 16.286

s 0.43 " Schätzer Std.Error Schätzer Std.Error Schätzer Std.Error

lcavol 0.5994 0.0898 0.3147 0.0389 0.4801 0.0548 lweight 0.1955 0.0731 0.1471 0.0398 0.0772 0.0196 age -0.1267 0.0721 -0.0230 0.0401 0.0000 0.0000 lbph 0.1346 0.0735 0.0762 0.0397 0.0000 0.0000 svi 0.2748 0.0876 0.1784 0.0389 0.1295 0.0262 lcp -0.1278 0.1102 0.0856 0.0363 0.0000 0.0000 gleason 0.0282 0.0985 0.0520 0.0377 0.0000 0.0000 pgg45 0.1106 0.1080 0.0648 0.0366 0.0000 0.0000

29

Beispiel Prostatakrebs (4)

Mittelwerte der Schätzer und Standardabweichung

Variablen

Mit

telw

erte

der

Sch

ätze

r

30

Beispiel Prostatakrebs (5)

Pfade der Lasso-Koeffizienten für verschiedene Wahl von "

pKQ

KQ, jj 1

t ts [0,1]

t

8!'

s

Sta

ndar

disi

erte

Koe

ffiz

ient

en

31

Zusammenfassung

$ Methode zur simultanen Schrumpfung und Variablenselektion

$ Art „stetige Subset Selection“

$ Designmatrix braucht keinen vollen Rang

$ Tibshirani betrachtet in seinem Paper 3 Szenarien:

a. wenige starke Effekte Subset, Lasso, Ridge

b. eine kleine bis mittlere Anzahl moderater Effekte Lasso, Ridge, Subset

c. eine große Anzahl kleiner Effekte Ridge, Lasso, Subset

Lasso-Schätzer relativ gut bzgl. Vorhersage

$ Außerdem: gute Interpretierbarkeit

Am besten bzgl. MSE:

32

Grenzen des Lasso-Schätzers

$ In einigen Fällen stößt das Lasso-Verfahren an seine Grenzen:

- Mehr Kovariablen als Beobachtungen d.h. p nB : maximal n Variablen können durch Lasso-Schätzung ausgewählt werden

- Hohe paarweise Korrelation:

Lasso-Methode wählt lediglich eine der korrelierten Kovariablen aus

(vgl.: H. Zou, T. Hastie)

33

Ausblick

$ Ausweitungen möglich beispielsweise auf GLMs

$ 1-Penalisierung Spezialfall von r-Penalisierung: rp

jj 1

!' , r "8

Im 2 :

% &r : (a) r 4, (b r 2 R e) idg , % &(c) , (d) r 1 2,r 1 Lasso (e) r 1 10

$ Bayesianische Herangehensweise mit Doppelexponentialverteilung als

Priori für % &j, j 1,...,p! (vgl. Tibshirani (1996), Park und Casella (2008))

34

Literaturverzeichnis

[1] B. Efron, T. Hastie, I. Johnstone, R. Tibshirani: Least Angle Regression (2002). [2] L. Fahrmeir, T. Kneib, S. Lang: Regression. Modelle, Methoden und Anwendungen. Springer- Verlag Berlin Heidelberg (2007). [3] T. Hastie, R. Tibshirani, J. Friedman: The Elements of Statistical Learning. Data Mining, Inference, and Prediction. Springer, New York (2001). [4] A. Hoerl, R. Kennard: Ridge regression: biased estimation for nonorthogonal problems. Technometrics, Vol. 12:55-67 (1970). [5] L. Huan, H. Motoda: Computational methods of feature selection. Chapman&Hall (2008). [6] S. Konrath: Bayesianische Regularisation mit Anwendungen. Masterthesis. (2007). [7] T. Park und G. Casellea: The Bayesian Lasso. Technical report. University of Florida (2005). [8] R. Tibshirani: Regression Shrinkage and Selection via the Lasso. Journal of the Royal Statistical Society. Series B (Methodological), Volume 58, Issue 1 (1996), 267-288. [9] H. Toutenburg: Lineare Modelle. Theorie und Anwendungen. Physica- Verlag Heidelberg (2003). [10] H. Zou, T. Hastie : Regularization and variable selection via the elastic net. Journal of

the Royal Statistical Society. Series B, Volume 67 (2005), 301-320.