Stochastyczny spadek gradientu - Stochastic gradient descent

Stochastyczny metoda gradientu prostego (w skrócie SGD ) jest iteracyjna metoda do optymalizacji jest konkretna funkcja odpowiednimi gładkość właściwości (np różniczkowalną lub subdifferentiable ). Może on być traktowany jako stochastyczny zbliżenia do największego spadku optymalizacji, ponieważ zastępuje rzeczywisty nachylenia (obliczoną na podstawie całego zestawu danych ) przez jej szacunkowej (obliczony na losowo wybranej podgrupie danych). Zmniejsza to obciążenie obliczeniowe, szczególnie w problemach optymalizacji wysokowymiarowej, osiągając szybsze iteracje w handlu przy niższym współczynniku zbieżności.

Podczas gdy podstawową ideę aproksymacji stochastycznej można wywieść z algorytmu Robbinsa-Monro z lat 50., stochastyczne opadanie gradientowe stało się ważną metodą optymalizacji w uczeniu maszynowym .

Tło

Zarówno statystyczny szacunek i uczenie maszynowe rozważyć problem minimalizacji jest konkretna funkcja , która ma postać sumy:

${\ Displaystyle Q (w) = {\ Frac {1} {n}} \ suma _ {i = 1} ^ {n} Q_ {i} (w)}$

gdzie należy oszacować parametr minimalizujący . Każda funkcja summand jest zazwyczaj powiązana z -tą obserwacją w zbiorze danych (używaną do uczenia). ${\ Displaystyle w}$${\ Displaystyle Q (w)}$${\displaystyle Q_{i}}$${\displaystyle i}$

W statystyce klasycznej problemy minimalizacji sumy pojawiają się w najmniejszych kwadratach iw estymacji maksymalnego prawdopodobieństwa (dla niezależnych obserwacji). Ogólna klasa estymatorów, które powstają jako minimalizatory sum, nazywa się M-estymatorami . Jednak w statystykach od dawna wiadomo, że wymaganie nawet lokalnej minimalizacji jest zbyt restrykcyjne w przypadku niektórych problemów związanych z szacowaniem maksymalnego prawdopodobieństwa. W związku z tym, współczesne teoretycy statystyczne często uważają nieruchomych punktów z funkcji prawdopodobieństwa (lub jego pochodnej zera, a z funkcji punktowej i innych równań szacowania ).

Problem minimalizacji sumy pojawia się również w przypadku minimalizacji ryzyka empirycznego . W tym przypadku jest to wartość funkcji straty w -tym przykładzie i jest to ryzyko empiryczne. ${\ Displaystyle Q_ {i} (w)}$${\displaystyle i}$${\ Displaystyle Q (w)}$

W przypadku użycia do zminimalizowania powyższej funkcji, standardowa (lub „wsadowa”) metoda gradientu obniżania wykonałaby następujące iteracje:

${\ Displaystyle w: = w- \ eta \ nabla Q (w) = w- {\ Frac {\ eta} {n}} \ suma _ {i = 1} ^ {n} \ nabla Q_ {i} (w ),}$

gdzie jest rozmiarem kroku (czasami nazywanym szybkością uczenia się w uczeniu maszynowym). ${\displaystyle \eta}$

W wielu przypadkach funkcje summand mają prostą postać, która umożliwia niedrogie oceny funkcji sumy i gradientu sumy. Na przykład w statystyce jednoparametrowe rodziny wykładnicze umożliwiają ekonomiczne oceny funkcji i oceny gradientów.

Jednak w innych przypadkach ocena gradientu sumy może wymagać kosztownych ocen gradientów ze wszystkich funkcji summand. Gdy zbiór uczący jest ogromny i nie istnieją proste formuły, obliczanie sum gradientów staje się bardzo kosztowne, ponieważ obliczanie gradientu wymaga oceny wszystkich gradientów funkcji summand. Aby zaoszczędzić na kosztach obliczeniowych w każdej iteracji, stochastyczne opadanie gradientowe na każdym kroku pobiera próbkę podzbioru funkcji summand. Jest to bardzo skuteczne w przypadku problemów z uczeniem maszynowym na dużą skalę.

Metoda iteracyjna

W stochastycznym (lub „on-line”) spadku gradientu, prawdziwy gradient jest aproksymowany przez gradient na jednym przykładzie: ${\ Displaystyle Q (w)}$

${\ Displaystyle w: = w- \ eta \ nabla Q_ {i} (w).}$

Gdy algorytm przegląda zbiór uczący, wykonuje powyższą aktualizację dla każdego przykładu uczącego. W zestawie uczącym można wykonać kilka przejść, aż algorytm się zbiegnie. Jeśli tak się stanie, dane mogą być przetasowane dla każdego przebiegu, aby zapobiec cyklom. Typowe implementacje mogą wykorzystywać adaptacyjną szybkość uczenia się , aby algorytm był zbieżny.

W pseudokodzie stochastyczne opadanie gradientu można przedstawić w następujący sposób:

Kompromisem między obliczeniem prawdziwego gradientu a gradientem w jednym przykładzie jest obliczenie gradientu względem więcej niż jednego przykładu uczącego (nazywanego „mini-partią”) na każdym kroku. Może to działać znacznie lepiej niż opisane „prawdziwe” stochastyczne zejście gradientowe, ponieważ kod może korzystać z bibliotek wektoryzacji zamiast obliczać każdy krok osobno. Może to również skutkować płynniejszą zbieżnością, ponieważ gradient obliczany na każdym kroku jest uśredniany na podstawie większej liczby przykładów treningowych.

Zbieżność stochastycznego spadku gradientu została przeanalizowana przy użyciu teorii minimalizacji wypukłej i aproksymacji stochastycznej . Krótko mówiąc, gdy tempo uczenia się zmniejsza się z odpowiednią szybkością i przy stosunkowo łagodnych założeniach, stochastyczne zniżanie gradientu prawie na pewno zbiega się do globalnego minimum, gdy funkcja celu jest wypukła lub pseudowypukła , a w przeciwnym razie prawie na pewno zbiega się do lokalnego minimum. Jest to w rzeczywistości konsekwencja twierdzenia Robbinsa-Siegmunda . ${\displaystyle \eta}$

Przykład

Załóżmy, że chcemy dopasować linię prostą do zbioru treningowego z obserwacjami i odpowiadającymi im estymowanymi odpowiedziami przy użyciu metody najmniejszych kwadratów . Funkcja celu do zminimalizowania to: ${\displaystyle {\kapelusz {y}}=\!w_{1}+w_{2}x}$${\displaystyle (x_{1},x_{2},\ldots,x_{n})}$${\ Displaystyle ({\ kapelusz {y_ {1}}}, {\ kapelusz {y_ {2}}}, \ ldots, {\ kapelusz {y_ {n}}})}$

${\ Displaystyle Q (w) = \ suma _ {i = 1} ^ {n} Q_ {i} (w) = \ suma _ {i = 1} ^ {n} \ lewo ({\ kapelusz {y_ {i }}}-y_{i}\right)^{2}=\sum _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\ dobrze)^{2}.}$

Ostatnia linia w powyższym pseudokodzie dla tego konkretnego problemu będzie wyglądać tak:

${\displaystyle {\zaczynać{bmatrix}w_{1}\\w_{2}\koniec{bmatrix}}:={\rozpocząć{bmatrix}w_{1}\\w_{2}\koniec {bmatrix}}- \eta {\begin{bmatrix}{\frac {\częściowy }{\częściowy w_{1}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\\ {\frac {\częściowy }{\częściowy w_{2}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\end{bmatrix}}={\begin {bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}2(w_{1}+w_{2}x_{i}-y_{i})\ \2x_{i}(w_{1}+w_{2}x_{i}-y_{i})\end{bmatrix}}.}$

Należy zauważyć, że w każdej iteracji (zwanej również aktualizacją) tylko gradient oceniany jest w jednym punkcie zamiast oceniania w zestawie wszystkich próbek. ${\displaystyle x_{i}}$

Kluczowa różnica w porównaniu ze standardowym (wsadowym) gradientem spadku polega na tym, że do obliczenia kroku jest używany tylko jeden fragment danych z zestawu danych, a fragment danych jest wybierany losowo na każdym kroku.

Wybitne aplikacje

Stochastyczne opadanie gradientu to popularny algorytm uczenia szerokiej gamy modeli w uczeniu maszynowym , w tym (liniowych) maszyn wektorów pomocniczych , regresji logistycznej (patrz np. Vowpal Wabbit ) i modeli graficznych . W połączeniu z algorytmem wstecznej propagacji błędów jest to de facto standardowy algorytm uczenia sztucznych sieci neuronowych . Jego użycie zostało również zgłoszone w społeczności Geofizyki , szczególnie w zastosowaniach Full Waveform Inversion (FWI).

Stochastyczne zejście gradientowe konkuruje z szeroko stosowanym algorytmem L-BFGS . Stochastyczne zejście gradientowe jest używane od co najmniej 1960 roku do trenowania modeli regresji liniowej , pierwotnie pod nazwą ADALINE .

Innym algorytmem stochastycznego spadku gradientu jest adaptacyjny filtr najmniejszych kwadratów (LMS) .

Rozszerzenia i warianty

Zaproponowano i zastosowano wiele ulepszeń podstawowego algorytmu stochastycznego spadku gradientu. W szczególności w uczeniu maszynowym za problematyczną uznano konieczność ustalenia szybkości uczenia się (wielkości kroku). Ustawienie tego parametru zbyt wysoko może spowodować rozbieżność algorytmu; ustawienie zbyt nisko powoduje powolne zbieżność. Koncepcyjnie proste przedłużenie stochastycznego gradientu pochodzenia sprawia, że szybkość uczenia się malejącą funkcją Ti _t od liczby iteracji t , dając rozkład szybkości uczenia się , tak, że pierwsze iteracje powodują duże zmiany w parametrach, a później z nich zrobić tylko dostrajania . Takie harmonogramy są znane od czasu prac MacQueena nad grupowaniem k- średnich . Praktyczne wskazówki dotyczące wyboru wielkości kroku w kilku wariantach SGD udziela Spall.

Aktualizacje niejawne (ISGD)

Jak wspomniano wcześniej, klasyczny stochastyczny gradient gradientowy jest ogólnie wrażliwy na szybkość uczenia się η . Szybka konwergencja wymaga dużych szybkości uczenia się, ale może to powodować niestabilność liczbową. Problem można w dużej mierze rozwiązać, rozważając niejawne aktualizacje, w których gradient stochastyczny jest oceniany w następnej iteracji, a nie w bieżącej:

${\ Displaystyle w ^ {\ rm {nowy}}: = w ^ {\ rm {stary}} - \ eta \ nabla Q_ {i} (w ^ {\ rm {nowy}}).}$

To równanie jest niejawne, ponieważ pojawia się po obu stronach równania. Jest to stochastyczna forma metody gradientu proksymalnego, ponieważ aktualizację można również zapisać jako: ${\ Displaystyle w ^ {\ rm {nowy}}}$

${\ Displaystyle w ^ {\ rm {nowy}}: = \ arg \ min _ {w} \ {Q_ {i} (w) + {\ Frac {1} {2 \ eta}} | | ww ^ {\ rm {stary}}||^{2}\}.}$

Jako przykład rozważmy najmniejsze kwadraty z cechami i obserwacjami . Chcemy rozwiązać: ${\ Displaystyle x_ {1}, \ ldots, x_ {n} \ w \ mathbb {R} ^ {p}}$${\ Displaystyle y_ {1}, \ ldots, y_ {n} \ w \ mathbb {R}}$

${\ Displaystyle \ min _ {w} \ suma _ {j = 1} ^ {n} (y_ {j} -x_ {j} 'w) ^ {2},}$

gdzie wskazuje produkt wewnętrzny. Zwróć uwagę, że pierwszy element zawierający przecięcie może zawierać „1”. Klasyczny stochastyczny spadek gradientu przebiega następująco: ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}}$${\displaystyle x}$

${\ Displaystyle w ^ {\ rm {nowy}} = w ^ {\ rm {stary}} + \ eta (y_ {i} -x_ {i} 'w ^ {\ rm {stary}}) x_ {i} }$

gdzie pobierana jest jednolita próbka między 1 a . Chociaż teoretyczna zbieżność tej procedury zachodzi przy stosunkowo łagodnych założeniach, w praktyce procedura może być dość niestabilna. W szczególności, gdy jest błędnie określony tak, że ma duże bezwzględne wartości własne z dużym prawdopodobieństwem, procedura może różnić się liczbowo w ciągu kilku iteracji. Natomiast niejawny stochastyczny spadek gradientu (skrócony jako ISGD) można rozwiązać w formie zamkniętej jako: ${\displaystyle i}$${\ Displaystyle n}$${\displaystyle \eta}$${\ Displaystyle I- \ eta x_ {i} x_ {i}'}$

${\ Displaystyle w ^ {\ rm {nowy}} = w ^ {\ rm {stary}} + {\ Frac {\ eta {1 + \ eta | | x_ {i} | | ^ {2}}} ( y_{i}-x_{i}'w^{\rm {stary}})x_{i}.}$

Ta procedura pozostanie numerycznie stabilna praktycznie dla wszystkich, ponieważ szybkość uczenia się jest teraz znormalizowana. Takie porównanie klasycznego i niejawnego gradientu stochastycznego w zagadnieniu najmniejszych kwadratów jest bardzo podobne do porównania między najmniejszymi średnimi kwadratami (LMS) i znormalizowanym filtrem najmniejszych średnich kwadratów (NLMS) . ${\displaystyle \eta}$

Mimo że rozwiązanie w formie zamkniętej dla ISGD jest możliwe tylko w najmniejszych kwadratach, procedurę można skutecznie wdrożyć w wielu różnych modelach. Załóżmy konkretnie, że zależy to tylko od kombinacji liniowej z cechami , abyśmy mogli napisać , gdzie może zależeć również od , ale nie od z wyjątkiem przez . Zasada najmniejszych kwadratów jest zgodna z tą zasadą, podobnie jak regresja logistyczna i większość uogólnionych modeli liniowych . Na przykład w najmniejszych kwadratach , aw regresji logistycznej , gdzie jest funkcją logistyczną . W regresji Poissona , i tak dalej. ${\ Displaystyle Q_ {i} (w)}$${\ Displaystyle w}$${\displaystyle x_{i}}$${\ Displaystyle \ nabla _ {w} Q_ {i} (w) = -q (x_ {i} 'w) x_ {i}}$${\ Displaystyle q () \ w \ mathbb {R}}$${\displaystyle x_{i},y_{i}}$${\ Displaystyle w}$${\displaystyle x_{i}'w}$${\ Displaystyle q (x_ {i} 'w) = y_ {i} -x_ {i} 'w}$${\ Displaystyle q (x_ {i} 'w) = y_ {i} - S (x_ {i} 'w)}$${\ Displaystyle S (u) = e ^ {u} / (1 + e ^ {u})}$${\ Displaystyle q (x_ {i} 'w) = y_ {i} -e ^ {x_ {i} 'w}}$

W takich ustawieniach ISGD jest po prostu zaimplementowany w następujący sposób. Niech , gdzie jest skalar. Wtedy ISGD jest równoważne: ${\ Displaystyle f (\ xi) = \ eta q (x_ {i} 'w ^ {stary} + \ xi | | x_ {i} | | ^ {2})}$${\displaystyle \xi}$

${\ Displaystyle w ^ {\ rm {nowy}} = w ^ {\ rm {stary}} + \ xi ^ {\ ast} x_ {i} ~ {\ tekst {gdzie}} ~ \ xi ^ {\ ast }=f(\xi ^{\ast }).}$

Współczynnik skalowania można znaleźć metodą bisekcji, ponieważ w większości zwykłych modeli, takich jak wspomniane wcześniej uogólnione modele liniowe, funkcja maleje, a zatem granice wyszukiwania wynoszą . ${\ Displaystyle \ xi ^ {\ ast} \ w \ mathbb {R}}$${\displaystyle q()}$${\ Displaystyle \ xi ^ {\ ast}}$${\ Displaystyle [\ min (0, f (0)), \ max (0, f (0))]}$

Pęd

Dalsze propozycje obejmują metodę momentum , która pojawiła się w artykule Rumelharta , Hintona i Williamsa na temat uczenia się wstecznej propagacji błędów. Stochastyczne opadanie gradientu z pędem zapamiętuje aktualizację Δ w przy każdej iteracji i określa następną aktualizację jako liniową kombinację gradientu i poprzedniej aktualizacji:

${\ Displaystyle \ Delta W: = \ alfa \ Delta W \ eta \ nabla Q_ {i} (w)}$

${\displaystyle w:=w+\delta w}$

co prowadzi do:

${\ Displaystyle w: = w- \ eta \ nabla Q_ {i} (w) + \ alfa \ Delta w}$

gdzie parametr, który minimalizuje ma być oszacowany , jest rozmiarem kroku (czasami nazywanym szybkością uczenia się w uczeniu maszynowym) i jest wykładniczym współczynnikiem zaniku między 0 a 1, który określa względny udział bieżącego gradientu i wcześniejszych gradientów w zmianie wagi . ${\ Displaystyle w}$${\ Displaystyle Q (w)}$${\displaystyle \eta}$${\ Displaystyle \ alfa}$

Nazwa pęd wywodzi się z analogii do pędu w fizyce: wektor wagowy , pomyślany jako cząstka podróżująca przez przestrzeń parametrów, podlega przyspieszeniu z gradientu ubytku (" siła "). W przeciwieństwie do klasycznego stochastycznego opadania gradientowego, ma tendencję do poruszania się w tym samym kierunku, zapobiegając oscylacjom. Momentum jest z powodzeniem wykorzystywane przez informatyków w treningu sztucznych sieci neuronowych od kilkudziesięciu lat. Metoda pędu jest ściśle związana z niedotłumioną dynamiką Langevina i może być połączona z symulowanym wyżarzaniem . ${\ Displaystyle w}$

Uśrednianie

Uśredniony stochastyczny spadek gradientu , wynaleziony niezależnie przez Rupperta i Polyaka pod koniec lat 80., jest zwykłym stochastycznym spadkiem gradientu, który rejestruje średnią wektora parametrów w czasie. Oznacza to, że aktualizacja jest taka sama jak w przypadku zwykłego stochastycznego spadku gradientu, ale algorytm śledzi również

${\ Displaystyle {\ bar {w}} = {\ Frac {1} {t}} \ suma _ {i = 0} ^ {t-1} w_ {i}}$.

Po zakończeniu optymalizacji ten uśredniony wektor parametrów zajmuje miejsce w .

AdaGrad

AdaGrad (dla adaptacyjnego algorytmu gradientu ) to zmodyfikowany stochastyczny algorytm gradientu gradientu z szybkością uczenia się według parametru , opublikowany po raz pierwszy w 2011 roku. Nieformalnie zwiększa to szybkość uczenia się dla rzadszych parametrów i zmniejsza szybkość uczenia się dla tych, które są mniej rzadkie. Strategia ta często poprawia wydajność zbieżności w porównaniu ze standardowym stochastycznym spadkiem gradientu w warunkach, w których dane są rzadkie, a parametry rzadkie są bardziej pouczające. Przykłady takich zastosowań obejmują przetwarzanie języka naturalnego i rozpoznawanie obrazów. Nadal ma bazową szybkość uczenia η , ale jest ona mnożona przez elementy wektora { G _{j , j} } będącego przekątną macierzy iloczynu zewnętrznego

${\ Displaystyle G = \ suma _ {\ tau =1} ^ {t} g_ {\ tau} g_ {\ tau} ^ {\ mathsf {T}}}$

gdzie , gradient, w iteracji τ . Przekątna jest dana przez ${\ Displaystyle g_ {\ tau} = \ nabla Q_ {i} (w)}$

${\ Displaystyle G_ {j, j} = \ suma _ {\ tau =1} ^ {t} g_ {\ tau, j} ^ {2}}$.

Ten wektor jest aktualizowany po każdej iteracji. Formuła aktualizacji jest teraz

${\ Displaystyle w: = w- \ eta \ \ operatorname {diag} (G) ^ {- {\ Frac {1} {2}}} \ dot g}$

lub napisane jako aktualizacje parametrów,

${\ Displaystyle w_ {j}: = w_ {j} - {\ Frac {\ eta} {\ sqrt {G_ {j, j}}}} g_ {j}.}$

Każdy { G _{( ja , ja )} } powoduje powstanie Współczynnik skalowania szybkości uczenia się, który odnosi się do pojedynczego parametru w _I . Ponieważ mianownik tego czynnika jest ℓ ₂ normą poprzednich pochodnych ekstremalne aktualizacje parametru GET tłumione, natomiast parametry, które się kilka lub małe aktualizacje otrzymują wyższe stawki uczenia się. ${\ Displaystyle {\ sqrt {G_ {i}}} = {\ sqrt {\ suma _ {\ tau =1} ^ {t} g_ {\ tau} ^ {2}}}}$

Chociaż AdaGrad został zaprojektowany z myślą o problemach wypukłych , został z powodzeniem zastosowany do optymalizacji niewypukłej.

RMSPPro

RMSProp ( propagacja średniokwadratowa ) to również metoda, w której szybkość uczenia jest dostosowywana do każdego z parametrów. Pomysł polega na podzieleniu szybkości uczenia się dla danej wagi przez średnią kroczącą wartości ostatnich gradientów dla tej wagi. Tak więc najpierw średnia krocząca jest obliczana jako średnia kwadratowa,

${\ Displaystyle v (w, t): = \ gamma v (w, t-1) + (1-\ gamma ) (\ nabla Q_ {i} (w)) ^ {2}}$

gdzie jest czynnik zapominania. ${\ Displaystyle \ gamma}$

A parametry są aktualizowane jako,

${\ Displaystyle w: = w-{\ Frac {\ eta} {\ sqrt {v (w, t)}}} \ nabla Q_ {i} (w)}$

RMSProp wykazał dobrą adaptację szybkości uczenia się w różnych aplikacjach. RMSProp może być postrzegany jako uogólnienie Rprop i jest zdolny do pracy zarówno z mini partiami, jak i tylko z pełnymi partiami.

Adam

Adam (skrót od Adaptive Moment Estimation) to aktualizacja optymalizatora RMSProp . W tym algorytmie optymalizacji wykorzystywane są średnie bieżące zarówno gradientów, jak i drugich momentów gradientów. Biorąc pod uwagę parametry i funkcję straty , gdzie indeksuje aktualną iterację treningu (indexed at ), aktualizacja parametru Adama jest wyrażona wzorem: ${\ Displaystyle w ^ {(t)}}$${\ Displaystyle L ^ {(t)}}$${\displaystyle t}$${\ Displaystyle 0}$

${\ Displaystyle m_ {w} ^ {(t + 1)} \ leftarrow \ beta _ {1} m_ {w} ^ {(t)} + (1-\ beta _ {1}) \ nabla _ {w} L^{(t)}}$

${\ Displaystyle v_ {w} ^ {(t + 1)} \ leftarrow \ beta _ {2} v_ {w} ^ {(t)} + (1-\ beta _ {2}) (\ nabla _ {w }L^{(t)})^{2}}$

${\ Displaystyle {\ kapelusz {m}} _ {w} = {\ Frac {m_ {w} ^ {(t + 1)}} {1-\ beta _ {1} ^ {t}}}}$

${\ Displaystyle {\ kapelusz {v}} _ {w} = {\ Frac {v_ {w} ^ {(t + 1)}} {1-\ beta _ {2} ^ { t}}}}$

${\ Displaystyle w ^ {(t + 1)} \ leftarrow w ^ {(t)} - ​​\ eta {\ Frac {{\ kapelusz {m}} _ {w}} {{\ sqrt {{\ kapelusz {v }}_{w}}}+\epsilon }}}$

gdzie jest małym skalarem (np. ) używanym do zapobiegania dzieleniu przez 0, a (np. 0,9) i (np. 0,999) są współczynnikami zapominania odpowiednio dla gradientów i drugich momentów gradientów. Kwadratowanie i zakorzenianie kwadratowe odbywa się elementarnie. ${\displaystyle \epsilon}$${\ Displaystyle 10 ^ {-8}}$${\displaystyle \beta_{1}}$${\displaystyle \beta_{2}}$

Wyszukiwanie linii z wycofywaniem

Wyszukiwanie linii z nawrotem to kolejny wariant opadania gradientowego. Wszystkie poniższe pochodzą ze wspomnianego linku. Opiera się na stanie znanym jako stan Armijo-Goldsteina. Obie metody umożliwiają zmianę szybkości uczenia się w każdej iteracji; jednak sposób zmiany jest inny. Wyszukiwanie linii z nawrotem wykorzystuje ewaluację funkcji do sprawdzenia stanu Armijo, iw zasadzie pętla w algorytmie określania szybkości uczenia się może być z góry długa i nieznana. Adaptacyjny SGD nie wymaga pętli przy określaniu szybkości uczenia się. Z drugiej strony, adaptacyjny SGD nie gwarantuje „właściwości zejścia” – którą cieszy wyszukiwanie linii z nawrotem – czyli dla wszystkich n. Jeżeli gradient funkcji kosztu jest globalnie ciągły Lipschitza, ze stałą Lipschitza L, a współczynnik uczenia jest wybrany rzędu 1/L, to standardowa wersja SGD jest szczególnym przypadkiem wyszukiwania linii z nawrotem. ${\ Displaystyle f (x_ {n + 1}) \ leq f (x_ {n})}$

Metody drugiego rzędu

Stochastyczny odpowiednik standardowego (deterministycznego) algorytmu Newtona-Raphsona (metoda „drugiego rzędu”) zapewnia asymptotycznie optymalną lub prawie optymalną formę optymalizacji iteracyjnej w ustawieniu aproksymacji stochastycznej. Metoda wykorzystująca bezpośrednie pomiary heskich macierzy sum w funkcji ryzyka empirycznego została opracowana przez Byrda, Hansena, Nocedala i Singera. Jednak bezpośrednie określenie wymaganych macierzy Hess do optymalizacji może nie być w praktyce możliwe. Praktyczne i teoretycznie rozsądne metody dla wersji drugiego rzędu SGD, które nie wymagają bezpośredniej informacji z Hesji, podają Spall i inni. (Mniej wydajną metodę opartą na skończonych różnicach, zamiast równoczesnych perturbacji, podaje Ruppert.) Te metody niewymagające bezpośredniej informacji hesowskiej są oparte albo na wartościach sum w powyższej empirycznej funkcji ryzyka, albo na wartościach gradientów sum. (tj. wejścia SGD). W szczególności, optymalność drugiego rzędu jest asymptotycznie osiągalna bez bezpośredniego obliczania macierzy heskich sum w empirycznej funkcji ryzyka.

Uwagi

Zobacz też

• Wyszukiwanie linii z wycofywaniem
• Zejście ze współrzędnych – zmienia jedną współrzędną na raz, a nie jeden przykład
• Klasyfikator liniowy
• Uczenie maszynowe online
• Stochastyczna wspinaczka górska

Bibliografia

Dalsza lektura

• Bottou, Léon (2004), "Stochastic Learning" , Zaawansowane wykłady na temat uczenia maszynowego , LNAI, 3176 , Springer, s. 146-168, ISBN 978-3-540-23122-6
• Buduma, Nikhil; Locascio, Nicholas (2017), „Beyond Gradient Descent” , Podstawy głębokiego uczenia: projektowanie algorytmów inteligencji maszyn nowej generacji , O'Reilly
• LeCun, Yann A .; Bottou, Leon; Orr, Genevieve B.; Müller, Klaus-Robert (2012), "Efficient BackProp" , Sieci neuronowe: Tricks of the Trade , Springer, s. 9-48, ISBN 978-3-642-35288-1
• Spall, James C. (2003), Wprowadzenie do wyszukiwania stochastycznego i optymalizacji , Wiley , ISBN 978-0-471-33052-3

Zewnętrzne linki

• Używanie stochastycznego gradientu gradientu w C++, Boost, Ublas do regresji liniowej
• Algorytmy uczenia maszynowego
• „Spadek gradientu, jak uczą się sieci neuronowe” . 3Niebieski1Brązowy . 16 października 2017 – przez YouTube .
• Goh (4 kwietnia 2017). „Dlaczego Momentum naprawdę działa” . Destylować . Artykuł interaktywny wyjaśniający pęd.