Co powoduje, że lasso jest niestabilne przy wyborze funkcji?

12

argminc1subject to y=Xc
c

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ę XN×M=(x1,,xM) . c jest wektorem Ω rzadkim ( ΩM ). Proces y=Xc generuje odpowiedź y . Jeśli X ma NSP (właściwość pustego miejsca) rzędu Ω a macierz kowariancji X nie ma wartości własnej bliskiej zeru, będzie unikalne rozwiązanie dla

argminc1subject to y=Xc
czyli dokładnie c które daje y .

To twierdzenie mówi również, że jeśli nie ma NSP rzędu , po prostu beznadziejne jest rozwiązanie .Ω argmin c : y = X cc 1XΩargminc:y=Xcc1


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 DXN×Mn<pD

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 ΩΩcXΩ

W przypadku ogólnej macierzy , jeśli zostanie naruszone, toN > C Ω ln MN×MN>CΩlnM

brak stabilnego i stabilne odzyskiwanie z i jest możliwaD PcDP

XD odpowiada , odpowiadaXyPy

... 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ΩlnM

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.

meTchaikovsky
źródło
2
Dla kontekstu problem optymalizacji, który zapisujesz na początku swojego Q, nazywa się „pogoń za podstawą”. Jeśli zamienisz równość na przybliżoną równość (do pewnego błędu L2), wówczas nazywa się to „odwracaniem od podstaw”. Odmawianie podstawy ścigania jest matematycznie równoważne lasso. y X cy=XcyXc
ameba
Przydatny zestaw slajdów (ale niełatwy) można znaleźć tutaj: pages.iu.edu/~dajmcdon/research/talks/lasso.pdf i twierdzenie o darmowym lunchu users.ece.utexas.edu/~cmcaram/pubs/ XuCaramanisMannor.NFL.pdf
Xavier Bourret Sicotte
Twierdzenie, które przytaczasz, dotyczy wyjątkowości. Twoje pytanie jest mylące, ponieważ wyjątkowość niekoniecznie wiąże się ze stabilnością.
ameba
2
Tak, uważam, że OP jest nieco zdezorientowany, a pytanie nie jest jasne, stąd różne możliwe odpowiedzi ... Wyjątkowość dotyczy jednego zestawu punktów danych, stabilność dotyczy weryfikacji krzyżowej, bootstrapu lub nowych punktów danych
Xavier Bourret Sicotte

Odpowiedzi:

8

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:V.βV

SZm  i{1,...,m},  sup|>V(fs,z)V(fS|i,z)|  β

Uważany za funkcję termin można zapisać jako . Mówimy, że algorytm jest stabilny, gdy zmniejsza się jako .β β m β m 1mββmβm1m

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

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

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:

Xavier Bourret Sicotte
źródło
1
Dziękujemy za wyczerpującą odpowiedź! Zestaw dostarczonych slajdów jest po prostu doskonały!
meTchaikovsky
1
Nadal próbuję przetworzyć tę definicję stabilności. Moje tłumaczenie jest takie, że „algorytm jest stabilny, jeśli zmiana funkcji błędu / straty w pominięciu jednej weryfikacji krzyżowej ma górną granicę która zmniejsza się jako ", gdy zwiększamy liczbę folds / test-sets "1β1m , mam nadzieję, że dobrze to zrozumiałem. Zastanawiam się, dlaczego jest to pożądana właściwość, aby lasso działało dobrze (a ściślej zastanawiam się, czy jest to niezbędna właściwość).
Sextus Empiricus
1
Tak, z wyjątkiem m to liczba punktów danych. spójrz tutaj na stronę 7, aby znaleźć probabilistyczną granicę: math.arizona.edu/~hzhang/math574m/Read/LOOtheory.pdf - chodzi o to, że nie ma ograniczenia tability poprzez zwiększenie rozmiaru zestawu danych, co oznacza, że ​​algorytm może przeskakiwać do odległych funkcji hipotezy w zależności od określonego zestawu danych. Właśnie dlatego zaproponowano alternatywne warunki, które odnoszą się do podstawowej struktury dystrybucji i korelacji (tak myślę) - ale potrzebowałyby pomocy w ich wyjaśnieniu
Xavier Bourret Sicotte
Innym ważnym pojęciem jest spójność, jak wyjaśniono tutaj, na przykład: stat.ethz.ch/~nicolai/stability.pdf - powiązanie stabilności i spójności jest niejasne, ale wydaje się być przedmiotem aktywnych badań, np. Cbcl.mit.edu/publications /ps/mukherjee-AImemoOctNov.pdf
Xavier Bourret Sicotte
Niezła odpowiedź! Czy możesz również zaktualizować niektóre linki o bardziej szczegółowe opisy na wypadek, gdyby same linki zniknęły w przyszłości? (Zrobiłem już dla ciebie.)
Richard Hardy
7

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 ”λ . 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 ]||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 > nλ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 iYXi

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.

Xavier Bourret Sicotte
źródło
5

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.

Phil
źródło
@ Dziękuję Ci! Czy możesz dodać krótkie streszczenie tych referencji?
meTchaikovsky,
Hasite i in. (2009) to książka obejmująca wiele tematów, w tym regresję Lasso i Ridge'a. Warto ją przeczytać i można ją pobrać ze strony głównej Hastie : web.stanford.edu/~hastie/ElemStatLearn/download.html Hoerl & Kennard (1970) to klasyczne odniesienie do regresji Ridge i prawdopodobnie nie jest tak istotne dla twojego pytania, inne niż przeczytać o regresji Ridge'a. Tibshirani (2013) zawiera informacje o tym, kiedy Lasso ma unikalne rozwiązanie (i kiedy ma nieskończoną liczbę rozwiązań).
Phil
3

Co powoduje niejednoznaczność.

Dla wektorów (gdzie jest znakiem wskazującym, czy zmiana wzrośnie, czy zmniejszys i c ic 1sixisicic1 ), ilekroć są one zależne od siebie:

αisixi=0andαi=0

istnieje nieskończona liczba kombinacji , które nie zmieniają rozwiązania i normy X c c 1ci+γαiXcc1 .

Na przykład:

y=[11]=[210111][c1c2c3]=Xc

ma dlac1=1 rozwiązania:

[c1c2c3]=[010]+γ[121]

z0γ12

Możemy w pewnym sensie zamienić wektor za pomocąx2x2=0.5x1+0.5x3


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.XX
  2. Affinely niezależny Kiedy kolumnyXs 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 zkk2k1αisixiαi=1ksjxjαisixiα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)x1x2x3[[21][11][01]]

  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.XXX

    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

Sextus Empiricus
źródło
+1, ale myślę, że to, co rozumie się przez niestabilność w ostatnich dyskusjach, wiąże się z wyborem cech poprzez krzyżową weryfikację w obecności skorelowanych cech
Xavier Bourret Sicotte
@XavierBourretSicotte czy masz na myśli, że nawet jeśli istnieje unikalne rozwiązanie, proces selekcji może być niestabilny ze względu na skorelowane funkcje, które utrudniają (numerycznie) znalezienie tego unikalnego rozwiązania? Jest to nieco mylące, ponieważ pytanie z jednej strony dotyczy stabilności, az drugiej strony wyjątkowości.
Sextus Empiricus,
Tak, o to mi chodzi, niekoniecznie z powodu niestabilności liczbowej, ale z powodu nieodłącznych różnic w fałdach danych (podczas CV), które prowadzą do różnych rozwiązań dla różnych wartości we wszystkich fałdach. Może być jeszcze gorzej podczas ładowaniaλ
Xavier Bourret Sicotte
@XavierBourretSicotte Obecnie nie mam jasnego intuicyjnego obrazu, dlaczego to (różne rozwiązania dla różnych i zestawów treningowych) ma być niestabilne. Myślę, że możesz to opublikować jako odpowiedź i wyjaśnić. λ
Sextus Empiricus,
@Martijn Weterings Dziękujemy! Nadal mam trzy pytania: 1. w jaki sposób wykrywam zależność afiniczną? Czy powinienem dowiedzieć się, czy są niezależne ( math.stackexchange.com/q/82189 )? 2. Jak powinienem określić w praktyce? 3. co to znaczy „ogólna pozycja” ? s i X{v1v0,v2v0,,vkv0}siX
meTchaikovsky