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 β^=(XTX+λI)1XTY 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=xTβ^ .

W trybie online ciągle rysuję nowe punkty danych. Jak mogę zaktualizować β^ 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

Odpowiedzi:

11

β^n=(XXT+λI)1i=0n1xiyi

Niech Mn1=(XXT+λI)1 , a następnie

β^n+1=Mn+11(i=0n1xiyi+xnyn) oraz

Mn+1Mn=xnxnT , możemy dostać

β^n+1=β^n+Mn+11xn(ynxnTβ^n)

Zgodnie z formułą Woodbury mamy

Mn+11=Mn1Mn1xnxnTMn1(1+xnTMn1xn)

W rezultacie,

β^n+1=β^n+Mn11+xnTMn1xnxn(ynxnTβ^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.ηn=nαMn11+xnTMn1xnα0.51α


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

β^n+1=β^n+ηnni=0n1xi(yixiTβ^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. λXβy2λβ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? λ
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. λ
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)λnλλN/nN
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.β^

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λ

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 ).XTXXTyXTX/nXTy/n

Jeśli napiszesz i jako:Xy

X=(x1TxnT),y=(y1yn),

możemy zapisać aktualizacje online do i (obliczone do rzędu) jako:XTX/nXTy/nt

At=(11t)At1+1txtxtT,

bt=(11t)bt1+1txtyt.

Twój internetowy szacunek wtedyβ

β^t=(At+λI)1bt.

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

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

jutro
źródło