Biorąc pod uwagę funkcję wypukłego kosztu, wykorzystującą SGD do optymalizacji, będziemy mieli gradient (wektor) w pewnym punkcie podczas procesu optymalizacji.

Moje pytanie brzmi: biorąc pod uwagę punkt na wypukłości, czy gradient wskazuje tylko w kierunku, w którym funkcja rośnie / zmniejsza się najszybciej, czy gradient zawsze wskazuje na optymalny / skrajny punkt funkcji kosztu ?

Pierwsza z nich to koncepcja lokalna, druga to koncepcja globalna.

SGD może ostatecznie zbliżyć się do ekstremalnej wartości funkcji kosztu. Zastanawiam się nad różnicą między kierunkiem gradientu podanym dowolnym punktem na wypukłym a kierunkiem wskazującym na ekstremalną wartość globalną.

Kierunek gradientu powinien być kierunkiem, w którym funkcja zwiększa się / zmniejsza najszybciej w tym punkcie, prawda?

Mówią, że obraz jest wart więcej niż tysiąc słów. W poniższym przykładzie (dzięki uprzejmości MS Paint, poręcznego narzędzia zarówno dla amatorskich, jak i profesjonalnych statystyków) widać wypukłą powierzchnię funkcji i punkt, w którym kierunek najbardziej stromego zejścia wyraźnie różni się od kierunku w kierunku optymalnego.

Mówiąc poważnie: w tym wątku są o wiele lepsze odpowiedzi, które również zasługują na aprobatę.

• Metody zejścia gradientowego wykorzystują nachylenie powierzchni.
• Będzie to nie koniecznie (lub nawet najprawdopodobniej nie) punkt bezpośrednio do punktu skrajnego.

Intuicyjnym widokiem jest wyobrażenie sobie ścieżki zejścia, która jest zakrzywioną ścieżką. Zobacz na przykład poniższe przykłady.

Jako analogię: wyobraź sobie, że zasłaniam ci oczy i umieszczam cię gdzieś na górze z zadaniem powrotu do skrajnego (niskiego) punktu. Na wzgórzu, jeśli masz tylko lokalne informacje, to jesteś nie wiedząc, w jakim kierunku będzie dno jeziora.

Jeśli możesz założyć wypukłość

• Wtedy wiesz, że jest tylko jeden skrajny punkt.
• Wtedy wiesz, że na pewno dotrzesz do skrajnego punktu, dopóki schodzisz w dół.
• $\pi/2$

Bez wypukłości

• $\pi/2$

  W przypadku wypukłego problemu nie jest to możliwe. Można to odnieść do izolinii dla funkcji kosztu mającej krzywiznę w tym samym kierunku, gdy problem jest wypukły.

W stochastycznym spadku gradientu

• Podążasz za najbardziej stromym kierunkiem dla pojedynczego punktu (i wielokrotnie robisz krok dla innego punktu). W tym przykładzie problem jest wypukły, ale może istnieć więcej niż jedno rozwiązanie. W tym przykładzie wartości ekstremalne są na linii (zamiast jednego punktu) iz tego konkretnego punktu widzenia można powiedzieć, że najbardziej stromy kierunek zniżania może wskazywać bezpośrednio na „optymalne” (chociaż jest to tylko optymalne dla funkcji tego konkretnego punktu próbki szkolenia)

Poniżej znajduje się inny widok dla czterech punktów danych . Każdy z czterech obrazów pokazuje powierzchnię dla innego pojedynczego punktu. Na każdym kroku wybierany jest inny punkt, wzdłuż którego obliczany jest gradient. To sprawia, że ​​są tylko cztery kierunki, wzdłuż których jest wykonywany krok, ale rozmiary kroków zmniejszają się, gdy zbliżamy się do rozwiązania.

Powyższe obrazy dotyczą 4 punktów danych wygenerowanych przez funkcję:

x = 0      2      4      6           
y = 0.006  0.249  0.153  0.098

Co skutkuje w:

• $$S(a,b) = \sum_{i=1} \left( y_i - (e^{-ax_i}-e^{-b x_i}) \right)^2$$ $$\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} 2 x_i e^{-a x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \\ \sum_{i=1} -2 x_i e^{-b x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \end{bmatrix}$$

• $$S(a,b) = \sum_{i=1} \left( y_i - (a e^{-0.4 x_i}- b e^{-0.8 x_i} )\right)^2$$ $$\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ \sum_{i=1} 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$$

• $i$

  $$S(a,b) = \left( y_i - (a e^{-0.4 b x_i}- b e^{-0.8 x_i}) \right)^2$$ $$\nabla S(a,b) = \begin{bmatrix} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$$ $a$$b$$S = 0$

Napisane przez StackExchangeStrike

Strome zejście może być nieefektywne, nawet jeśli funkcja celu jest mocno wypukła.

Zwykłe opadanie gradientu

Mam na myśli „nieefektywny” w tym sensie, że najbardziej strome zejście może powodować kroki, które oscylują daleko od optymalnego, nawet jeśli funkcja jest mocno wypukła lub nawet kwadratowa.

$f(x)=x_1^2 + 25x_2^2$$x=[0,0]^\top$

$\alpha=0.035$$x^{(0)}=[0.5, 0.5]^\top,$

który wykazuje ten niesamowicie oscylujący postęp w kierunku minimum.

$\theta$$(x^{(i)}, x^*)$$(x^{(i)}, x^{(i+1)})$

$x_2$$x_1$$\nabla^2 f(x)$

Bezpośrednią ścieżką do minimum byłoby poruszanie się „po przekątnej” zamiast w ten sposób, który jest silnie zdominowany przez oscylacje pionowe. Zejście gradientowe zawiera jednak tylko informacje o lokalnej stromości, więc „nie wie”, że strategia byłaby bardziej wydajna i podlega kaprysu Hesji, który ma wartości własne w różnych skalach.

Spadek gradientu stochastycznego

SGD ma te same właściwości, z tą różnicą, że aktualizacje są głośne, co oznacza, że ​​powierzchnia konturu wygląda inaczej z jednej iteracji na drugą, a zatem gradienty również są różne. Oznacza to, że kąt między kierunkiem kroku gradientu a optymalnym również będzie powodował szum - wyobraź sobie te same wykresy z pewnym drżeniem.

Więcej informacji:

• Czy możemy zastosować analityczność sieci neuronowej w celu poprawy po spadku gradientu?

• Dlaczego pochodne drugiego rzędu są przydatne w optymalizacji wypukłej?

• Jak zmiana funkcji kosztów może być dodatnia?

Ta odpowiedź zapożycza ten przykład i rysunek z Neural Networks Design (wyd. 2) Rozdział 9 autorstwa Martina T. Hagana, Howarda B. Demutha, Marka Hudsona Beale'a, Orlando De Jesús.

Lokalny najbardziej stromy kierunek różni się od globalnego optymalnego kierunku. Gdyby tak było, kierunek gradientu nie zmieniłby się; ponieważ jeśli zawsze dążysz do swojego optimum, wektor kierunku zawsze wskazywałby optimum. Ale tak nie jest. Jeśli tak, to po co zawracać sobie głowę obliczaniem gradientu przy każdej iteracji?

Inne odpowiedzi podkreślają pewne irytujące problemy dotyczące współczynnika konwergencji dla GD / SGD, ale twój komentarz „SGD może się zbiegać ...” nie zawsze jest poprawny (ignorując pedantyczne uwagi na temat użycia słowa „może”, ponieważ wydaje się, że miałeś na myśli "Wola").

Nie jestem pewien, czy wypukłość jest wystarczająca, aby przełamać gorsze zachowanie, które istnieje w przypadku ogólnego SGD, ale jeśli dopuścisz funkcje nawet tak złożone jak sześcienne dla twojej funkcji kosztu, SGD może podskakiwać na gęstym podzbiorze domeny i nigdy nie zbiegać się nigdzie lub zbliżyć się do dowolnego cyklu.

$\infty$$\pm\infty$

Interesującą rzeczą w całej sytuacji jest to, że istnieje niezliczona ilość funkcji (takich jak SGD), które przyjmują dowolne funkcje wypukłe jako dane wejściowe, a następnie generują regułę aktualizacji, która zawsze szybko zbiega się do globalnego minimum (jeśli taka istnieje). Chociaż koncepcyjnie istnieje ich mnóstwo, nasze najlepsze próby optymalizacji wypukłej mają patologiczne kontrprzykłady. Jakoś pomysł prostej / intuicyjnej / wydajnej reguły aktualizacji jest sprzeczny z ideą możliwej do udowodnienia poprawnej reguły aktualizacji.

Być może odpowiedzi na to pytanie wymagają szybkiej aktualizacji. Wygląda na to, że SGD daje globalne minimum także w przypadku niewypukłym (wypukły jest tylko specjalnym przypadkiem):

SGD zbiega się do globalnego minimum w głębokim uczeniu się poprzez Star-Convex Path, anonimowi autorzy , artykuł pod podwójną ślepą recenzją na ICLR 2019

https://openreview.net/pdf?id=BylIciRcYQ

Autorzy ustalili konwergencję SGD do globalnego minimum dla niepoprawnych problemów optymalizacyjnych, które często występują w szkoleniu sieci neuronowej. Argument wykorzystuje następujące dwie ważne właściwości: 1) utrata treningu może osiągnąć wartość zerową (w przybliżeniu); 2) SGD podąża ścieżką wypukłą gwiazdy. W takim kontekście, chociaż SGD od dawna uważany jest za algorytm randomizowany, praca ujawnia, że ​​zbiega się on w sposób wewnętrznie deterministyczny do globalnego minimum.

Należy to jednak wziąć z odrobiną soli. Artykuł jest nadal w trakcie przeglądu.

Pojęcie ścieżki wypukłej gwiazdy daje wskazówkę w kierunku, w którym gradient wskazywałby przy każdej iteracji.