Jeśli p> n, lasso wybiera co najwyżej n zmiennych

Jedną z motywów elastycznej siatki było następujące ograniczenie LASSO:

W przypadku lasso wybiera co najwyżej n zmiennych przed nasyceniem, ze względu na naturę problemu optymalizacji wypukłej. Wydaje się, że jest to cecha ograniczająca metodę wyboru zmiennych. Co więcej, lasso nie jest dobrze zdefiniowane, chyba że granica normy L1 współczynników jest mniejsza niż pewna wartość. $p > n$

( http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9868.2005.00503.x/full )

Rozumiem, że LASSO jest kwadratowym problemem programistycznym, ale można go również rozwiązać za pomocą LARS lub elementarnego spadku gradientu. Ale nie rozumiem, gdzie w tych algorytmach napotykam problem, jeśli gdzie jest liczbą predyktorów, a jest wielkością próbki. I dlaczego ten problem rozwiązano za pomocą elastycznej siatki, w której zwiększam problem do zmiennych , które wyraźnie przekraczają . $p > n$ $p$ $n$ $p+n$ $p$

— użytkownik1137731
źródło

Jeśli lasso ogranicza użycie do zachowania p <= n, dlaczego jest to wada, a nie cnota. nadmierne dopasowanie jest poważnym problemem, który pojawia się, gdy p = n. Model z p = n jest modelem nasyconym i często ten model pasuje, ponieważ idealnie pasuje do obserwowanych danych, ale niekoniecznie dobrze predykuje przyszłe przypadki.

— Michael R. Chernick

To, że lasso wybiera tylko do zmiennych, może być postrzegane jako konsekwencja faktu, że można je rozwiązać za pomocą (niewielkiej modyfikacji) algorytmu LARS, który dopuszcza tylko zmiennych do zestawu aktywnego w danym momencie. To, że nie ma to miejsca w przypadku siatki elastycznej, wynika zasadniczo z włączenia kary a zatem zachowuje się bardziej jak regresja kalenicy, z której ta ostatnia normalnie powoduje, że wszystkie współczynniki są niezerowe.

n

$n$

n

$n$

ℓ_{2}

$\ell_2$

— kardynał

Dziękuję za odpowiedzi i jak mogę zobaczyć spadek gradientu, który można wybrać co najwyżej n zmiennych: Prezentacja na cs.cmu.edu/afs/cs/project/link-3/lafferty/www/ml-stat2/talks/ ... Papier (rozdział 4) w datamining.dongguk.ac.kr/papers/GLASSO_JRSSB_V1.final.pdf

— user1137731

@ użytkownik: Myślę, że możesz pogodzić problem matematyczny z jego rozwiązaniem numerycznym. Algorytm LARS pokazuje, że rozwiązanie lasso wybierze co najwyżej zmiennych. Jest to niezależne od rzeczywistych środków numerycznych służących do znalezienia rozwiązania, tj. Algorytm LARS daje wgląd w problem, ale oczywiście każda inna metoda, która równo rozwiązuje problem, musi mieć tę samą właściwość! :-)

n

$n$

— kardynał

Rozważmy zduplikowaną funkcję razy. Będzie istniał estymator lasso z dokładnie nonzeroes (nawet jeśli ) Dlatego twoje stwierdzenie nie jest prawdziwe, jak napisano.

p

$p$

p

$p$

p > n

$p>n$

— user795305

Odpowiedzi:

Jak powiedziano, nie jest to właściwość algorytmu, ale problem optymalizacji. Warunki KKT w zasadzie dają, że aby współczynnik był niezerowy, musi odpowiadać stałej korelacji z resztkowym ( jest parametrem regularyzacji). $\beta_j$ $|X_j^t(y-X\beta)| = \lambda$ $\lambda$

Po rozwiązaniu różnych komplikacji z wartością bezwzględną itp., Pozostaje Ci liniowe równanie dla każdego niezerowego współczynnika. Ponieważ ranga macierzy wynosi co najwyżej gdy , jest to liczba równań, które można rozwiązać, a zatem istnieje co najwyżej n niezerowych wartości (chyba że występują nadmiarowości). $X$ $n$ $p>n$

Nawiasem mówiąc, dotyczy to każdej funkcji utraty, nie tylko standardowego lassa z utratą . W rzeczywistości jest to właściwość kary lasso. Istnieje wiele artykułów, które pokazują ten widok KKT i wynikające z niego wnioski, mogę wskazać na nasz artykuł: Rosset i Zhu, Piecewise Linear Regularized Solutions Paths, Annals of Stats 2007 i odnośniki tam zawarte. $L_2$

— Saharon Rosset
źródło

Co oznacza skrót KKT? Czy to możliwe, że masz na myśli utratę L1, gdy mówisz o standardowym lasso?

— miura

Cześć Saharon i witam na stronie. Możesz użyć LaTeXa, aby formuły były bardziej czyste (zrobiłem to w twojej odpowiedzi) i nie musisz podpisywać swoich postów, ponieważ podpis jest dodawany automatycznie.

— Peter Flom - Przywróć Monikę

@miura: KKT oznacza Karush-Kuhn-Tucker. Warunki KKT to pewne równania, które muszą spełniać rozwiązania (wystarczająco regularne) problemów optymalizacyjnych ( artykuł na Wikipedii ).

— mogron

Widzę tylko, że Ryan Tibshirani ma bardzo odpowiedni dokument roboczy „The Lasso Problem and Uniqueness”: stat.cmu.edu/~ryantibs/papers/lassounique.pdf

— user1137731

$n < p$ $X$ $n$ $p - n$ $z$ $\beta$ $p - n$ $p$ $\beta+z$ $n$ $\beta_j$

‖ y - X (β + z) ‖_{2}^{2} + λ ‖ β + z ‖_{1} = ‖ y - X β ‖_{2}^{2} + λ ‖ β + z ‖_{1} < ‖ y - X β ‖_{2}^{2} + λ ‖ β ‖_{1}

zmniejszył się.

— użytkownik2969758
źródło

(+1) Jest tu luka: zobacz mój komentarz do postu PO.

— user795305