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?
Odpowiedzi:
Liniowe współczynniki regresjiy= a x + b są = C O V ( x , y ) / V R ( x ) i b = m e a N ( r ) - ⋅ m wiadomość e o n ( x ) .a = c o v ( x , y) / v a r ( x ) b = m e a n ( y) - a ⋅ m e a n ( x )
Tak więc wszystko, czego naprawdę potrzebujesz, to inkrementalna metoda obliczaniac o v ( x , y) . Na podstawie tej wartości i wariancji x oraz średniej zarówno y jak i x można obliczyć parametry za 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:
Znalazłem to pytanie, szukając równoważnego algorytmu przyrostowo obliczającego regresję wielowymiarową jakoR=(X′X)−1X′Y tak, że XR=Y+ϵ
źródło
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:
Istnieją jednak inne internetowe (lub inkrementalne) metody regresji, na które warto przyjrzeć się, na przykład lokalnie ważona regresja projekcji (LWPR)
źródło
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
źródło
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ń.
źródło
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
źródło
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:
Podglądanie poprzednio opublikowanej odpowiedzi i rozwijanie jej w celu uwzględnienia wykładniczego ruchomego okna:
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
źródło