Pokazuje równoważność

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.

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

Wpisz pytanie jako tekst, a nie tylko publikuj zdjęcie (patrz tutaj ).

— gung - Przywróć Monikę

Odpowiedzi:

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 (β) = \underset{β}{a r g m i n} {\sum_{i = 1}^{N} {(y_{i} - \sum_{j = 1}^{p} x_{i j} β_{j})}^{2}} + μ {(1 - α) \sum_{j = 1}^{p} | β_{j} | + α \sum_{j = 1}^{p} β_{j}^{2}}

$\mathcal L(\beta) = \underset{\beta}{\mathrm{argmin}}\,\left\{\sum_{i=1}^N \left(y_i - \sum_{j=1}^p x_{ij} \beta_j\right)^2\right\} + \mu \left\{(1-\alpha) \sum_{j=1}^p |\beta_j| + \alpha \sum_{j=1}^p \beta_j^2\right\}$ gdzie

μ

$\mu$ 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

β

$\beta$ 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ś.

max_{x} f (x) + λ g (x)

$\max_x f(x) + \lambda g(x)$

max_{x} f (x) + λ g (x) = max_{t} (max_{x} f (x) s . t g (x) = t) + λ t

$\max_x f(x) + \lambda g(x) = \max_t \left(\max_x f(x)\ \mathrm{ s.t }\ g(x) = t\right) + \lambda t$

λ

$\lambda$

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

\underset{β}{a r g m i n} {\sum_{i = 1}^{N} y_{i} - x_{i}^{T} β} s . t . | | β | |^{2} \leq M

$\underset{\beta}{\mathrm{argmin}} \left\{\sum_{i=1}^N y_i - x_i^T \beta\right\}\quad\mathrm{s.t.}\, ||\beta||^2 \leq M$

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ć: $\beta^{OLS}$ $M < \left|\left|\beta^{OLS}\right|\right|$

L (β) = \underset{β}{a r g m i n} {\sum_{i = 1}^{N} y_{i} - x_{i}^{T} β} - μ \cdot | | β | |^{2} \leq M

$\mathcal L(\beta) = \underset{\beta}{\mathrm{argmin}} \left\{\sum_{i=1}^N y_i - x_i^T \beta\right\} - \mu\cdot||\beta||^2 \leq M$

0 = - 2 (\sum_{i = 1}^{N} y_{i} x_{i} + (\sum_{i = 1}^{N} x_{i} x_{i}^{T} + μ I) β)

$0 = -2 \left(\sum_{i=1}^N y_i x_i + \left(\sum_{i=1}^N x_i x_i^T + \mu I\right) \beta\right)$

\hat{β} = {(\sum_{i = 1}^{N} x_{i} x_{i}^{T} + μ I)}^{- 1} (\sum_{i = 1}^{N} y_{i} x_{i})

$\hat\beta = \left(\sum_{i=1}^N x_i x_i^T + \mu I\right)^{-1}\left(\sum_{i=1}^N y_i x_i\right)$ dla pewnego wyboru mnożnika . Następnie mnożnik jest po prostu wybierany, aby ograniczenie było prawdziwe, tzn. Potrzebujemy

μ

$\mu$

{({(\sum_{i = 1}^{N} x_{i} x_{i}^{T} + μ I)}^{- 1} (\sum_{i = 1}^{N} y_{i} x_{i}))}^{T} ({(\sum_{i = 1}^{N} x_{i} x_{i}^{T} + μ I)}^{- 1} (\sum_{i = 1}^{N} y_{i} x_{i})) = M

$\left(\left(\sum_{i=1}^N x_i x_i^T + \mu I\right)^{-1}\left(\sum_{i=1}^N y_i x_i\right)\right)^T\left(\left(\sum_{i=1}^N x_i x_i^T + \mu I\right)^{-1}\left(\sum_{i=1}^N y_i x_i\right)\right) = 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

μ

$\mu$

μ \in (0, \infty)

$\mu \in (0,\infty)$

M \in (0, | | β^{O L S} | |)

$M \in \left(0, \left|\left|\beta^{OLS}\right|\right|\right)$

lim_{μ \to 0} M (μ) = | | β^{O L S} | |

$\lim_{\mu\to 0} M(\mu) = \left|\left|\beta^{OLS}\right|\right|$

lim_{μ \to \infty} M (μ) = 0

$\lim_{\mu \to \infty} M(\mu) = 0$

μ (M)

$\mu(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

$M$

μ \to 0

$\mu \to 0$

M \to | | β^{O L S} | |

$M \to \left|\right|\beta^{OLS}\left|\right|$

— 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 > | | β^{O L S} | |

$M > ||\beta^{OLS}||$

— stats_model

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$ $\lambda$

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: \arg min_{x} \frac{1}{2} {‖ A x - y ‖}_{2}^{2} + λ {‖ x ‖}_{2}^{2}

$\text{The Regularized Model: } \arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{2}^{2}$

The Constrained Model: \begin{aligned} \arg min_{x} & \frac{1}{2} {‖ A x - y ‖}_{2}^{2} \\ subject to & {‖ x ‖}_{2}^{2} \leq t \end{aligned}

$\text{The Constrained Model: } \begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| x \right\|}_{2}^{2} \leq t \end{align*}$

Załóżmy, że to rozwiązanie modelu uregulowanego, a to rozwiązanie modelu ograniczonego. $\hat{x}$ $\tilde{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$ $\lambda$ $\hat{x} = \tilde{x}$
$\lambda$ $t$ ${L}_{2}$

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

Solver zasadniczo rozwiązuje:

\begin{aligned} \arg_{λ} & λ \\ subject to & {‖ {(A^{T} A + 2 λ I)}^{- 1} A^{T} b ‖}_{2}^{2} - t = 0 \end{aligned}

$\begin{align*} \arg_{\lambda} \quad & \lambda \\ \text{subject to} \quad & {\left\| {\left( {A}^{T} A + 2 \lambda I \right)}^{-1} {A}^{T} b \right\|}_{2}^{2} - t = 0 \end{align*}$

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:

To jest mapowanie:

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

Powiększanie do zakresu [0, 10]:

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

— Royi
źródło