Rekurencyjny (online) uregulowany algorytm najmniejszych kwadratów

12

Czy ktoś może skierować mnie w stronę internetowego (rekurencyjnego) algorytmu regularyzacji Tichonowa (uregulowane najmniejsze kwadraty)?

W trybie offline obliczyłem $\hat\beta=(X^TX+λI)^{−1}X^TY$ przy użyciu mojego oryginalnego zestawu danych, w którym znaleziono $λ$ przy użyciu n-krotnej weryfikacji krzyżowej. Nową wartość $y$ można przewidzieć dla danego $x$ używając $y=x^T\hat\beta$ .

W trybie online ciągle rysuję nowe punkty danych. Jak mogę zaktualizować $\hat\beta$ gdy narysuję nowe dodatkowe próbki danych bez pełnego przeliczania całego zestawu danych (oryginalny + nowy)?

— rnoodle
źródło

1

Twoje najmniejsze kwadraty uregulowane przez Tichonowa są być może częściej nazywane w kręgach statystycznych Levenberg-Marquardt , nawet jeśli dotyczą prostych problemów liniowych (jak tutaj). Jest artykuł na temat internetowej Levenberg Marquardt tutaj . Nie wiem czy to jakaś pomoc.

— Glen_b

11

$\hat\beta_n=(XX^T+λI)^{−1} \sum\limits_{i=0}^{n-1} x_iy_i$

Niech $M_n^{-1} = (XX^T+λI)^{−1}$ , a następnie

$\hat\beta_{n+1}=M_{n+1}^{−1} (\sum\limits_{i=0}^{n-1} x_iy_i + x_ny_n)$ oraz

$M_{n+1} - M_n = x_nx_n^T$ , możemy dostać

$\hat\beta_{n+1}=\hat\beta_{n}+M_{n+1}^{−1} x_n(y_n - x_n^T\hat\beta_{n})$

Zgodnie z formułą Woodbury mamy

$M_{n+1}^{-1} = M_{n}^{-1} - \frac{M_{n}^{-1}x_nx_n^TM_{n}^{-1}}{(1+x_n^TM_n^{-1}x_n)}$

W rezultacie,

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n} x_n(y_n - x_n^T\hat\beta_{n})$

Uśrednianie Polyak wskazuje, że możesz użyć do przybliżenia z zakresami od do . Możesz spróbować w swoim przypadku wybrać najlepszy dla swojej rekurencji. $\eta_n = n^{-\alpha}$ $\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$ $\alpha$ $0.5$ $1$ $\alpha$

Myślę, że to działa również, jeśli zastosujesz algorytm gradientu wsadowego:

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{\eta_n}{n} \sum\limits_{i=0}^{n-1}x_i(y_i - x_i^T\hat\beta_{n})$

— lennon310
źródło

Co jeśli zaktualizuję mój regressor za każdym razem próbkami partii nowych danych, gdzie każda kolejna partia jest pobierana z nieco innego rozkładu? tj. nie IID. W takim przypadku chciałbym, aby regressor wziął pod uwagę nowe dane, ale nie wpływał na jego przewidywania w lokalizacji starych danych (poprzednich partii)? Czy możesz wskazać mi jakąkolwiek literaturę, którą możesz uznać za przydatną?

— rnoodle

Dobre pytanie, ale obecnie niestety nie mogę powiedzieć, jak bardzo wpłynęłoby to na Twój model, jeśli nadal użyjesz formuły gradientu wsadowego w odpowiedzi lub aproksymując, stosując bezpośrednio formę macierzy: eta ^ (- alfa) * X (Y-X 'beta_n) gdzie X, Y to twoje nowe próbki partii

— lennon310

cześć, wydaje się, że współczynnik regularyzacji nie bierze udziału w formule rekurencyjnej aktualizacji? czy ma to znaczenie tylko przy inicjalizacji odwrotności macierzy M.

— Peng Zhao

4

Sprawą, do której nikt dotąd nie zwrócił uwagi, jest to, że utrzymywanie stałego parametru regulowania stałym poziomie w miarę dodawania punktów danych nie ma sensu . Powodem tego jest to, że zwykle rośnie liniowo wraz z liczbą punktów danych, podczas gdy termin regularyzacji nie. $\lambda$ $\| X \beta -y \|^{2}$ $\| \lambda\beta \|^{2}$

— Brian Borchers
źródło

To interesujący punkt. Ale dlaczego właściwie to „nie ma sensu”? Utrzymywanie stałej jest z pewnością poprawne matematycznie, więc „bez sensu” należy rozumieć w pewnym kontekście statystycznym. Ale w jakim kontekście? Co idzie nie tak? Czy byłoby jakieś łatwe rozwiązanie, takie jak zamiana sum kwadratów na średnie kwadraty?

λ

$\lambda$

— whuber

Zastąpienie sumy kwadratów wersją skalowaną (np. Średni błąd kwadratu) miałoby sens, ale zwykłe użycie rekurencyjnych najmniejszych kwadratów nie osiągnie tego.

— Brian Borchers,

Jeśli chodzi o to, co pójdzie nie tak, w zależności od wyboru , otrzymasz bardzo nieregularne rozwiązanie z dużą liczbą punktów danych lub bardzo przeregulowane rozwiązanie z małą liczbą punktów danych.

λ

$\lambda$

— Brian Borchers,

Można by przypuszczać, że jeśli jednak zostanie dostrojona początkowo po otrzymaniu punktów danych, a następnie zostanie dodanych więcej punktów danych, to czy powstałe rozwiązania z większą liczbą punktów danych i tą samą zostaną nadmiernie lub zbyt słabo uregulowane, będą zależeć od tych nowych punkty danych. Może to być analizowane punkty danych, zakładając, że działa jak IID próbki z rozkładem wielu zmiennych, w tym przypadku pojawia powinien być ustawiony w etapie . Zmieniłoby to formuły aktualizujące, ale w tak regularny i prosty sposób, że wydajne obliczenia mogą być nadal możliwe. (+1)

λ

$\lambda$

n

$n$

λ

$\lambda$

λ

$\lambda$

N / n

$N/n$

N

$N$

— whuber

3

Być może może tu działać coś w rodzaju stochastycznego spadku . Oblicz przy użyciu powyższego równania w początkowym zestawie danych, który będzie początkowym oszacowaniem. Dla każdego nowego punktu danych można wykonać jeden krok spadku gradientu, aby zaktualizować oszacowanie parametru. $\hat{\beta}$

— Max S.
źródło

Od tego czasu zdałem sobie sprawę, że SGD (być może minibatch) jest sposobem na rozwiązanie problemów online, takich jak aktualizacja przybliżeń funkcji.

— rnoodle

1

W regresji liniowej jedną z możliwości jest bezpośrednia aktualizacja rozkładu , jak wyjaśniono tutaj . Chyba, że jeśli nie chcesz ponownie oszacować po dodaniu każdego nowego punktu danych, coś bardzo podobnego można zrobić z regresją grzbietu. $X$ $\lambda$

— Matteo Fasiolo
źródło

0

Oto alternatywne (i mniej złożone) podejście w porównaniu do użycia formuły Woodbury. Zauważ, że i można zapisać jako sumy . Ponieważ obliczamy rzeczy online i nie chcemy, aby suma się wysadziła, możemy alternatywnie użyć środków ( i ). $X^TX$ $X^Ty$ $X^TX/n$ $X^Ty/n$

Jeśli napiszesz i jako: $X$ $y$

X = (\begin{matrix} x_{1}^{T} \\ ⋮ \\ x_{n}^{T} \end{matrix}), y = (\begin{matrix} y_{1} \\ ⋮ \\ y_{n} \end{matrix}),

$X = \begin{pmatrix} x_1^T \\ \vdots \\ x_n^T \end{pmatrix}, \quad y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix},$

możemy zapisać aktualizacje online do i (obliczone do rzędu) jako: $X^TX/n$ $X^Ty/n$ $t$

A_{t} = (1 - \frac{1}{t}) A_{t - 1} + \frac{1}{t} x_{t} x_{t}^{T},

$A_t = \left(1 - \frac{1}{t}\right) A_{t-1} + \frac{1}{t}x_t x_t^T,$

b_{t} = (1 - \frac{1}{t}) b_{t - 1} + \frac{1}{t} x_{t} y_{t} .

$b_t = \left(1 - \frac{1}{t}\right) b_{t-1} + \frac{1}{t}x_t y_t.$

Twój internetowy szacunek wtedy $\beta$

{\hat{β}}_{t} = (A_{t} + λ I)^{- 1} b_{t} .

$\hat\beta_t = (A_t + \lambda I)^{-1}b_t.$

Zauważ, że pomaga to również w interpretacji pozostającej stałej podczas dodawania obserwacji! $\lambda$

Ta procedura jest sposobem, w jaki https://github.com/joshday/OnlineStats.jl oblicza szacunki online regresji liniowej / kalenicowej.

— jutro
źródło