Wyprowadzenie zamkniętego rozwiązania lasso

$\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
źródło

To wydaje się nieco zdezorientowane. Na początku zakładamy ograniczenie

t

$t$ aw rozwiązaniu wprowadzamy parametr

γ

$\gamma$ . Zgaduję, że zamierzasz połączyć tych dwóch poprzez podwójny problem, ale może możesz wyjaśnić, czego szukasz.

kardynał

Częściowa odpowiedź na @cardinal, znalezienie

β

$\beta$ która minimalizuje

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

$(Y-X\beta )'(Y-X\beta )$ zastrzeżeniem

‖ β ‖_{1} \leq t

$\|\beta\|_1 \leq t$ jest równoważne znalezieniu

β

$\beta$ która minimalizuje

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

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ . Jest 1-1 zależność pomiędzy

t

$t$ i

γ

$\gamma$ . Aby „łatwo” zrozumieć, dlaczego tak jest w przypadku miękkiego progu, zaleciłbym rozwiązanie drugiego wyrażenia (w moim komentarzu).

Kolejna uwaga, znajdując

β

$\beta$ która minimalizuje

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

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ ,

problem na przypadki

β_{j} > 0

$\beta_j >0$ ,

β_{j} < 0

$\beta_j<0$ i

β = 0

$\beta=0$ .

@ kardynał Ah tak, 1-1 jest niepoprawny. Korekta: dla każdego

t \geq 0

$t\geq0$ można znaleźć

γ \geq 0

$\gamma\geq 0$ .

Dzięki za wspaniałą dyskusję! Natknąłem się na ten film na Coursera - Wyprowadzanie aktualizacji zejścia współrzędnych lasso , która jest bardzo istotna w tej dyskusji i bardzo elegancko omawia rozwiązanie. Może być pomocny dla przyszłych gości :-)

zorbar

Odpowiedzi:

Można to zaatakować na wiele sposobów, w tym dość ekonomiczne podejście w warunkach Karusha-Kuhna-Tuckera .

Poniżej znajduje się dość elementarny alternatywny argument.

Rozwiązanie najmniejszych kwadratów dla projektu ortogonalnego

Załóżmy, że składa się z kolumn ortogonalnych. Zatem rozwiązaniem najmniejszych kwadratów jest $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 \>.$

Niektóre równoważne problemy

Poprzez formularz Lagrangian łatwo jest zauważyć, że problemem równoważnym do rozważanego w pytaniu jest

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

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

Rozszerzając pierwszy termin otrzymujemy a ponieważ nie zawiera żadnych zmiennych będących przedmiotem zainteresowania, możemy je odrzucić i rozważyć kolejny równoważny problem, $\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 \>.$

Zwracając uwagę, że , poprzedni problem można przepisać jako $\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| \> .$

Nasza funkcja celu jest teraz sumą celów, z których każdy odpowiada osobnej zmiennej , więc każdy z nich można rozwiązać indywidualnie. $\beta_i$

Całość jest równa sumie jej części

Napraw niektóre . Następnie chcemy zminimalizować $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| \> .$

Jeśli , to musimy mieć ponieważ w przeciwnym razie moglibyśmy przerzucić jego znak i uzyskać niższą wartość dla funkcji celu. Podobnie, jeśli , to musimy wybrać . $\bls_i > 0$ $\beta_i \geq 0$ $\bls_i < 0$ $\beta_i \leq 0$

Przypadek 1 : . Od , i różnicując to w odniesieniu do i ustawienia równego zeru , otrzymujemy i jest to wykonalne tylko wtedy, gdy prawa strona jest nieujemna, więc w tym przypadku faktycznym rozwiązaniem jest $\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)^+ \>.$

Przypadek 2 : . Oznacza to, że musimy mieć a więc Rozróżniając względem i ustawiając wartość równą zero, otrzymujemy . Ale znowu, aby upewnić się, że jest to wykonalne, potrzebujemy , co osiąga się przyjmując $\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)^+ \>.$

W obu przypadkach otrzymujemy pożądaną formę, więc gotowe.

Uwagi końcowe

kardynał
źródło

Świetny napis @ cardinal!

Gary

+1 Całą drugą połowę można zastąpić prostą obserwacją, że funkcją celu jest połączenie części dwóch wypukłych parabol z wierzchołkami w , gdzie znak ujemny jest brany dla a dodatni w przeciwnym razie. Formuła jest tylko fantazyjnym sposobem wyboru niższego wierzchołka.

β \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

Jeśli to możliwe, chciałbym zobaczyć pochodne przy użyciu warunków optymalności KKT. Jakie są inne sposoby uzyskania tego wyniku?

user1137731,

@Cardinal: dzięki za fajną pochodną. Jedna obserwacja. O ile pamiętam, macierz z kolumnami ortogonalnymi nie jest tym samym co macierz ortogonalna (inaczej ortonormalna). Następnie dla pewnej macierzy diagonalnej (niekoniecznie macierz identyczności). Przy założeniu macierzy ortogonalnej (jak w pierwotnym pytaniu) mamy i wszystko wygląda świetnie :)

X^{'} X = D

$X'X=D$

D

$D$

X^{'} X = I

$X'X=I$

Oleg Melnikov

@ cardinal Nie rozumiem, dlaczego mówisz „ponieważ w przeciwnym razie moglibyśmy odwrócić jego znak i uzyskać niższą wartość dla funkcji celu”. Bierzemy pochodną funkcji celu. A co jeśli funkcja celu jest wyższa lub niższa, kogo to obchodzi. Jedyne, na czym nam zależy, to pochodne ustawione na zero, dbamy o ekstremum. To, czy jest ona wyższa czy niższa o stałą, nie wpływa na argmin.

user13985,

Załóżmy, że zmienne , kolumny , są znormalizowane tak, że . Jest to dla wygody później: bez tego notacja staje się coraz cięższa, ponieważ jest tylko przekątna. Dalej zakładamy, że . Jest to niezbędne założenie do utrzymania wyniku. Zdefiniuj estymator najmniejszych kwadratów . Następnie (forma Lagrange'a) estymatora lasso $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 *} gdzie jest bliższym operatorem funkcji i miękkich progów o wartość

{p r o x}_{f}

$\mathrm{prox}_f$

f

$f$

S_{α}

$S_{\alpha}$

α

$\alpha$ .

Jest to wyprowadzenie, które pomija szczegółowe wyprowadzenie bliższego operatora, które opracowuje Kardynał, ale mam nadzieję, że wyjaśnia główne kroki, które umożliwiają zamknięcie formularza.

użytkownik795305
źródło