Dlaczego moje wyprowadzenie rozwiązania lasso w zamkniętej formie jest nieprawidłowe?

Problem lasso ma rozwiązanie w formie zamkniętej: \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _ j) (| \ beta_j ^ {\ text {LS }} | - \ alpha) ^ + jeśli X ma kolumny ortonormalne. Pokazano to w tym wątku: Wyprowadzenie zamkniętego rozwiązania lasso .

$$\beta^{\text{lasso}}= \operatorname*{argmin}_\beta \| y-X\beta\|^2_2 + \alpha \| \beta\|_1$$ $$\beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\alpha)^+$$ $X$

Nie rozumiem jednak, dlaczego ogólnie nie ma rozwiązania w formie zamkniętej. Korzystając z subdifferentials otrzymałem następujące.

( $X$ jest $n \times p$ )

$$f(\beta)=\|{y-X\beta}\|_2^2 + \alpha\|{\beta}\|_1$$ $$=\sum_{i=1}^n (y_i-X_i\beta)^2 + \alpha \sum_{j=1}^p |\beta_j|$$ ( $X_i$ to i-ty rząd $X$ ) $$= \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 \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}^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}$$ Z $\frac{\partial f}{\partial \beta_j} = 0$ otrzymujemy

$$\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}$$

Czy ktoś widzi, gdzie popełniłem błąd?

Odpowiedź:

Jeśli piszemy problem w postaci macierzy, możemy bardzo łatwo zrozumieć, dlaczego rozwiązanie formy zamkniętej istnieje tylko w przypadku ortonormalnym z $X^TX= I$ :

$$f(\beta)= \| y-X\beta\|^2_2 + \alpha \| \beta\|_1$$ $$= y^Ty -2\beta^TX^Ty + \beta^TX^TX\beta + \alpha \| \beta\|_1$$ $$\Rightarrow \nabla f(\beta)=-2X^Ty + 2X^TX\beta + \nabla(\alpha| \beta\|_1)$$ (tutaj zrobiłem wiele kroków naraz. Jednak, do tego momentu jest to całkowicie analogiczne do wyprowadzania rozwiązania najmniejszych kwadratów. Więc powinieneś być w stanie znaleźć tam brakujące kroki.) $$\Rightarrow \frac{\partial f}{\partial \beta_j}=-2X^T_{j} y + 2(X^TX)_j \beta + \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|)$$

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

$$2(X^TX)_j \beta =2X^T_{j} y - \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|)$$ $$\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$$

Widzimy teraz, że nasze rozwiązanie dla jednego zależy od wszystkich pozostałych więc nie jest jasne, jak postępować tutaj. Jeśli jest ortonormalny, mamy więc na pewno istnieje rozwiązanie w formie zamkniętej.$\beta_j$$\beta_{i\neq j}$$X$$2(X^TX)_j \beta = 2(I)_j \beta = 2\beta_j$

Dziękuję Guðmundurowi Einarssonowi za jego odpowiedź, na której tu opracowałem. Mam nadzieję, że tym razem jest to poprawne :-)

Zwykle odbywa się to z regresją najmniejszego kąta, papier można znaleźć tutaj .

Przepraszam za moje zamieszanie na początku, podejmę kolejną próbę.

Po rozszerzeniu funkcji otrzymujesz$f(\beta)$

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

Następnie obliczasz pochodną cząstkową w odniesieniu do . Moje obawy dotyczą twojego wyliczenia pochodnej cząstkowej ostatniego terminu przed normą 1, tj. Wyrażenia kwadratowego. Przeanalizujmy to dalej. Mamy to:$\beta_j$

$$X_i\beta = \beta^T X_i^T = (\beta_1 X_{i1}+\beta_2 X_{i2}+\cdots+ \beta_p X_{ip})$$ Tak więc możesz zasadniczo przepisać swój kwadratowy termin jako: Teraz możemy użyć reguły łańcucha do obliczenia pochodnej tego wrt : $$\sum_{i=1}^n \beta^T X_i^T X_i \beta = \sum_{i=1}^n (X_i \beta)^2$$ $\beta_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}$$

Więc teraz twój problem nie upraszcza się tak łatwo, ponieważ masz wszystkie współczynniki obecne w każdym równaniu.$\beta$

To nie odpowiada na pytanie, dlaczego nie ma zamkniętego rozwiązania Lasso, mógłbym dodać coś później.