Uregulowane najmniejsze kwadraty — Regularized least squares

Część serii na
Analiza regresji
Modele
Regresja liniowa Prosta regresja Regresja wielomianowa Ogólny model liniowy
Uogólniony model liniowy Dyskretny wybór Regresja dwumianowa Regresja binarna Regresja logistyczna Wielomianowa regresja logistyczna Logit mieszany Probit Probit wielomianowy Zamówiony logit Zamówiony probit Poissona
Model wielopoziomowy Naprawiono efekty Efekty losowe Liniowy model efektów mieszanych Nieliniowy model efektów mieszanych
Regresja nieliniowa Nieparametryczny Półparametryczny Krzepki Kwantyl Izotoniczny Główne składniki Najmniejszy kąt Lokalny Segmentowane
Błędy w zmiennych
Oszacowanie
Najmniej kwadratów Liniowy Nieliniowy
Zwyczajny Ważony Uogólnione
Częściowy Całkowity Nieujemny Regresja grzbietowa Uregulowany
Najmniejsze bezwzględne odchylenia Iteracyjnie ponownie ważony Bayesian Wielowymiarowa bayesowska
Tło
Walidacja regresji Średnia i przewidywana odpowiedź Błędy i pozostałości Dobroć dopasowania Studentyzowane rezydualne Twierdzenie Gaussa-Markowa
Portal matematyczny
v T mi

Regularyzowane metody najmniejszych kwadratów ( RLS ) to rodzina metod rozwiązywania problemu najmniejszych kwadratów przy użyciu regularyzacji do dalszego ograniczania otrzymanego rozwiązania.

RLS jest używany z dwóch głównych powodów. Pierwszy pojawia się, gdy liczba zmiennych w układzie liniowym przekracza liczbę obserwacji. W takich warunkach zwykły problem najmniejszych kwadratów jest źle postawiony i dlatego jest niemożliwy do dopasowania, ponieważ związany z nim problem optymalizacji ma nieskończenie wiele rozwiązań. RLS umożliwia wprowadzenie dalszych ograniczeń, które jednoznacznie determinują rozwiązanie.

Drugi powód, dla którego stosuje się RLS, występuje, gdy liczba zmiennych nie przekracza liczby obserwacji, ale wyuczony model cierpi na słabą generalizację . W takich przypadkach RLS może być używany do poprawy uogólniania modelu poprzez ograniczenie go w czasie uczenia. Ograniczenie to może w jakiś sposób zmusić rozwiązanie do „rzadkiego” lub odzwierciedlać inną wcześniejszą wiedzę na temat problemu, taką jak informacje o korelacjach między cechami. Bayesa zrozumienia to może być osiągnięte, pokazując, że metody RLS są często równoważne priors na rozwiązanie problemu najmniejszych kwadratów.

Ogólna formuła

Rozważmy ustawienie nauki podane przez przestrzeń probabilistyczną , . Pozwolić oznaczają zestaw szkoleniowy par IID względem . Niech będzie funkcją straty. Zdefiniuj jako przestrzeń funkcji taką, że oczekiwane ryzyko: ${\displaystyle (X\razy Y\rho (X,Y))}$${\ Displaystyle Y \ w R}$${\ Displaystyle S = \ {x_ {i}, y_ {i} \} _ {i = 1} ^ {n}}$${\ Displaystyle n}$${\ Displaystyle \ rho}$${\displaystyle V:Y\razy R\rightarrow [0;\infty)}$${\ Displaystyle F}$

${\ Displaystyle \ varepsilon (f) = \ int V (y, f (x)) \ d \ rho (x, y)}$

jest dobrze zdefiniowany. Głównym celem jest minimalizacja oczekiwanego ryzyka:

${\ Displaystyle \ inf _ {f \ w F} \ varepsilon (f)}$

Ponieważ problemu nie da się dokładnie rozwiązać, istnieje potrzeba określenia, w jaki sposób mierzyć jakość rozwiązania. Dobry algorytm uczenia powinien zapewnić estymatorowi niewielkie ryzyko.

Ponieważ wspólny rozkład jest zwykle nieznany, podejmowane jest ryzyko empiryczne. Dla regularyzowanych najmniejszych kwadratów wprowadzono kwadratową funkcję straty: ${\ Displaystyle \ rho}$

${\ Displaystyle \ varepsilon (f) = {\ Frac {1} {n}} \ suma _ {i = 1} ^ {n} V (y_ {i}, f (x_ {i})) = {\ Frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}}$

Jednakże, jeśli funkcje pochodzą ze stosunkowo nieograniczonej przestrzeni, takiej jak zbiór funkcji całkowalnych do kwadratu na , to podejście może nadmiernie dopasować dane uczące i prowadzić do słabego uogólnienia. Powinno to więc w jakiś sposób ograniczać lub karać złożoność funkcji . W RLS osiąga się to poprzez wybranie funkcji z odtwarzającej jądra przestrzeni Hilberta (RKHS) i dodanie do funkcji celu terminu regularyzacji, proporcjonalnego do normy funkcji w : ${\ Displaystyle X}$${\displaystyle f}$${\ Displaystyle {\ Mathcal {H}}}$${\ Displaystyle {\ Mathcal {H}}}$

${\ Displaystyle \ inf _ {f \ w F} \ varepsilon (f) + \ lambda R (f), \ lambda > 0}$

Formuła jądra

Definicja RKHS

RKHS może być zdefiniowany przez symetryczną dodatnio określoną funkcję jądra z właściwością odtwarzania: ${\ Displaystyle K (x, z)}$

${\ Displaystyle \ langle K_ {x}, f \ rangle _ {\ mathcal {H}} = f (x),}$

gdzie . RKHS dla jądra składa się z uzupełnienia przestrzeni funkcji rozpiętych przez : , gdzie wszystkie są liczbami rzeczywistymi. Niektóre powszechnie używane jądra obejmują jądro liniowe, indukujące przestrzeń funkcji liniowych: ${\ Displaystyle K_ {x} (z) = K (x, z)}$${\ Displaystyle K}$${\ Displaystyle \ lewo \ {K_ {x} \ mid x \ w X \ po prawej \}}$${\ Displaystyle f (x) = \ suma _ {i = 1} ^ {n} \ alfa _ {i} K_ {x_ {i}} (x), \, f \ w {\ mathcal {H}}}$${\ Displaystyle \ alfa _ {i}}$

${\ Displaystyle K (x, z) = x ^ {T} z}$

jądro wielomianowe, indukujące przestrzeń wielomianowych funkcji porządku : ${\displaystyle d}$

${\ Displaystyle K (x, z) = (x ^ {T} z + 1) ^ {d}}$

i jądro Gaussa:

${\ Displaystyle K (x, z) = e ^ {- {\ Frac {\ | xz \ | ^ {2}} {\ sigma ^ {2}}}}.}$

Zauważ, że dla dowolnej funkcji straty , to podejście definiuje ogólną klasę algorytmów o nazwie regularyzacja Tichonowa. Na przykład użycie utraty zawiasów prowadzi do algorytmu maszyny wektora nośnego , a użycie utraty niewrażliwej na epsilon prowadzi do regresji wektora nośnego . ${\ Displaystyle V}$

Jądro arbitralne

W representer twierdzenie gwarantuje, że rozwiązanie można zapisać jako:

${\ Displaystyle f (x) = \ suma _ {i = 1} ^ {n} c_ {i} K (x_ {i} x)}$dla niektórych .${\ Displaystyle c \ w \ mathbb {R} ^ {n}}$

Problem minimalizacji można wyrazić jako:

${\ Displaystyle \ min _ {c \ w \ mathbb {R} ^ {n}} \ Frac {1} {n}} \ | Y-Kc \ | _ {\ mathbb {R} ^ {n}} ^ {2}+\lambda \|f\|_{H}^{2},}$

gdzie, z pewnym nadużyciem notacji, wpis macierzy jądra (w przeciwieństwie do funkcji jądra ) to . ${\displaystyle ja,j}$${\ Displaystyle K}$${\displaystyle K(\cdot,\cdot)}$${\ Displaystyle K (x_ {i}, x_ {j})}$

Dla takiej funkcji,

${\ Displaystyle {\ zacząć {wyrównany} i \ | f \ | _ {H} ^ {2} = \ langle f, f \ rangle _ {H} = \ lewo \ langle \ suma _ {i = 1} ^ { n}c_{i}K(x_{i},\cdot ),\sum _{j=1}^{n}c_{j}K(x_{j},\cdot )\right\rangle _{H }\\={}&\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}\langle K(x_{i},\cdot ),K(x_{j},\cdot )\rangle _{H}=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j }K(x_{i},x_{j})=c^{T}Kc,\end{wyrównany}}}$

Można uzyskać następujący problem minimalizacji:

${\ Displaystyle \ min _ {c \ w \ mathbb {R} ^ {n}} \ Frac {1} {n}} \ | Y-Kc \ | _ {\ mathbb {R} ^ {n}} ^ {2}+\lambda c^{T}Kc}$.

Ponieważ suma funkcji wypukłych jest wypukła, rozwiązanie jest unikalne, a jego minimum można znaleźć ustawiając gradient wrt na : ${\displaystyle c}$${\ Displaystyle 0}$

${\ Displaystyle - {\ Frac {1} {n}} K (Y-Kc) + \ lambda Kc = 0 \ Rightarrow K (K + \ Lambda nI) c = KY \ Rightarrow c = (K + \ Lambda nI) ^ { -1}T,}$

gdzie ${\ Displaystyle c \ w \ mathbb {R} ^ {n}.}$

Złożoność

Złożoność uczenia to w zasadzie koszt obliczenia macierzy jądra plus koszt rozwiązania systemu liniowego, który jest w przybliżeniu . Obliczenie macierzy jądra dla jądra liniowego lub Gaussa to . Złożoność testowania to . ${\ Displaystyle O (n ^ {3})}$${\ Displaystyle O (n ^ {2} D)}$${\ Displaystyle O (n)}$

Prognoza

Przewidywanie w nowym punkcie testowym to: ${\displaystyle x_{*}}$

${\ Displaystyle f (x_ {*}) = \ suma _ {i = 1} ^ {n} c_ {i} K (x_ {i}, x_ {*}) = K (X, X_ {*}) ^ {T}c}$

Jądro liniowe

Dla wygody wprowadzono notację wektorową. Pozwolić Be matrycę, w której rzędy są wejściowe wektory i do wektora, w którym pozycje są odpowiednimi wyjściami. Jeśli chodzi o wektory, macierz jądra można zapisać jako . Funkcja uczenia się może być zapisana jako: ${\ Displaystyle X}$${\displaystyle n\razy d}$${\ Displaystyle Y}$${\displaystyle n\razy 1}$${\ Displaystyle \ nazwa operatora {K} = \ nazwa operatora {X} \ nazwa operatora {X} ^ {T}}$

${\ Displaystyle f (x_ {*}) = \ operatorname {K} _ {x_ {*}} c = x_ {*} ^ {T} \ operatorname {X} ^ {T} c = x_ {*} ^ { T}w}$

Tutaj definiujemy . Funkcję celu można przepisać jako: ${\ Displaystyle w = X ^ {T} c, w \ w R ^ {d}}$

${\ Displaystyle {\ zacząć {wyrównany} i {\ Frac {1} {n}} \ | Y- \ Operatorname {K} c \ | _ {\ mathbb {R} ^ {n}} ^ {2} + \ lambda c^{T}\nazwa operatora {K} c\\[4pt]={}&{\frac {1}{n}}\|y-\nazwa operatora {X} \nazwa operatora {X} ^{T}c \|_{\mathbb {R} ^{n}}^{2}+\lambda c^{T}\nazwa operatora {X} \nazwa operatora {X} ^{T}c={\frac {1}{n }}\|y-\nazwa operatora {X} w\|_{\mathbb {R} ^{n}}^{2}+\lambda \|w\|_{\mathbb {R} ^{d}} ^{2}\end{wyrównany}}}$

Pierwszym wyrazem jest funkcja celu ze zwykłej regresji najmniejszych kwadratów (OLS), odpowiadająca resztowej sumie kwadratów . Drugi termin to termin regularyzacyjny, nieobecny w OLS, który karze duże wartości. Rozważany jest gładki problem skończenie wymiarowy i możliwe jest zastosowanie standardowych narzędzi rachunku różniczkowego. W celu zminimalizowania funkcji celu obliczany jest gradient względem i ustawiany na zero: ${\ Displaystyle w}$${\ Displaystyle w}$

${\ Displaystyle \ operatorname {X} ^ {T} \ operatorname {X} w- \ operatorname {X} ^ {T} y + \ lambda nw = 0}$

${\ Displaystyle w = (\ nazwa operatora {X} ^ {T} \ nazwa operatora {X} + \ lambda n \ nazwa operatora {I} ) ^ {-1} \ nazwa operatora {X} ^ {T} y}$

To rozwiązanie bardzo przypomina standardową regresję liniową, z dodatkowym wyrazem . Jeśli założenia regresji MNK są spełnione, rozwiązanie , z , jest nieobciążonym estymatorem i jest liniowym nieobciążonym estymatorem o minimalnej wariancji, zgodnie z twierdzeniem Gaussa-Markowa . Termin ten prowadzi zatem do tendencyjnego rozwiązania; jednak ma również tendencję do zmniejszania wariancji. Łatwo to zauważyć, ponieważ macierz kowariancji wartości - jest proporcjonalna do , a zatem duże wartości będą prowadzić do mniejszej wariancji. Dlatego manipulowanie odpowiada stronniczości i wariancji wyprzedaży. W przypadku problemów z oszacowaniami o wysokiej wariancji , takich jak przypadki ze stosunkowo małymi lub skorelowanymi regresorami, optymalną dokładność predykcji można uzyskać, stosując wartość niezerową , a tym samym wprowadzając pewne obciążenie w celu zmniejszenia wariancji. Co więcej, w uczeniu maszynowym nierzadko zdarzają się przypadki , w których , w którym to przypadku jest niedostateczna ranga , a do obliczenia konieczne jest niezerowe . ${\ Displaystyle \ lambda \ operatorname {I}}$${\ Displaystyle w = (\ nazwa operatora {X} ^ {T} \ nazwa operatora {X} ) ^ {-1} \ nazwa operatora {X} ^ {T} y}$${\ Displaystyle \ lambda = 0}$${\displaystyle \lambda n\operator {I}}$${\ Displaystyle w}$${\ Displaystyle (\ nazwa operatora {X} ^ {T} \ nazwa operatora {X} + \ lambda n \ nazwa operatora {I}) ^ {-1}}$${\ Displaystyle \ lambda}$${\ Displaystyle \ lambda}$${\ Displaystyle w}$${\ Displaystyle n}$${\ Displaystyle \ lambda}$${\displaystyle n<d}$${\ Displaystyle X ^ {T} X}$${\ Displaystyle \ lambda}$${\ Displaystyle (\ nazwa operatora {X} ^ {T} \ nazwa operatora {X} + \ lambda n \ nazwa operatora {I}) ^ {-1}}$

Złożoność

Parametr kontroluje odwracalność matrycy . Do rozwiązania powyższego układu liniowego można zastosować kilka metod, przy czym rozkład Choleskiego jest prawdopodobnie metodą z wyboru, ponieważ macierz jest symetryczna i dodatnio określona . Złożoność tej metody dotyczy szkolenia i testowania. Koszt jest zasadniczo kosztem obliczeń , podczas gdy obliczenia odwrotne (a raczej rozwiązanie systemu liniowego) są z grubsza . ${\ Displaystyle \ lambda}$${\ Displaystyle X ^ {T} X + \ lambda nI}$${\ Displaystyle X ^ {T} X + \ lambda nI}$${\ Displaystyle O (nD ^ {2})}$${\ Displaystyle O(D)}$${\ Displaystyle O (nD ^ {2})}$${\ Displaystyle X ^ {T} X}$${\ Displaystyle O (D ^ {3})}$

Mapy cech i twierdzenie Mercera

W tej sekcji zostanie pokazane, jak rozszerzyć RLS na dowolny rodzaj jądra odtwarzającego K. Zamiast jądra liniowego rozważana jest mapa cech dla pewnej przestrzeni Hilberta , zwanej przestrzenią cech. W tym przypadku jądro jest zdefiniowane jako: Macierz jest teraz zastąpiona przez nową macierz danych , gdzie , lub -ty składnik . ${\ Displaystyle \ Phi : X \ rightarrow F}$${\ Displaystyle F}$${\ Displaystyle X}$${\ Displaystyle \ Phi}$${\ Displaystyle \ Phi _ {ij} = \ varphi _ {j} (x_ {i})}$${\displaystyle j}$${\ Displaystyle \ varphi (x_ {i})}$

${\ Displaystyle K (x, x ') = \ langle \ Phi (x), \ Phi (x ') \ rangle _ {F}.}$

Oznacza to, że dla danego zestawu treningowego . Zatem funkcję celu można zapisać jako ${\ Displaystyle K = \ Phi \ Phi ^ {T}}$

${\ Displaystyle \ min _ {c \ w \ mathbb {R} ^ {n}} \ | Y- \ Phi \ Phi ^ {T} c \ | _ {\ mathbb {R} ^ {n}} ^ {2 }+\lambda c^{T}\Phi \Phi ^{T}c.}$

Takie podejście jest znane jako sztuczka z jądrem . Ta technika może znacznie uprościć operacje obliczeniowe. Jeśli jest wielowymiarowy, obliczenia mogą być dość intensywne. Jeśli znana jest jawna forma funkcji jądra, wystarczy obliczyć i zapisać macierz jądra . ${\ Displaystyle F}$${\ Displaystyle \ varphi (x_ {i})}$${\displaystyle n\razy n}$${\displaystyle \operatorname {K}}$

W rzeczywistości przestrzeń Hilberta nie musi być izomorficzna i może być nieskończenie wymiarowa. Wynika to z twierdzenia Mercera , które stwierdza, że ​​ciągłą, symetryczną, dodatnio określoną funkcję jądra można wyrazić jako ${\ Displaystyle F}$${\ Displaystyle \ mathbb {R} ^ {m}}$

${\ Displaystyle K (x, z) = \ suma _ {i = 1} ^ {\ infty} \ sigma _ {i} e_ {i} (x) e_ {i} (z)}$

gdzie tworzą ortonormalną podstawę dla , i . Jeśli mapy elementów są zdefiniowane z komponentami , wynika z tego . Pokazuje to, że dowolne jądro może być powiązane z mapą cech i że RLS generalnie składa się z liniowego RLS wykonywanego w jakiejś przestrzeni cech, być może o wyższym wymiarze. Podczas gdy twierdzenie Mercera pokazuje, w jaki sposób jedna mapa cech może być powiązana z jądrem, w rzeczywistości wiele map cech może być powiązanych z danym odtwarzającym jądrem. Na przykład mapa spełnia właściwość dowolnego jądra odtwarzającego. ${\ Displaystyle e_ {i} (x)}$${\displaystyle \ell ^{2}(X)}$${\ Displaystyle \ sigma _ {i} \ w \ mathbb {R}}$${\ Displaystyle \ varphi (x)}$${\ Displaystyle \ varphi _ {i} (x) = {\ sqrt {\ sigma _ {i}}} e_ {i} (x)}$${\ Displaystyle K (x, z) = \ langle \ varphi (x), \ varphi (z) \ rangle }$${\ Displaystyle \ varphi (x) = K_ {x}}$${\ Displaystyle K (x, z) = \ langle \ varphi (x), \ varphi (z) \ rangle }$

Interpretacja bayesowska

Metoda najmniejszych kwadratów może być postrzegana jako maksymalizacja wiarygodności przy założeniu reszt o rozkładzie normalnym. Dzieje się tak, ponieważ wykładnik rozkładu Gaussa jest w danych kwadratowy, podobnie jak funkcja celu najmniejszych kwadratów. W tych ramach, warunki regularyzacji RLS mogą być rozumiane jako kodowanie a priori na . Na przykład regularyzacja Tichonowa odpowiada wcześniej o rozkładzie normalnym, które jest wyśrodkowane na 0. Aby to zobaczyć, najpierw zauważ, że cel OLS jest proporcjonalny do funkcji logarytmu wiarygodności, gdy każda próbka ma rozkład normalny wokół . Następnie zaobserwuj, że normalny a priori wyśrodkowany na 0 ma logarytmiczne prawdopodobieństwo postaci ${\ Displaystyle w}$${\ Displaystyle w}$${\ Displaystyle y ^ {i}}$${\ Displaystyle w ^ {T} \ cdot x ^ {i}}$${\ Displaystyle w}$

${\ Displaystyle \ log P (w) = q- \ alfa \ suma _ {j = 1} ^ {d} w_ {j} ^ {2}}$

gdzie i są stałymi, które zależą od wariancji wcześniejszego i są niezależne od . Zatem minimalizacja logarytmu prawdopodobieństwa razy a priori jest równoważna minimalizacji sumy funkcji straty OLS i członu regularyzacji regresji grzbietowej. ${\displaystyle q}$${\ Displaystyle \ alfa}$${\ Displaystyle w}$

Daje to bardziej intuicyjną interpretację, dlaczego regularyzacja Tichonowa prowadzi do unikalnego rozwiązania problemu najmniejszych kwadratów: istnieje nieskończenie wiele wektorów spełniających ograniczenia uzyskane z danych, ale ponieważ dochodzimy do problemu z wcześniejszym przekonaniem, które ma rozkład normalny wokół początku, ostatecznie wybierzemy rozwiązanie z myślą o tym ograniczeniu. ${\ Displaystyle w}$${\ Displaystyle w}$

Inne metody regularyzacji odpowiadają różnym a priori. Zobacz poniższą listę, aby uzyskać więcej informacji.

Konkretne przykłady

Regresja grzbietowa (lub regularyzacja Tichonowa)

Jednym ze szczególnie powszechnych wyborów dla funkcji kary jest norma kwadratowa , tj. ${\ Displaystyle R}$${\displaystyle \ell_{2}}$

${\ Displaystyle R (w) = \ suma _ {j = 1} ^ {d} w_ {j} ^ {2}}$

${\ Displaystyle {\ Frac {1} {n}} \ | Y- \ nazwa operatora {X} w \ | _ {2} {2} + \ lambda \ suma _ {j = 1} ^ {d} | w_ {j}|^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}}$

Najbardziej popularne nazwy to regularyzacja Tichonowa i regresja grzbietowa . Dopuszcza rozwiązanie w formie zamkniętej dla : ${\ Displaystyle w}$

${\ Displaystyle w = (X ^ {T} X + \ alfa I) ^ {-1} X ^ {T} Y}$

Nazwa regresja grzbietowa odnosi się do faktu, że termin dodaje dodatnie wpisy wzdłuż ukośnego „grzbieta” przykładowej macierzy kowariancji . ${\ Displaystyle \ alfa I}$ ${\ Displaystyle X ^ {T} X}$

Kiedy , tj. w przypadku zwykłych najmniejszych kwadratów , warunek, który powoduje, że próbka macierz kowariancji nie ma pełnego rzędu, a więc nie może być odwrócona w celu uzyskania jednoznacznego rozwiązania. Dlatego może istnieć nieskończona liczba rozwiązań zwykłego problemu najmniejszych kwadratów, gdy . Jednak gdy , tj. gdy używana jest regresja grzbietowa, dodanie do próbki macierzy kowariancji zapewnia, że ​​wszystkie jej wartości własne będą ściśle większe od 0. Innymi słowy, staje się ona odwracalna, a rozwiązanie staje się unikalne. ${\ Displaystyle \ alfa = 0}$${\displaystyle d>n}$ ${\ Displaystyle X ^ {T} X}$${\displaystyle d>n}$${\ Displaystyle \ alfa > 0}$${\ Displaystyle \ alfa I}$

W porównaniu ze zwykłymi najmniejszymi kwadratami regresja grzbietowa nie jest bezstronna. Akceptuje niewielkie obciążenie w celu zmniejszenia wariancji i błędu średniokwadratowego oraz pomaga poprawić dokładność przewidywania. Zatem estymator grzbietu daje bardziej stabilne rozwiązania poprzez zmniejszanie współczynników, ale cierpi na brak wrażliwości na dane.

Regresja lasso

Innym popularnym wyborem jest metoda najmniejszej selekcji i skurczu (LASSO). W regresji lasso , funkcja kary lasso jest normą , tj. ${\ Displaystyle R}$${\displaystyle \ell_{1}}$

${\ Displaystyle R (w) = \ suma _ {j = 1} ^ {d} \ lewo | w_ {j} \ prawo |}$

${\ Displaystyle {\ Frac {1} {n}} \ | Y- \ nazwa operatora {X} w \ | _ {2} {2} + \ lambda \ suma _ {j = 1} ^ {d} | w_ {j}|\rightarrow \min _{w\in \mathbb {R} ^{d}}}$

Zauważ, że funkcja kary lassa jest wypukła, ale nie ściśle wypukła. W przeciwieństwie do regularyzacji Tichonowa , ten schemat nie ma wygodnego rozwiązania formy zamkniętej: zamiast tego rozwiązanie jest zwykle znajdowane za pomocą programowania kwadratowego lub bardziej ogólnych metod optymalizacji wypukłej , a także za pomocą określonych algorytmów, takich jak algorytm regresji najmniejszego kąta .

Ważną różnicą między regresją lasso a regularyzacją Tichonowa jest to, że regresja lasso wymusza więcej wpisów do faktycznie równych 0 niż w innym przypadku. W przeciwieństwie do tego, podczas gdy regularyzacja Tichonowa wymusza, aby wejścia były małe, nie wymusza jednak większej liczby z nich, aby były równe 0, niż byłoby inaczej. Tak więc regularyzacja LASSO jest bardziej odpowiednia niż regularyzacja Tichonowa w przypadkach, w których spodziewamy się, że liczba niezerowych wpisów o będzie mała, a regularyzacja Tichonowa jest bardziej odpowiednia, gdy spodziewamy się, że wpisy o będą generalnie małe, ale niekoniecznie zero. Który z tych systemów jest bardziej odpowiedni, zależy od konkretnego zestawu danych. ${\ Displaystyle w}$${\ Displaystyle w}$${\ Displaystyle w}$${\ Displaystyle w}$

Oprócz wyboru funkcji opisanych powyżej, LASSO ma pewne ograniczenia. Regresja grzbietowa zapewnia lepszą dokładność w przypadku wysoce skorelowanych zmiennych. W innym przypadku, LASSO wybiera co najwyżej zmienne. Co więcej, LASSO ma tendencję do wybierania arbitralnych zmiennych z grupy silnie skorelowanych próbek, więc nie ma efektu grupowania. ${\displaystyle n>d}$${\displaystyle n<d}$${\ Displaystyle n}$

ℓ ₀ Kara

${\ Displaystyle {\ Frac {1} {n}} \ | Y- \ nazwa operatora {X} w \ | _ {2} {2} + \ lambda \ | w_ {j} \ | _ {0} \ rightarrow \min _{w\in \mathbb {R} ^{d}}}$

Najbardziej ekstremalnym sposobem wymuszenia rzadkości jest stwierdzenie, że rzeczywista wielkość współczynników nie ma znaczenia; raczej jedyną rzeczą, która decyduje o złożoności, jest liczba wpisów niezerowych. Odpowiada to ustawienie się być normą od . Ta funkcja regularyzacji, choć atrakcyjna ze względu na rzadkość, jaką gwarantuje, jest bardzo trudna do rozwiązania, ponieważ wymaga optymalizacji funkcji, która nie jest nawet słabo wypukła . Regresja lassowa jest minimalną możliwą relaksacją penalizacji, która daje słabo wypukły problem optymalizacji. ${\ Displaystyle w}$${\ Displaystyle w}$${\ Displaystyle R (w)}$${\displaystyle \ell_{0}}$${\ Displaystyle w}$${\displaystyle \ell_{0}}$

Elastyczna siatka

Dla każdego nieujemnego, a cel ma następującą postać: ${\ Displaystyle \ lambda _ {1}}$${\ Displaystyle \ lambda _ {2}}$

${\ Displaystyle {\ Frac {1} {n}} \ | Y- \ nazwa operatora {X} w \ | _ {2} {2} + \ lambda _ {1} \ suma _ {j = 1} ^ { d}|w_{j}|+\lambda _{2}\sum _{j=1}^{d}|w_{j}|^{2}\rightarrow \min _{w\in \mathbb {R } ^{d}}}$

Niech , to rozwiązanie problemu minimalizacji jest opisane jako: ${\ Displaystyle \ alfa = {\ Frac {\ lambda _ {1}} {\ lambda _ {1} + \ lambda _ {2}}}}$

${\ Displaystyle {\ Frac {1} {n}} \ | Y- \ nazwa operatora {X} w \ | _ {2} {2} \ rightarrow \ min _ {w \ w \ mathbb {R} ^ {d }}{\text{ st }}(1-\alpha )\|w\|_{1}+\alpha \|w\|_{2}\leq t}$dla niektórych .${\displaystyle t}$

Rozważ jako funkcję kary elastycznej netto. ${\ Displaystyle (1- \ alfa ) \ | w \ | _ {1} + \ alfa \ | w \ | _ {2} \ leq t}$

Kiedy , elastyczna siatka staje się regresją grzbietu, podczas gdy staje się Lasso. Elastyczna funkcja kary netto nie ma pierwszej pochodnej na 0 i jest ściśle wypukła, przyjmując właściwości zarówno regresji lassa, jak i regresji grzbietowej . ${\ Displaystyle \ alfa =1}$${\ Displaystyle \ alfa = 0}$${\displaystyle \forall \alfa \in (0,1]}$${\ Displaystyle \ dla wszystkich \ alfa > 0}$

Jedną z głównych właściwości sieci elastycznej jest to, że może ona wybierać grupy skorelowanych zmiennych. Różnica między wektorami mas próbek i jest wyrażona wzorem: ${\displaystyle x_{i}}$${\displaystyle x_{j}}$

${\ Displaystyle | w_ {i} ^ {*} (\ lambda _ {1} \ lambda _ {2}) - w_ {j} ^ {*} (\ lambda _ {1} \ lambda _ {2} )|\leq {\frac {\sum _{i=1}^{n}|y_{i}|}{\lambda _{2}}}{\sqrt {2(1-\rho _{ij} )}}}$, gdzie .${\ Displaystyle \ rho _ {ij} = x_ {i} ^ {T} x_ {j}}$

Jeśli i są silnie skorelowane ( ), wektory wag są bardzo zbliżone. W przypadku próbek skorelowanych ujemnie ( ) można pobrać próbki . Podsumowując, dla zmiennych silnie skorelowanych wektory wag są zwykle równe do znaku w przypadku zmiennych ujemnie skorelowanych. ${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\ Displaystyle \ rho _ {ij} \ rightarrow 1}$${\ Displaystyle \ rho _ {ij} \ rightarrow -1}$${\displaystyle -x_{j}}$

Częściowa lista metod RLS

Poniżej znajduje się lista możliwych wyborów funkcji regularyzacji , wraz z nazwą każdej z nich, odpowiednim przed, jeśli jest prosty, oraz sposobami obliczania rozwiązania powstałego problemu optymalizacji. ${\displaystyle R(\cdot)}$

Nazwa	Funkcja regularyzacji	Odpowiadający przed	Metody rozwiązywania
Regularyzacja Tichonowa	${\displaystyle \|w\|_{2}^{2}}$	Normalna	Formularz zamknięty
Regresja lasso	${\displaystyle \|w\|_{1}}$	Laplace	Proksymalny spadek gradientu , regresja najmniejszego kąta
${\displaystyle \ell_{0}}$ kara	${\displaystyle \|w\|_{0}}$	–	Wybór w przód , eliminacja wsteczna , użycie a priori, takich jak kolec i płyta
Siatki elastyczne	${\ Displaystyle \ beta \ | w \ | _ {1} + (1-\ beta) \ | w \ | _ {2} ^ {2}}$	Mieszanka normalna i Laplacea	Proksymalny spadek gradientu
Całkowita regulacja zmienności	${\ Displaystyle \ suma _ {j = 1} ^ {d-1} | w_ {j + 1} - w_ {j} |}$	–	m.in. metoda Split–Bregman

Zobacz też

• Najmniej kwadratów
• Regularyzacja w matematyce.
• Błąd generalizacji , jeden z powodów, dla których używana jest regularyzacja.
• Regularyzacja Tichonowa
• Regresja lasso
• Elastyczna regularyzacja sieci
• Regresja najmniejszego kąta

Bibliografia

Linki zewnętrzne

• http://www.stanford.edu/~hastie/TALKS/enet_talk.pdf Regularyzacja i wybór zmiennych poprzez elastyczną sieć (prezentacja)
• Uregulowane najmniejsze kwadraty i maszyny wektorów nośnych (prezentacja)
• Uregulowane najmniejsze kwadraty (prezentacja)