Herleitung der Lasso-Lösung in geschlossener Form

Für das Lasso-Problem so dass . Ich sehe oft das Ergebnis der Schwelle für den orthonormalen 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_\beta (Y-X\beta)^T(Y-X\beta)$ $\|\beta\|_1 \leq t$

β_{j}^{lasso} = s g n (β_{j}^{LS}) (| β_{j}^{LS} | - γ)^{+}

$\beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\gamma)^+$

X

$X$

lasso Gary
quelle

Dies scheint etwas verwirrt. Zu Beginn nehmen Sie eine Bedingung

t

$t$ und geben in der Lösung einen Parameter

γ

$\gamma$ . 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

Teilweise auf @cardinal zu antworten und das

β

$\beta$ , das

minimiert

(Y - X β)^{'} (Y - X β)

$(Y-X\beta )'(Y-X\beta )$ abhängig von

‖ β ‖_{1} \leq t

$\|\beta\|_1 \leq t$ ist gleichbedeutend mit dem Finden des

β

$\beta$ , das minimiert

(Y - X β)^{'} (Y - X β) + γ \sum_{j} | β_{j} |

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ . Es gibt eine 1-1 Beziehung zwischen

t

$t$ und

γ

$\gamma$ . 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.

Ein weiterer Hinweis, wenn Sie das

β

$\beta$ , das

(Y - X β)^{'} (Y - X β) + γ \sum_{j} | β_{j} |

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ Teilen Sie das Problem in die Fälle

β_{j} > 0

$\beta_j >0$ ,

β_{j} < 0

$\beta_j<0$ und

β = 0

$\beta=0$ .

@ Kardinal Ah ja, 1-1 ist falsch. Korrektur: Für jedes

t \geq 0

$t\geq0$ gibt es ein

γ \geq 0

$\gamma\geq 0$ .

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:

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 $X$

{\hat{β}}^{LS} = (X^{T} X)^{- 1} X^{T} y = X^{T} y .

$\newcommand{\bls}{\hat{\beta}^{{\small \text{LS}}}}\newcommand{\blasso}{\hat{\beta}^{{\text{lasso}}}} \bls = (X^T X)^{-1} X^T y = X^T y \>.$

Einige äquivalente Probleme

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

min_{β} \frac{1}{2} ‖ y - X β ‖_{2}^{2} + γ ‖ β ‖_{1} .

$\min_\beta \frac{1}{2} \|y - X \beta\|_2^2 + \gamma \|\beta\|_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: $\frac{1}{2} y^T y - y^T X \beta + \frac{1}{2}\beta^T \beta$ $y^T y$

min_{β} (- y^{T} X β + \frac{1}{2} ‖ β ‖^{2}) + γ ‖ β ‖_{1} .

$\min_\beta (- y^T X \beta + \frac{1}{2} \|\beta\|^2) + \gamma \|\beta\|_1 \>.$

Mit kann das vorherige Problem als umgeschrieben werden. $\bls = X^T y$

min_{β} \sum_{i = 1}^{p} - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ | β_{i} | .

$\min_\beta \sum_{i=1}^p - \bls_i \beta_i + \frac{1}{2} \beta_i^2 + \gamma |\beta_i| \> .$

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

Das Ganze ist gleich der Summe seiner Teile

Repariere ein bestimmtes . Dann wollen wir minimieren $i$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ | β_{i} | .

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma |\beta_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 . $\bls_i > 0$ $\beta_i \geq 0$ $\bls_i < 0$ $\beta_i \leq 0$

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 $\bls_i > 0$ $\beta_i \geq 0$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ β_{i},

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma \beta_i \> ,$

β_{i}

$\beta_i$

β_{i} = {\hat{β}}_{i}^{LS} - γ

$\beta_i = \bls_i - \gamma$

{\hat{β}}_{i}^{lasso} = ({\hat{β}}_{i}^{LS} - γ)^{+} = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)^{+} .

$\blasso_i = (\bls_i - \gamma)^+ = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>.$

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 $\bls_i \leq 0$ $\beta_i \leq 0$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} - γ β_{i} .

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 - \gamma \beta_i \> .$

β_{i}

$\beta_i$

β_{i} = {\hat{β}}_{i}^{LS} + γ = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)

$\beta_i = \bls_i + \gamma = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)$

β_{i} \leq 0

$\beta_i \leq 0$

{\hat{β}}_{i}^{lasso} = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)^{+} .

$\blasso_i = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>.$

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

Schlussbemerkungen

Kardinal
quelle

Großartige Beschreibung @ cardinal!

Gary

+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.

β \to \frac{1}{2} β^{2} + (\pm γ - \hat{β}) β

$\beta\to\frac{1}{2}\beta^2+(\pm\gamma-\hat{\beta})\beta$

\pm γ - \hat{β}

$\pm\gamma-\hat{\beta}$

β < 0

$\beta\lt 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

@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 :)

X^{'} X = D

$X'X=D$

D

$D$

X^{'} X = I

$X'X=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

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 $x_j$ $X \in \mathbb{R}^{n \times p}$ $X^T X = I$ $X^T X$ $n \geq p$ $\hat\beta_{OLS} = \arg\min_\beta \|y - X \beta\|_2^2$

\begin{aligned} (defn.) & {\hat{β}}_{λ} & = \arg min_{β} \frac{1}{2 n} ‖ y - X β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (OLS is projection) & = \arg min_{β} \frac{1}{2 n} ‖ X {\hat{β}}_{O L S} - X β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (X^{T} X = I) & = \arg min_{β} \frac{1}{2 n} ‖ {\hat{β}}_{O L S} - β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (algebra) & = \arg min_{β} \frac{1}{2} ‖ {\hat{β}}_{O L S} - β ‖_{2}^{2} + n λ ‖ β ‖_{1} \\ (defn.) & = {p r o x}_{n λ ‖ \cdot ‖_{1}} ({\hat{β}}_{O L S}) \\ (takes some work) & = S_{n λ} ({\hat{β}}_{O L S}), \end{aligned}

$\begin{align*} \hat\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 is projection} \\ & = \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{takes some work}, \end{align*}$ \ end {align *} wobei der proximale Operator einer Funktion und weiche Schwellen um den Betrag

{p r o x}_{f}

$\mathrm{prox}_f$

f

$f$

S_{α}

$S_{\alpha}$

α

$\alpha$ .

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