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

Wydaje mi się, że jest to podstawowe pytanie i dotyczy samego kierunku gradientu, ale szukam przykładów, w których metody drugiego rzędu (np. BFGS ) są bardziej skuteczne niż proste zejście gradientu.

Oto wspólny schemat interpretacji zarówno gradientu opadania, jak i metody Newtona, co może być przydatnym sposobem, aby potraktować różnicę jako uzupełnienie odpowiedzi @ Sycorax. (BFGS zbliża się do metody Newtona; nie będę tu mówić o tym szczególnie).

Minimalizujemy funkcję , ale nie wiemy, jak to zrobić bezpośrednio. Zamiast tego bierzemy przybliżenie lokalne w naszym obecnym punkcie i minimalizujemy to.$f$$x$

Metoda Newtona aproksymuje funkcję za pomocą rozszerzenia Taylora drugiego rzędu: gdzie oznacza gradient w punkcie a Hesjan w . Następnie do i powtarza.∇ f ( x ) f x ∇ 2 f ( x ) x arg min y N x ( y

$$f(y) \approx N_x(y) := f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y - x)^T \, \nabla^2 f(x) \, (y - x) ,$$ $\nabla f(x)$$f$$x$$\nabla^2 f(x)$$x$$\arg\min_y N_x(y)$

Zejście gradientu, mające tylko gradient, a nie Hesję, nie może po prostu dokonać przybliżenia pierwszego rzędu i zminimalizować go, ponieważ jak zauważył @Hurkyl, nie ma minimum. Zamiast tego definiujemy rozmiar kroku krok do . Pamiętaj jednak, że Tak więc opadanie gradientu minimalizuje funkcję x - t ∇ f ( x ) x - $t$$x - t \nabla f(x)$Gx(y):=f(x)+∇f(x)T(y-x)+

$$\begin{align} x - t \,\nabla f(x) &= \arg\max_y \left[f(x) + \nabla f(x)^T (y - x) + \tfrac{1}{2 t} \lVert y - x \rVert^2\right] \\&= \arg\max_y \left[f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y-x)^T \tfrac{1}{t} I (y - x)\right] .\end{align}$$ $$G_x(y) := f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y-x)^T \tfrac{1}{t} I (y - x).$$

Tak więc metoda gradientu prostego jest trochę jak za pomocą metody Newtona, ale zamiast podejmowania drugiego rzędu Taylor ekspansji, udajemy, że jest Hesji . Ta jest często znacznie gorszym przybliżeniem do niż , a zatem zejście gradientu często ma znacznie gorsze kroki niż metoda Newtona. Jest to oczywiście równoważone przez to, że każdy krok spadku gradientu jest o wiele tańszy do obliczenia niż każdy krok metody Newtona. To, co jest lepsze, zależy całkowicie od charakteru problemu, zasobów obliczeniowych i wymagań dotyczących dokładności.Gf$\tfrac1t I$$G$$f$$N$

Patrząc na przykład @ Sycoraxa minimalizowania kwadratowego , warto zauważyć, że ta perspektywa pomaga zrozumieć obie metody.

$$f(x) = \tfrac12 x^T A x + d^T x + c$$

Dzięki metodzie Newtona otrzymamy dzięki czemu zakończy się ona dokładną odpowiedzią (aż do problemów z dokładnością zmiennoprzecinkową) w jednym kroku.$N = f$

Z kolei gradient opadający używa którego płaszczyzna styczna w punkcie wynosi poprawne, ale którego krzywizna jest całkowicie błędna i faktycznie odrzuca ważne różnice w różnych kierunkach, gdy wartości własne różnią się znacznie.

$$G_x(y) = f(x) + (A x + d)^T y + \tfrac12 (x - y)^T \tfrac1t I (x-y)$$ $x$$A$

Zasadniczo zaletą metody drugiej pochodnej, takiej jak metoda Newtona, jest to, że ma jakość zakończenia kwadratowego. Oznacza to, że może zminimalizować funkcję kwadratową w skończonej liczbie kroków. Metoda taka jak opadanie gradientu zależy w dużej mierze od szybkości uczenia się, co może powodować, że optymalizacja albo zbiega się powoli, ponieważ odbija się wokół wartości optymalnej, albo całkowicie się różni. Można znaleźć stabilne wskaźniki uczenia się ... ale wymagają obliczenia hessian. Nawet przy stabilnym tempie uczenia się możesz mieć problemy takie jak oscylacja wokół optymalnego, tzn. Nie zawsze wybierzesz ścieżkę „bezpośrednią” lub „wydajną” w kierunku minimum. Może to potrwać wiele iteracji, nawet jeślijesteś stosunkowo blisko. BFGS i metoda Newtona mogą zbiegać się szybciej, nawet jeśli wysiłek obliczeniowy każdego kroku jest droższy.

Na prośbę o przykłady: Załóżmy, że masz funkcję celu Gradient to i wprowadzenie do najbardziej stromej formy zniżania ze stałą szybkością uczenia się

$$F(x)=\frac{1}{2}x^TAx+d^Tx+c$$ $$\nabla F(x)=Ax+d$$ $$x_{k+1}= x_k-\alpha(Ax_k+d) = (I-\alpha A)x_k-\alpha d.$$

Będzie to stabilne, jeśli wielkości wektorów własnych będą mniejsze niż 1. Możemy użyć tej właściwości, aby pokazać, że stabilna szybkość uczenia się spełnia gdzie jest największą wartością własną . Współczynnik zbieżności algorytmu najbardziej stromego jest ograniczony przez największą wartość własną, a procedura zbiega się najszybciej w kierunku odpowiadającego jej wektora własnego. Podobnie będzie on zbiegał się najwolniej w kierunkach wektora własnego najmniejszej wartości własnej. Gdy występuje duża różnica między dużymi i małymi wartościami własnymi dla , opadanie gradientu będzie powolne. Dowolny$I-\alpha A$

$$\alpha<\frac{2}{\lambda_{max}},$$ $\lambda_{max}$$A$$A$$A$ z tą właściwością będzie powoli zbiegać się przy użyciu opadania gradientu.

W szczególnym kontekście sieci neuronowych książka Neural Network Design zawiera sporo informacji na temat numerycznych metod optymalizacji. Powyższa dyskusja stanowi kondensację rozdziału 9-7.

$$f(x)=c+\beta x + \alpha x^2$$

$$\partial^2 f(x)/\partial x^2=2\alpha$$

$$\text{guess}=-\frac{\beta}{2\alpha}$$

Przypadek wielowymiarowy jest bardzo podobny, wystarczy użyć gradientów dla instrumentów pochodnych.

@Dougal już dał świetną odpowiedź techniczną.

Wyjaśnienie bez matematyki polega na tym, że podczas gdy przybliżenie liniowe (rząd 1) zapewnia „płaszczyznę”, która jest styczna do punktu na powierzchni błędu, przybliżenie kwadratowe (rząd 2) zapewnia powierzchnię, która obejmuje krzywiznę powierzchni błędu.

Filmy w tym linku świetnie odwzorowują tę koncepcję. Wyświetlają przybliżenia rzędu 0, rzędu 1 i rzędu 2 na powierzchni funkcji, co po prostu intuicyjnie weryfikuje matematycznie pozostałe odpowiedzi.

Dobry blog na ten temat (dotyczący sieci neuronowych) jest tutaj .