Uczenie maszynowe online — Online machine learning

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY WYLECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

W informatyce , uczenie maszynowe Internecie jest metodą uczenia maszynowego , w którym dane będzie dostępny w porządku sekwencyjnym i służy do aktualizacji najlepszą prognozą dla danych przyszłych na każdym kroku, w przeciwieństwie do partii naukę technik, które generują najlepszą predyktorem Ucząc na całym zestawie danych treningowych jednocześnie. Nauka online jest powszechną techniką stosowaną w obszarach uczenia maszynowego, w których obliczeniowo niewykonalne jest trenowanie na całym zbiorze danych, co wymaga użycia algorytmów spoza rdzenia . Wykorzystywany jest również w sytuacjach, gdy konieczne jest dynamiczne dostosowywanie się algorytmu do nowych wzorców w danych lub gdy same dane są generowane w funkcji czasu, np . prognoza cen akcji . Algorytmy uczenia się online mogą być podatne na katastrofalne zakłócenia , problem, który można rozwiązać, stosując metody uczenia przyrostowego .

Wstęp

Przy ustalaniu uczenia nadzorowanego , funkcją jest się nauczyć, gdzie jest uważany za przestrzeń wejść i jako przestrzeń wyjść, które przewiduje, że również w instancjach są sporządzone z wspólny rozkład prawdopodobieństwa na . W rzeczywistości uczący się nigdy nie zna prawdziwego podziału na instancje. Zamiast tego uczący się zwykle ma dostęp do zestawu przykładów szkoleniowych . W tym ustawieniu funkcja straty jest podawana jako , tak aby mierzyć różnicę między wartością przewidywaną a wartością rzeczywistą . Idealnym celem jest wybranie funkcji , gdzie jest przestrzenią funkcji zwaną przestrzenią hipotez, tak aby zminimalizować pewne pojęcie całkowitej straty. W zależności od typu modelu (statystyczny lub kontradyktoryjny) można wymyślić różne pojęcia straty, które prowadzą do różnych algorytmów uczenia się. ${\displaystyle f:X\do Y}$${\ Displaystyle X}$${\ Displaystyle Y}$ ${\displaystyle p(x,y)}$${\ Displaystyle X \ razy Y}$${\displaystyle p(x,y)}$${\ styl wyświetlania (x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})}$${\ Displaystyle V: Y \ razy Y \ do \ mathbb {R}}$${\displaystyle V(f(x),y)}$${\displaystyle f(x)}$${\displaystyle y}$${\ Displaystyle f \ w {\ mathcal {H}}}$${\ Displaystyle {\ Mathcal {H}}}$

Statystyczny widok nauki online

W statystycznych modelach uczenia zakłada się , że próba ucząca została wylosowana z rzeczywistego rozkładu, a celem jest zminimalizowanie oczekiwanego „ryzyka” ${\ Displaystyle (x_ {i}, Y_ {i})}$${\displaystyle p(x,y)}$

${\ Displaystyle I [f] = \ mathbb {E} [V (f (x), y)] = \ int V (f (x), y) \ dp (x, y) \ .}$

Powszechnym paradygmatem w tej sytuacji jest szacowanie funkcji poprzez minimalizację ryzyka empirycznego lub uregulowaną minimalizację ryzyka empirycznego (zwykle regularyzacja Tichonowa ). Wybór funkcji straty w tym przypadku daje początek kilku dobrze znanym algorytmom uczenia, takim jak uregulowane najmniejszych kwadratów i maszyny wektorów nośnych . Model czysto online w tej kategorii uczyłby się tylko na podstawie nowych danych wejściowych , bieżącego najlepszego predyktora i pewnych dodatkowych przechowywanych informacji (które zwykle mają wymagania dotyczące pamięci niezależne od rozmiaru danych uczących). W przypadku wielu sformułowań, na przykład nieliniowych metod jądra , prawdziwe uczenie online nie jest możliwe, chociaż forma hybrydowego uczenia online z algorytmami rekurencyjnymi może być stosowana tam, gdzie jest to dozwolone i od wszystkich poprzednich punktów danych . W takim przypadku wymagania dotyczące miejsca nie są już gwarantowane jako stałe, ponieważ wymaga przechowywania wszystkich poprzednich punktów danych, ale obliczenie rozwiązania po dodaniu nowego punktu danych może zająć mniej czasu w porównaniu z technikami uczenia wsadowego. ${\displaystyle {\kapelusz {f}}}$${\ Displaystyle (x_ {t + 1}, y_ {t + 1})}$${\displaystyle f_{t}}$${\displaystyle f_{t+1}}$${\displaystyle f_{t}}$${\displaystyle (x_{1},y_{1}),\ldots,(x_{t},y_{t})}$

Powszechną strategią rozwiązywania powyższych problemów jest uczenie się za pomocą mini-partii, które przetwarzają jednocześnie niewielką partię punktów danych, można to uznać za uczenie pseudo-online dla znacznie mniejszej liczby punktów szkoleniowych. Stosowane są techniki mini-partii z wielokrotnym przekazywaniem danych uczących w celu uzyskania zoptymalizowanych, out-of-core wersji algorytmów uczenia maszynowego, na przykład stochastycznego spadku gradientu . W połączeniu z propagacją wsteczną jest to obecnie de facto metoda uczenia sztucznych sieci neuronowych . ${\displaystyle b\geq 1}$${\displaystyle b}$

Przykład: liniowe najmniejszych kwadratów

Prosty przykład liniowych najmniejszych kwadratów służy do wyjaśnienia różnych pomysłów w nauce online. Idee są na tyle ogólne, że można je zastosować w innych ustawieniach, na przykład z innymi wypukłymi funkcjami straty.

Nauka wsadowa

Rozważ ustawienie nadzorowanego uczenia się jako funkcji liniowej, której należy się nauczyć: ${\displaystyle f}$

${\ Displaystyle f (x_ {j}) = \ langle w, x_ {j} \ rangle = w \ cdot x_ {j}}$

gdzie jest wektorem wejść (punktów danych) i jest liniowym wektorem filtra. Celem jest obliczenie wektora filtru . W tym celu kwadratowa funkcja straty ${\ Displaystyle x_ {j} \ w \ mathbb {R} ^ {d}}$${\ Displaystyle w \ w \ mathbb {R} ^ {d}}$${\ Displaystyle w}$

${\ Displaystyle V (f (x_ {j}), y_ {j}) = (f (x_ {j}) -y_ {j}) ^ {2} = (\ langle w, x_ {j} \ rangle - y_{j})^{2}}$

służy do obliczania wektora, który minimalizuje straty empiryczne ${\ Displaystyle w}$

${\ Displaystyle I_ {n} [w] = \ suma _ {j = 1} ^ {n} V (\ langle w, x_ {j} \ rangle, y_ {j}) = \ suma _ {j = 1} ^{n}(x_{j}^{T}w-y_{j})^{2}}$

gdzie

${\ Displaystyle y_ {j} \ w \ mathbb {R}}$.

Niech będzie macierzą danych i jest wektorem kolumnowym wartości docelowych po przybyciu pierwszych punktów danych. Zakładając, że macierz kowariancji jest odwracalna (w przeciwnym razie preferowane jest postępowanie w podobny sposób z regularyzacją Tichonowa), najlepszym rozwiązaniem problemu liniowego najmniejszych kwadratów jest równanie ${\ Displaystyle X}$${\displaystyle i\razy d}$${\ Displaystyle y \ w \ mathbb {R} ^ {i}}$${\displaystyle i}$${\ Displaystyle \ Sigma _ {i} = X ^ {T} X}$${\ Displaystyle f ^ {*} (x) = \ langle w ^ {*} x \ rangle}$

${\ Displaystyle w ^ {*} = (X ^ {T} X) ^ {-1} X ^ {T} y = \ Sigma _ {i} ^ {-1} \ suma _ {j = 1} ^ { ja}x_{j}y_{j}}$.

Teraz obliczenie macierzy kowariancji zajmuje czas , odwrócenie macierzy zajmuje czas , podczas gdy reszta mnożenia zajmuje czas , co daje całkowity czas . Gdy w zbiorze danych znajduje się całkowita liczba punktów, aby ponownie obliczyć rozwiązanie po przybyciu każdego punktu danych , naiwne podejście będzie miało całkowitą złożoność . Należy pamiętać, że podczas przechowywania macierzy , aktualizowanie jej na każdym etapie wymaga tylko dodania , co zajmuje czas, zmniejszając całkowity czas do , ale z dodatkową przestrzenią do przechowywania . ${\ Displaystyle \ Sigma _ {i} = \ suma _ {j = 1} ^ {i} x_ {j} x_ {j} ^ {T}}$${\ Displaystyle O (id ^ {2})}$${\displaystyle d\razy d}$${\ Displaystyle O (d ^ {3})}$${\ Displaystyle O (d ^ {2})}$${\ Displaystyle O (id ^ {2} + d ^ {3})}$${\ Displaystyle n}$${\displaystyle i=1,\ldots,n}$${\ Displaystyle O (n ^ {2} d ^ {2} + nd ^ {3})}$${\ Displaystyle \ Sigma _ {i}}$${\ Displaystyle x_ {i + 1} x_ {i + 1} ^ {T}}$${\ Displaystyle O (d ^ {2})}$${\ Displaystyle O (nd ^ {2} + nd ^ {3}) = O (nd ^ {3})}$${\ Displaystyle O (d ^ {2})}$${\ Displaystyle \ Sigma _ {i}}$

Nauka online: rekurencyjna metoda najmniejszych kwadratów

Rekurencyjny algorytm najmniejszych kwadratów (RLS) uwzględnia podejście online do problemu najmniejszych kwadratów. Można wykazać, że inicjując i , rozwiązanie liniowego problemu najmniejszych kwadratów podanego w poprzednim podrozdziale można obliczyć za pomocą następującej iteracji: ${\ Displaystyle \ textstyle w_ {0} = 0 \ w \ mathbb {R} ^ {d}}$${\ Displaystyle \ textstyle \ Gamma _ {0} = ja \ w \ mathbb {R} ^ {d \ razy d}}$

${\ Displaystyle \ Gamma _ {i} = \ Gamma _ {i-1} - {\ Frac {\ Gamma _ {i-1} x_ {i} x_ {i} ^ {T} \ Gamma _ {i-1 }}{1+x_{i}^{T}\Gamma _{i-1}x_{i}}}}$

${\ Displaystyle w_ {i} = w_ {i-1} - \ Gamma _ {i} x_ {i} (x_ {i} ^ {T} w_ {i-1} -y_ {i})}$

Powyższy algorytm iteracji można udowodnić za pomocą indukcji na . Dowód również pokazuje, że . Na RLS można spojrzeć również w kontekście filtrów adaptacyjnych (patrz RLS ). ${\displaystyle i}$${\ Displaystyle \ Gamma _ {i} = \ Sigma _ {i} ^ {-1}}$

Złożoność kroków tego algorytmu wynosi , co jest o rząd wielkości szybszą niż odpowiadająca im złożoność uczenia wsadowego. Wymagania dotyczące przechowywania na każdym kroku to przechowywanie matrycy , która jest stała na . W przypadku, gdy nie jest odwracalna, rozważ uregulowaną wersję funkcji straty problemu . Następnie łatwo wykazać, że ten sam algorytm działa z , a iteracje przechodzą do dawania . ${\ Displaystyle n}$${\ Displaystyle O (nd ^ {2})}$${\displaystyle i}$${\ Displaystyle \ Gamma _ {i}}$${\ Displaystyle O (d ^ {2})}$${\ Displaystyle \ Sigma _ {i}}$${\ Displaystyle \ suma _ {j = 1} ^ {n} (x_ {j} ^ {T} w-y_ {j}) ^ {2} + \ lambda | | w | | _ {2} ^ {2 }}$${\ Displaystyle \ Gamma _ {0} = (I + \ Lambda I) ^ {-1}}$${\ Displaystyle \ Gamma _ {i} = (\ Sigma _ {i} + \ lambda I) ^ {-1}}$

Stochastyczne zejście gradientowe

Kiedy to

${\ Displaystyle \ textstyle w_ {i} = w_ {i-1} - \ Gamma _ {i} x_ {i} (x_ {i} ^ {T} w_ {i-1} -y_ {i})}$

jest zastąpiony przez

${\ Displaystyle \ textstyle w_ {i} = w_ {i-1} - \ gamma _ {i} x_ {i} (x_ {i} ^ {T} w_ {i-1} -y_ {i}) = w_ {i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})}$

lub przez , staje się to algorytmem stochastycznego spadku gradientu. W takim przypadku złożoność kroków tego algorytmu zmniejsza się do . Wymagania dotyczące przechowywania na każdym etapie są stałe w . ${\ Displaystyle \ Gamma _ {i} \ w \ mathbb {R} ^ {d \ razy d}}$${\ Displaystyle \ gamma _ {i} \ w \ mathbb {R}}$${\ Displaystyle n}$${\ Displaystyle O (nd)}$${\displaystyle i}$${\ Displaystyle O(d)}$

Jednak wielkość kroków musi być starannie dobrana, aby rozwiązać oczekiwany problem minimalizacji ryzyka, jak opisano powyżej. Wybierając zanikający rozmiar kroku można udowodnić zbieżność średniej iteracji . To ustawienie jest szczególnym przypadkiem optymalizacji stochastycznej , dobrze znanego problemu w optymalizacji. ${\ Displaystyle \ gamma _ {i}}$${\ Displaystyle \ gamma _ {i} \ około {\ Frac {1} {\ sqrt {i}}}}$${\ Displaystyle {\ overline {w}} _ {n} = {\ Frac {1} {n}} \ suma _ {i = 1} ^ {n} w_ {i}}$

Przyrostowy stochastyczny spadek gradientu

W praktyce na danych można wykonać wiele stochastycznych przejść gradientowych (zwanych również cyklami lub epokami). Otrzymany w ten sposób algorytm nazywa się metodą gradientu przyrostowego i odpowiada iteracji

${\ Displaystyle \ textstyle w_ {i} = w_ {i-1} - \ gamma _ {i} \ nabla V (\ langle w_ {i-1}, x_ {t_ {i}} \ rangle, y_ {t_ { i}})}$

Główna różnica w stosunku do metody gradientu stochastycznego polega na tym, że tutaj wybierana jest sekwencja, która decyduje, który punkt treningowy jest odwiedzany w -tym kroku. Taka sekwencja może być stochastyczna lub deterministyczna. Liczba iteracji jest następnie oddzielona od liczby punktów (każdy punkt można rozpatrywać więcej niż raz). Można wykazać, że metoda gradientu przyrostowego zapewnia minimalizację ryzyka empirycznego. Techniki przyrostowe mogą być korzystne przy rozpatrywaniu funkcji celu składających się z sumy wielu terminów, np. błąd empiryczny odpowiadający bardzo dużemu zbiorowi danych. ${\displaystyle t_{i}}$${\displaystyle i}$

Metody jądra

Kernels można wykorzystać do rozszerzenia powyższych algorytmów na modele nieparametryczne (lub modele, w których parametry tworzą przestrzeń nieskończenie wymiarową). Odpowiednia procedura nie będzie już prawdziwie online i zamiast tego będzie obejmować przechowywanie wszystkich punktów danych, ale nadal będzie szybsza niż metoda brute force. Ta dyskusja ogranicza się do przypadku straty kwadratowej, chociaż można ją rozszerzyć na dowolną stratę wypukłą. Za pomocą łatwej indukcji można wykazać, że jeśli jest macierzą danych i jest wyjściem po krokach algorytmu SGD, to ${\ Displaystyle X_ {i}}$${\displaystyle w_{i}}$${\displaystyle i}$

${\ Displaystyle w_ {i} = X_ {i} ^ {T} c_ {i}}$

gdzie i sekwencja spełnia rekurencję: ${\ Displaystyle \ textstyle c_ {i} = ((c_ {i}) _ {1} (c_ {i}) _ {2}, ... (c_ {i}) _ {i}) \ w \mathbb {R} ^{i}}$${\displaystyle c_{i}}$

${\displaystyle c_{0}=0}$

${\ Displaystyle (c_ {i}) _ {j} = (c_ {i-1}) _ {j}, j = 1,2, ..., i-1}$ oraz

${\ Displaystyle (c_ {i}) _ {i} = \ gamma _ {i} {\ duży (} y_ {i} - \ suma _ {j = 1} ^ {i-1} (c_ {i-1) })_{j}\langle x_{j},x_{i}\rangle {\duży )}}$

Zauważ, że tutaj jest tylko standardowe jądro włączone , a predyktor ma postać ${\ Displaystyle \ langle x_ {j}, x_ {i} \ rangle}$${\ Displaystyle \ mathbb {R} ^ {d}}$

${\ Displaystyle f_ {i} (x) = \ langle w_ {i-1} x \ rangle = \ suma _ {j = 1} ^ {i-1} (c_ {i-1}) _ {j} \langle x_{j},x\rangle }$.

Teraz, jeśli zamiast tego zostanie wprowadzone ogólne jądro i niech predyktor będzie ${\ Displaystyle K}$

${\ Displaystyle f_ {i} (x) = \ suma _ {j = 1} ^ {i-1} (c_ {i-1}) _ {j} K (x_ {j}, x)}$

wtedy ten sam dowód pokaże również, że predyktor minimalizujący stratę najmniejszych kwadratów uzyskuje się zmieniając powyższą rekurencję na

${\ Displaystyle (c_ {i}) _ {i} = \ gamma _ {i} {\ duży (} y_ {i} - \ suma _ {j = 1} ^ {i-1} (c_ {i-1) })_{j}K(x_{j},x_{i}){\Duży )}}$

Powyższe wyrażenie wymaga przechowywania wszystkich danych do aktualizacji . Całkowita złożoność czasowa dla rekurencji podczas oceny dla -tego punktu danych wynosi , gdzie jest kosztem oceny jądra na pojedynczej parze punktów. Zatem użycie jądra umożliwiło przejście od skończenie wymiarowej przestrzeni parametrów do możliwie nieskończenie wymiarowej cechy reprezentowanej przez jądro poprzez wykonanie rekurencji w przestrzeni parametrów , której wymiar jest taki sam jak rozmiar zbioru danych treningowych . Generalnie jest to konsekwencja twierdzenia o reprezentatorze . ${\displaystyle c_{i}}$${\ Displaystyle n}$${\ Displaystyle O (n ^ {2} dk)}$${\displaystyle k}$${\ Displaystyle \ textstyle w_ {i} \ w \ mathbb {R} ^ {d}}$${\ Displaystyle K}$${\ Displaystyle \ textstyle C_ {i} \ w \ mathbb {R} ^ {i}}$

Optymalizacja wypukła online

Optymalizacja wypukła online (OCO) to ogólne ramy podejmowania decyzji, które wykorzystują optymalizację wypukłą, aby umożliwić wydajne algorytmy. Struktura polega na powtarzaniu gry w następujący sposób:

Do ${\displaystyle t=1,2,...,T}$

• Uczeń otrzymuje dane wejściowe ${\displaystyle x_{t}}$
• Wyjścia ucznia ze stałego zestawu wypukłego${\displaystyle w_{t}}$${\displaystyle S}$
• Natura odsyła z powrotem wypukłą funkcję straty .${\ Displaystyle v_ {t}: S \ rightarrow \ mathbb {R}}$
• Uczeń ponosi stratę i aktualizuje swój model${\ Displaystyle v_ {t} (w_ {t})}$

Celem jest zminimalizowanie żalu , czyli różnicy między skumulowaną stratą a utratą najlepszego stałego punktu z perspektywy czasu. Jako przykład rozważmy przypadek regresji liniowej metodą najmniejszych kwadratów online. Tutaj wektory wag pochodzą ze zbioru wypukłego , a natura odsyła wypukłą funkcję utraty . Zwróć uwagę, że jest to niejawnie wysyłane z . ${\ Displaystyle u \ w S}$${\ Displaystyle S = \ mathbb {R} ^ {d}}$${\ Displaystyle v_ {t} (w) = (\ langle w, x_ {t} \ rangle -y_ {t}) ^ {2}}$${\displaystyle y_{t}}$${\displaystyle v_{t}}$

Niektóre problemy z prognozowaniem online nie mieszczą się jednak w ramach OCO. Na przykład w klasyfikacji online domena predykcji i funkcje straty nie są wypukłe. W takich scenariuszach stosuje się dwie proste techniki wypukłości: randomizację i zastępcze funkcje straty.

Niektóre proste algorytmy optymalizacji wypukłej online to:

Podążaj za liderem (FTL)

Najprostszą zasadą uczenia się do wypróbowania jest wybranie (na obecnym etapie) hipotezy, która ma najmniejszą stratę we wszystkich poprzednich rundach. Ten algorytm nazywa się Podążaj za liderem i jest po prostu podawany przez: ${\displaystyle t}$

${\ Displaystyle w_ {t} = \ operatorname {arg \, min} _ {w \ w S} \ suma _ {i = 1} ^ {t-1} v_ {i} (w)}$

Metodę tę można zatem uznać za algorytm zachłanny . W przypadku optymalizacji kwadratowej online (gdzie funkcją straty jest ) można wykazać granicę żalu, która rośnie jako . Jednak podobnych ograniczeń nie można uzyskać dla algorytmu FTL dla innych ważnych rodzin modeli, takich jak optymalizacja liniowa online. W tym celu modyfikuje się FTL, dodając regularyzację. ${\ Displaystyle v_ {t} (w) = | | w-x_ {t} | | _ {2} ^ {2}}$${\ Displaystyle \ log (T)}$

Podążaj za regularyzowanym liderem (FTRL)

Jest to naturalna modyfikacja FTL, która służy do stabilizacji rozwiązań FTL i uzyskania lepszych granic żalu. Funkcja regularyzacji jest wybierana i uczenie odbywa się w rundzie t w następujący sposób: ${\displaystyle R:S\rightarrow \mathbb {R}}$

${\ Displaystyle w_ {t} = \ operatorname {arg \, min} _ {w \ w S} \ suma _ {i = 1} ^ {t-1} v_ {i} (w) + R (w)}$

Jako szczególny przykład rozważmy przypadek optymalizacji liniowej online, tj. gdzie natura odsyła funkcje strat postaci . Niech też . Załóżmy, że funkcja regularyzacji jest wybrana dla pewnej liczby dodatniej . Wtedy można pokazać, że żal minimalizujący iterację staje się ${\ Displaystyle v_ {t} (w) = \ langle w, z_ {t} \ rangle}$${\ Displaystyle S = \ mathbb {R} ^ {d}}$${\ Displaystyle R (w) = {\ Frac {1} {2 \ eta}} | | w | | _ {2} ^ {2}}$${\displaystyle \eta}$

${\ Displaystyle w_ {t + 1} = - \ eta \ suma _ {i = 1} ^ {t} z_ {i} = w_ {t} - \ eta z_ {t}}$

Zauważ, że można to przepisać jako , co wygląda dokładnie tak, jak gradient online. ${\ Displaystyle w_ {t + 1} = w_ {t} - \ eta \ nabla v_ {t} (w_ {t})}$

Jeśli S jest zamiast tego jakąś wypukłą podprzestrzenią , S musiałby być rzutowany na, prowadząc do zmodyfikowanej reguły aktualizacji ${\ Displaystyle \ mathbb {R} ^ {d}}$

${\ Displaystyle w_ {t + 1} = \ pi _ {S} (- \ eta \ suma _ {i = 1} ^ {t} z_ {i}) = \ pi _ {S} (\ eta \ teta _ {t+1})}$

Algorytm ten jest znany jako projekcja leniwa, ponieważ wektor akumuluje gradienty. Jest również znany jako algorytm podwójnego uśredniania Niestierowa. W tym scenariuszu liniowych funkcji straty i kwadratowej regularyzacji żal jest ograniczony przez , a zatem średni żal osiąga wartość 0 zgodnie z potrzebami. ${\displaystyle \theta_{t+1}}$${\ Displaystyle O ({\ sqrt {T}})}$

Online subgradient down (OSD)

Powyższe okazało się żalem związanym z liniowymi funkcjami strat . Aby uogólnić algorytm na dowolną wypukłą funkcję straty, podgradient z jest używany jako przybliżenie liniowe do near , co prowadzi do internetowego algorytmu opadania podgradientu: ${\ Displaystyle v_ {t} (w) = \ langle w, z_ {t} \ rangle}$ ${\ Displaystyle \ częściowe v_ {t} (w_ {t})}$${\displaystyle v_{t}}$${\displaystyle v_{t}}$${\displaystyle w_{t}}$

Zainicjuj parametr ${\displaystyle \eta,w_{1}=0}$

Do ${\displaystyle t=1,2,...,T}$

• Przewiduj używając , otrzymuj od natury.${\displaystyle w_{t}}$${\displaystyle f_{t}}$
• Wybierać ${\ Displaystyle Z_ {t} \ w \ częściowy v_ {t} (w_ {t})}$
• Jeśli , zaktualizuj jako${\ Displaystyle S = \ mathbb {R} ^ {d}}$${\ Displaystyle w_ {t + 1} = w_ {t} - \ eta z_ {t}}$
• Jeśli , rzutuj skumulowane gradienty na ie${\ Displaystyle S \ podzbiór \ mathbb {R} ^ {d}}$${\displaystyle S}$${\ Displaystyle w_ {t + 1} = \ Pi _ {S} (\eta \ theta _ {t + 1}), \ theta _ {t + 1} = \ theta _ {t} + z_ {t}}$

Można użyć algorytmu OSD, aby wyznaczyć granice żalu dla wersji online SVM do klasyfikacji, które wykorzystują utratę zawiasów${\ Displaystyle O ({\ sqrt {T}})}$${\ Displaystyle v_ {t} (w) = \ max \ {0,1-y_ {t} (w \ cdot x_ {t}) \}}$

Inne algorytmy

Algorytmy FTRL uregulowane kwadratowo prowadzą do leniwie rzutowanych algorytmów gradientowych, jak opisano powyżej. Aby użyć powyższego do dowolnych funkcji wypukłych i regulatorów, używa się funkcji lustra online. Optymalną regularyzację z perspektywy czasu można wyprowadzić dla liniowych funkcji straty, co prowadzi do algorytmu AdaGrad . Dla regularyzacji euklidesowej można wykazać granicę żalu , która może być dalej poprawiona do funkcji straty silnie wypukłej i ex-wklęsłej. ${\ Displaystyle O ({\ sqrt {T}})}$${\ Displaystyle O (\ log T)}$

Ciągła nauka

Ciągłe uczenie się oznacza ciągłe doskonalenie wyuczonego modelu poprzez przetwarzanie ciągłych strumieni informacji. Możliwości ciągłego uczenia się są niezbędne dla systemów oprogramowania i autonomicznych agentów współdziałających w stale zmieniającym się świecie rzeczywistym. Jednak ciągłe uczenie się jest wyzwaniem dla uczenia maszynowego i modeli sieci neuronowych, ponieważ ciągłe pozyskiwanie przyrostowo dostępnych informacji z niestacjonarnych dystrybucji danych zazwyczaj prowadzi do katastrofalnego zapominania .

Interpretacje nauki online

Paradygmat uczenia się online ma różne interpretacje w zależności od wyboru modelu uczenia się, z których każdy ma inne implikacje dotyczące predykcyjnej jakości sekwencji funkcji . W tej dyskusji wykorzystano prototypowy algorytm stochastycznego spadku gradientu. Jak wspomniano powyżej, jego rekurencja jest podana przez ${\displaystyle f_{1},f_{2},\ldots,f_{n}}$

${\ Displaystyle \ textstyle w_ {t} = w_ {t-1} - \ gamma _ {t} \ nabla V (\ langle w_ {t-1}, x_ {t} \ rangle, y_ {t})}$

Pierwsza interpretacja uwzględnia metodę stochastycznego spadku gradientu w zastosowaniu do problemu minimalizacji oczekiwanego ryzyka określonego powyżej. Rzeczywiście, w przypadku nieskończonego strumienia danych, ponieważ zakłada się , że przykłady są wyciągane iid z rozkładu , ciąg gradientów w powyższej iteracji jest iid próbką stochastycznych oszacowań gradientu oczekiwanego ryzyka, a zatem można zastosować wyniki złożoności dla metody stochastycznego spadku gradientu do ograniczenia odchylenia , gdzie jest minimalizatorem . Ta interpretacja obowiązuje również w przypadku skończonego zbioru uczącego; chociaż przy wielokrotnych przejściach przez dane gradienty nie są już niezależne, nadal można uzyskać wyniki złożoności w szczególnych przypadkach. ${\ Displaystyle I [w]}$${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\ldots}$${\displaystyle p(x,y)}$${\displaystyle V(\cdot,\cdot)}$${\ Displaystyle I [w]}$${\ Displaystyle I [w_ {t}]-ja [w ^ {\ ast}]}$${\ Displaystyle w ^ {\ ast}}$${\ Displaystyle I [w]}$

Druga interpretacja dotyczy przypadku skończonego zbioru uczącego i traktuje algorytm SGD jako przykład metody incremental gradient descent. W tym przypadku zamiast tego przyjrzymy się ryzyku empirycznemu:

${\ Displaystyle I_ {n} [w] = {\ Frac {1} {n}} \ suma _ {i = 1} ^ {n} V (\ langle w, x_ {i} \ rangle, y_ {i} )\ .}$

Ponieważ gradienty w iteracjach incremental gradient descent są również stochastycznymi oszacowaniami gradientu , interpretacja ta jest również związana z metodą stochastic gradient descent, ale stosowana w celu zminimalizowania ryzyka empirycznego w przeciwieństwie do ryzyka oczekiwanego. Ponieważ ta interpretacja dotyczy ryzyka empirycznego, a nie oczekiwanego, wielokrotne przechodzenie przez dane jest łatwo dozwolone i faktycznie prowadzi do ściślejszego ograniczenia odchyleń , gdzie jest minimalizacją . ${\displaystyle V(\cdot,\cdot)}$${\ Displaystyle I_ {n} [w]}$${\ Displaystyle I_ {n} [w_ {t}]-I_ {n} [w_ {n} ^ {\ ast}]}$${\ Displaystyle w_ {n} ^ {\ ast}}$${\ Displaystyle I_ {n} [w]}$

Realizacje

• Vowpal Wabbit : Szybki, out-of-core system uczenia online typu open source, który wyróżnia się obsługą wielu redukcji uczenia maszynowego, ważenia ważności oraz wyboru różnych funkcji utraty i algorytmów optymalizacji. Wykorzystuje sztuczkę haszującą do ograniczania rozmiaru zestawu funkcji niezależnie od ilości danych treningowych.
• scikit-learn : Zapewnia out-of-core implementacje algorytmów dla
  • Klasyfikacja: Perceptron , SGD klasyfikator , Naiwny klasyfikator Bayesa .
  • Regresja: regresor SGD, pasywny regresor agresywny.
  • Klastrowanie: mini-partia k-średnich .
  • Wyodrębnianie funkcji: nauka słownika mini-partii , przyrostowe PCA .

Zobacz też

Paradygmaty uczenia się

• Uczenie przyrostowe
• Leniwa nauka
• Nauka offline , odwrotny model
• Nauka wzmacniania
• Nadzorowana nauka

Ogólne algorytmy

• Algorytm online
• Optymalizacja online
• Algorytm przesyłania strumieniowego
• Stochastyczne zejście gradientowe

Modele uczenia się

• Adaptacyjna teoria rezonansu
• Hierarchiczna pamięć czasowa
• algorytm k-najbliższego sąsiada
• Nauka kwantyzacji wektorowej
• Perceptron

Bibliografia

Linki zewnętrzne

• http://onlineprediction.net/ , Wiki do prognozowania on-line.
• 6.883: Metody online w uczeniu maszynowym: teoria i aplikacje. Aleksandra Rachlina. MIT