Pokazuje równoważność

12

Według odniesień Księga 1 , Księga 2 i papier .

Wspomniano, że istnieje równoważność między regresją regulowaną (Ridge, LASSO i Elastic Net) a ich formułami ograniczeń.

Patrzyłem również na Cross Validated 1 i Cross Validated 2 , ale nie widzę wyraźnej odpowiedzi pokazującej, że równoważność lub logika.

Moje pytanie brzmi

Jak wykazać tę równoważność za pomocą Karush – Kuhn – Tucker (KKT)?

Poniższe formuły dotyczą regresji Ridge'a.

Grzbiet

UWAGA

To pytanie nie jest pracą domową. Tylko w celu lepszego zrozumienia tego tematu.

AKTUALIZACJA

Nie mam jeszcze pomysłu.

jeza
źródło
Dlaczego potrzebujesz więcej niż 1 odpowiedzi? Wydaje się, że obecna odpowiedź wyczerpująco odnosi się do pytania. Jeśli chcesz dowiedzieć się więcej o metodach optymalizacji, dobrym pomysłem na rozpoczęcie jest wypukła optymalizacja Lieven Vandenberghe i Stephen P. Boyd.
Sycorax mówi: Przywróć Monikę
@Sycorax, dziękuję za komentarze i książkę, którą mi dostarczasz. Odpowiedź nie jest dla mnie tak jasna i nie mogę prosić o więcej wyjaśnień. Tak więc, więcej niż jedna odpowiedź może pozwolić mi zobaczyć inną perspektywę i sposób opisu.
jeza
@jeza, Czego brakuje w mojej odpowiedzi?
Royi
1
Wpisz pytanie jako tekst, a nie tylko publikuj zdjęcie (patrz tutaj ).
gung - Przywróć Monikę

Odpowiedzi:

10

Bardziej techniczną odpowiedzią jest to, że ograniczony problem optymalizacji można zapisać w kategoriach mnożników Lagrange'a. W szczególności Lagrangian związany z ograniczonym problemem optymalizacji daje

L(β)=argminβ{i=1N(yij=1pxijβj)2}+μ{(1α)j=1p|βj|+αj=1pβj2}
gdzieμto mnożnik wybrany w celu spełnienia ograniczeń problemu. Warunki pierwszego rzędu (które są wystarczające, ponieważ pracujesz z ładnymi odpowiednimi funkcjami wypukłymi) dla tego problemu optymalizacji można zatem uzyskać przez różnicowanie Lagrangian w odniesieniu do β i ustawienie pochodnych równych 0 (jest to trochę bardziej niuansowe od LASSO część ma nierozróżnialne punkty, ale istnieją metody z analizy wypukłej, aby uogólnić pochodną, ​​aby warunek pierwszego rzędu nadal działał). Oczywiste jest, że te warunki pierwszego rzędu są identyczne z warunkami pierwszego rzędu nieograniczonego problemu, który zapisałeś.

maxxf(x)+λg(x)
maxxf(x)+λg(x)=maxt(maxxf(x) s.t g(x)=t)+λt
λt który rozwiązuje problem zewnętrznej optymalizacji. To daje nam rodzaj odwzorowania od nieograniczonych problemów optymalizacyjnych do ograniczonych problemów. W twoim konkretnym ustawieniu, ponieważ wszystko jest ładnie zachowywane w przypadku regresji elastycznej sieci, to odwzorowanie powinno w rzeczywistości być jeden do jednego, więc przydaje się możliwość przełączania się między tymi dwoma kontekstami, w zależności od tego, który jest bardziej przydatny dla konkretnej aplikacji. Zasadniczo ta relacja między ograniczonymi i nieograniczonymi problemami może być mniej dobrze zachowana, ale nadal przydatne może być zastanowienie się, w jakim stopniu można poruszać się między ograniczonym i nieograniczonym problemem.

Edycja: Zgodnie z prośbą przedstawię bardziej konkretną analizę regresji grzbietu, ponieważ zawiera ona główne idee, unikając przy tym konieczności radzenia sobie z technicznymi aspektami związanymi z niezróżnicowaniem kary LASSO. Przypomnijmy, że rozwiązujemy problem optymalizacji (w notacji macierzowej):

argminβ{i=1NyixiTβ}s.t.||β||2M

Niech będzie rozwiązaniem OLS (tzn. Gdy nie ma ograniczeń). Następnie skupię się na sprawie, w której(pod warunkiem, że istnieje), ponieważ w przeciwnym razie ograniczenie jest nieciekawe, ponieważ nie wiąże. Lagrangian dla tego problemu można napisać Następnie różnicując , otrzymujemy warunki pierwszego zamówienia: który jest tylko układem równań liniowych i dlatego można go rozwiązać: βOLSM<||βOLS||

L(β)=argminβ{i=1NyixiTβ}μ||β||2M
0=2(i=1Nyixi+(i=1NxixiT+μI)β)
β^=(i=1NxixiT+μI)1(i=1Nyixi)
dla pewnego wyboru mnożnika . Następnie mnożnik jest po prostu wybierany, aby ograniczenie było prawdziwe, tzn. Potrzebujemyμ

((i=1NxixiT+μI)1(i=1Nyixi))T((i=1NxixiT+μI)1(i=1Nyixi))=M
który istnieje, ponieważ LHS jest monotoniczny w . To równanie daje wyraźne odwzorowanie od mnożników na ograniczenia, z gdy istnieje RHS i To odwzorowanie faktycznie odpowiada czemuś dość intuicyjnemu. Twierdzenie koperta mówi nam, żeμμ(0,)M(0,||βOLS||)
limμ0M(μ)=||βOLS||
limμM(μ)=0
μ(M)odpowiada marginalnej spadku błędu otrzymujemy od małego rozluźnienia ograniczenie . To wyjaśnia, dlaczego gdy odpowiada. Gdy ograniczenie nie jest już wiążące, nie ma sensu go rozluźniać, dlatego mnożnik znika.Mμ0M||βOLS||

stats_model
źródło
czy możesz podać nam szczegółową odpowiedź krok po kroku z praktycznym przykładem, jeśli to możliwe.
jeza
wielkie dzięki, dlaczego nie wspominasz o KKT? Nie znam tego obszaru, więc traktuj mnie jak uczennicę liceum.
jeza
Warunki KKT w tym przypadku są uogólnieniem „warunków pierwszego rzędu”, o których wspominam, różnicując Lagrangian i ustawiając pochodną równą 0. Ponieważ w tym przykładzie ograniczenia są równe, nie potrzebujemy warunków KKT w ogólnie pełny. W bardziej skomplikowanych przypadkach dzieje się tak, że niektóre z powyższych równości stają się nierównościami, a mnożnik staje się 0, ponieważ ograniczenia stają się niewiążące. Na przykład dokładnie tak się dzieje, gdyw powyższym. M>||βOLS||
stats_model
3

Istnieje wielka analiza przez stats_model w jego odpowiedzi .

Próbowałem odpowiedzieć na podobne pytanie w The Proof of Equivalent Formulas of Ridge Regression .

W tej sprawie zajmę się bardziej praktycznym podejściem.
Spróbujmy zobaczyć mapowanie między i w modelach 2.tλ

Jak napisałem i można go zobaczyć ze stats_model w jego analizie, mapowanie zależy od danych. Dlatego wybierzemy konkretną realizację problemu. Jednak kod i szkicowanie rozwiązania doda intuicji do tego, co się dzieje.

Porównamy następujące 2 modele:

The Regularized Model: argminx12Axy22+λx22

The Constrained Model: argminx12Axy22subject tox22t

Załóżmy, że to rozwiązanie modelu uregulowanego, a to rozwiązanie modelu ograniczonego. x^x~

Patrzymy na mapowanie od do tak, że . Patrząc na moje rozwiązanie do Solver dla Norm ograniczenie najmniejszych kwadratów można było zobaczyć, że rozwiązywanie ograniczonego modelu polega na rozwiązywaniu uregulowana modelu i znalezienie , który pasuje do (Rzeczywisty kod jest przedstawiony w najmniejszych kwadratów z euklidesowej ( ) Ograniczenie normy ).tλx = ~ x λ t L 2x^=x~
λtL2

Uruchomimy więc ten sam solver i dla każdego wyświetlimy optymalną .tλ

Solver zasadniczo rozwiązuje:

argλλsubject to(ATA+2λI)1ATb22t=0

Oto nasza Matryca:

mA =

   -0.0716    0.2384   -0.6963   -0.0359
    0.5794   -0.9141    0.3674    1.6489
   -0.1485   -0.0049    0.3248   -1.7484
    0.5391   -0.4839   -0.5446   -0.8117
    0.0023    0.0434    0.5681    0.7776
    0.6104   -0.9808    0.6951   -1.1300

A oto nasz wektor:

vB =

    0.7087
   -1.2776
    0.0753
    1.1536
    1.2268
    1.5418

To jest mapowanie:

wprowadź opis zdjęcia tutaj

Jak widać powyżej, dla wystarczająco wysokiej wartości parametr zgodnie z oczekiwaniami.tλ=0

Powiększanie do zakresu [0, 10]:

wprowadź opis zdjęcia tutaj

Pełny kod jest dostępny w moim repozytorium GitHub Q401212 StackExchange Cross Validated .

Royi
źródło