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

32

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?

chl
źródło
1
Dzięki ogromnemu zestawowi treningowemu lub ciągłemu wejściowemu strumieniowi danych możesz korzystać z iteracyjnych algorytmów, takich jak Stochastic Gradient Descent i przechwytywać dane wejściowe w małych seriach podczas ruchu. Czy o to pytałeś?
andreister
1
Algorytm RLS wyszukiwania i jego warianty. pl.wikipedia.org/wiki/Recursive_least_squares_filter
Memming

Odpowiedzi:

20

Liniowe współczynniki regresji y=ax+b= 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)amean(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=(XX)1XY tak, że XR=Y+ϵ

chmike
źródło
4
Dziękuję za twój wkład! Część pytania o regresję liniową jest w rzeczywistości duplikatem stats.stackexchange.com/questions/6920/…, którego odpowiedzi pokazują, jak zaktualizować model wielokrotnej regresji liniowej. Obecny wątek może pozostać, ponieważ część pytania dotycząca regresji logistycznej jest niezależna od zainteresowania. W rzeczywistości nawet część logistyczna została zduplikowana na stronie stats.stackexchange.com/questions/59174/… .
whuber
1
Myślałem, że ta odpowiedź będzie przydatna, biorąc pod uwagę tekst referencyjny podany w pytaniu. Dziękuję za link. Jednak nie tego szukam. Mój przypadek użycia jest najwyraźniej szczególny.
chmike
3
Uważam, że może być przydatny i jest wyjątkowy w oferowaniu działającego kodu.
whuber
Czy mogę zapytać, dlaczego pozwalasz dx * dy razy (n-1) / n?
FavorMylikes,
Czy możesz poprawić kod, aby obliczyć wartość p?
Nathan
12

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)

tdc
źródło
Jeśli chodzi o regresję logistyczną, myślę, że jesteś niepotrzebnie pesymistyczny. Regresja logistyczna jest równoważna z obliczaniem prawdopodobieństw klasy tylnej dla problemu dwóch klas z każdą klasą rozkładu Gaussa, przy użyciu różnych środków i wspólnej kowariancji. MLE dla kowariancji jest tylko ważoną sumą kowariancji dla poszczególnych klas, więc wystarczające statystyki to tylko liczba, suma i suma kwadratów dla poszczególnych klas. Oczywiście łatwo jest przeprowadzić dokładną aktualizację przy użyciu wystarczających statystyk.
Robert Dodier
3
@RobertDodier Opisałeś liniową analizę dyskryminacyjną, a nie regresję logistyczną. Ostatni akapit części wprowadzającej tutaj wyjaśnia związek.
ahfoss
@ahfoss Nawet jeśli dane dla poszczególnych klas nie są normalnie dystrybuowane, nadal można zbudować model równoważny regresji logistycznej za pomocą kowariancji dla poszczególnych klas.
Robert Dodier
1
@RobertDodier Jaki jest równoważny model? Wydaje się, że sugerujesz, że istnieje oczywiste rozwiązanie zasadniczo trudnego problemu. Twoje rozwiązanie jest albo bardziej genialne niż myślisz, albo znacznie mniej.
ahfoss,
11

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

Glen_b - Przywróć Monikę
źródło
Zgadzam się z pomysłem utrzymywania wystarczających statystyk (jeśli istnieją dla problemu), ale czy obecność wystarczających statystyk nie powoduje, że inne rzeczy są niepotrzebne? Jeśli masz wystarczające statystyki, możesz obliczyć zaktualizowane parametry dokładnie tak, jakbyś używał całego zestawu danych. Nie ma potrzeby uwzględniania bieżących parametrów ani eksperymentowania z metodami optymalizacji.
Robert Dodier
2
Ważne jest, aby pamiętać, że posiadanie wystarczających statystyk nie oznacza, że ​​masz rozwiązanie równań.
Glen_b
8

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ń.

Alexandre Passos
źródło
6

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.


źródło
5

yt=βtxt+εt,βt=βt1+ηt
βt=βt1

yt=logit(βtxt+εt),βt=βt1+ηt
Kochede
źródło
2

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

Chris
źródło