Programowanie kwadratowe i Lasso

Próbuję wykonać regresję lasso, która ma następującą postać:

Minimalizuj w $w$ $(Y - Xw)'(Y - Xw) + \lambda \;|w|_1$

Biorąc pod uwagę , doradzono mi, aby znaleźć optymalne za pomocą programowania kwadratowego, które przyjmuje następującą postać: $\lambda$ $w$

Minimalizuj w , z zastrzeżeniem $x$ $\frac{1}{2} x'Qx + c'x$ $Ax \le b.$

Teraz zdaję sobie sprawę, że termin należy przekształcić w termin , co jest dość proste. Jednak jakoś nie rozumiem, jak mógłbym przenieść pierwszy człon pierwszego równania do pierwszego członu drugiego. Nie mogłem znaleźć dużo na ten temat w sieci, więc postanowiłem zapytać tutaj. $\lambda$ $Ax \le b$

regression lasso quadratic-form

— Spurra
źródło

Odpowiedzi:

Pamiętając, że pracujemy z jako zmienną „ ” w standardowej formie, rozwiń i zbieraj terminy w i i , a stałymi. $w$ $x$ $(Y - Xw)'(Y - Xw)$ $w'\, [\,_{^{^\text{something}}}]\,w$ $w'$ $w$

Wyjaśnij, dlaczego możesz zignorować stałe.

Wyjaśnić, dlaczego można połączyć oraz kategoriach. $w'$ $w$

Jak BananaCode został już zorientowali się, ze niektórzy wiodący wzdłuż ścieżki, można napisać i lub prościej, można po prostu napisać i (ponieważ i mają ten sam argmin dla dowolnego ). $Q=2X'X$ $c=-2X'Y$ $Q=X'X$ $c=-X'Y$ $f(x)$ $kf(x)$ $k>0$

— Glen_b - Przywróć Monikę
źródło

Stałe można zignorować, ponieważ jeśli x_ jest minimum do f (x), to x_ + c jest minimum f (x) + c, stąd możemy zignorować stałą c. Przeredaguję moje pytanie, aby pokazać, gdzie utknąłem.

— spurra

Banana Kod wyjaśnienia ma kilka wad. Jeśli przez „jest minimalna do

” masz na myśli „jest argument, w którym

jest zminimalizowane”, można powiedzieć coś w stylu „

jest

”. Ale twój wniosek jest błędny. Jeśli dodasz

, nie dodasz

do argmin.

f (x)

$f(x)$

f (x)

$f(x)$

x^{*}

$x^*$

argmin

$\text{argmin}$

f

$f$

c

$c$

f

$f$

c

$c$

— Glen_b

Zobacz gdzie napisałem

moim odpowiedź? Jakie jestcoś,co teraz masz między

na dole pytania?

w^{'} [something] w

$w'\, [\,\text{something}]\,w$

w^{'}

$w'$

w

$w$

— Glen_b

Tak, przeznaczona

. Czy możesz podać przykład, w którym mój wniosek jest błędny?

jest

matrycy mi próby formy. Jeśli rozwinę

, otrzymam

x *

$x*$

a r g m i n

$argmin$

f

$f$

[s o m e t h i n g]

$[something]$

Q

$Q$

w^{'} (X^{'} X w - X^{'} Y)

$w'(X'Xw - X'Y)$

. Pierwsza część stanowiłaby formę

matrycy, jednak nie można się pozbyć drugi składnik

w^{'} X^{'} X w - w^{'} X^{'} Y

$w'X'Xw - w'X'Y$

Q

$Q$

- w^{'} X^{'} Y

$-w'X'Y$

— spurra

@ AD.Net Ograniczenia są w większości ujęte w drugiej odpowiedzi.

— Glen_b

Chciałem dodać, jak rozwiązać transformację ograniczeń w użyteczną formę do programowania kwadratowego, ponieważ nie jest to tak proste, jak myślałem. Nie można znaleźć prawdziwej macierzy takiej, że . $\sum |w_i| \le s$ $A$ $Aw \le s \leftrightarrow \sum |w_i| \le s$

Metoda I zastosowano do dzielenia elementów wektora w i tak, . Jeśli , masz oraz , w przeciwnym razie masz i $w_i$ $w$ $w_i^+$ $w_i^-$ $w_i = w_i^+ - w_i^-$ $w_i \ge 0$ $w_i^+ = w_i$ $w_i^- = 0$ $w_i^- = |w_i|$ . Lub bardziej matematycznie, $w_i^+ = 0$ oraz $w_i^+ = \frac{|w_i| + w_i}{2}$ Zarówno i są liczbami nieujemnymi. Pomysł dzielenia liczb jest taki, że masz , skutecznie pozbywając się wartości bezwzględnych. $w_i^- = \frac{|w_i| - w_i}{2}.$ $w_i^-$ $w_i^+$ $|w_i| = w_i^+ + w_i^-$

Funkcja optymalizacji zmienia się w: , z zastrzeżeniem $\frac{1}{2}(w^+ - w^-)^TQ(w^+ - w^-) + c^T(w^+ - w^-)$ $w_i^+ + w_i^- \le s, \\ w_i^+,w_i^- \ge 0$

Gdzie i podano jak podano powyżej przez Glen_b $Q$ $c$

To musi zostać przekształcone w użyteczną formę, tzn. Potrzebujemy jednego wektora. Odbywa się to w następujący sposób:

$\frac{1}{2} \bigg[ \begin{array}{c} w^+ \\ w^- \end{array} \bigg]^T \bigg[ \begin{array}{cc} Q & -Q \\ -Q & Q \end{array} \bigg] \bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg] + \big[ \begin{array}{cc} c^T & -c^T \end{array} \big] \bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg]$

z zastrzeżeniem

$\bigg[ \begin{array}{cc} I_D & I_D \\ -I_{2D} \end{array} \bigg]\bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg] \le \bigg[ \begin{array}{c} s_D \\ 0_{2D} \end{array}\bigg]$

Gdzie jest macierzą wymiarowej jednostki, jest wektorem wymiarowym składającym się tylko z wartości a jest w wymiarze wektora zerowego Pierwsza połowa zapewnia , drugie Teraz w użytecznej formie można użyć programowania kwadratowego do wyszukiwania $I_D$ $D$ $s_D$ $D$ $s$ $0_D$ $2*D$ $|w_i| = w_i^+ + w_i^- \le s$ $w_i^+,w_i^- \ge 0$ i , biorąc pod uwagę . Po wykonaniu tego optymalnym parametrem w odniesieniu do jest . $w^+$ $w^-$ $s$ $s$ $w = w^+ - w^-$

Źródło i dalsze czytanie: Rozwiązywanie problemu programowania kwadratowego z ograniczeniami liniowymi zawierającymi wartości bezwzględne

— Spurra
źródło

Załóżmy, że znaleźliśmy optymalny

-wymiarową wektor

. Co zapewnia, że

są w rzeczywistości dodatnimi i ujemnymi częściami niektórych wektorów

, tzn. Że ich pozycje wejścia

pasują do siebie?

2 D

$2D$

(w^{+}, w^{-})

$(w^+, w^-)$

w^{+}

$w^+$

w^{-}

$w^-$

w

$w$

0

$0$

— Myath

Macierz i wektor w ostatecznym wyrażeniu mogą być prostsze, a właściwie bardziej poprawne. Zamiast [Id Id] [w + w-] '≤ Sd można po prostu umieścić [1 1 .... 1] [w + w-]' ≤ s. Jest to dosłownie równoważne z ∑ | wi | = ∑ (wi + + wi−) ≤ s.

— Marko,