Programowanie kwadratowe i Lasso

11

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

Minimalizuj w( Y - X w ) ( Y - X w ) + λw(YXw)(YXw)+λ|w|1

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

Minimalizuj w , z zastrzeżeniem1xAxb.12xQx+cxAxb.

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.A x bλAxb

Spurra
źródło

Odpowiedzi:

10

Pamiętając, że pracujemy z jako zmienną „ ” w standardowej formie, rozwiń i zbieraj terminy w i i , a stałymi.x ( Y - X w ) ( Y - X w ) w wx(YXw)(YXw)w ww[something]www

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

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


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 ).c = - 2 X Y Q = X X c = - X Y f ( x ) k f ( x ) k > 0Q=2XXc=2XY Q=XXc=XYf(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 f ( x ) jest zminimalizowane”, można powiedzieć coś w stylu „ x * jest argmin od f ”. Ale twój wniosek jest błędny. Jeśli dodasz c do f , nie dodasz c do argmin. f(x)f(x)xargminfcfc
Glen_b
Zobacz gdzie napisałem moim odpowiedź? Jakie jestcoś,co teraz masz między w ' i w na dole pytania? w[something]www
Glen_b
Tak, przeznaczona IS R G dla M i n w f . Czy możesz podać przykład, w którym mój wniosek jest błędny? [ E o m e t H i n g ] jest P matrycy mi próby formy. Jeśli rozwinę w ( X X w - X Y ) , otrzymam w X X w - w X xargminf[something]Qw(XXwXY) . Pierwsza część stanowiłaby formę Q matrycy, jednak nie można się pozbyć drugi składnik - w ' X ' Y . wXXwwXYQwXY
spurra
1
@ AD.Net Ograniczenia są w większości ujęte w drugiej odpowiedzi.
Glen_b
11

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 A takiej, że A w s | w i | s .|wi|sAAws|wi|s

Metoda I zastosowano do dzielenia elementów wektora W w W + I i W - I tak, w I = W + I - W - I . Jeśli w i0 , masz w + i = w i oraz w - i = 0 , w przeciwnym razie masz w - i = | w i | i wwiwwi+wiwi=wi+wiwi0wi+=wiwi=0wi=|wi|. Lub bardziej matematycznie,w + i =| wi| +wiwi+=0 orazw - i =| wi| -wiwi+=|wi|+wi2Zarównow - i, jak iw + i są liczbami nieujemnymi. Pomysł dzielenia liczb jest taki, że masz| wi| =w + i +w - i , skutecznie pozbywając się wartości bezwzględnych.wi=|wi|wi2.wiwi+|wi|=wi++wi

Funkcja optymalizacji zmienia się w: , z zastrzeżeniem w + i +w - is,12(w+w)TQ(w+w)+cT(w+w)wi++wis,wi+,wi0

Gdzie i c podano jak podano powyżej przez Glen_bQc

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

12[w+w]T[QQQQ][w+w]+[cTcT][w+w]

z zastrzeżeniem

[IDIDI2D][w+w][sD02D]

Gdzie jest macierzą D- wymiarowej jednostki, s D jest wektorem D- wymiarowym składającym się tylko z wartości s, a 0 D jest w wymiarze wektora zerowego 2 D. Pierwsza połowa zapewnia | w i | = w + i + w - is , drugie w + i , w - i0 Teraz w użytecznej formie można użyć programowania kwadratowego do wyszukiwaniaIDDsDDs0D2D|wi|=wi++wiswi+,wi0 i w - , biorąc pod uwagę s . Po wykonaniu tego optymalnym parametrem w odniesieniu do s jest w = w + - w - .w+wssw=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 ( w + , w - ) . Co zapewnia, że w + i w - są w rzeczywistości dodatnimi i ujemnymi częściami niektórych wektorów w , tzn. Że ich pozycje wejścia 0 pasują do siebie? 2D(w+,w)w+ww0
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,