Czy istnieje podobne twierdzenie dotyczące lasso? Jeśli istnieje takie twierdzenie, nie tylko zagwarantuje ono stabilność lasso, ale także zapewni lasso bardziej sensowną interpretację:

lasso może odkryć wektor współczynnika regresji rzadkiej $c$ który jest używany do wygenerowania odpowiedzi $y$ przez $y = Xc$ .

Są dwa powody, dla których zadaję to pytanie:

1. Myślę, że „lasso preferuje rzadkie rozwiązanie” nie jest odpowiedzią na to, dlaczego używamy lasso do wyboru funkcji, ponieważ nie jesteśmy nawet w stanie powiedzieć, jaka jest zaleta wybranych przez nas funkcji.

2. Dowiedziałem się, że lasso słynie z niestabilności w wyborze funkcji. W praktyce musimy uruchomić próbki bootstrap, aby ocenić jego stabilność. Jaki jest najważniejszy powód, który powoduje tę niestabilność?

Dodatek:

Biorąc pod uwagę $X_{N \times M} = (x_1, \cdots, x_M)$ . $c$ jest wektorem $\Omega$ rzadkim ( $\Omega \leqslant M$ ). Proces $y = Xc$ generuje odpowiedź $y$ . Jeśli $X$ ma NSP (właściwość pustego miejsca) rzędu $\Omega$ a macierz kowariancji $X$ nie ma wartości własnej bliskiej zeru, będzie unikalne rozwiązanie dla

To twierdzenie mówi również, że jeśli nie ma NSP rzędu , po prostu beznadziejne jest rozwiązanie .Ω argmin c : y = X c ‖ c ‖ $X$$\Omega$$\text{argmin}_{c: y = Xc} \Vert c \Vert_1$

EDYTOWAĆ:

Po otrzymaniu tych wspaniałych odpowiedzi zdałem sobie sprawę, że byłem zdezorientowany, kiedy zadawałem to pytanie.

Dlaczego to pytanie jest mylące:

Czytam artykuł badawczy, w którym musimy zdecydować, ile funkcji (kolumn) będzie miała macierz projektowa (funkcje pomocnicze są tworzone z funkcji pierwotnych). Ponieważ jest to typowy problem , oczekuje się, że będzie dobrze skonstruowany, dzięki czemu rozwiązanie lasso może być dobrym przybliżeniem rzeczywistego rozwiązania rzadkiego. n < p $X_{N \times M}$$n < p$$D$

Rozumowanie opiera się na twierdzeniu, o którym wspomniałem w załączniku: jeśli chcemy znaleźć rozwiązanie rzadkie , lepiej jest mieć NSP rzędu .c X $\Omega$$c$$X$$\Omega$

W przypadku ogólnej macierzy , jeśli zostanie naruszone, toN > C Ω ln $N \times M$$N > C \Omega \ln M$

brak stabilnego i stabilne odzyskiwanie z i jest możliwaD $c$$D$$P$

$D$ odpowiada , odpowiada$X$$P$$y$

... zgodnie z oczekiwaniami w relacji , wybór deskryptora staje się bardziej niestabilny, tj. dla różnych zbiorów szkoleniowych wybrany deskryptor często się różni ...$N = C \Omega \ln M$

Drugi cytat to ta część, która mnie myli. Wydaje mi się, że gdy naruszona zostanie nierówność, nie tylko rozwiązanie może być nieunikalne (nie wspomniane), ale deskryptor stanie się również bardziej niestabilny.

AKTUALIZACJA

Zobacz ten drugi post , aby uzyskać informacje zwrotne od McDonalda na temat mojej odpowiedzi, w której pojęcie spójności ryzyka jest związane ze stabilnością.

1) Wyjątkowość a stabilność

Na twoje pytanie trudno odpowiedzieć, ponieważ wymienia dwa bardzo różne tematy: wyjątkowość i stabilność .

• Intuicyjnie rozwiązanie jest unikalne, jeśli przy ustalonym zestawie danych algorytm zawsze daje takie same wyniki. Odpowiedź Martina opisuje tę kwestię bardzo szczegółowo.

• Z drugiej strony stabilność można intuicyjnie rozumieć jako taką, dla której prognozowanie nie zmienia się znacznie, gdy dane treningowe zostaną nieznacznie zmodyfikowane.

Stabilność dotyczy twojego pytania, ponieważ wybór funkcji Lasso jest (często) wykonywany przez Cross Validation, dlatego algorytm Lasso jest wykonywany na różnych fałdach danych i może dawać różne wyniki za każdym razem.

Twierdzenie o stabilności i braku darmowego lunchu

Używając stąd definicji , jeśli zdefiniujemy Jednorodną stabilność jako:

Algorytm ma jednolitą stabilność w odniesieniu do funkcji straty jeśli:$\beta$$V$

$$\forall S \in Z^m \ \ \forall i \in \{ 1,...,m\}, \ \ \sup | > V(f_s,z) - V(f_{S^{|i},z}) |\ \ \leq \beta$$

Uważany za funkcję termin można zapisać jako . Mówimy, że algorytm jest stabilny, gdy zmniejsza się jako .β β m β m $m$$\beta$$\beta_m$$\beta_m$$\frac{1}{m}$

wtedy „Twierdzenie o braku darmowego lunchu, Xu i Caramis (2012)” stwierdza, że

Jeśli algorytm jest rzadki , w tym sensie, że identyfikuje nadmiarowe cechy, wówczas algorytm ten nie jest stabilny (a jednolita granica stabilności nie spada do zera). [...] Jeśli algorytm jest stabilny, nie ma nadziei, że będzie rzadki. (strony 3 i 4)$\beta$

Na przykład regresja jest stabilna i nie identyfikuje zbędnych funkcji, natomiast regulowana (Lasso) jest niestabilna. L $L_2$$L_1$

Próba odpowiedzi na twoje pytanie

Myślę, że „lasso preferuje rzadkie rozwiązanie” nie jest odpowiedzią na to, dlaczego używać lasso do wyboru funkcji

• Nie zgadzam się, ponieważ Lasso jest używane do wyboru funkcji, ponieważ daje rzadkie rozwiązanie i można wykazać, że ma właściwość IRF, tj. Identyfikuje funkcje nadmiarowe.

Jaki jest najważniejszy powód, który powoduje tę niestabilność

• Twierdzenie o braku darmowego lunchu

Idąc dalej

Nie oznacza to, że połączenie Cross Validation i Lasso nie działa ... w rzeczywistości wykazano eksperymentalnie (i przy dużej teorii wspierającej), że działa bardzo dobrze w różnych warunkach. Główne słowa kluczowe to spójność , ryzyko, nierówności wyroczni itp.

Następujące slajdy i artykuł McDonald i Homrighausen (2013) opisują niektóre warunki, w których dobór funkcji Lasso działa dobrze: slajdy i papier: „Lasso, trwałość i walidacja krzyżowa, McDonald i Homrighausen (2013)” . Sam Tibshirani również opublikował wielki zestaw notatek na temat rzadkości , regresji liniowej

Różne warunki spójności i ich wpływ na Lasso są aktywnym tematem badań i na pewno nie są trywialne. Mogę skierować Cię w stronę istotnych artykułów badawczych:

• Wykłady wideo na temat twierdzenia No free lunch, autorstwa Xu
• HM Bøvelstad i in., Porównanie metod selekcji cech do selekcji genów, (2007)
• Lasso, upór i walidacja krzyżowa, McDonald i Homrighausen (2013)
• Huang i Bowick, Podsumowanie i dyskusja na temat: „Wybór stabilności”
• Lim and Yu, Estimation Stability with Cross Validation, (2015)
• Rozmowa przez Petera Bulmanna: Wybór Stabilność High-wymiarowej danych, (2008) oraz towarzyszący mu papier
• Wang, Nan i inni, Random Lasso, (2011)
• Słupek wymiany stosu: stabilność modelu w przypadku dużego problemu , małego$p$$n$
• Roberts, Nowakm Stabilizacja lassa przed zmiennością walidacji krzyżowej, (2014) które twierdzą, że „percentyl-lasso może skutkować znacznym zmniejszeniem zarówno niestabilności wyboru modelu, jak i błędu wyboru modelu, w porównaniu z lasso”
• Niesamowity zestaw notatek Tibshirani i Wassermana na temat rzadkości , regresji liniowej

Komentarze Daniela J. McDonalda

Adiunkt na Uniwersytecie Indiana Bloomington, autor dwóch artykułów wymienionych w oryginalnej odpowiedzi Xaviera Bourreta Sicotte .

Twoje wyjaśnienie jest ogólnie dość poprawne. Chciałbym wskazać kilka rzeczy:

1. Naszym celem w serii artykułów na temat CV i lasso było udowodnienie, że „Lasso + Cross Validation (CV)” radzi sobie równie dobrze jak „Lasso + optimum ”$\lambda$ . W szczególności chcieliśmy pokazać, że prognozy również się sprawdzają (bez modelu). Aby wypowiedzieć się na temat poprawnego odzyskania współczynników (znalezienie właściwych nieskromnych), należy przyjąć rzadką prawdę, czego nie chcieliśmy zrobić.

2. Stabilność algorytmiczna implikuje spójność ryzyka (jak sądzę, po raz pierwszy udowodnione przez Bousquet i Elisseeff). Przez spójność ryzyka rozumiem, żeidzie do zera, gdzie f jest albo albo najlepszym predyktorem w danej klasie, jeśli klasa jest źle określona. Jest to jednak tylko wystarczający warunek. Jest to wspomniane na slajdach, które łączysz, jako „możliwa technika dowodu, która nie zadziała, ponieważ lasso nie jest stabilne”.E [ Y | X $||\hat{f}(X) - f(X)||$$E[Y|X]$

3. Stabilność jest wystarczająca, ale nie konieczna. Udało nam się wykazać, że pod pewnymi warunkami „lasso + CV” przewiduje, a także „lasso + optimum ”. Artykuł, który zacytowałeś, zawiera najsłabsze możliwe założenia (te na slajdzie 16, które pozwalają na ), ale używa ograniczonej formy lasso zamiast bardziej powszechnej wersji Lagrangian. Inny artykuł ( http://www3.stat.sinica.edu.tw/statistica/J27N3/J27N34/J27N34.html ) używa wersji Lagrangian. Pokazuje również, że w znacznie silniejszych warunkach wybór modelu będzie również działał. Nowszy artykuł ( https://arxiv.org/abs/1605.02214 ) innych osób twierdzi, że poprawia te wyniki (nie przeczytałem go uważnie).p > $\lambda$$p>n$

4. Zasadniczo, ponieważ lasso (lub dowolny algorytm selekcji) nie jest stabilny, trzeba dokładniejszej analizy i / lub silnych założeń, aby pokazać, że „algorytm + CV” wybierze właściwy model. Nie zdaję sobie sprawy z koniecznych warunków, choć ogólnie byłoby to niezwykle interesujące. Nietrudno jest wykazać, że dla ustalonej lambdy predyktorem lasso jest lokalnie Lipschitz w wektorze (uważam, że robi to jeden lub więcej artykułów Ryana Tibshirani). Gdyby można również argumentować, że dotyczy to , byłoby to bardzo interesujące i istotne w tym przypadku.X $Y$$X_i$

Główną kwestią, którą chciałbym dodać do twojej odpowiedzi: „stabilność” oznacza „spójność ryzyka” lub „dokładność prognozowania”. Może również oznaczać „spójność szacowania parametrów” przy większej liczbie założeń. Ale twierdzenie o braku darmowego lunchu oznacza „wybór” „niestabilna”. Lasso nie jest stabilny nawet z ustaloną lambda. Jest z pewnością niestabilny, dlatego w połączeniu z CV (dowolnego typu). Jednak pomimo braku stabilności jest nadal zgodny z ryzykiem i wybór zgodny z lub bez CV Wyjątkowość jest tutaj nieistotna.$\rightarrow$

Lasso, w przeciwieństwie do regresji Ridge'a (patrz np. Hoerl i Kennard, 1970; Hastie i in., 2009), nie zawsze ma unikalne rozwiązanie, chociaż zazwyczaj ma. Zależy to od liczby parametrów w modelu, tego, czy zmienne są ciągłe czy dyskretne, oraz od rangi macierzy projektowej. Warunki wyjątkowości można znaleźć w Tibshirani (2013).

Bibliografia:

Hastie, T., Tibshirani, R., i Friedman, J. (2009). Elementy uczenia statystycznego . Seria Springera w statystykach. Springer, Nowy Jork, 11. druk, 2. wydanie.

Hoerl, AE i Kennard, RW (1970). Regresja grzbietu: błędne oszacowanie problemów nieortogonalnych. Technometrics , 12 (1), 55-67.

Tibshirani, RJ (2013). Problem lasso i wyjątkowość. Electronic Journal of Statistics , 7, 1456-1490.

Co powoduje niejednoznaczność.

Dla wektorów (gdzie jest znakiem wskazującym, czy zmiana wzrośnie, czy zmniejszys i c i ‖ c ‖ $s_ix_i$$s_i$$c_i$$\Vert c \Vert_1$ ), ilekroć są one zależne od siebie:

istnieje nieskończona liczba kombinacji , które nie zmieniają rozwiązania i normy X c ‖ c ‖ $c_i + \gamma\alpha_i$$Xc$$\Vert c\Vert_1$ .

Na przykład:

ma dla$\Vert c \Vert_1 = 1$ rozwiązania:

z$0\leq \gamma \leq \frac{1}{2}$

Możemy w pewnym sensie zamienić wektor za pomocą$x_2$$x_2 = 0.5 x_1 + 0.5 x_3$

Sytuacje bez tego warunku

W artykule Tibshirani (z odpowiedzi Phila) opisano trzy wystarczające warunki, aby lasso miał unikalne rozwiązanie.

1. Liniowo niezależny Gdy przestrzeń zerowa jest pusta lub równoważnie, gdy ranga jest równa liczbie kolumn (M). W takim przypadku nie masz kombinacji liniowych jak wyżej.$X$$X$

2. Affinely niezależny Kiedy kolumny$Xs$ są w ogólnej pozycji.

   Oznacza to, że żadna kolumn nie reprezentuje punktów w płaszczyźnie wymiarowej . Płaszczyznę wymiarową k-2 można sparametryzować dowolnymi punktami jako z . Z punktem na tej samej płaszczyźnie miałbyś warunki z$k$$k-2$$k-1$$\sum \alpha_i s_ix_i$$\sum \alpha_i = 1$$k$$s_jx_j$$\sum \alpha_i s_ix_i$$\sum \alpha_i = 0$

   Zauważ, że w przykładzie kolumny , i znajdują się w jednym wierszu. (Jest to jednak nieco niewygodne, ponieważ znaki mogą być ujemne, np. Macierz właśnie jak również brak unikalnego rozwiązania)$x_1$$x_2$$x_3$$\left[ [2 \, 1] \, [1 \, 1] \, [-0 \, -1] \right]$

3. Gdy kolumny pochodzą z ciągłego rozkładu, jest mało prawdopodobne (prawdopodobieństwo prawie zero), że kolumny nie będą w ogólnej pozycji.$X$$X$

   W przeciwieństwie do tego, jeśli kolumny są zmienną kategorialną, prawdopodobieństwo to niekoniecznie jest prawie zerowe. Prawdopodobieństwo, że zmienna ciągła będzie równa pewnemu zestawowi liczb (tj. Płaszczyznom odpowiadającym rozpiętości afinicznej innych wektorów) wynosi „prawie” zero. Nie dotyczy to jednak zmiennych dyskretnych.$X$