W jaki sposób stochastyczne zejście gradientu pozwala uniknąć problemu lokalnego minimum?

19

Wiem, że opadanie gradientu stochastycznego ma losowe zachowanie, ale nie wiem dlaczego.
Czy jest na to jakieś wyjaśnienie?

SunshineAtNoon
źródło
10
Co twoje pytanie ma wspólnego z twoim tytułem?
Neil G,

Odpowiedzi:

22

Algorytm gradientu stochastycznego (SG) zachowuje się jak algorytm symulowanego wyżarzania (SA), w którym szybkość uczenia się SG jest związana z temperaturą SA. Losowość lub hałas wprowadzony przez SG pozwala uciec od lokalnych minimów, aby osiągnąć lepsze minimum. Oczywiście zależy to od tego, jak szybko zmniejszysz tempo uczenia się. Przeczytaj rozdział 4.2 Stochastycznego uczenia gradientowego w sieciach neuronowych (pdf) , gdzie wyjaśniono to bardziej szczegółowo.

Clara
źródło
4
Nie przejmuj się dobrze sekcją 4.1, gdzie drugie twierdzenie dotyczy ograniczonego przypadku funkcji niekonwekcjonalnych, mówiąc, że zbiega się ono (z nieskończonymi próbkami) do pewnego punktu z gradientem 0. To może nie być globalne minimum lub nawet maksimum . SGD jest bardziej interesujący z bardziej praktycznych powodów, takich jak uczenie się rozproszone, nie na pewno dlatego, że „uniknie” lokalnego minimum.
zero
2

W stochastycznym spadku gradientu parametry są szacowane dla każdej obserwacji, w przeciwieństwie do całej próbki w regularnym spadku gradientu (opadanie gradientu serii). To daje dużo losowości. Ścieżka stochastycznego zejścia gradientu błąka się po większej liczbie miejsc i dlatego jest bardziej prawdopodobne, że „wyskoczy” z lokalnego minimum i znajdzie globalne minimum (Uwaga *). Jednak stochastyczne zejście gradientowe wciąż może utknąć w lokalnym minimum.

Uwaga: Często utrzymuje się stałą szybkość uczenia się, w tym przypadku opadanie gradientu stochastycznego nie jest zbieżne; po prostu błąka się po tym samym punkcie. Jeśli jednak szybkość uczenia się maleje z upływem czasu, powiedzmy, jest odwrotnie proporcjonalna do liczby iteracji, wówczas zejście gradientu stochastycznego zbiegnie się.

Akavall
źródło
Nie jest prawdą, że stochastyczne zejście gradientu tak naprawdę się nie zbiega i po prostu zastanawia się nad pewnym punktem. Tak by było, gdyby współczynnik uczenia się był stały. Jednak współczynniki uczenia się mają tendencję do zera, ponieważ w ten sposób, gdy algorytm jest bliski minimum funkcji wypukłej, przestaje oscylować i zbiega się. Kluczem dowodu zbieżności gradientu stochastycznego są warunki nałożone na szereg wskaźników uczenia się. Zobacz równania (6) i (27) oryginalnej pracy Robbinsa i Monro.
clara
2

Jak już wspomniano w poprzednich odpowiedziach, stochastyczne opadanie gradientu ma znacznie głośniejszą powierzchnię błędu, ponieważ iteracyjnie oceniasz każdą próbkę. Podczas gdy robisz krok w kierunku globalnego minimum w zejściu gradientu wsadowego w każdej epoce (omiń zestaw treningowy), poszczególne kroki swojego stochastycznego gradientu zejścia gradientu nie zawsze muszą wskazywać w kierunku globalnego minimum, w zależności od ocenianej próbki.

Aby to zobrazować na dwuwymiarowym przykładzie, oto kilka rysunków i rysunków z lekcji uczenia maszynowego Andrew Ng.

Pierwsze zejście gradientu:

wprowadź opis zdjęcia tutaj

Po drugie, stochastyczne zejście gradientowe:

wprowadź opis zdjęcia tutaj

Czerwone kółko na dolnej cyfrze pokazuje, że opadanie gradientu stochastycznego „będzie się aktualizować” gdzieś w okolicy globalnego minimum, jeśli używasz stałej szybkości uczenia się.

Oto kilka praktycznych wskazówek dotyczących stochastycznego spadku gradientu:

1) potasuj zestaw treningowy przed każdą epoką (lub iteracją w wariancie „standardowym”)

2) użyj adaptacyjnego wskaźnika uczenia się, aby „wygrzać” bliżej globalnego minimum


źródło
Dlaczego chcesz wymieszać zestaw treningowy przed każdą epoką? Algorytm SGD wybiera losowo przykłady treningu.
Vladislavs Dovgalecs
Tasowanie jest w zasadzie jednym ze sposobów losowego wybierania próbek treningowych. W moich implementacjach zwykle for
2
Hm, na Wikipedii, algorytm SGD jest opisany jako „bez zamiany”, jednak Bottou opisuje go tak jak ty (Bottou, Léon. „Uczenie maszynowe na dużą skalę ze stochastycznym spadkiem gradientu.” Postępowanie z COMPSTAT'2010. HD, 2010. 177-186.), I myślę, że tutaj bardziej zaufałbym Bottou niż temu wpisowi w Wikipedii.
4
@xeon Sprawdź ten artykuł , który dowodzi, że próbkowanie bez zamiany jest lepsze. Rozumiem, że bez wymiany wydaje się być empirycznie lepszy, ale analizy teoretyczne były dostępne dopiero od niedawna.
Dougal,
1
@xeon Właśnie spojrzałem na moje slajdy PDF z kursu Andrew Nga i wygląda na to, że opisał je jak w Wikipedii (wariant „bez wymiany”), a nie jak Bottou. Przesłałem tutaj zrzut ekranu