Czy istnieją algorytmy obliczania „działających” parametrów regresji liniowej lub logistycznej?

Artykuł „Dokładne obliczanie wariancji biegu” na stronie http://www.johndcook.com/standard_deviation.html pokazuje, jak obliczyć średnią biegu, wariancję i odchylenia standardowe.

Czy istnieją algorytmy, w których parametry modelu regresji liniowej lub logistycznej mogą być podobnie „dynamicznie” aktualizowane w miarę dostarczania każdego nowego rekordu szkolenia?

Liniowe współczynniki regresji $y = ax + b$ są = C O V ( x , y ) / V R ( x ) i b = m e a N ( r ) - ⋅ m wiadomość e o n ( x ) .$a = cov(x,y)/var(x)$$b = mean(y) - a \cdot mean(x)$

Tak więc wszystko, czego naprawdę potrzebujesz, to inkrementalna metoda obliczania $cov(x,y)$ . Na podstawie tej wartości i wariancji $x$ oraz średniej zarówno $y$ jak i $x$ można obliczyć parametry $a$ i $b$ . Jak zobaczysz w pseudo-kodzie podanym poniżej obliczenia przyrostowe $cov(x,y)$ są bardzo podobne do obliczeń przyrostowych $var(x)$ . To nie powinno być zaskoczeniem, ponieważ $var(x) = cov(x,x)$ .

Oto pseudo kod, którego prawdopodobnie szukasz:

init(): meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0

update(x,y):
n += 1
dx = x - meanX
dy = y - meanY
varX += (((n-1)/n)*dx*dx - varX)/n
covXY += (((n-1)/n)*dx*dy - covXY)/n
meanX += dx/n
meanY += dy/n

getA(): return covXY/varX
getB(): return meanY - getA()*meanX

Znalazłem to pytanie, szukając równoważnego algorytmu przyrostowo obliczającego regresję wielowymiarową jako $R = (X'X)^{-1}X'Y$ tak, że $XR = Y+\epsilon$

Dla dwóch konkretnych przykładów:

Regresja liniowa W artykule „Online regresja liniowa i jej zastosowanie do uczenia opartego na modelach zbrojenia” Alexander Strehl i Michael Littman opisuje algorytm o nazwie „Regresja liniowa KWIK” (patrz algorytm 1), który zapewnia przybliżenie rozwiązania regresji liniowej przy użyciu aktualizacji przyrostowych . Zauważ, że nie jest to uregulowane (tj. Nie jest to regresja Ridge'a). Jestem całkiem pewien, że metoda Strehl & Littman nie może rozciągać się na to ustawienie.

Regresja logistyczna

Ten wątek rzuca nieco światła na tę sprawę. Cytowanie:

Nawet bez ograniczenia regularyzacji regresja logistyczna jest nieliniowym problemem optymalizacji. Już nie ma to rozwiązania analitycznego, które zwykle jest warunkiem wstępnym uzyskania rozwiązania aktualizacyjnego. Z ograniczeniem regularyzacji staje się ograniczonym problemem optymalizacji. Wprowadza to zupełnie nowy zestaw nieanalitycznych komplikacji oprócz tych, które już miał nieograniczony problem.

Istnieją jednak inne internetowe (lub inkrementalne) metody regresji, na które warto przyjrzeć się, na przykład lokalnie ważona regresja projekcji (LWPR)

Zasadniczo:

0) utrzymujesz wystarczające statystyki i aktualne oszacowania ML

1) po otrzymaniu nowych danych zaktualizuj wystarczające statystyki i szacunki

2) Jeśli nie masz wystarczających statystyk, musisz użyć wszystkich danych.

3) Zazwyczaj nie masz zamkniętych rozwiązań; użyj poprzednich MLE jako punktu wyjścia, skorzystaj z wygodnej metody optymalizacji, aby znaleźć nowy optymalny stamtąd. Być może trzeba trochę poeksperymentować, aby znaleźć metody, które najlepiej kompromisują dla poszczególnych rodzajów problemów.

Jeśli twój problem ma specjalną strukturę, prawdopodobnie możesz go wykorzystać.

Kilka potencjalnych odniesień, które mogą, ale nie muszą, mieć pewną wartość:

McMahan, HB i M. Streeter (2012),
Open Problem: Better Bounds for Online Logistic
Regress , JMLR: Workshop and Conference Proceedings , tom 23, 44,1–44,3

Penny, WD i SJ Roberts (1999),
Dynamic Logistic Regression ,
Proceedings IJCNN '99

Dodając do odpowiedzi tdc, nie są znane metody obliczania dokładnych oszacowań współczynników w dowolnym momencie przy jedynie stałym czasie na iterację. Istnieją jednak rozsądne i interesujące alternatywy.

Pierwszym modelem, na który należy zwrócić uwagę, jest ustawienie uczenia się online . W tym ustawieniu świat najpierw ogłasza wartość x, twój algorytm przewiduje wartość y, świat ogłasza prawdziwą wartość y, a twój algorytm traci stratę l (y, y '). Dla tego ustawienia wiadomo, że proste algorytmy (między innymi gradient opadania i gradient wykładniczy) osiągają podżeganie żałobne. Oznacza to, że gdy widzisz więcej przykładów, liczba dodatkowych błędów popełnianych przez algorytm (w porównaniu z najlepszym możliwym predyktorem liniowym) nie rośnie wraz z liczbą przykładów. Działa to nawet w ustawieniach przeciwnych. Jest dobry artykuł wyjaśniający jedną popularną strategię, aby udowodnić te granice żalu. Przydatne są również notatki z wykładu Shai Shaleva-Schwartza .

Istnieje rozszerzenie ustawienia uczenia się online zwane ustawieniem bandyty, w którym algorytm otrzymuje tylko liczbę reprezentującą jego błędność (i brak wskaźnika do właściwej odpowiedzi). Imponująco wiele wyników uczenia się online przenosi się na to ustawienie, z tym wyjątkiem, że tutaj trzeba zarówno eksplorować, jak i wykorzystywać, co prowadzi do różnego rodzaju interesujących wyzwań.

Inne odpowiedzi wskazywały na świat uczenia maszynowego iz pewnością jest to jedno z miejsc, w których rozwiązano ten problem.

Jednak innym podejściem, które może być lepiej dostosowane do twoich potrzeb, jest zastosowanie faktoryzacji QR z aktualizacjami niskiej rangi. Podejścia do zrobienia tego i użycia go do rozwiązania problemów z najmniejszymi kwadratami podano w:

Aktualizacja faktoryzacji QR i problemu najmniejszych kwadratów przez Hammerlinga i Lucasa.

To jest dodanie do odpowiedzi @chmike.

Metoda wydaje się podobna do internetowego algorytmu BP Welford dla odchylenia standardowego, który również oblicza średnią. Jan Kucharz daje dobre wyjaśnienie tutaj . Tony Finch w 2009 roku zapewnia wykładniczą średnią ruchomą i odchylenie standardowe:

diff := x – mean 
incr := alpha * diff 
mean := mean + incr 
variance := (1 - alpha) * (variance + diff * incr)

Podglądanie poprzednio opublikowanej odpowiedzi i rozwijanie jej w celu uwzględnienia wykładniczego ruchomego okna:

init(): 
    meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0,
    meanXY = 0, varY = 0, desiredAlpha=0.01 #additional variables for correlation

update(x,y):
    n += 1
    alpha=max(desiredAlpha,1/n) #to handle initial conditions

    dx = x - meanX
    dy = y - meanY
    dxy = (x*y) - meanXY #needed for cor

    varX += ((1-alpha)*dx*dx - varX)*alpha
    varY += ((1-alpha)*dy*dy - varY)*alpha #needed for corXY
    covXY += ((1-alpha)*dx*dy - covXY)*alpha

    #alternate method: varX = (1-alpha)*(varX+dx*dx*alpha)
    #alternate method: varY = (1-alpha)*(varY+dy*dy*alpha) #needed for corXY
    #alternate method: covXY = (1-alpha)*(covXY+dx*dy*alpha)

    meanX += dx * alpha
    meanY += dy * alpha
    meanXY += dxy  * alpha

getA(): return covXY/varX
getB(): return meanY - getA()*meanX
corXY(): return (meanXY - meanX * meanY) / ( sqrt(varX) * sqrt(varY) )

W powyższym „kodzie” pożądana Alfa może być ustawiona na 0, a jeśli tak, kod działałby bez ważenia wykładniczego. Można zasugerować ustawienie żądanegoAlpha na 1 / pożądanyWindowSize, zgodnie z sugestią Zmodyfikowanej_ruchomości_średniej dla rozmiaru ruchomego okna.

Pytanie poboczne: z powyższych obliczeń alternatywnych, czy są jakieś uwagi, które są lepsze z punktu widzenia precyzji?

Referencje:

chmike (2013) https://stats.stackexchange.com/a/79845/70282

Cook, John (nd) Dokładnie obliczająca wariancja bieżąca http://www.johndcook.com/blog/standard_deviation/

Finch, Tony. (2009) Przyrostowe obliczanie średniej ważonej i wariancji. https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf

Wikipedia. (nd) Algorytm online Welforda https://en.wikipedia.org/wiki/Al Algorytmy_for_calculating_variance# Online_alameterm