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,

111

Rozważ wektor gdzie jest małe. W and normy , odpowiednio, są podane $\vec{x}=(1,\varepsilon)\in\mathbb{R}^2$ $\varepsilon>0$ $l_1$ $l_2$ $\vec{x}$

| | \vec{x} | |_{1} = 1 + ε, | | \vec{x} | |_{2}^{2} = 1 + ε^{2}

$||\vec{x}||_1 = 1+\varepsilon,\ \ ||\vec{x}||_2^2 = 1+\varepsilon^2$

Powiedzmy teraz, że w ramach procedury regularyzacji zmniejszymy wielkość jednego z elementów o . Jeśli zmienimy na , wynikowe normy to $\vec{x}$ $\delta\leq\varepsilon$ $x_1$ $1-\delta$

| | \vec{x} - (δ, 0) | |_{1} = 1 - δ + ε, | | \vec{x} - (δ, 0) | |_{2}^{2} = 1 - 2 δ + δ^{2} + ε^{2}

$||\vec{x}-(\delta,0)||_1 = 1-\delta+\varepsilon,\ \ ||\vec{x}-(\delta,0)||_2^2 = 1-2\delta+\delta^2+\varepsilon^2$

Z drugiej strony zmniejszenie o daje normy $x_2$ $\delta$

| | \vec{x} - (0, δ) | |_{1} = 1 - δ + ε, | | \vec{x} - (0, δ) | |_{2}^{2} = 1 - 2 ε δ + δ^{2} + ε^{2}

$||\vec{x}-(0,\delta)||_1 = 1-\delta+\varepsilon,\ \ ||\vec{x}-(0,\delta)||_2^2 = 1-2\varepsilon\delta+\delta^2+\varepsilon^2$

Należy tutaj zauważyć, że dla kary , uregulowanie większego składnika powoduje znacznie większe zmniejszenie normy niż w przypadku mniejszego składnika . Jednak w przypadku kary redukcja jest taka sama. Tak więc, podczas karania modelu za pomocą normy , jest bardzo mało prawdopodobne, aby cokolwiek kiedykolwiek wyzerowało się, ponieważ zmniejszenie normy od do jest prawie nieistniejące, gdy jest małe. Z drugiej strony, zmniejszenie $l_2$ $x_1$ $x_2\approx 0$ $l_1$ $l_2$ $l_2$ $\varepsilon$ $0$ $\varepsilon$ $l_1$ norma jest zawsze równa , bez względu na karaną ilość. $\delta$

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

— 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

dla dowolnego

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

(proporcjonalna do liczby niezerowych wpisów) jest dobrym rozwiązaniem, tak się składa, że praca z nim jest trochę koszmarem.

l_{1}

$l_1$

l_{α}

$l_\alpha$

α \leq 1

$\alpha\leq1$

l_{0}

$l_0$

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

$(w_1, w_2, \dots, w_m)$

$L_1(w)$ $\Sigma_i |w_i|$

$L_2(w)$ $\frac{1}{2} \Sigma_i w_i^2$

$\eta$

$\frac{dL_1(w)}{dw} = sign(w)$ $sign(w) = (\frac{w_1}{|w_1|}, \frac{w_2}{|w_2|}, \dots, \frac{w_m}{|w_m|})$

$\frac{dL_2(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:

$L_1$ $w_1 = 0$ $L_2$

$w_1 = 5$ $\eta = \frac{1}{2}$ $w_1 := w_1 - \eta \cdot \frac{dL_1(w)}{dw} = w_1 - \frac{1}{2} \cdot 1$ $w_1 = 0$

wprowadź opis zdjęcia tutaj

$\eta = \frac{1}{2}$ $w_1$ $w_1 := w_1 - \eta \cdot \frac{dL_2(w)}{dw} = w_1 - \frac{1}{2} \cdot w_1$

wprowadź opis zdjęcia tutaj

$\eta$

— Kent Munthe Caspersen
źródło

3

η = 0.5

$\eta = 0.5$

w_{f i r s t s t e p} = 0.1 - 0.5 * (+ 1) => w = - 0.4

$w_{first\text{ }step} = 0.1 - 0.5*(+1) => w = -0.4$

w_{s e c o n d s t e p} = - 0.4 - 0.5 * (- 1) = 0.1.

$w_{second step} = -0.4 - 0.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:

$\hat{\beta}$ $\beta_1$ $\beta_2$ $\hat{\beta}$ $L_1$ $L_2$ ) 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.

$L_1$

— 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

\hat{β}

$\hat{\beta}$

β_{1}

$\beta_1$

β_{2}

$\beta_2$

β_{1} = β_{2}

$\beta_1 = \beta_2$

13

$\hat \beta$ $\hat \beta$ $\ell_1 (\hat \beta) < t$ $\ell_2 (\hat \beta) < t$

$\ell_1$ $\ell_1$ $\{ x : \ell_1(x) \le 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

\hat{β}

$\hat \beta$

ℓ_{1}

$\ell_1$

ℓ_{2}

$\ell_2$

ℓ_{1}

$\ell_1$

ℓ_{2}

$\ell_2$

\hat{β}

$\hat \beta$

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

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}

$\ell_2$

β_{1} = 1

$\beta_1 = 1$

β_{1} = 0

$\beta_1 = 0$

L_{1}

$L_1$