Jak zastosować do modelu LASSO metodę Iterative Reweighted Least Squares (IRLS)?

12

Zaprogramowałem regresję logistyczną przy użyciu algorytmu IRLS . Chciałbym zastosować karę LASSO , aby automatycznie wybrać odpowiednie funkcje. Przy każdej iteracji rozwiązuje się następujące kwestie:

(X^{T} W X) δ \hat{β} = X^{T} (y - p)

$\mathbf{\left(X^TWX\right) \delta\hat\beta=X^T\left(y-p\right)}$

Niech będzie nieujemną liczbą rzeczywistą. Nie penalizuję przechwytywania, jak sugerowano w The Elements of. Nauka statystyczna . To samo dotyczy już zerowych współczynników. W przeciwnym razie odejmuję termin z prawej strony: $\lambda$

X^{T} (y - p) - λ \times s i g n (\hat{β})

$\mathbf{X^T\left(y-p\right)-\lambda\times \mathrm{sign}\left(\hat\beta\right)}$

Jednak nie jestem pewien co do modyfikacji algorytmu IRLS. Czy to właściwy sposób?

Edycja: Chociaż nie byłem tego pewien, oto jedno z rozwiązań, które w końcu wymyśliłem. Co ciekawe, to rozwiązanie odpowiada temu, co teraz rozumiem na temat LASSO. W każdej iteracji istnieją rzeczywiście dwa kroki zamiast tylko jednego:

pierwszy krok jest taki sam jak poprzednio: wykonujemy iterację algorytmu (tak jakby we wzorze na gradient powyżej), $\lambda=0$
drugi krok jest nowy: stosujemy miękki próg dla każdego komponentu (z wyjątkiem komponentu , który odpowiada przecięcia) wektora uzyskanego w pierwszym kroku. Nazywa się to iteracyjnym algorytmem miękkiego progowania . $\beta_0$ $\beta$

\forall i \geq 1, β_{i} \leftarrow s i g n (β_{i}) \times max (0, | β_{i} | - λ)

$\forall i \geq 1, \beta_{i}\leftarrow\mathrm{sign}\left(\beta_{i}\right)\times\max\left(0,\,\left|\beta_{i}\right|-\lambda\right)$

— Wok
źródło

Nadal nie można uzyskać lepszej konwergencji poprzez dostosowanie IRLS. : '(

— Wok

12

Ten problem zazwyczaj rozwiązuje się przez dopasowanie przez opadanie współrzędnych ( patrz tutaj ). Ta metoda jest bezpieczniejsza, bardziej wydajna numerycznie, algorytmicznie łatwiejsza do wdrożenia i ma zastosowanie do bardziej ogólnej gamy modeli (w tym również regresji Coxa). Implementacja R jest dostępna w pakiecie R glmnet . Kody są typu open source (częściowo w C, częściowo w R), więc możesz używać ich jako schematów.

— użytkownik603
źródło

@wok Warto zauważyć, że pakiet scikit.learn oferuje również wydajną implementację w Pythonie dla tego rodzaju rzeczy.

— chl

Algorytm opadania współrzędnych jest interesujący. Dzięki. Nadal o tym myślę.

— Wok

5

Funkcja utraty LASSO ma nieciągłość zerową wzdłuż każdej osi, więc IRLS będzie miał z nią problemy. Uważam, że podejście oparte na sekwencyjnej minimalnej optymalizacji (SMO) jest bardzo skuteczne, patrz np

http://bioinformatics.oxfordjournals.org/content/19/17/2246

jest wersja z oprogramowaniem MATLAB

http://bioinformatics.oxfordjournals.org/content/22/19/2348

oprogramowanie jest dostępne tutaj:

http://theoval.cmp.uea.ac.uk/~gcc/cbl/blogreg/

Podstawową ideą jest optymalizacja współczynników pojedynczo i testowanie, czy przekraczasz nieciągłość jeden współczynnik na raz, co jest łatwe, ponieważ przeprowadzasz optymalizację skalarną. Może to zabrzmieć powoli, ale w rzeczywistości jest dość wydajne (choć spodziewam się, że od tego czasu opracowano lepsze algorytmy - prawdopodobnie przez Keerthi lub Chih-Jen Lin, którzy są wiodącymi ekspertami w tego rodzaju sprawach).

— Dikran Torbacz
źródło

Dzięki. Czytam to i myślę o tym. Byłaby to jednak ogromna modyfikacja obecnego algorytmu.

— Wok

4

Możesz sprawdzić artykuł: Wydajna regresja logistyczna z regulacją L1, która jest algorytmem opartym na IRLS dla LASSO. Jeśli chodzi o implementację, link może być dla Ciebie przydatny (http://ai.stanford.edu/~silee/softwares/irlslars.htm).

0

IRLS dla problemu LASSO jest następujący:

\arg min_{x} \frac{1}{2} {‖ A x - b ‖}_{2}^{2} + λ {‖ x ‖}_{1} = \arg min_{x} \frac{1}{2} {‖ A x - b ‖}_{2}^{2} + λ x^{T} W x

$\arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda \left\| x \right\|_{1} = \arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda {x}^{T} W {x}$

Gdzie jest macierzą diagonalną - . Pochodzi z . $W$ ${W}_{i, i} = \frac{1}{ \left| {x}_{i} \right| }$
$\left\| x \right\|_{1} = \sum_{i} \left| {x}_{i} \right| = \sum_{i} \frac{ {x}_{i}^{2} } { \left| {x}_{i} \right| }$

Teraz powyższe jest po prostu regularyzacją Tichonowa .
Ponieważ jednak zależy od należy go rozwiązać iteracyjnie (anuluje to również 2 czynnik w regularyzacji Tichonowa, jako pochodna w odniesieniu do gdy jest stała, to co odpowiada ): $W$ $x$ ${x}^{T} W x$ $x$ $x$ $\operatorname{diag} \left( \operatorname{sign} \left( x \right) \right)$ $W x$

x^{k + 1} = {(A^{T} A + λ W^{k})}^{- 1} A^{T} b

${x}^{k + 1} = \left( {A}^{T} A + \lambda {W}^{k} \right)^{-1} {A}^{T} b$

Gdzie . ${W}_{i, i}^{K} = \frac{1}{ \left| {x}^{k}_{i} \right| }$

Inicjalizacja może odbywać się . $W = I$

Zwróć uwagę, że to nie działa dobrze dla dużych wartości i lepiej użyj ADMM lub Descent Coordinate Descent. $\lambda$

— Royi
źródło