Spørsmål:
Utledning av lukket form lasso løsning
Gary
2011-11-01 05:03:49 UTC
view on stackexchange narkive permalink

For lassoproblemet $ \ min_ \ beta (Y-X \ beta) ^ T (Y-X \ beta) $ slik at $ \ | \ beta \ | _1 \ leq t $. Jeg ser ofte det myke terskelresultatet $$ \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _ j) (| \ beta_j ^ {\ text {LS} } | - \ gamma) ^ + $$ for det ortonormale $ X $ tilfellet. Det hevdes at løsningen kan "lett vises" for å være slik, men jeg har aldri sett en bearbeidet løsning. Har noen sett en eller kanskje har gjort avledningen?

Dette virker litt forvirret. I begynnelsen antar du en begrensning $ t $, og i løsningen introduserer du en parameter $ \ gamma $. Jeg antar at du har tenkt at disse to skal være relatert via det dobbelte problemet, men kanskje du kan gjøre klart hva du leter etter.
Delvis å svare på at @cardinal, finner $ \ beta $ som minimerer $ (YX \ beta) '(YX \ beta) $ underlagt $ \ | \ beta \ | _1 \ leq t $ tilsvarer å finne $ \ beta $ som minimerer $ (YX \ beta) '(YX \ beta) + \ gamma \ sum_j | \ beta_j | $. Det er et 1-1 forhold mellom $ t $ og $ \ gamma $. For å 'enkelt' se hvorfor det myke terskelresultatet er slik, vil jeg anbefale å løse det andre uttrykket (i min kommentar).
En annen merknad, når du finner $ \ beta $ som minimerer $ (YX \ beta) '(YX \ beta) + \ gamma \ sum_j | \ beta_j | $, deler du problemet opp i sakene $ \ beta_j> 0 $, $ \ beta_j <0 $, og $ \ beta = 0 $.
@Mike: Angående din første kommentar: Det var poenget mitt. Jeg håpet å få OP til å avklare dette for seg selv (og andre).
@Mike: Dessuten er forholdet ikke helt en-til-en, for for store nok $ t $ vil løsningen alltid være den minste kvadratiske løsningen, dvs. den som tilsvarer $ \ gamma = 0 $. :)
@cardinal Din metode for å egg OP for å videreutdype problemet er god :) Jeg prøvde å bruke spørsmålet ditt som en innledning til mitt hint. Jeg antok at OP var ukjent med resultatet - hvis jeg er feil, beklager Gary!
@cardinal Ah ja, 1-1 er feil. Korrigering: for hver $ t \ geq0 $ kan du finne $ \ gamma \ geq 0 $.
@Mike: Jeg liker å gjøre det. Noen ganger "degenererer" den til lange kommentarstrømmer; men det er alltid hyggelig å se når det klikker i hodet på noen fordi han / hun tenkte på det i stedet for å bli vist. Når det er sagt, har jeg gått frem og motstått den fristelsen litt i dette tilfellet. Jubel. :)
-1
@MikeWierzbicki faktisk. Det ser ut til at dette forholdet mellom $ t $ og $ \ gamma $ er $ \ sum_ {i} ^ p (| \ hat {\ beta} _i ^ {\ text {LS}} | - \ gamma) _ + = t $
Takk for en flott diskusjon! Jeg kom over denne videoen på coursera - [Deriving the lasso coordinate descent update] (https://www.coursera.org/learn/ml-regression/lecture/6OLyn/deriving-the-lasso-coordinate-descent-update),som er veldig relevant for denne diskusjonen, og går veldig elegant gjennom løsningen.Kan være nyttig for fremtidige besøkende :-)
Se [her] (https://stats.stackexchange.com/questions/123672/coordinate-descent-soft-thresholding-update-operator-for-lasso/351134#351134) for en fullstendig avledning av koordinatnedstigningssaken
To svar:
cardinal
2011-11-01 06:49:28 UTC
view on stackexchange narkive permalink

Dette kan angripes på en rekke måter, inkludert ganske økonomiske tilnærminger via Karush – Kuhn – Tucker-forholdene.

Nedenfor er et ganske elementært alternativt argument.

Den minste firkantede løsningen for en ortogonal design

Anta at $ X $ består av ortogonale kolonner. Deretter er løsningen med de minste kvadratene $$ \ newcommand {\ bls} {\ hat {\ beta} ^ {{\ small \ text {LS}}}} \ newcommand {\ blasso} {\ hat {\ beta} ^ {{\ text {lasso}}}} \ bls = (X ^ TX) ^ {- 1} X ^ T y = X ^ T y \ >. $$

Noen tilsvarende problemer

Via Lagrangian-formen er det greit å se at et tilsvarende problem som det som er vurdert i spørsmålet er $$ \ min_ \ beta \ frac {1} {2} \ | y - X \ beta \ | _2 ^ 2 + \ gamma \ | \ beta \ | _1 \ >. $$

Ved å utvide den første terminen får vi $ \ frac {1} {2} y ^ T y - y ^ TX \ beta + \ frac {1} {2} \ beta ^ T \ beta $ og siden $ y ^ T y $ ikke inneholder noen av variablene av interesse, kan vi forkaste den og vurdere enda et tilsvarende problem , $$ \ min_ \ beta (- y ^ TX \ beta + \ frac {1} {2} \ | \ beta \ | ^ 2) + \ gamma \ | \ beta \ | _1 \ >. $$

Legg merke til at $ \ bls = X ^ T y $, det forrige problemet kan skrives om som $$ \ min_ \ beta \ sum_ {i = 1} ^ p - \ bls_i \ beta_i + \ frac {1} { 2} \ beta_i ^ 2 + \ gamma | \ beta_i | \ >. $$

Vår målfunksjon er nå en sum av mål, som hver tilsvarer en separat variabel $ \ beta_i $, slik at de kan løses hver for seg.

Helheten er lik summen av delene

Fiks en viss $ i $. Deretter ønsker vi å minimere $$ \ mathcal L_i = - \ bls_i \ beta_i + \ frac {1} {2} \ beta_i ^ 2 + \ gamma | \ beta_i | \ >. $$

Hvis $ \ bls_i > 0 $, så må vi ha $ \ beta_i \ geq 0 $ siden vi ellers kunne snu tegnet og få en lavere verdi for objektivfunksjonen. På samme måte hvis $ \ bls_i < 0 $, så må vi velge $ \ beta_i \ leq 0 $.

Sak 1 : $ \ bls_i > 0 $. Siden $ \ beta_i \ geq 0 $, $$ \ mathcal L_i = - \ bls_i \ beta_i + \ frac {1} {2} \ beta_i ^ 2 + \ gamma \ beta_i \ >, $$ og å differensiere dette med hensyn til $ \ beta_i $ og innstilling lik null, får vi $ \ beta_i = \ bls_i - \ gamma $ og dette er bare mulig hvis høyre side ikke er negativ, så i dette tilfellet er den faktiske løsningen $$ \ blasso_i = (\ bls_i - \ gamma) ^ + = \ mathrm { sgn} (\ bls_i) (| \ bls_i | - \ gamma) ^ + \ >. $$

Sak 2 : $ \ bls_i \ leq 0 $. Dette antyder at vi må ha $ \ beta_i \ leq 0 $ og så $$ \ mathcal L_i = - \ bls_i \ beta_i + \ frac {1} {2} \ beta_i ^ 2 - \ gamma \ beta_i \ >. $$ Differensiering med med hensyn til $ \ beta_i $ og innstilling lik null, får vi $ \ beta_i = \ bls_i + \ gamma = \ mathrm {sgn} (\ bls_i) (| \ bls_i | - \ gamma) $. Men igjen, for å sikre at dette er mulig, trenger vi $ \ beta_i \ leq 0 $, som oppnås ved å ta $$ \ blasso_i = \ mathrm {sgn} (\ bls_i) (| \ bls_i | - \ gamma) ^ + \ >. $$

I begge tilfeller får vi ønsket form, og så er vi ferdige.

Avsluttende kommentarer

Vær oppmerksom på at når $ \ gamma $ øker, vil hver av $ | \ blasso_i | $ nødvendigvis reduseres, og dermed øker $ \ | \ blasso \ | _1 $. Når $ \ gamma = 0 $, gjenoppretter vi OLS-løsningene, og for $ \ gamma > \ max_i | \ bls_i | $, får vi $ \ blasso_i = 0 $ for alle $ i $.

Stor oppskrivning @cardinal!
+1 Hele andre halvdel kan erstattes av den enkle observasjonen at målfunksjonen $ \ beta \ to \ frac {1} {2} \ beta ^ 2 + (\ pm \ gamma- \ hat {\ beta}) \ beta $ er en forening av deler av to konvekse paraboler med hjørner ved $ \ pm \ gamma- \ hat {\ beta} $, hvor det negative tegnet blir tatt for $ \ beta \ lt 0 $ og det positive ellers. Formelen er bare en fancy måte å velge nedre toppunkt på.
Hvis det er mulig, vil jeg se derivatene ved å bruke KKT-optimalitetsbetingelsene. Hvilke andre måter er det å utlede dette resultatet på?
@Cardinal: takk for en fin avledning. En observasjon. Hvis jeg husker, er ikke matrise med ortogonale kolonner det samme som en ortogonal (aka ortonormal) matrise. Deretter $ X'X = D $ for en diagonal matrise $ D $ (ikke nødvendigvis identitetsmatrise). Med ortogonal matrise antagelse (som det er i det opprinnelige spørsmålet), har vi $ X'X = I $ og alt ser bra ut :)
@cardinal Jeg skjønner ikke hvorfor du sier "siden vi ellers kunne snu skiltet og få en lavere verdi for den objektive funksjonen".Vi tar avledningen av den objektive funksjonen.Så hva om den objektive funksjonen er høyere eller lavere, hvem bryr seg.Alt vi bryr oss om er at derivatet er satt til null, vi bryr oss om ekstremet.Om det er høyere eller lavere med en konstant, påvirker ikke argminen.
Jeg forstod ikke nøyaktig løsningen din.Jeg stilte et lignende spørsmål her: https://stats.stackexchange.com/questions/323234/how-is-the-lasso-orthogonal-design-case-solution-derived/323242?noredirect=1#comment613347_323242
hvorfor $ \ beta_i> 0 $ innebærer LS $ \ beta_i> 0 $?@cardinal
hvorfor $ \ beta_i> 0 $ innebærer LS $ \ beta_i> 0 $?eller kanskje jeg burde si hvorfor LS $ \ beta_i> 0 $ innebærer $ \ beta_i> 0 $ @cardinal
user795305
2017-07-13 23:08:51 UTC
view on stackexchange narkive permalink

Anta at samvariasjonene $ x_j $, kolonnene til $ X \ i \ mathbb {R} ^ {n \ ganger p} $, også er standardiserte slik at $ X ^ T X = I $. Dette er bare for bekvemmelighet senere: uten den blir notasjonen bare tyngre siden $ X ^ T X $ bare er diagonal. Anta videre at $ n \ geq p $. Dette er en nødvendig forutsetning for at resultatet skal holde. Definer estimat for minste kvadrat $ \ hat \ beta_ {OLS} = \ arg \ min_ \ beta \ | y - X \ beta \ | _2 ^ 2 $. Deretter (Lagrangian form av) lasso estimator \ begin {align *} \ hatt \ beta_ \ lambda & = \ arg \ min _ {\ beta} \ frac {1} {2n} \ | y - X \ beta \ | _2 ^ 2 + \ lambda \ | \ beta \ | _1 \ tag {defn.} \\ & = \ arg \ min_ \ beta \ frac {1} {2n} \ | X \ hat \ beta_ {OLS} - X \ beta \ | _2 ^ 2 + \ lambda \ | \ beta \ | _1 \ tag {OLS er projeksjon} \\ & = \ arg \ min_ \ beta \ frac {1} {2n} \ | \ hat \ beta_ {OLS} - \ beta \ | _2 ^ 2 + \ lambda \ | \ beta \ | _1 \ tag {$ X ^ TX = I $} \\ & = \ arg \ min_ \ beta \ frac {1} {2} \ | \ hat \ beta_ {OLS} - \ beta \ | _2 ^ 2 + n \ lambda \ | \ beta \ | _1 \ tag {algebra} \ \ & = \ mathrm {prox} _ {n \ lambda \ | \ cdot \ | _1} \ left (\ hat \ beta_ {OLS} \ right) \ tag {defn.} \\ & = S_ {n \ lambda} \ left (\ hat \ beta_ {OLS} \ right) \ tag {tar litt arbeid}, \ end {align *} der $ \ mathrm {prox} _f $ er den proksimale operatøren for en funksjon $ f $ og $ S _ {\ alpha} $ myke terskler med beløpet $ \ alpha $.

Dette er en avledning som hopper over den detaljerte avledningen av den proksimale operatøren som Cardinal utarbeider, men håper jeg klargjør hovedtrinnene som muliggjør en lukket form.



ⓘ
Denne spørsmålet ble automatisk oversatt fra engelsk.Det opprinnelige innholdet er tilgjengelig på stackexchange, som vi takker for cc by-sa 3.0-lisensen den distribueres under.
Loading...