25

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?

neural-networks optimization gradient-descent sgd convex Tyler 十三将士归玉门
źródło

6

Czy zdarzyło Ci się kiedyś zejść prosto z grzbietu górskiego, by znaleźć się w dolinie, która prowadzi w dół w innym kierunku? Wyzwaniem jest wyobrazić sobie taką sytuację z wypukłą topografią: pomyśl o krawędzi noża, w której grzbiet jest najbardziej stromy na szczycie.

whuber

4

Nie, ponieważ jest to stochastyczne zejście gradientowe, a nie gradientowe. Cały sens SGD polega na tym, że wyrzucasz niektóre informacje o gradiencie w zamian za zwiększoną wydajność obliczeniową - ale oczywiście odrzucając niektóre informacje o gradientach, nie będziesz już miał kierunku oryginalnego gradientu. To już ignoruje kwestię, czy regularne punkty gradientu w kierunku optymalnego zejścia, ale chodzi o to, że nawet jeśli miało to miejsce przy regularnym spadku, nie ma powodu, aby oczekiwać stochastycznego spadku.

Chill2Macht

3

@Tyler, dlaczego twoje pytanie dotyczy stochastycznego spadku gradientu. Czy wyobrażasz sobie coś innego w porównaniu ze standardowym spadkiem gradientu?

Sextus Empiricus,

2

Gradient zawsze będzie wskazywał na optimum w tym sensie, że kąt między gradientem a wektorem do optimum będzie miał kąt mniejszy niż

i idąc w kierunku gradientu, nieskończenie mała ilość zbliży cię do optimum.

\frac{π}{2}

$\frac{\pi}{2}$

Przywróć Monikę

5

Gdyby gradient wskazywał bezpośrednio na globalny minimalizator, optymalizacja wypukła stałaby się bardzo łatwa, ponieważ moglibyśmy po prostu przeprowadzić jednowymiarowe wyszukiwanie linii, aby znaleźć globalny minimalizator. To za wiele na co można liczyć.

littleO

36

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ę.

Jan Kukacka
źródło

27

A dzisiejszym kontrprzykładem jest ... awokado!

JDL

11

Widzisz, że podczas wycinania awokado, należy ciąć w najbardziej stromym kierunku, aby uniknąć ziaren i możliwej kontuzji .

Jan Kukacka

28

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ę:

y_{i} = e^{- 0.4 x_{i}} - e^{- 0.8 x_{i}} + ϵ_{i}

$y_i = e^{-0.4x_i}-e^{-0.8 x_i} + \epsilon_i$

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

Co skutkuje w:

$S (a, b) = \sum_{i = 1} {(y_{i} - (e^{- a x_{i}} - e^{- b x_{i}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (e^{-ax_i}-e^{-b x_i}) \right)^2$ $\nabla S (a, b) = [\begin{matrix} \sum_{i = 1} 2 x_{i} e^{- a x_{i}} (y_{i} - e^{- a x_{i}} - e^{- b x_{i}}) \\ \sum_{i = 1} - 2 x_{i} e^{- b x_{i}} (y_{i} - e^{- a x_{i}} - e^{- b x_{i}}) \end{matrix}]$ $\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} {(y_{i} - (a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}))}^{2}$ $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{matrix} \sum_{i = 1} - 2 e^{- 0.4 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \\ \sum_{i = 1} 2 e^{- 0.8 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \end{matrix}]$ $\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) = {(y_{i} - (a e^{- 0.4 b x_{i}} - b e^{- 0.8 x_{i}}))}^{2}$ $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{matrix} - 2 e^{- 0.4 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \\ 2 e^{- 0.8 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \end{matrix}]$ $\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

Sextus Empiricus
źródło

17

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$

\nabla f (x) = [\begin{matrix} 2 x_{1} \\ 50 x_{2} \end{matrix}]

$\nabla f(x)= \begin{bmatrix} 2x_1 \\ 50x_2 \end{bmatrix}$

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

x^{(1)} = x^{(0)} - α \nabla f (x^{(0)})

$x^{(1)} =x^{(0)}-\alpha \nabla f\left(x^{(0)}\right)$

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:

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.

Sycorax mówi Przywróć Monikę
źródło

13

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?

pistolety
źródło

3

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").

(x_{0}, y_{0}) = (1, 0)

$(x_0,y_0)=(1,0)$

α

$\alpha$

f (x, α) = \sqrt{α^{2} - α x} .

$f(x,\alpha)=\sqrt{\alpha^2-\alpha x}.$

(f (x_{0}, α) - y_{0})^{2} = α^{2} - α,

$(f(x_0,\alpha)-y_0)^2=\alpha^2-\alpha,$

β

$\beta$

α_{n + 1} = α_{n} - β (2 α_{n} - 1) = α_{n} - (2 α_{n} - 1) = 1 - α_{n} .

$\alpha_{n+1}=\alpha_n-\beta(2\alpha_n-1)=\alpha_n-(2\alpha_n-1)=1-\alpha_n.$

α = \frac{1}{2}

$\alpha=\frac12$ $p=\frac12$

p

$p$

1 - p

$1-p$

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.

Hans Musgrave
źródło

1

β = 1

$\beta=1$

1

Zauważ, że dowód zbieżności SGD zakłada malejący rozmiar kroku ...

Jan Kukacka,

@MartijnWeterings Dobra obserwacja. Wydaje mi się, że mój przykład faktycznie wskazuje właściwy kierunek. Czy powinienem zaktualizować go o przykład 2D, który nigdy nie wskazuje właściwego kierunku i nie jest rozbieżny?

Hans Musgrave,

β = 1

$\beta=1$

β > 0

$\beta>0$

β

$\beta$

f (x, α) = \sqrt{\frac{α^{2} - α x}{β}} .

$f(x,\alpha)=\sqrt{\frac{\alpha^2-\alpha x}{\beta}}.$

f

$f$

β

$\beta$

2

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.

Tolga Birdal
źródło

Czy w przypadku problemów wypukłych gradient w Stochastic Descent Gradient (SGD) zawsze wskazuje na ekstremalną wartość globalną?

Odpowiedzi:

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

Bez wypukłości

W stochastycznym spadku gradientu

Zwykłe opadanie gradientu

Spadek gradientu stochastycznego