Dlaczego norma L1 dla rzadkich modeli

97

Czytam książki o regresji liniowej. Istnieje kilka zdań na temat norm L1 i L2. Znam je, po prostu nie rozumiem, dlaczego norma L1 dla rzadkich modeli. Czy ktoś może użyć prostego wyjaśnienia?

Yongwei Xing
źródło
4
Zasadniczo rzadkość jest wywoływana przez ostre krawędzie leżące na osi powierzchni izosferycznej. Najlepsze wyjaśnienie graficzne, jakie do tej pory znalazłem, znajduje się w tym filmie: youtube.com/watch?v=sO4ZirJh9ds
felipeduque
1
Jest artykuł na blogu o tym samym chioka.in/…
prashanth
Sprawdź następujący post Medium. Może to pomóc medium.com/@vamsi149/…
solver149,

Odpowiedzi:

111

Rozważ wektor gdzie ε > 0 jest małe. W L 1 and L 2 normy x , odpowiednio, są podanex=(1,ε)R2ε>0l1l2x

||x||1=1+ε,  ||x||22=1+ε2

Powiedzmy teraz, że w ramach procedury regularyzacji zmniejszymy wielkość jednego z elementów o δ ε . Jeśli zmienimy x 1 na 1 - δ , wynikowe normy toxδεx11δ

||x(δ,0)||1=1δ+ε,  ||x(δ,0)||22=12δ+δ2+ε2

Z drugiej strony zmniejszenie o δ daje normyx2δ

||x(0,δ)||1=1δ+ε,  ||x(0,δ)||22=12εδ+δ2+ε2

Należy tutaj zauważyć, że dla kary , uregulowanie większego składnika x 1 powoduje znacznie większe zmniejszenie normy niż w przypadku mniejszego składnika x 20 . Jednak w przypadku kary 1 l redukcja jest taka sama. Tak więc, podczas karania modelu za pomocą normy l 2 , jest bardzo mało prawdopodobne, aby cokolwiek kiedykolwiek wyzerowało się, ponieważ zmniejszenie normy l 2 od ε do 0 jest prawie nieistniejące, gdy ε jest małe. Z drugiej strony, zmniejszenie l 1l2x1x20l1l2l2ε0εl1norma jest zawsze równa , bez względu na karaną ilość.δ

Innym sposobem, aby myśleć o tym: to nie jest tak dużo, że Kary zachęcić sparsity, lecz l 2 kary w pewnym sensie zniechęcić sparsity ulegając malejących przychodów jako elementy zbliżyły się do zera.l1l2

bnaul
źródło
3
Dzięki za odpowiedź! Jednak ostatni punkt mnie nie przekonuje. Jeśli uruchomisz regresję liniową bez kary, prawie nigdy nie uzyskasz rzadkich rozwiązań (podczas gdy dodanie kary za L1 często da ci rzadkość). Tak więc kary L1 w rzeczywistości zachęcają do rzadkości, wysyłając współczynniki, które zaczynają się dokładnie od zera do zera dokładnie.
Stefan Wager
2
@StefanWager może to trochę przesadzenie, ale myślę, że to prawda, że ​​nie ma tu nic specjalnego z karą kara l α dla dowolnego α 1 spowoduje również rzadkość, ale w praktyce zdarza się to rzadziej ( prawdopodobnie dlatego, że nie są wypukłe). Jeśli naprawdę chcesz tylko sparowania, to droga l 0 (proporcjonalna do liczby niezerowych wpisów) jest dobrym rozwiązaniem, tak się składa, że ​​praca z nim jest trochę koszmarem. l1lαα1l0
bnaul
1
Tak, to jest poprawne. Istnieje wiele norm, które prowadzą do rzadkości (np. Jak wspomniałeś, każda norma Lp z p <= 1). Ogólnie rzecz biorąc, każda norma z ostrym kątem zerowym powoduje rzadkość. Wracając do pierwotnego pytania - norma L1 indukuje rzadkość poprzez nieciągłe nachylenie w punkcie zerowym (i zrobi to również każda inna kara z tą właściwością).
Stefan Wager
3
Jeśli ktoś chce przeczytać więcej, istnieje aktywna literatura na temat niewypukłych funkcji karnych, które są alternatywą dla normy L1 (np. Ostatnio papers.nips.cc/paper/… ).
Stefan Wager
1
świetna odpowiedź, zastanawiałem się przez jakiś czas, dopóki nie znalazłem tego.
Hady Elsahar
72

W modelu rzadkim myślimy o modelu, w którym wiele wag wynosi 0. Rozważmy zatem, w jaki sposób regularyzacja L1 ma większe szanse na utworzenie wag 0.

(w1,w2,,wm)

L1(w)Σi|wi|

L2(w)12Σiwi2

η

dL1(w)dw=sign(w)sign(w)=(w1|w1|,w2|w2|,,wm|wm|)

dL2(w)dw=w

Jeśli wykreślimy funkcję straty i jej pochodną dla modelu składającego się tylko z jednego parametru, wygląda to tak dla L1:

wprowadź opis zdjęcia tutaj

I tak w przypadku L2:

wprowadź opis zdjęcia tutaj

L1w1=0L2

w1=5η=12w1:=w1ηdL1(w)dw=w1121w1=0

wprowadź opis zdjęcia tutaj

η=12w1w1:=w1ηdL2(w)dw=w112w1

wprowadź opis zdjęcia tutaj

η

Kent Munthe Caspersen
źródło
3
η=0.5
wfirst step=0.10.5(+1)=>w=0.4
wsecondstep=0.40.5(1)=0.1.
5
@AlexYashin jest poprawny - jeśli zaktualizujemy wagi tylko na podstawie regularyzacji L1, możemy skończyć z wagami oscylującymi w pobliżu 0. Ale nigdy nie używamy samej regularyzacji do regulacji wag. Używamy regularyzacji w połączeniu z optymalizacją funkcji strat. W ten sposób regularyzacja popycha wagi do zera, a my jednocześnie próbujemy popchnąć wagi do wartości, która zoptymalizuje prognozy. Drugim aspektem jest współczynnik uczenia się. Przy mniejszym współczynniku uczenia się możemy zbliżyć się do wartości, która może wahać się wokół regularyzacji, i możemy ją zaniedbać
Kent Munthe Caspersen,
1
Dlaczego dL2(w)/dw„moduł” jest nie tylko liniowy?
mrgloom
1
@mrgloom dL2(w)/dwmożna odczytać jako zmianę L2(w)na zmianę wagi. Ponieważ regularyzacja L2 podnosi do kwadratu odważniki, L2(w)zmieni się znacznie bardziej dla tej samej zmiany odważników, gdy mamy wyższe odważniki. Właśnie dlatego funkcja jest wypukła podczas kreślenia. Jednak w przypadku L1 zmiana L1(w)na zmianę ciężaru jest taka sama, niezależnie od tego, jakie są twoje ciężary - prowadzi to do funkcji liniowej.
Kent Munthe Caspersen
1
@KentMuntheCaspersen Niesamowite wyjaśnienie! Dziękujemy za wykresy i wysiłek włożony w uczynienie tego intuicyjnym!
Layser
15

Rysunek 3.11 z elementów statystycznego uczenia się autorstwa Hastie, Tibshirani i Friedmana jest bardzo ilustrujący:wprowadź opis zdjęcia tutaj

β^β1β2β^L1L2) odpowiednio regresja. Heurystycznie dla każdej metody szukamy przecięcia czerwonych elips i niebieskiego obszaru, ponieważ celem jest zminimalizowanie funkcji błędu przy jednoczesnym zachowaniu wykonalności.

L1

Zhanxiong
źródło
16
Ilustracja nie jest zbyt przekonująca bez dodatkowych informacji. Np. Dlaczego kontury błędu powinny znajdować się tam, gdzie są na rysunku?
wabbit
@HrishikeshGanu W końcu miałem trochę czasu na edycję postu.
Zhanxiong,
Wszystkie kontury będą miały tę samą formę ...
kjetil b halvorsen
1
β^β1β2β1=β2
13

β^β^1(β^)<t2(β^)<t

11{x:1(x)1}

Mówiąc bardziej ogólnie, ta książka stanowi dobre odniesienie do tego tematu: zarówno rygorystyczne, jak i dobrze zilustrowane, świetne wyjaśnienia.

Elvis
źródło
3
Myślę, że twój drugi akapit jest kluczem ... przynajmniej dla mojej intuicji: „kula l1” bardziej przypomina diament, który jest kolczasty wzdłuż osi, co oznacza, że ​​hiperpłaszczyzna ograniczona do uderzenia ma większe szanse na zero osie.
Wayne,
2
β^1212β^
3
Książka jest dobra, ale nigdy nie wyjaśnia, skąd się wzięła i jaka jest matematyka.
user13985,
2

Prosta niematematyczna odpowiedź brzmiałaby:

W przypadku L2: kara jest podniesiona do kwadratu , więc podniesienie do kwadratu małej wartości spowoduje jej zmniejszenie. Nie musimy ustawiać go na zero, aby osiągnąć nasz cel polegający na uzyskaniu minimalnego błędu kwadratowego, otrzymamy go wcześniej.

W przypadku L1: kara jest bezwzględna , może być konieczne zejście do zera, ponieważ nie ma katalizatora, aby zmniejszyć małe .

To mój punkt widzenia.

Arnab Mukherjee
źródło
Niezbyt przekonujące dla mnie.
Tyler 十三 将士 归 玉门
2

Norma L1 vs Norma L2

Zdjęcie pokazuje kształty obszaru zajmowanego przez L1 i L2 Norm. Drugi obraz składa się z różnych konturów spadku gradientu dla różnych problemów z regresją. Na wszystkich wykresach konturowych obserwuj czerwony okrąg, który przecina grzbiet lub normę L2. przecięcie nie jest na osiach. Czarny okrąg we wszystkich konturach reprezentuje ten, który przecina Normę L1 lub Lasso. Przecina się stosunkowo blisko osi. Powoduje to uzyskanie współczynników do 0, a zatem wybór funkcji. Stąd norma L1 sprawia, że ​​model jest rzadki.

Bardziej szczegółowe wyjaśnienie pod następującym linkiem: Kliknij opcję Post w kierunku Data Science

solver149
źródło
2β1=1β1=0L1