Rekurencyjny (online) uregulowany algorytm najmniejszych kwadratów

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

$\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})$

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}$

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}$

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$

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$

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

Twój internetowy szacunek wtedy$\beta$

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.