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

Das Lasso-Problem hat die geschlossene Form Lösung: wenn orthonormale Spalten hat. Dies wurde in diesem Thread gezeigt: Herleitung einer Lasso-Lösung in geschlossener Form .

β^{lasso} = \underset{β}{argmin} ‖ y - X β ‖_{2}^{2} + α ‖ β ‖_{1}

$\beta^{\text{lasso}}= \operatorname*{argmin}_\beta \| y-X\beta\|^2_2 + \alpha \| \beta\|_1$

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

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

X

$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 \times p$ Matrix)

f (β) = ‖ y - X β ‖_{2}^{2} + α ‖ β ‖_{1}

$f(\beta)=\|{y-X\beta}\|_2^2 + \alpha\|{\beta}\|_1$

= \sum_{i = 1}^{n} (y_{i} - X_{i} β)^{2} + α \sum_{j = 1}^{p} | β_{j} |

$=\sum_{i=1}^n (y_i-X_i\beta)^2 + \alpha \sum_{j=1}^p |\beta_j|$ ( ist die i-te Reihe von )

X_{i}

$X_i$

X

$X$

= \sum_{i = 1}^{n} y_{i}^{2} - 2 \sum_{i = 1}^{n} y_{i} X_{i} β + \sum_{i = 1}^{n} β^{T} X_{i}^{T} X_{i} β + α \sum_{j = 1}^{p} | β_{j} |

$= \sum_{i=1}^n y_i^2 -2\sum_{i=1}^n y_i X_i \beta + \sum_{i=1}^n \beta^T X_i^T X_i \beta + \alpha \sum_{j=1}^p |\beta_j|$

\Rightarrow \frac{\partial f}{\partial β_{j}} = - 2 \sum_{i = 1}^{n} y_{i} X_{i j} + 2 \sum_{i = 1}^{n} X_{i j}^{2} β_{j} + \frac{\partial}{\partial β_{j}} (α | β_{j} |)

$\Rightarrow \frac{\partial f}{\partial \beta_j}= -2\sum_{i=1}^ny_i X_{ij} + 2 \sum_{i=1}^n X_{ij}^2\beta_j + \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|)$

= {\begin{cases} - 2 \sum_{i = 1}^{n} y_{i} X_{i j} + 2 \sum_{i = 1}^{n} X_{i j}^{2} β_{j} + α for β_{j} > 0 \\ - 2 \sum_{i = 1}^{n} y_{i} X_{i j} + 2 \sum_{i = 1}^{n} X_{i j}^{2} β_{j} - α for β_{j} < 0 \\ [- 2 \sum_{i = 1}^{n} y_{i} X_{i j} - α, - 2 \sum_{i = 1}^{n} y_{i} X_{i j} + α] for β_{j} = 0 \end{cases}

$= \begin{cases} -2\sum_{i=1}^ny_i X_{ij} + 2 \sum_{i=1}^n X_{ij}^2\beta_j + \alpha \text{ for } \beta_j > 0 \\ -2\sum_{i=1}^ny_i X_{ij} + 2 \sum_{i=1}^n X_{ij}^2\beta_j - \alpha \text{ for } \beta_j < 0 \\ [-2\sum_{i=1}^ny_i X_{ij} - \alpha, -2\sum_{i=1}^ny_i X_{ij} + \alpha] \text{ for } \beta_j = 0 \end{cases}$ Mit wir

\frac{\partial f}{\partial β_{j}} = 0

$\frac{\partial f}{\partial \beta_j} = 0$

β_{j} = {\begin{cases} (2 (\sum_{i = 1}^{n} y_{i} X_{i j}) - α) / 2 \sum_{i = 1}^{n} X_{i j}^{2} & for \sum_{i = 1}^{n} y_{i} X_{i j} > α \\ (2 (\sum_{i = 1}^{n} y_{i} X_{i j}) + α) / 2 \sum_{i = 1}^{n} X_{i j}^{2} & for \sum_{i = 1}^{n} y_{i} X_{i j} < - α \\ 0 & for \sum_{i = 1}^{n} y_{i} X_{i j} \in [- α, α] \end{cases}

$\beta_j = \begin{cases} \left( 2(\sum_{i=1}^ny_i X_{ij}) - \alpha \right)/ 2\sum_{i=1}^n X_{ij}^2 &\text{for } \sum_{i=1}^ny_i X_{ij} > \alpha \\ \left( 2(\sum_{i=1}^ny_i X_{ij}) + \alpha \right)/ 2\sum_{i=1}^n X_{ij}^2 &\text{for } \sum_{i=1}^ny_i X_{ij} < -\alpha \\ 0 &\text{ for }\sum_{i=1}^ny_i X_{ij} \in [-\alpha, \alpha] \end{cases}$

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 $X^TX= I$ :

f (β) = ‖ y - X β ‖_{2}^{2} + α ‖ β ‖_{1}

$f(\beta)= \| y-X\beta\|^2_2 + \alpha \| \beta\|_1$

= y^{T} y - 2 β^{T} X^{T} y + β^{T} X^{T} X β + α ‖ β ‖_{1}

$= y^Ty -2\beta^TX^Ty + \beta^TX^TX\beta + \alpha \| \beta\|_1$

\Rightarrow \nabla f (β) = - 2 X^{T} y + 2 X^{T} X β + \nabla (α | β ‖_{1})

$\Rightarrow \nabla f(\beta)=-2X^Ty + 2X^TX\beta + \nabla(\alpha| \beta\|_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.)

\Rightarrow \frac{\partial f}{\partial β_{j}} = - 2 X_{j}^{T} y + 2 (X^{T} X)_{j} β + \frac{\partial}{\partial β_{j}} (α | β_{j} |)

$\Rightarrow \frac{\partial f}{\partial \beta_j}=-2X^T_{j} y + 2(X^TX)_j \beta + \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|)$

Mit $\frac{\partial f}{\partial \beta_j} = 0$ wir

2 (X^{T} X)_{j} β = 2 X_{j}^{T} y - \frac{\partial}{\partial β_{j}} (α | β_{j} |)

$2(X^TX)_j \beta =2X^T_{j} y - \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|)$

\Leftrightarrow 2 (X^{T} X)_{j j} β_{j} = 2 X_{j}^{T} y - \frac{\partial}{\partial β_{j}} (α | β_{j} |) - 2 \sum_{i = 1, i \neq j}^{p} (X^{T} X)_{j i} β_{i}

$\Leftrightarrow 2(X^TX)_{jj} \beta_j = 2X^T_{j} y - \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|) - 2\sum_{i=1,i\neq j}^p(X^TX)_{ji}\beta_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. $\beta_j$ $\beta_{i\neq j}$ $X$ $2(X^TX)_j \beta = 2(I)_j \beta = 2\beta_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 :-)

regression lasso regularization Norbert
quelle

Willkommen bei CrossValidated und herzlichen Glückwunsch zu einem sehr schönen ersten Beitrag!

S. Kolassa - Wiedereinsetzung von Monica

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 also $f(\beta)$

f (β) = \sum_{i = 1}^{n} y_{i}^{2} - 2 \sum_{i = 1}^{n} y_{i} X_{i} β + \sum_{i = 1}^{n} β^{T} X_{i}^{T} X_{i} β + α \sum_{j = 1}^{p} | β_{j} |

$f(\beta)=\sum_{i=1}^n y_i^2 -2\sum_{i=1}^n y_i X_i \beta + \sum_{i=1}^n \beta^T X_i^T X_i \beta + \alpha \sum_{j=1}^p |\beta_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: $\beta_j$

X_{i} β = β^{T} X_{i}^{T} = (β_{1} X_{i 1} + β_{2} X_{i 2} + \dots + β_{p} X_{i p})

$X_i\beta = \beta^T X_i^T = (\beta_1 X_{i1}+\beta_2 X_{i2}+\cdots+ \beta_p X_{ip})$ Sie können Ihren quadratischen Ausdruck also im Wesentlichen wie umschreiben: Nun können wir die Ableitung dieses wrt : mit der Kettenregel berechnen.

\sum_{i = 1}^{n} β^{T} X_{i}^{T} X_{i} β = \sum_{i = 1}^{n} (X_{i} β)^{2}

$\sum_{i=1}^n \beta^T X_i^T X_i \beta = \sum_{i=1}^n (X_i \beta)^2$

β_{j}

$\beta_j$

\frac{\partial}{\partial β_{j}} \sum_{i = 1}^{n} (X_{i} β)^{2} = \sum_{i = 1}^{n} \frac{\partial}{\partial β_{j}} (X_{i} β)^{2} = \sum_{i = 1}^{n} 2 (X_{i} β) X_{i j}

$\frac{\partial }{\partial \beta_j} \sum_{i=1}^n (X_i \beta)^2 = \sum_{i=1}^n \frac{\partial }{\partial \beta_j} (X_i \beta)^2 = \sum_{i=1}^n 2(X_i \beta)X_{ij}$

Jetzt vereinfacht sich Ihr Problem nicht mehr so einfach, da in jeder Gleichung alle Koeffizienten vorhanden sind. $\beta$

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

Vielen Dank. Ich kann jetzt tatsächlich sehen, warum es keine geschlossene Lösung gibt (siehe meine Bearbeitung).

Norbert

Süss! Tolle Arbeit :)

Gumeo