Jak można go uwięzić w siodle?

14

Obecnie jestem nieco zdziwiony tym, w jaki sposób opadanie gradientu mini-partii może być uwięzione w punkcie siodłowym.

Rozwiązanie może być zbyt trywialne, że go nie rozumiem.

Masz nową próbkę każda epoka, i oblicza nową błędów oparty na nowej partii, więc funkcja kosztu jest statyczne tylko dla każdej partii, co oznacza, że gradient również powinien zmieniać się dla każdej partii mini .. Ale zgodnie z tym powinna wdrożenie waniliowe ma problemy z punktami siodłowymi?

Innym kluczowym wyzwaniem, jakim jest minimalizowanie wysoce niewypukłych funkcji błędów wspólnych dla sieci neuronowych, jest unikanie uwięzienia w ich licznych suboptymalnych lokalnych minimach. Dauphin i in. [19] twierdzą, że trudność wynika w rzeczywistości nie z lokalnych minimów, ale z punktów siodłowych, tj. Punktów, w których jeden wymiar jest nachylony w górę, a inny w dół. Te punkty siodłowe są zwykle otoczone płaskowyżem tego samego błędu, co utrudnia SGD ucieczkę, ponieważ gradient jest bliski zeru we wszystkich wymiarach.

Chciałbym przez to powiedzieć, że szczególnie SGD miałoby wyraźną przewagę nad punktami siodłowymi, ponieważ zmienia się w kierunku zbieżności ... Wahania i losowe próbkowanie oraz funkcja kosztów różniąca się dla każdej epoki powinny być wystarczającym powodem, aby nie zostać uwięzionym w jednym.

W przypadku pełnego gradientu partii sensowne jest, czy można go uwięzić w punkcie siodłowym, ponieważ funkcja błędu jest stała.

Jestem trochę zdezorientowany w dwóch pozostałych częściach.

Fixining_ranges
źródło
1
Moti to rozumie. Punkt siodłowy z bardzo wysokimi zboczami i otoczony zboczem zerowym uruchamia gradientowe zejście dużymi schodami w „badlands”, z którego nie może się wycofać. Pomyśl o poszukiwaniu studni na zasadniczo płaskiej równinie. Pomyśl teraz o studni zarówno suchej, jak i mrówkowej w centrum. Zejście gradientowe, które wyląduje na wzgórzu mrówek, ale nie na dokładnym szczycie, spowoduje promieniowe poszukiwanie. Teraz wyobraź sobie, że rozmiar kroku poszukiwania jest tysiąc razy większy niż średnica studni. Jeśli poszukiwania kiedykolwiek znajdą studnię, mrowisko strzela do Montany
EngrStudent - Przywróć Monikę
Jestem zdezorientowany, o co pytasz. Czy jesteś zdezorientowany, dlaczego SGD nie może zostać uwięziony w punkcie siodłowym z powodu dziedziczonego hałasu SGD, więc według ciebie powinien być w stanie uciec? (inaczej niż w przypadku pełnej serii GD, jeśli gradient wynosi zero i nie ma hałasu, to nie może uciec, czy o to pytasz?)
Pinokio

Odpowiedzi:

16

Spójrz na zdjęcie poniżej z Off Convex . W funkcji wypukłej (obraz po lewej stronie) istnieje tylko jedno lokalne minimum, które jest również globalnym minimum. Ale w funkcji niewypukłej (obraz po prawej stronie) może istnieć wiele lokalnych minimów i często łączenie dwóch lokalnych minimów jest punktem siodłowym. Jeśli zbliżasz się z wyższego punktu, gradient jest stosunkowo płaski i ryzykujesz utknięcie w nim, szczególnie jeśli poruszasz się tylko w jednym kierunku.

Schematyczne przedstawienie punktu siodłowego

Teraz chodzi o to, czy optymalizujesz przy użyciu mini-partiilub stochastyczny spadek gradientu, podstawowa funkcja niewypukła jest taka sama, a gradient jest właściwością tej funkcji. Robiąc mini-partię, bierzesz pod uwagę wiele próbek na raz i uśredniasz dla nich krok gradientu. To zmniejsza wariancję. Ale jeśli średni kierunek gradientu nadal wskazuje ten sam kierunek, co punkt siodła, nadal istnieje ryzyko utknięcia w tym miejscu. Analogia jest taka, że ​​jeśli robisz 2 kroki do przodu i 1 krok do tyłu, uśredniając je, ostatecznie ostatecznie robisz 1 krok do przodu. Jeśli zamiast tego wykonasz SGD, wykonasz wszystkie kroki jeden po drugim, ale jeśli nadal poruszasz się w jednym kierunku, możesz dotrzeć do punktu siodła i stwierdzić, że gradient ze wszystkich stron jest dość płaski, a wielkość kroku wynosi za mały, aby przejść przez tę płaską część. To nie

Spójrz na wizualizację tutaj . Nawet w przypadku SGD, jeśli fluktuacje występują tylko wzdłuż jednego wymiaru, a stopnie stają się coraz mniejsze, zbiegają się w punkcie siodłowym. W takim przypadku metoda mini-partii po prostu zmniejszyłaby wielkość fluktuacji, ale nie byłaby w stanie zmienić kierunku gradientu.

SGD może czasem wyłamać się z prostych punktów siodełka, jeśli wahania przebiegają wzdłuż innych kierunków i jeśli wielkość stopnia jest wystarczająco duża, aby przejść przez płaskość. Ale czasami regiony siodłowe mogą być dość złożone, jak na poniższym obrazku.

Złożone regiony siodłowe

Metody, takie jak pęd, ADAGRAD, Adam itp. Są w stanie się z tego wydostać, biorąc pod uwagę wcześniejsze gradienty. Zastanów się,

vt=γvt1+ηthetaJ(θ)

vt1

Antymon
źródło
Cóż, niezupełnie! Aby uzyskać odpowiedź w praktyce, patrz: stats.stackexchange.com/a/284399/117305
allando
@AliAbbasinasab Myślę, że Antimony wyjaśnia dobrze. Oczywiście utknięcie w zwykłym punkcie siodłowym nie jest trudne, jak wspominasz w swojej odpowiedzi, ale pokazał tylko możliwość złapania SGD. I dla mnie pokazał kilka niezwykłych punktów siodełka, których SGD nie może uciec.
Kazuya Tomita,
2

Nie powinno.

[ 1 ] wykazał, że spadek gradientu z losową inicjalizacją i odpowiednią stałą wielkością kroku nie zbiega się w punkcie siodłowym. Jest to długa dyskusja, ale aby dać ci wyobrażenie, dlaczego warto zobaczyć następujący przykład:

f(x,y)=12x2+14y412y2

wprowadź opis zdjęcia tutaj

z1=[00],z2=[01],z3=[01]

z2z3z1

z0=[x0]z1z1xR2

2f(x,y)=[1003y21]

2f(z1)xxz1

Allando
źródło
Równie
1
Nie udało mi się dotrzeć do Twojego linku [1] - czy możesz podać pełne cytowanie? W międzyczasie możliwe jest skonstruowanie kontrprzykładów do twojego roszczenia, wskazując, że musi ono być oparte na dodatkowych niepotwierdzonych założeniach.
whuber
@ whuber możesz łatwo przygotować kontrprzykłady. Na przykład, jeśli masz tylko linię jako miejsce. Właśnie próbowałem dodać punkt, który dla wielu może nie być oczywisty (początkowo nie było dla mnie zbyt oczywiste dlaczego). Jeśli chodzi o referencję, nie mam pojęcia, dlaczego nie możesz do niej dotrzeć. Po dwukrotnym sprawdzeniu link jest ważny i również się aktualizuję. Możesz szukać „Gradient Descent Conversges to Minimizers”, Jason D. Lee, Max Simchowitz, Michael I. Jordan † i Benjamin Recht † ♯ Departament Inżynierii Elektrycznej i Informatyki † Wydział Statistcs University of California, Berkeley, 19 kwietnia 2019 „
allando
Dziękuję za referencje. Szybkie spojrzenie na to (link działa teraz) pokazuje, że analiza ogranicza się do „ścisłych siodeł” (gdzie istnieją zarówno dodatnie, jak i ujemne wartości własne Hesji), co wyklucza wiele możliwości. Końcowe stwierdzenia tego artykułu zawierają: „zauważamy, że istnieją bardzo trudne, nieskrępowane problemy z optymalizacją, gdy zawodzi ścisły warunek siodła”, i oferują przykładową kwartyzacyjną minimalizację.
whuber
0

Jeśli przejdziesz do dokumentu, do którego się odwołuje (pokazują także imperialnie, w jaki sposób ich podejście bez siodełka rzeczywiście poprawia się po mini-partii SGD), stwierdzają:

Krok metody opadania gradientu zawsze wskazuje we właściwym kierunku blisko punktu siodełka ... a zatem małe kroki są podejmowane w kierunkach odpowiadających wartościom własnym o małej wartości bezwzględnej.

Zwracają również uwagę na obecność „płaskowyżów” w pobliżu punktów siodełka (innymi słowy, siodło nie jest strome) - w takich przypadkach podjęcie zbyt małych kroków rzeczywiście doprowadziłoby do przedwczesnej zbieżności przed ucieczką z obszaru siodła. Ponieważ jest to optymalizacja niewypukła, konwergencja szybkości uczenia się pogorszyłaby to.

Wydaje się możliwe, że można spróbować zastosować podejście iteracyjne, w którym ponownie uruchamia się mini-partię SGD po jej zakończeniu (tj. Resetowaniu szybkości uczenia się), aby sprawdzić, czy można uciec od problematycznego regionu.

MotiN
źródło
0

Myślę, że problem polega na tym, że zbliżając się do punktu siodłowego, wchodzisz na płaskowyż, czyli obszar o niskich (w wartościach bezwzględnych) gradientach. Zwłaszcza, gdy zbliżasz się z grzbietu. Twój algorytm zmniejsza rozmiar kroku. Przy zmniejszonym rozmiarze kroku wszystkie gradienty (we wszystkich kierunkach) są małe w wartości bezwzględnej. Algorytm zatrzymuje się, myśląc, że jest minimalny.

Jeśli nie zmniejszysz liczby kroków, przeskoczysz ponad minimum i bardzo je przegapisz. Musisz jakoś zmniejszyć rozmiar kroku.

Aksakal
źródło