Spadek gradientu wsadowego a gradient gradientu stochastycznego

101

Załóżmy, że mamy pewien zestaw treningowy $(x_{(i)}, y_{(i)})$ dla $i = 1, \dots, m$ . Załóżmy również, że uruchamiamy pewien rodzaj algorytmu uczenia nadzorowanego na zestawie szkoleniowym. Hipotezy są reprezentowane jako $h_{\theta}(x_{(i)}) = \theta_0+\theta_{1}x_{(i)1} + \cdots +\theta_{n}x_{(i)n}$ . Musimy znaleźć parametry $\mathbf{\theta}$ które minimalizują „odległość” między $y_{(i)}$ i $h_{\theta}(x_{(i)})$ . Niech

J (θ) = \frac{1}{2} \sum_{i = 1}^{m} (y_{(i)} - h_{θ} (x_{(i)})^{2}

$J(\theta) = \frac{1}{2} \sum_{i=1}^{m} (y_{(i)}-h_{\theta}(x_{(i)})^{2}$

Następnie chcemy znaleźć $\theta$ która minimalizuje $J(\theta)$ . Podczas opadania gradientu inicjalizujemy każdy parametr i przeprowadzamy następującą aktualizację:

θ_{j} := θ_{j} - α \frac{\partial}{\partial θ_{j}} J (θ)

$\theta_j := \theta_j-\alpha \frac{\partial}{\partial \theta_{j}} J(\theta)$

Jaka jest kluczowa różnica między spadkiem gradientu wsadowego a spadkiem gradientu stochastycznego?

Oba używają powyższej reguły aktualizacji. Ale czy jedno jest lepsze od drugiego?

optimization gradient-descent sgd użytkownik20616
źródło

121

Możliwość zastosowania okresowego lub stochastycznego spadku gradientu naprawdę zależy od oczekiwanego rozmaitości błędów.

Opadanie gradientu wsadowego oblicza gradient na podstawie całego zestawu danych. Jest to idealne rozwiązanie dla wypukłych lub względnie gładkich rozmaitości błędów. W tym przypadku przechodzimy nieco bezpośrednio w kierunku optymalnego rozwiązania, lokalnego lub globalnego. Dodatkowo, opadanie gradientu partii, przy wyższym współczynniku uczenia się, ostatecznie znajdzie minimum w swoim basenie z atrakcją.

Stochastyczne pochylenie gradientu (SGD) oblicza gradient za pomocą pojedynczej próbki. Większość aplikacji SGD faktycznie korzysta z minibatchu kilku próbek, z powodów, które zostaną wyjaśnione nieco później. SGD działa dobrze (chyba nie dobrze, ale lepiej niż opadanie gradientu wsadowego) dla rozmaitości błędów, które mają wiele lokalnych maksimów / minimów. W tym przypadku nieco głośniejszy gradient obliczony przy użyciu zmniejszonej liczby próbek ma tendencję do szarpnięcia modelu z lokalnych minimów do regionu, który, miejmy nadzieję, jest bardziej optymalny. Pojedyncze próbki są naprawdę hałaśliwe, podczas gdy minibatche mają tendencję do zmniejszania hałasu. W ten sposób ilość szarpnięcia jest zmniejszona podczas korzystania z minibatch. Utrzymuje się dobrą równowagę, gdy rozmiar minibatchu jest wystarczająco mały, aby uniknąć niektórych złych lokalnych minimów, ale wystarczająco duży, aby nie Unikaj globalnych minimów lub lokalnych minimów o lepszych parametrach. (Nawiasem mówiąc, zakłada to, że najlepsze minima mają większy i głębszy basen przyciągania i dlatego łatwiej do nich wpaść).

Jedną z zalet SGD jest to, że jest obliczeniowo dużo szybszy. Dużych zestawów danych często nie można przechowywać w pamięci RAM, co sprawia, że wektoryzacja jest znacznie mniej wydajna. Raczej każda próbka lub partia próbek musi zostać załadowana, poddana obróbce, przechowywać wyniki itd. Z drugiej strony Minibatch SGD jest zwykle celowo wystarczająco mały, aby był wykonalny obliczeniowo.

Zwykle tę przewagę obliczeniową wykorzystuje się, wykonując znacznie więcej iteracji SGD, wykonując znacznie więcej kroków niż konwencjonalne opadanie gradientem wsadowym. Zwykle powoduje to, że model jest bardzo zbliżony do modelu, który można znaleźć poprzez opadanie gradientu partii lub lepiej.

Sposób, w jaki lubię myśleć o tym, jak działa SGD, polega na wyobrażeniu sobie, że mam jeden punkt reprezentujący mój rozkład wejściowy. Mój model próbuje nauczyć się tego rozkładu wejściowego. Wokół rozkładu wejściowego jest zacieniony obszar, który reprezentuje rozkłady wejściowe wszystkich możliwych minibatchów, które mogłem próbkować. Zazwyczaj jest to słuszne założenie, że rozkłady wejściowe minibatch są zbliżone do prawdziwego rozkładu wejściowego. Opadanie gradientu wsadowego na wszystkich etapach prowadzi najostrzejszą drogą do osiągnięcia prawdziwego rozkładu wejściowego. Z drugiej strony SGD wybiera losowy punkt w zacienionym obszarze i wybiera najbardziej stromą drogę do tego punktu. Jednak przy każdej iteracji wybiera nowy punkt. Średnia wszystkich tych kroków przybliża prawdziwy rozkład danych wejściowych, zwykle całkiem dobrze.

Jason_L_Bens
źródło

13

W praktyce nikt nie korzysta z Batch Gradient Descent. Jest to po prostu zbyt drogie obliczeniowo, aby nie dać tak dużego zysku. (Zysk polega na tym, że faktycznie obniżasz „prawdziwy” gradient.) Kiedy masz wysoce nie wypukłą funkcję utraty, musisz po prostu pójść we właściwym kierunku, a ostatecznie osiągniesz lokalne minimum. Zatem minibatch SGD.

sabalaba

@Jason_L_Bens Czy masz jakieś referencje (artykuły lub teksty online), w których mogę przeczytać więcej na temat tych algorytmów?

user110320,

1

@ user110320 Nie z mojej głowy, nie, chociaż są to bardzo popularne algorytmy, więc powinna być tona zasobów dostępnych na ten temat przy odrobinie wyszukiwania. Jeśli szukasz ogólnego podejścia, polecam zapoznanie się z częścią „Głębokie architektury uczenia się” przez Yoshua Bengio dla AI. Właśnie tam zacząłem.

Jason_L_Bens

6

Jak sugeruje inna odpowiedź, głównym powodem zastosowania SGD jest zmniejszenie kosztu obliczeń gradientu przy jednoczesnym utrzymaniu w dużej mierze kierunku gradientu, gdy uśrednia się go dla wielu mini-partii lub próbek - to z pewnością pomaga w osiągnięciu lokalnych minimów.

Dlaczego działa minibatch .

$p_{data}$ $\hat{p}_{data}$

g = E_{p_{d a t a}} (\frac{\partial J (θ)}{\partial θ})

$g = E_{p_{data}}({\partial J(\theta)\over \partial \theta})$

\frac{S E (\hat{g} (n))}{S E (\hat{g} (m))} = \sqrt{\frac{m}{n}}

${SE({\hat{g}(n)}) \over SE({\hat{g}(m)})} = { \sqrt {m \over n}}$

m

$m$

E_{{\hat{p}}_{d a t a}} (\hat{g} (m)) = E_{{\hat{p}}_{d a t a}} (\frac{\partial J (θ)}{\partial θ})

$E_{\hat{p}_{data}}(\hat{g}(m)) = E_{\hat{p}_{data}}({\partial J(\theta)\over \partial \theta})$

m

$m$

Dlaczego minibatch może działać lepiej .

Po pierwsze, minibatch sprawia, że niektóre problemy z nauką stają się technicznie niemożliwe do rozwiązania ze względu na zmniejszone zapotrzebowanie na obliczenia przy mniejszym rozmiarze partii.

Po drugie, zmniejszony rozmiar partii niekoniecznie oznacza zmniejszoną dokładność gradientu. Próbki szkoleniowe mają wiele dźwięków, wartości odstających lub tendencyjnych. Losowo pobrana próbka minibatch może odzwierciedlać rzeczywisty rozkład generowania danych lepiej (lub nie gorzej) niż oryginalna pełna partia. Jeśli niektóre iteracje aktualizacji gradientu minibatch dają lepsze oszacowanie, ogólnie uśredniony wynik jednej epoki może być lepszy niż gradient obliczony z pełnej partii.

Po trzecie, minibatch nie tylko pomaga radzić sobie z nieprzyjemnymi próbkami danych, ale także pomaga radzić sobie z nieprzyjemną funkcją kosztów, która ma wiele lokalnych minimów. Jak wspomina Jason_L_Bens, czasem rozmaitości błędów mogą łatwiej wychwytywać regularne gradienty do lokalnych minimów, a trudniejsze do wychwytywania tymczasowo losowych gradientów obliczanych za pomocą minibatchów.

Wreszcie, z opadaniem gradientu, nie osiągasz globalnych minimów w jednym kroku, ale iterujesz na rozmaitości erro. Gradient w dużej mierze daje tylko kierunek iteracji. Dzięki minibatch możesz iterować znacznie szybciej. W wielu przypadkach im więcej iteracji, tym lepszy punkt można osiągnąć. Tak naprawdę nie zależy ci na każdej pogodzie, punkt jest optymalny na całym świecie, a nawet lokalnie. Po prostu chcesz osiągnąć rozsądny model, który przynosi akceptowalny błąd uogólnienia. Minibatch ułatwia to.

Książka Ian Goodfellow i wsp. „Głębokie uczenie się” może znaleźć całkiem dobre dyskusje na ten temat, jeśli dokładnie ją przeczytacie.

Xiao-Feng Li
źródło

W przypadku problemów z wypukłą optymalizacją to, co powiedziałeś, jest w porządku. Aby jednak zastosować metody gradientu w funkcjach niewypukłych, pominął się bardzo krytyczny powód, że SGD jest lepszy niż pakiet GD. Zobacz moją odpowiedź datascience.stackexchange.com/questions/16807/…

horaceT

@horaceT Dziękujemy za komentarz. Ponieważ punkt, o którym wspomniałeś, został opisany powyżej przez Jason_L_Bens ze szczegółami, nie zawracałem sobie głowy powtórzeniem, ale z należytym szacunkiem odnosząc się do jego odpowiedzi w ostatnim trzecim akapicie. Aby rozwiązać problem optymalizacji spadku gradientu, niewypukłe są odzwierciedlane przez lokalne minima, w tym punkt siodłowy (patrz ostatni trzeci akapit); i ze względu na opis moja odpowiedź opisuje SGD jako minibatch, ale o wielkości partii 1 (patrz akapit trzeci).

Xiao-Feng Li

3

$2^{10-1} = 512$

Sven Ahlinder
źródło

Spadek gradientu wsadowego a gradient gradientu stochastycznego

Odpowiedzi: