Warum ist meine Ableitung einer Lasso-Lösung in geschlossener Form falsch?

28

Das Lasso-Problem hat die geschlossene Form Lösung: \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _ j) (| \ beta_j ^ {\ text {LS }} | - \ alpha) ^ + wenn X orthonormale Spalten hat. Dies wurde in diesem Thread gezeigt: Herleitung einer Lasso-Lösung in geschlossener Form .

βlasso=argminβyXβ22+αβ1
βjlasso=sgn(βjLS)(|βjLS|α)+
X

Ich verstehe jedoch nicht, warum es überhaupt keine geschlossene Lösung gibt. Unter Verwendung von Subdifferenzen erhielt ich das Folgende.

( X ist eine n×p Matrix)

f(β)=yXβ22+αβ1
=i=1n(yiXiβ)2+αj=1p|βj|
( ist die i-te Reihe von ) XiX
=i=1nyi22i=1nyiXiβ+i=1nβTXiTXiβ+αj=1p|βj|
fβj=2i=1nyiXij+2i=1nXij2βj+βj(α|βj|)
={2i=1nyiXij+2i=1nXij2βj+α for βj>02i=1nyiXij+2i=1nXij2βjα for βj<0[2i=1nyiXijα,2i=1nyiXij+α] for βj=0
Mit wirfβj=0

βj={(2(i=1nyiXij)α)/2i=1nXij2for i=1nyiXij>α(2(i=1nyiXij)+α)/2i=1nXij2for i=1nyiXij<α0 for i=1nyiXij[α,α]

Weiß jemand, wo ich falsch liege?

Antworten:

Wenn wir das Problem in Matrizen schreiben, können wir sehr leicht erkennen, warum eine geschlossene Lösung nur im orthonormalen Fall mit XTX=I :

f(β)=yXβ22+αβ1
=yTy2βTXTy+βTXTXβ+αβ1
f(β)=2XTy+2XTXβ+(α|β1)
(Ich habe hier jedoch viele Schritte auf einmal unternommen.) Bis zu diesem Punkt ist dies völlig analog zur Herleitung der Lösung der kleinsten Quadrate. Sie sollten also in der Lage sein, die fehlenden Schritte dort zu finden.)
fβj=2XjTy+2(XTX)jβ+βj(α|βj|)

Mit fβj=0 wir

2(XTX)jβ=2XjTyβj(α|βj|)
2(XTX)jjβj=2XjTyβj(α|βj|)2i=1,ijp(XTX)jiβi

Wir können jetzt sehen, dass unsere Lösung für ein von allen anderen abhängt, und es ist daher nicht klar, wie wir von hier aus vorgehen sollen. Wenn orthonormal ist, haben wir so dass es in diesem Fall sicherlich eine geschlossene Form gibt.βjβijX2(XTX)jβ=2(I)jβ=2βj

Vielen Dank an Guðmundur Einarsson für seine Antwort, auf die ich hier näher eingegangen bin. Ich hoffe diesmal ist es richtig :-)

Norbert
quelle
3
Willkommen bei CrossValidated und herzlichen Glückwunsch zu einem sehr schönen ersten Beitrag!
S. Kolassa - Wiedereinsetzung von Monica

Antworten:

16

Dies geschieht normalerweise mit geringster Winkelregression. Das Papier finden Sie hier .

Entschuldigen Sie meine anfängliche Verwirrung, ich werde es erneut versuchen.

Nach der Erweiterung Ihrer Funktion Sie alsof(β)

f(β)=i=1nyi22i=1nyiXiβ+i=1nβTXiTXiβ+αj=1p|βj|

Dann berechnen Sie die partielle Ableitung in Bezug auf . Mein Anliegen ist die Berechnung der partiellen Ableitung des letzten Terms vor der 1-Norm, dh des quadratischen Terms. Lassen Sie es uns weiter untersuchen. Wir haben das:βj

Xiβ=βTXiT=(β1Xi1+β2Xi2++βpXip)
Sie können Ihren quadratischen Ausdruck also im Wesentlichen wie umschreiben: Nun können wir die Ableitung dieses wrt : mit der Kettenregel berechnen.
i=1nβTXiTXiβ=i=1n(Xiβ)2
βj
βji=1n(Xiβ)2=i=1nβj(Xiβ)2=i=1n2(Xiβ)Xij

Jetzt vereinfacht sich Ihr Problem nicht mehr so ​​einfach, da in jeder Gleichung alle Koeffizienten vorhanden sind.β

Dies beantwortet nicht Ihre Frage, warum es keine geschlossene Lösung des Lasso gibt, ich möchte später noch etwas hinzufügen.

Gumeo
quelle
1
Vielen Dank. Ich kann jetzt tatsächlich sehen, warum es keine geschlossene Lösung gibt (siehe meine Bearbeitung).
Norbert
Süss! Tolle Arbeit :)
Gumeo