Przejdź do treści
Wróć do wyników wyszukiwania

Stochastyczne spuszczanie gradientu (SGD)

Autor metody
Robbins, H. & Monro, S.
Rok
1951
Typ
First-order iterative optimization algorithm

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Stochastyczne spuszczanie gradientu (SGD) to iteracyjny algorytm optymalizacji pierwszego rzędu, wywodzący się z ram stochastycznej aproksymacji wprowadzonej przez Robbinsa i Monro w 1951 roku, który minimalizuje funkcję celu poprzez aktualizację parametrów modelu z wykorzystaniem gradientu obliczonego na pojedynczym losowo wybranym przykładzie treningowym (lub małej mini-paczce) na każdym kroku.

Jest to podstawowy mechanizm optymalizacji stojący za nowoczesnym uczeniem maszynowym i głębokim uczeniem, umożliwiający trenowanie modeli na zbiorach danych zbyt dużych, aby zmieściły się w pamięci.

Intuicja stojąca za metodą

Zwykłe spuszczanie gradientu oblicza dokładny gradient straty na wszystkich przykładach treningowych przed wykonaniem pojedynczej aktualizacji parametrów — jest to poprawne, ale niewykonalnie wolne na dużych zbiorach danych. SGD poświęca dokładność na rzecz szybkości: losowo wybiera jeden przykład (lub małą paczkę), oblicza zaszumione oszacowanie gradientu i natychmiast aktualizuje parametry. Szum nie jest jedynie uciążliwością; działa jako niejawna regularyzacja, pomagając optymalizatorowi uciec od płytkich minimów lokalnych i punktów siodłowych. Po wielu iteracjach zaszumione kroki uśredniają się, a parametry zbiegają w kierunku minimum straty, podobnie jak pijany spacer, który jednak dociera do celu.

Historia

Teoretyczne podstawy SGD położył Herbert Robbins i Sutton Monro w swojej pracy z 1951 roku „A Stochastic Approximation Method”, która dowiodła, że iteracyjne zaszumione aktualizacje z zanikającym rozmiarem kroku zbiegają do pierwiastka funkcji regresji. Związek z optymalizacją opartą na gradiencie został wyraźnie zaznaczony przez Kiefera i Wolfowitza (1952), a później przez regułę LMS Widrowa i Hoffa (1960) dla filtrowania adaptacyjnego. SGD zyskał na znaczeniu w uczeniu maszynowym dzięki pracy LeCuna i współpracowników pod koniec lat 80. i w latach 90. do trenowania sieci neuronowych za pomocą propagacji wstecznej. Publikacja eksperymentów na dużą skalę przez Bottou i współpracowników w latach 2000. wykazała wyższość SGD nad metodami wsadowymi na danych przemysłowych. Nowoczesna formuła SGD z mini-paczkami stała się uniwersalna wraz z renesansem głębokiego uczenia około 2012 roku (AlexNet), a algorytm pozostaje dominującym optymalizatorem w tej dziedzinie, z wariantami takimi jak Adam (Kingma & Ba, 2014) zbudowanymi bezpośrednio na jego regule aktualizacji.

Kiedy stosować

SGD jest metodą wyboru, gdy zbiór treningowy jest wystarczająco duży, aby obliczenie pełnego gradientu na aktualizację było zbyt kosztowne, co obejmuje praktycznie cały nowoczesny trening sieci neuronowych i dopasowywanie modeli liniowych na dużą skalę. Ma zastosowanie do każdej różniczkowalnej funkcji straty. Kluczowe założenia: strata jest różniczkowalna (lub subróżniczkowalna) względem parametrów, punkty danych są próbkowane niezależnie, a estymator gradientu jest nieobciążony. Dla silnie wypukłych celów SGD osiąga zbieżność O(1/T); dla ogólnych celów niewypukłych (np. głębokie sieci) praktycznie znajduje punkty stacjonarne, chociaż nie ma gwarancji globalnej optymalności. SGD z mini-paczkami (rozmiary paczek 32–512) jest zazwyczaj preferowane nad czystym SGD z pojedynczymi przykładami, ponieważ zapewnia estymatory gradientu o niższej wariancji i wykorzystuje równoległość na nowoczesnym sprzęcie. Gdy zbiór danych jest wystarczająco mały dla pełnego spuszczania gradientu i cel jest dobrze uwarunkowany, metody drugiego rzędu, takie jak L-BFGS, mogą zbiegać szybciej.

Ograniczenia i uwagi

  • Estymatory gradientu są zaszumione, co powoduje, że strata fluktuuje, zamiast monotonicznie maleć, utrudniając diagnozę zbieżności.
  • Bardzo wrażliwy na współczynnik uczenia: zbyt duży powoduje dywergencję; zbyt mały sprawia, że trening jest niewykonalnie powolny.
  • Zbieżność do globalnego minimum nie jest gwarantowana dla celów niewypukłych, takich jak głębokie sieci neuronowe.
  • Izotropowe aktualizacje traktują wszystkie wymiary parametrów równo, co czyni go nieodpowiednim dla powierzchni straty o bardzo różnych krzywiznach wzdłuż różnych osi — motywując warianty z adaptacyjnym współczynnikiem.
  • Wymaga starannego dostrojenia harmonogramu współczynnika uczenia; złe harmonogramy znacznie pogarszają końcową wydajność.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Skaluje się do dowolnie dużych zbiorów danych, ponieważ każda aktualizacja wymaga tylko jednego przykładu lub mini-paczki, utrzymując stałą pamięć i obliczenia na krok.
  • Wbudowany szum zapewnia niejawne regularyzację i pomaga uciec od płytkich minimów lokalnych i punktów siodłowych w krajobrazach niewypukłych.
  • Niezwykle ogólny: ma zastosowanie do każdej różniczkowalnej funkcji straty, w tym entropii krzyżowej, średniego błędu kwadratowego, straty zawiasowej i niestandardowych celów.
  • Stanowi podstawę niemal wszystkich nowoczesnych optymalizatorów (Adam, RMSProp, AdaGrad, pęd Nestierova) — zrozumienie SGD jest warunkiem wstępnym do ich zrozumienia.
  • Prosty do zaimplementowania i zrównoleglenia na GPU przy użyciu mini-paczek.

Zastosowania

  • Trenowanie głębokich sieci neuronowych do klasyfikacji obrazów, rozpoznawania mowy i przetwarzania języka naturalnego.
  • Dopasowywanie modeli regresji logistycznej i liniowych SVM na dużą skalę w klasyfikacji tekstu i systemach rekomendacyjnych.
  • Ustawienia uczenia online, gdzie przykłady napływają sekwencyjnie, a model musi być aktualizowany w czasie rzeczywistym.
  • Metody gradientu polityki w uczeniu ze wzmocnieniem, gdzie oczekiwany zwrot jest optymalizowany przy użyciu próbkowanych trajektorii.
  • Faktoryzacja macierzy do filtrowania kolaboracyjnego w systemach rekomendacyjnych.

Jak to działa

Jak to działa

1

Celem treningowym jest średnia strata na wszystkich n przykładach. W przypadku zadań takich jak klasyfikacja z entropią krzyżową lub regresja z błędem kwadratowym, suma ta może zawierać miliardy składników, co czyni pełną ewaluację na każdej iteracji niepraktyczną.

Wzór
L(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(x_i; \theta),\, y_i)
2

Na kroku t losowo wybierany jest pojedynczy przykład treningowy (lub mini-paczka) z rozkładem jednostajnym. Gradient straty na tym przykładzie jest nieobciążonym estymatorem prawdziwego gradientu, więc średnio aktualizacja wskazuje właściwy kierunek, mimo że jest zaszumiona dla każdego indywidualnego kroku.

Wzór
\hat{g}_t = \nabla_\theta \ell(f(x_{i_t}; \theta_t),\, y_{i_t})
3

Wektor parametrów jest przesuwany w kierunku przeciwnym do estymatora gradientu, przeskalowany przez współczynnik uczenia eta_t. Mniejszy współczynnik uczenia sprawia, że aktualizacje są ostrożne, ale powolne; większy przyspiesza zbieżność, ale grozi przekroczeniem celu. Ta pojedyncza linia — aktualizacja Robbinsa-Monro — jest sercem niemal każdego nowoczesnego optymalizatora.

Wzór
\theta_{t+1} = \theta_t - \eta_t \, \hat{g}_t
4

Warunki Robbinsa-Monro (suma współczynników uczenia rozbiega się, suma kwadratów współczynników uczenia zbiega się) gwarantują zbieżność dla celów wypukłych. W praktyce powszechne harmonogramy obejmują zanik krokowy, wygaszanie kosinusowe i ciepłe restarty; warunki te stanowią teoretyczne uzasadnienie, dlaczego zanikający harmonogram jest konieczny.

Wzór
\sum_{t=1}^{\infty} \eta_t = \infty, \quad \sum_{t=1}^{\infty} \eta_t^2 < \infty

Częste pułapki

  • Używanie stałego współczynnika uczenia przez cały trening bez żadnego harmonogramu zaniku, co powoduje oscylowanie optymalizatora wokół minimum zamiast osadzenia się w nim.
  • Wybór rozmiaru paczki bez uwzględnienia niejawnego efektu regularyzacji: bardzo duże paczki zmniejszają szum i mogą zaszkodzić generalizacji w porównaniu do mniejszych paczek przy tej samej liczbie epok.
  • Zapomnienie o przetasowaniu danych treningowych przed każdą epoką, co może wprowadzić systematyczne błędy, gdy dane są uporządkowane według klasy lub czasu.
  • Dostrojenie współczynnika uczenia tylko na podstawie straty walidacyjnej raz, zamiast monitorowania krzywych treningowych, co powoduje przeoczenie oznak dywergencji lub przedwczesnego plateau.
  • Traktowanie SGD jako optymalizatora typu czarna skrzynka bez zrozumienia jego właściwości zbieżności, a następnie ślepe przełączanie na Adam, gdy zbieżność wydaje się powolna, bez diagnozowania pierwotnej przyczyny.

Najczęściej zadawane pytania

Jaka jest różnica między SGD, SGD z mini-paczkami a pełnym spuszczaniem gradientu?

Pełne spuszczanie gradientu oblicza dokładny gradient na wszystkich n przykładach treningowych na aktualizację — koszt dokładny, ale O(n) na krok. Czyste SGD używa dokładnie jednego losowo wybranego przykładu na aktualizację — koszt O(1), ale bardzo zaszumiony. SGD z mini-paczkami używa małego losowego podzbioru (zazwyczaj 32–512 przykładów) — praktyczny kompromis, który zmniejsza szum, jednocześnie utrzymując koszt w ryzach i wykorzystując równoległość GPU. W nowoczesnym użyciu „SGD” prawie zawsze oznacza SGD z mini-paczkami.

Jak powinienem ustawić współczynnik uczenia?

Nie ma uniwersalnej odpowiedzi, ale powszechną praktyką jest rozpoczęcie od umiarkowanej wartości (np. 0,01 lub 0,1), monitorowanie krzywej straty treningowej i zastosowanie harmonogramu zaniku, takiego jak zanik krokowy, wygaszanie kosinusowe lub ciepłe restarty. Lokalizatory współczynnika uczenia (przeszukiwanie współczynników na kilku paczkach i obserwacja straty) mogą zidentyfikować dobrą wartość początkową. Teoria Robbinsa-Monro wymaga, aby współczynnik zanikał do zera, ale w praktyce zanik jest często stosowany łagodnie, aby uniknąć przedwczesnego spowolnienia.

Dlaczego SGD czasami generalizuje lepiej niż Adam?

Optymalizatory z adaptacyjnym współczynnikiem, takie jak Adam, często zbiegają szybciej, ale mogą bardziej przeuczać, szczególnie w zadaniach klasyfikacji obrazów. Wyższy szum w SGD — zwłaszcza przy małych rozmiarach paczek — działa jako niejawna regularyzacja, pomagając modelowi znaleźć bardziej płaskie minima, które lepiej generalizują. Kilka badań empirycznych (np. Wilson i in., 2017) udokumentowało to zjawisko, dlatego SGD z pędem jest nadal preferowany do trenowania modeli widzenia komputerowego, takich jak ResNet.

Czy SGD gwarantuje znalezienie globalnego minimum?

Tylko dla celów ściśle wypukłych, zgodnie z warunkami dotyczącymi rozmiaru kroku Robbinsa-Monro. Dla celów niewypukłych (praktycznie wszystkie głębokie sieci) SGD zapewnia zbieżność do punktu stacjonarnego (gdzie gradient wynosi zero), który w praktyce zazwyczaj jest dobrym minimum lokalnym, a nie punktem siodłowym lub globalnym minimum. Empirycznie znalezione rozwiązania są często wystarczająco dobre, aby osiągnąć najnowocześniejszą wydajność.

Pokrewne metody

Źródła

  1. Robbins, H. & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Goodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning (Ch. 8). MIT Press.

    ISBN: 978-0-262-03561-3
    Skopiowano.