Modyfikacja Lasso dla LARS

12

Próbuję zrozumieć, w jaki sposób można zmodyfikować algorytm Larsa w celu wygenerowania Lasso. Chociaż rozumiem LARS, nie jestem w stanie zobaczyć modyfikacji Lasso z pracy Tibshirani i in. W szczególności nie rozumiem, dlaczego warunek znaku w tym, że znak niezerowej współrzędnej musi zgadzać się ze znakiem bieżącej korelacji. Czy ktoś mógłby mi z tym pomóc. Chyba szukam matematycznego dowodu przy użyciu warunku KKT na pierwotnym problemie normy L-1, tj. Lasso. Dzięki wielkie!

lasso

— nowicjusz
źródło

To dotyczy Efron wsp za stanford.edu/~hastie/Papers/LARS/LeastAngle_2002.pdf ? Potwierdza to Lemat 8 rozdziału 5. Czy też źle rozumiem twoje pytanie?

— Peter Ellis

1

Nie jestem również pewien pytania, ale tak naprawdę Lasso jest uproszczeniem Larsa: dla Lasso szukasz tylko pozytywnych korelacji między bieżącą resztą a pozostałymi funkcjami bazowymi, ponieważ tylko pozytywne korelacje prowadzą do pozytywnych (~ nieujemne) współczynniki.

— Mr. White

2

Niech (rozmiar ) oznacza zestaw standardowych danych wejściowych, (rozmiar ) wyśrodkowane odpowiedzi, (rozmiar ) wagi regresji i a -normalny współczynnik karania. $X$ $n\times p$ $y$ $n \times 1$ $\beta$ $p \times 1$ $\lambda > 0$ $l_1$

Problem LASSO zapisuje następnie

\begin{aligned} β^{*} & = {argmin}_{β} L (β, λ) \\ L (β, λ) & = ‖ y - X β ‖_{2}^{2} + λ ‖ β ‖_{1} \end{aligned}

$\begin{align} \beta^* &= \text{argmin}_{\beta}\ L(\beta,\lambda) \\ L(\beta,\lambda) &= \Vert y-X\beta \Vert_2^2 + \lambda \Vert \beta \Vert_1 \end{align}$

Rozwiązanie tego dla wszystkich wartości daje tak zwaną ścieżkę regularyzacji LASSO . $\lambda > 0$ $\beta^*(\lambda)$

Dla stałej wartości współczynnika karania (tj. Stałej liczby aktywnych predyktorów = ustalony krok algorytmu LARS), możliwe jest wykazanie, że spełnia (wystarczy zapisać warunek stacjonarności KKT, jak w tym przypadku odpowiedź ) $\lambda^*$ $\beta^*$

λ^{*} = 2 sign (β_{a}^{*}) X_{a}^{T} (y - X β^{*}), \forall a \in A

$\lambda^* = 2 \ \text{sign}(\beta_a^*) X_a^T (y - X \beta^*),\ \ \ \forall a \in A$

gdzie reprezentuje zestaw aktywnych predyktorów. $A$

Ponieważ musi być dodatnia (jest to współczynnik karania), jasne jest, że znak (waga dowolnego niezerowego, a więc aktywnego predyktora) powinien być taki sam jak tj. Korelacja z obecną resztkową regresją. $\lambda^*$ $\beta_a^*$ $X_a^T (y - X\beta^*) = X_{a}^T r$

— Quantuple
źródło

1

@ Mr._White podał świetne intuicyjne wyjaśnienie głównej różnicy między LARS a Lasso; Jedyne, co chciałbym dodać, to to, że lasso jest (w pewnym sensie) podejściem do selekcji wstecznej, znokautowując termin na każdym kroku, o ile istnieje termin, dla którego istnieje korelacja („znormalizowana” względem ). LARS utrzymuje wszystko tam - po prostu wykonując lasso w każdej możliwej kolejności. Oznacza to, że w lasso każda iteracja zależy od tego, które warunki zostały już usunięte. $X \times X$

Implementacja Effrona dobrze ilustruje różnice między nimi: lars.R w źródłowym pkg dla larsa . Zwróć uwagę na krok aktualizacji macierzy macierzy i rozpoczynający się od linii 180, oraz porzucenie warunków, dla których . Mogę sobie wyobrazić niektóre dziwne sytuacje wynikające ze spacji których warunki są niezrównoważone ( i są bardzo skorelowane, ale nie z innymi, z ale nie z innymi itd.), Kolejność wyboru może być dość stronnicza. $X \times X$ $\zeta$ $\zeta_{min} < \zeta_{current}$ $A$ $x_1$ $x_2$ $x_2$ $x_3$

— egbutter
źródło