Stochastyczny spadek gradientu

Stochastyczny spadek gradientu (często w skrócie SGD ) to iteracyjna metoda optymalizacji funkcji celu z odpowiednimi właściwościami gładkości (np. różniczkowalna lub podróżniczkowalna ). Można to uznać za stochastyczne przybliżenie optymalizacji zejścia gradientu , ponieważ zastępuje rzeczywisty gradient (obliczony z całego zbioru danych ) jego oszacowaniem (obliczonym z losowo wybranego podzbioru danych). Zwłaszcza w dużych wymiarach problemów optymalizacji zmniejsza to bardzo duże obciążenie obliczeniowe , osiągając szybsze iteracje w zamian za niższy współczynnik zbieżności.

Podczas gdy podstawową ideę stochastycznego przybliżenia można prześledzić wstecz do algorytmu Robbinsa-Monro z lat pięćdziesiątych XX wieku, stochastyczny spadek gradientu stał się ważną metodą optymalizacji w uczeniu maszynowym .

Tło

Główny artykuł: M-estymacja

Zobacz też: Szacowanie równania

Zarówno estymacja statystyczna , jak i uczenie maszynowe rozpatrują problem minimalizacji funkcji celu , która ma postać sumy:

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

gdzie $\ displaystyle Q (w)}$ oszacować parametr , $w$ minimalizuje { . Każda funkcja sumy $używanym$$zwykle$ powiązana z obserwacją w danych ( do szkolenia).

W statystyce klasycznej problemy z minimalizacją sumy pojawiają się przy najmniejszych kwadratach i przy estymacji największej wiarygodności (dla niezależnych obserwacji). Ogólna klasa estymatorów, które powstają jako minimalizatory sum, nazywana jest M-estymatorami . Jednak w statystyce od dawna uznaje się, że wymaganie nawet lokalnej minimalizacji jest zbyt restrykcyjne dla niektórych problemów szacowania maksymalnej wiarygodności. Dlatego współcześni teoretycy statystyki często biorą pod uwagę punkty stacjonarne funkcji wiarygodności ( lub zera jej pochodnej, funkcji punktacji). i inne równania szacujące ).

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

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

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

gdzie $jest$ wielkością kroku (czasami nazywaną uczenia się w uczeniu maszynowym).

W wielu przypadkach funkcje sumy mają prostą postać, która umożliwia niedrogie oszacowanie funkcji sumy i gradientu sumy. Na przykład w statystyce rodziny wykładnicze z jednym parametrem 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 sumy. Gdy zbiór uczący jest ogromny i nie istnieją żadne proste formuły, obliczenie sum gradientów staje się bardzo kosztowne, ponieważ obliczenie gradientu wymaga oszacowania wszystkich gradientów funkcji sumy. Aby zaoszczędzić na kosztach obliczeniowych w każdej iteracji, stochastyczne zejście gradientowe próbkuje podzbiór funkcji sumy na każdym kroku. Jest to bardzo skuteczne w przypadku problemów z uczeniem maszynowym na dużą skalę.

Metoda iteracyjna

Przyjmuje się fluktuacje całkowitej funkcji celu jako kroki gradientu w odniesieniu do mini-partii.

W stochastycznym (lub „on-line”) spadku gradientu prawdziwy gradient jest przybliżony przez gradient w pojedynczej próbce: ${\ Displaystyle Q (w)}$

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

Gdy algorytm przegląda zestaw treningowy, wykonuje powyższą aktualizację dla każdej próbki treningowej. W zbiorze uczącym można wykonać kilka przejść, aż algorytm osiągnie zbieżność. Jeśli tak się stanie, dane mogą być tasowane dla każdego przebiegu, aby zapobiec cyklom. Typowe implementacje mogą wykorzystywać adaptacyjną szybkość uczenia się, aby algorytm był zbieżny.

W pseudokodzie stochastyczny spadek gradientu można przedstawić jako:

• $displaystyle$ parametrów i szybkość uczenia się $\ eta}$ .
• Powtarzaj, aż do uzyskania przybliżonego minimum:
  • Losowo przetasuj próbki w zbiorze uczącym.
  • Dla ${\ Displaystyle i = 1,2, ..., n}$ , robić:
    • ${\ Displaystyle w: = w - \ eta \ nabla Q_ {i} (w).}$

Kompromisem między obliczeniem rzeczywistego gradientu a gradientem dla pojedynczej próbki jest obliczenie gradientu dla więcej niż jednej próbki treningowej (zwanej „mini-partią”) na każdym kroku. Może to działać znacznie lepiej niż opisane „prawdziwe” stochastyczne zejście gradientowe, ponieważ kod może wykorzystywać wektoryzacji zamiast obliczać każdy krok osobno, jak po raz pierwszy pokazano, gdzie nazwano go „algorytmem propagacji wstecznej w trybie wiązki”. Może to również skutkować płynniejszą zbieżnością, ponieważ gradient obliczony na każdym kroku jest uśredniany dla większej liczby próbek treningowych.

Zbieżność stochastycznego spadku gradientu została przeanalizowana przy użyciu teorii minimalizacji wypukłej i aproksymacji stochastycznej . Krótko mówiąc, kiedy współczynniki uczenia się spadają z odpowiednim tempem i przy stosunkowo łagodnych założeniach, stochastyczny spadek gradientu prawie na pewno zbiega się do globalnego minimum, gdy funkcja celu jest wypukła lub pseudowypukła ${\ displaystyle \ eta}$ , a poza tym zbiega się prawie na pewno do lokalnego minimum. W rzeczywistości jest to konsekwencją twierdzenia Robbinsa-Siegmunda.

Przykład

Załóżmy $,$${\ Displaystyle (x_ {1}, x_ {2}, \ ldots, x_ {n})}$ z i odpowiadające im oszacowane odpowiedzi ${\ Displaystyle ({\ kapelusz {y_ {1}}}, {\ kapelusz {y_ {2}}}, \ ldots, {\ kapelusz {y_ {n}}}}} przy użyciu$ najmniejszych kwadratów . Minimalizowana funkcja celu to:

${\ Displaystyle Q (w) = \ suma _ {i = 1} ^ {n} Q_ {i} (w) = \ suma _ {i = 1} ^ {n} \ lewo ({\ kapelusz {y_ {i }}}-y_{i}\right)^{2}=\suma_{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 miała postać:

${\ Displaystyle {\ rozpocząć {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{bmacierz}}.}$

$,$ że w każdej iteracji (zwanej również aktualizacją) gradient jest oceniany tylko w jednym punkcie, a zbiorze wszystkich próbek.

Kluczowa różnica w porównaniu ze standardowym (wsadowym) opadaniem gradientu polega na tym, że do obliczenia kroku używana jest tylko jedna część danych ze zbioru danych, a część danych jest wybierana losowo na każdym etapie.

Godne uwagi aplikacje

Stochastyczny spadek gradientu jest popularnym algorytmem do uczenia szerokiej gamy modeli w uczeniu maszynowym , w tym (liniowych) maszyn wektorów nośnych , regresji logistycznej (patrz np. Vowpal Wabbit ) i modeli graficznych . W połączeniu z propagacji wstecznej jest to de facto standardowy algorytm uczenia sztucznych sieci neuronowych . Jego użycie zostało również opisane w Geofizyce społeczność, w szczególności do zastosowań Full Waveform Inversion (FWI).

Stochastyczny spadek gradientu konkuruje z algorytmem L-BFGS , który jest również szeroko stosowany. Stochastyczne zejście gradientowe było używane od co najmniej 1960 r. do trenowania regresji liniowej , pierwotnie pod nazwą ADALINE .

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

Rozszerzenia i warianty

Zaproponowano i zastosowano wiele ulepszeń podstawowego algorytmu stochastycznego gradientu. W szczególności w uczeniu maszynowym za problematyczną uznano potrzebę ustalenia tempa uczenia się (wielkości kroku). Ustawienie zbyt wysokiego parametru może spowodować rozbieżność algorytmu; ustawienie go zbyt nisko spowalnia zbieżność. Konceptualnie proste rozszerzenie stochastycznego spadku gradientu sprawia, że ​​​​szybkość uczenia się jest malejącą funkcją η _t liczby iteracji t , dając harmonogram szybkości uczenia się , tak aby pierwsze iteracje powodowały duże zmiany parametrów, a późniejsze tylko dostrajanie. Takie rozkłady są znane od czasów pracy MacQueena nad grupowaniem k -średnich . Praktyczne wskazówki dotyczące wyboru wielkości stopnia w kilku wariantach SGD podaje Spall.

Niejawne aktualizacje (ISGD)

Jak wspomniano wcześniej, klasyczne zejście gradientu stochastycznego jest generalnie wrażliwe na szybkość uczenia się η . Szybka konwergencja wymaga dużych szybkości uczenia się, ale może to powodować niestabilność numeryczną. 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ż $się$ stronach równania Jest to stochastyczna postać metody gradientu proksymalnego, ponieważ aktualizację można również zapisać jako:

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

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

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

gdzie ${\ Displaystyle x_ {j} 'w = x_ {j1} w_ {1} + x_ {j, 2} w_ {2} +... + x_ {j, p} w_ {p }}$ wskazuje produkt wewnętrzny. Zauważ, że ${\ displaystyle x}$ może mieć „1” jako pierwszy element zawierający punkt przecięcia. Klasyczny gradient stochastyczny przebiega w następujący sposób:

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

gdzie $displaystyle$ jednolicie próbkowany między 1 a $n}$ . Chociaż teoretyczna zbieżność tej procedury zachodzi przy stosunkowo łagodnych założeniach, w praktyce procedura ta może być dość niestabilna. W szczególności, gdy jest błędnie określony, tak że $ja$$eta x_ {i} x_ {i}'}$ ma duże bezwzględne wartości własne z dużym prawdopodobieństwem, procedura może różnić się numerycznie w ciągu kilku iteracji. W przeciwieństwie do tego, niejawne stochastyczne zejście gradientowe (w skrócie ISGD) można rozwiązać w postaci zamkniętej jako:

${\ 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 liczbowo stabilna praktycznie dla wszystkich, $tempo$ uczenia się jest teraz znormalizowane. Takie porównanie klasycznego i niejawnego stochastycznego spadku gradientu w problemie najmniejszych kwadratów jest bardzo podobne do porównania między najmniejszymi średnimi kwadratami (LMS) a znormalizowanym filtrem najmniejszych średnich kwadratów (NLMS) .

Chociaż rozwiązanie w postaci zamkniętej dla ISGD jest możliwe tylko w metodzie najmniejszych kwadratów, procedurę można skutecznie wdrożyć w szerokiej gamie modeli. W szczególności załóżmy, że $w$ od $displaystyle$ poprzez liniową kombinację z $w$ mogli napisz ${\ Displaystyle \ nabla _ {w} Q_ {i} (w) = - q (x_ {i} 'w) x_ {i}} , gdzie$ q $\ Displaystyle q () \ w \mathbb {R}}$ może również zależeć od ${\ displaystyle x_ {i}, y_ {i}},$ ale nie od ${\ displaystyle w}$ z wyjątkiem ${\ displaystyle x_ { ja}'w}$ . Metoda najmniejszych kwadratów jest zgodna z tą zasadą, podobnie jak regresja logistyczna i większość uogólnione modele liniowe . Na przykład w najmniejszych kwadratach ${\ Displaystyle q (x_ {i} 'w) = y_ {i} -x_ {i}' w$ } gdzie $_$ _ ${\ Displaystyle S (u) = e ^ {u} / (1 + e ^ {u})}$ jest funkcją logistyczną . W regresji Poissona , ${\ Displaystyle q (x_ {i} 'w) = y_ {i} -e ^ {x_ {i}' w}$ } i tak dalej.

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

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

Współczynnik skalowania $, ponieważ$ znaleźć metodą bisekcji jak wspomniane wyżej uogólnione modele liniowe, ${\ Displaystyle q ()}$$, \ max (0, f (0))]}$ ) $zatem$ granice wyszukiwania dla to

Pęd

Dalsze propozycje obejmują metodę momentum , która pojawiła się w artykule Rumelharta , Hintona i Williamsa na temat uczenia się metodą wstecznej propagacji. Stochastyczny spadek 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)} w$

${\ styl wyświetlania w:=w+\Delta w}$

co prowadzi do:

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

gdzie należy oszacować parametr , który minimalizuje $jest$ wielkością kroku (czasami nazywaną $eta$$}$ się w uczeniu maszynowym) i w jest $wykładniczym$ współczynnikiem rozpadu między 0 a 1, który określa względny udział obecnego gradientu i wcześniejszych gradientów w zmianie masy

Nazwa pęd wywodzi się z analogii do pędu w fizyce: wektor ciężaru , uważany za cząstkę podróżującą przez przestrzeń parametrów, podlega przyspieszeniu $wynikającemu$ gradientu straty („ siła ”). W przeciwieństwie do klasycznego gradientu stochastycznego, ma tendencję do poruszania się w tym samym kierunku, zapobiegając oscylacjom. Momentum jest z powodzeniem wykorzystywane przez informatyków w szkoleniu sztucznych sieci neuronowych od kilkudziesięciu lat. Metoda pędu jest ściśle związana z niedotłumiona dynamika Langevina i może być połączona z symulowanym wyżarzaniem .

Uśrednianie

Uśrednione stochastyczne zejście gradientowe , wymyślone niezależnie przez Rupperta i Polyaka pod koniec lat 80., jest zwykłym stochastycznym zejściem gradientowym, które rejestruje średnią swojego wektora parametrów w czasie. Oznacza to, że aktualizacja jest taka sama jak w przypadku zwykłego gradientu stochastycznego, ale algorytm również ją śledzi

${\ 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 .

Ada Grad

AdaGrad (dla adaptacyjnego algorytmu gradientu ) to zmodyfikowany stochastyczny algorytm opadania gradientu z szybkością uczenia się na parametr , opublikowany po raz pierwszy w 2011 r. Nieformalnie zwiększa to szybkość uczenia się dla rzadszych parametrów i zmniejsza szybkość uczenia się dla tych, które są mniej rzadkie. Ta strategia często poprawia wydajność konwergencji w porównaniu ze standardowym gradientem stochastycznym w ustawieniach, w których dane są rzadkie, a rzadkie parametry dostarczają więcej informacji. Przykłady takich zastosowań obejmują przetwarzanie języka naturalnego i rozpoznawanie obrazów. Nadal ma podstawową szybkość uczenia się η , ale jest to mnożone przez elementy wektora { G _{j , j} } , który jest przekątną zewnętrznej macierzy iloczynu

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

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

$\ 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} }}\odot g}$

lub, napisane jako aktualizacje parametrów,

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

Każde { G _{( i , i )} } powoduje wzrost współczynnika skalującego dla szybkości uczenia się, który ma zastosowanie do pojedynczego _parametru wi . Ponieważ mianownik w tym czynniku ${\ Displaystyle {\ sqrt {G_ {i}}} = {\ sqrt {\ suma _ {\ tau = 1} ^ {t} g_ {\tau}^{2}}}}$ jest normą ℓ ₂ poprzednich pochodnych, ekstremalne aktualizacje parametrów są tłumione, podczas gdy parametry, które otrzymują niewiele lub małe aktualizacje, uzyskują wyższe wskaźniki uczenia się.

Zaprojektowany dla problemów wypukłych , AdaGrad został z powodzeniem zastosowany do optymalizacji niewypukłych.

RMSProp

RMSProp (od Root Mean Square Propagation) to także metoda, w której szybkość uczenia się jest dostosowywana do każdego z parametrów. Chodzi o to, aby podzielić szybkość uczenia się dla wagi przez średnią ruchomą wielkoś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 $.$ czynnikiem zapominania

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żna postrzegać jako uogólnienie Rprop i jest w stanie pracować z mini-partiami, a także w przeciwieństwie do tylko pełnych partii.

Adama

Adam (skrót od Adaptive Moment Estimation) to aktualizacja optymalizatora RMSProp . W tym algorytmie optymalizacji używane są średnie ruchome zarówno gradientów, jak i drugich momentów gradientów. $\ Displaystyle$ uwagę parametry i funkcję straty $(t)}}$ gdzie $indeksuje$ bieżącą iterację szkolenia indeksowane w ${\ displaystyle 0}$ ), aktualizacja parametrów Adama jest dana przez:

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

${\ Displaystyle v_ {w} ^ {(t + 1)} \ strzałka w lewo \ beta _ {2} v_ {w} ^ {(t)} + (1 - \ beta _ {2}} (\ nabla _ {w} L ^ {(t)}) ^ {2}} m ^ w$

${\ 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 $}$ małym skalarem (np ${\ Displaystyle \ epsilon$ używanym do zapobiegania dzieleniu przez 0 i $($ np 0,9) i ${\ Displaystyle \ beta _ {2}}$ (np. 0,999) są współczynnikami zapominania odpowiednio dla gradientów i drugich momentów gradientów. Podnoszenie do kwadratu i pierwiastkowanie odbywa się po elementach. Głęboki wpływ tego algorytmu zainspirował wiele nowszych, mniej znanych schematów optymalizacji opartych na pędzie, wykorzystujących gradienty wzmocnione przez Nesterova (np. NAdam i FASFA ) oraz różne interpretacje informacji drugiego rzędu (np. Powerpropagation i AdaSqrt ). Jednak najczęściej używanymi wariantami są AdaMax , który uogólnia Adama za pomocą normy nieskończoności, oraz AMSGrad , który dotyczy problemów konwergencji od Adama.

Wycofanie wyszukiwania linii

Wyszukiwanie linii z wycofywaniem to kolejny wariant zejścia po gradiencie. Wszystkie poniższe pochodzą ze wspomnianego linku. Opiera się na warunku znanym jako warunek Armijo-Goldsteina. Obie metody umożliwiają zmianę szybkości uczenia się w każdej iteracji; jednak sposób zmiany jest inny. Wyszukiwanie linii wstecznej wykorzystuje oceny funkcji do sprawdzania stanu Armijo iw zasadzie pętla w algorytmie do określania szybkości uczenia się może być długa i nieznana z góry. Adaptacyjne SGD nie potrzebuje pętli w określaniu współczynników uczenia się. Z drugiej strony, adaptacyjne SGD nie gwarantuje „właściwości zejścia” – z której korzysta wyszukiwanie linii Backtracking – czyli to, że ${\ Displaystyle f (x_ {n + 1}) \ równoważnik f (x_ {n})}$ dla wszystkich n. Jeśli gradient funkcji kosztu jest globalnie ciągły Lipschitza, ze stałą Lipschitza L i szybkością uczenia się rzędu 1/L, to standardowa wersja SGD jest szczególnym przypadkiem wyszukiwania liniowego wstecznego.

Metody drugiego rzędu

Stochastyczny odpowiednik standardowego (deterministycznego) algorytmu Newtona-Raphsona (metoda „drugiego rzędu”) zapewnia asymptotycznie optymalną lub prawie optymalną formę optymalizacji iteracyjnej przy ustawieniu aproksymacji stochastycznej [ . Metoda wykorzystująca bezpośrednie pomiary macierzy Hessego sum w funkcji ryzyka empirycznego opracowali Byrd, Hansen, Nocedal i Singer. Jednak bezpośrednie określenie wymaganych macierzy Hessego do optymalizacji może nie być możliwe w praktyce. Spall i inni podają praktyczne i teoretycznie rozsądne metody dla wersji SGD drugiego rzędu, które nie wymagają bezpośrednich informacji z Hesji. (Mniej wydajną metodę opartą na skończonych różnicach zamiast jednoczesnych perturbacji podaje Ruppert.) Innym podejściem do aproksymacyjnej macierzy Hessego jest zastąpienie jej macierzą informacyjną Fishera, która przekształca zwykły gradient na naturalny. Te metody, które nie wymagają bezpośrednich informacji z Hesji, opierają się albo na wartościach sum w powyższej empirycznej funkcji ryzyka, albo na wartościach gradientów sum (tj. danych wejściowych SGD). W szczególności optymalność drugiego rzędu jest asymptotycznie osiągalna bez bezpośredniego obliczania macierzy Hessego sum w empirycznej funkcji ryzyka.

Zobacz też

• Wycofanie wyszukiwania linii
• Zejście współrzędnych – zmienia jedną współrzędną na raz, a nie jeden przykład
• Klasyfikator liniowy
• Uczenie maszynowe w Internecie
• Stochastyczna wspinaczka górska
• Redukcja wariancji stochastycznej

Dalsza lektura

•   Bottou, Léon (2004), „Stochastic Learning” , Zaawansowane wykłady na temat uczenia maszynowego , LNAI, tom. 3176, Springer, s. 146–168, ISBN 978-3-540-23122-6
• Buduma, Nikhil; Locascio, Nicholas (2017), „Beyond Gradient Descent” , Podstawy głębokiego uczenia się: projektowanie algorytmów inteligencji maszynowej 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 i optymalizacji stochastycznej , Wiley , ISBN 978-0-471-33052-3

Linki zewnętrzne

• Wykorzystanie stochastycznego spadku gradientu w C++, Boost, Ublas do regresji liniowej
• Algorytmy uczenia maszynowego
• „Zejście gradientowe, jak uczą się sieci neuronowe” . 3Niebieski1Brązowy . 16 października 2017 r. Zarchiwizowane od oryginału w dniu 22.12.2021 r. – przez YouTube .
• Goh (4 kwietnia 2017). „Dlaczego Momentum naprawdę działa” . destylować . 2 (4). doi : 10.23915/destyl.00006 . Interaktywny papier wyjaśniający pęd.