Herleitung der Lasso-Lösung in geschlossener Form

52

Für das Lasso-Problem so dass . Ich sehe oft das Ergebnis der schwachen Schwelle \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _ j) (| \ beta_j ^ {\ text {LS}} |) - \ gamma) ^ + für den orthonormalen X- Fall. Es wird behauptet, dass die Lösung "leicht gezeigt" werden kann, aber ich habe noch nie eine funktionierende Lösung gesehen. Hat jemand einen gesehen oder hat vielleicht die Ableitung gemacht?minβ(YXβ)T(YXβ)β1t

βjlasso=sgn(βjLS)(|βjLS|γ)+
X
Gary
quelle
Dies scheint etwas verwirrt. Zu Beginn nehmen Sie eine Bedingung t und geben in der Lösung einen Parameter γ . Ich nehme an, Sie beabsichtigen, dass diese beiden über das doppelte Problem in Beziehung stehen, aber vielleicht können Sie klarstellen, wonach Sie suchen.
Kardinal
2
Teilweise auf @cardinal zu antworten und das β , das (YX \ beta) minimiert '(YX \ beta)(YXβ)(YXβ) abhängig von β1t ist gleichbedeutend mit dem Finden des β , das minimiert (YXβ)(YXβ)+γj|βj|. Es gibt eine 1-1 Beziehung zwischen t und γ . Um 'leicht' zu verstehen, warum das Ergebnis der weichen Schwelle so ist, würde ich empfehlen, den zweiten Ausdruck (in meinem Kommentar) zu lösen.
2
Ein weiterer Hinweis, wenn Sie das β , das (YXβ)(YXβ)+γj|βj|Teilen Sie das Problem in die Fälle βj>0 , βj<0 und β=0 .
2
@ Kardinal Ah ja, 1-1 ist falsch. Korrektur: Für jedes t0 gibt es ein γ0 .
3
Vielen Dank für ein tolles Gespräch! Ich bin auf coursera auf dieses Video gestoßen - Ableiten des Lasso-Koordinaten-Abstiegs-Updates , das für diese Diskussion sehr relevant ist, und gehe die Lösung sehr elegant durch.
Könnte

Antworten:

63

Dies kann auf verschiedene Arten angegriffen werden, einschließlich relativ wirtschaftlicher Ansätze über die Karush-Kuhn-Tucker-Bedingungen .

Im Folgenden finden Sie ein recht elementares alternatives Argument.

Die Lösung der kleinsten Quadrate für ein orthogonales Design

Angenommen, besteht aus orthogonalen Spalten. Dann ist die Lösung der kleinsten β LS = ( X T X ) - 1 X T y = X T yX

β^LS=(XTX)1XTy=XTy.

Einige äquivalente Probleme

Über die Lagrange-Form ist es einfach zu erkennen, dass ein zu dem in der Frage betrachteten äquivalentes Problem

minβ12yXβ22+γβ1.

Wenn wir den ersten Term erweitern, erhalten wir und da keine enthält von den interessierenden Variablen können wir es verwerfen und ein weiteres gleichwertiges Problem betrachten: yTyminβ(-yTXβ+112yTyyTXβ+12βTβyTy

minβ(yTXβ+12β2)+γβ1.

Mit kann das vorherige Problem als umgeschrieben werden. minβp Σ i=1 - β LS i & beta;i+1β^LS=XTy

minβi=1pβ^iLSβi+12βi2+γ|βi|.

Unsere Zielfunktion ist nun eine Summe von Zielen, die jeweils einer separaten Variablen , sodass sie jeweils einzeln gelöst werden können.βi

Das Ganze ist gleich der Summe seiner Teile

Repariere ein bestimmtes . Dann wollen wir minimieren L i = - β LS i & beta; i + 1i

Li=β^iLSβi+12βi2+γ|βi|.

Wenn , müssen wir da wir sonst das Vorzeichen umdrehen und einen niedrigeren Wert für die Zielfunktion erhalten könnten. Wenn , müssen wir wählen .βi0 β LS i <0βi0β^iLS>0βi0β^iLS<0βi0

Fall 1 : . Da , ist und dies in Bezug auf differenzieren und gleich Null zu setzen erhalten wir und dies ist nur möglich, wenn die rechte Seite nicht ist. In diesem Fall lautet die tatsächliche Lösung also βi0Li= - β LS i & beta;i+1β^iLS>0βi0

Li=β^iLSβi+12βi2+γβi,
βiβi=β^iLSγ
β^ilasso=(β^iLSγ)+=sgn(β^iLS)(|β^iLS|γ)+.

Fall 2 : . Dies impliziert, dass wir und daher Differenziert man in Bezug auf und setzt es auf Null, so erhält man . Aber um dies zu gewährleisten, brauchen wir , was durch β^iLS0βi0

Li=β^iLSβi+12βi2γβi.
βiβi=β^iLS+γ=sgn(β^iLS)(|β^iLS|γ)βi0
β^ilasso=sgn(β^iLS)(|β^iLS|γ)+.

In beiden Fällen erhalten wir die gewünschte Form und sind fertig.

Schlussbemerkungen

Beachten Sie, dass mit zunehmendem jedes dernimmt notwendigerweise ab, daher auch . Wenn , werden die OLS-Lösungen wiederhergestellt, und fürerhalten wir für alle .γ|β^ilasso|β^lasso1γ=0γ>maxi|β^iLS|β^ilasso=0i

Kardinal
quelle
2
Großartige Beschreibung @ cardinal!
Gary
9
+1 Die gesamte zweite Hälfte kann durch die einfache Beobachtung ersetzt werden, dass die Zielfunktion ist eine Vereinigung von Teilen zweier konvexer Parabeln mit Eckpunkten bei , wobei das negative Vorzeichen für und das positive für das andere genommen wird. Die Formel ist nur eine ausgefallene Möglichkeit, den unteren Scheitelpunkt auszuwählen. β12β2+(±γβ^)β±γβ^β<0
whuber
Wenn möglich, möchte ich die Ableitungen unter Verwendung der KKT-Optimalitätsbedingungen sehen. Welche anderen Möglichkeiten gibt es, um dieses Ergebnis abzuleiten?
user1137731
5
@Cardinal: danke für eine nette ableitung. Eine Beobachtung. Wenn ich mich recht entsinne, ist eine Matrix mit orthogonalen Spalten nicht die gleiche wie eine orthogonale (auch als orthonormal bezeichnete) Matrix. Dann ist für eine Diagonalmatrix (nicht notwendigerweise eine Identitätsmatrix). Mit orthogonalen Matrixannahmen (wie in der ursprünglichen Frage) haben wir und alles sieht gut aus :)XX=DDXX=I
Oleg Melnikov
@ cardinal Ich verstehe nicht, warum Sie sagen, "da wir sonst das Vorzeichen umdrehen und einen niedrigeren Wert für die Zielfunktion erhalten könnten". Wir leiten die objektive Funktion ab. Was ist, wenn die Zielfunktion höher oder niedriger ist? Wir kümmern uns nur darum, dass die Ableitung auf Null gesetzt wird, wir kümmern uns um die Extreme. Ob es um eine Konstante höher oder niedriger ist, hat keinen Einfluss auf das Argmin.
user13985
7

Angenommen, die Kovariaten , die Spalten von , sind ebenfalls standardisiert, so dass . Dies dient später nur der Vereinfachung: Ohne wird die Notation nur schwerer, da nur diagonal ist. Weiter wird angenommen, dass . Dies ist eine notwendige Voraussetzung, damit das Ergebnis erhalten bleibt. Definieren Sie den Schätzer der kleinsten Quadrate . Dann die (Lagrange-Form des) Lasso-Schätzers xjXRn×pXTX=IXTXnpβ^OLS=argminβyXβ22 proxffS& agr;& agr;

(defn.)β^λ=argminβ12nyXβ22+λβ1(OLS is projection)=argminβ12nXβ^OLSXβ22+λβ1(XTX=I)=argminβ12nβ^OLSβ22+λβ1(algebra)=argminβ12β^OLSβ22+nλβ1(defn.)=proxnλ1(β^OLS)(takes some work)=Snλ(β^OLS),
\ end {align *} wobei der proximale Operator einer Funktion und weiche Schwellen um den BetragproxffSαα.

Dies ist eine Ableitung, die die detaillierte Ableitung des von Cardinal ausgearbeiteten proximalen Operators überspringt, aber hoffentlich die Hauptschritte klärt, die eine geschlossene Form ermöglichen.

user795305
quelle