Jeśli Hesjanie są tak dobrzy do optymalizacji (patrz np . Metoda Newtona ), po co się tu zatrzymywać? Użyjmy trzeciej, czwartej, piątej i szóstej pochodnej? Dlaczego nie?

Interpretuję to pytanie jako „dlaczego metoda Newtona wykorzystuje tylko pierwszą i drugą pochodną, ​​a nie trzecią lub wyższą?”

W rzeczywistości, w wielu przypadkach, przejście do trzeciej pochodnej pomaga; Wcześniej robiłem to z niestandardowymi rzeczami. Jednak ogólnie rzecz biorąc, przejście na wyższe pochodne powoduje złożoność obliczeniową - musisz znaleźć i obliczyć wszystkie te pochodne, a w przypadku problemów wielowymiarowych istnieje znacznie więcej trzecich pochodnych niż pierwszych pochodnych! - to znacznie przewyższa ewentualne oszczędności w liczbie kroków. Na przykład, jeśli mam problem trójwymiarowy, mam 3 pierwsze pochodne, 6 drugie pochodne i 10 trzecie pochodne, więc przejście do wersji trzeciego rzędu ponad dwukrotnie zwiększa liczbę ocen, które muszę wykonać (od 9 do 19), nie wspominając o zwiększonej złożoności obliczania kierunku / wielkości kroku po wykonaniu tych ocen, ale prawie na pewno nie zmniejszy liczby kroków, które muszę podjąć o połowę.

Teraz, w ogólnym przypadku z zmiennych, zbiór pochodnych cząstkowych będzie miał numer , więc w przypadku problemu z pięcioma zmiennymi, całkowita liczba trzeciego , czwarty i piąty częściowe pochodne będą równe 231, ponad 10-krotny wzrost w stosunku do liczby pierwszego i drugiego częściowego pochodnego (20). Musiałbyś mieć problem, który jest bardzo, bardzo bliski wielomianowi piątego rzędu w zmiennych, aby zobaczyć wystarczająco duże zmniejszenie liczby iteracji, aby zrekompensować to dodatkowe obciążenie obliczeniowe.$k$$n^{th}$${k+n-1} \choose {k-1}$

Naprawdę nie rozumiem, jaki jest statystyczny aspekt tego pytania, więc odpowiem na część dotyczącą optymalizacji.

Konwergencja składa się z 2 części: kosztów iteracji i liczby iteracji

Prawie każda odpowiedź tutaj koncentruje się tylko na koszcie iteracji i ignoruje liczbę iteracji . Ale oba mają znaczenie. Metoda, która iteruje w 1 nanosekundę, ale do uzyskania zbieżności nic ci nie da. A metoda, która się wysadzi, też nie pomoże, bez względu na to, jak tani jest koszt iteracji.$10^{20}$

Zastanówmy się, co się dzieje.

Więc: dlaczego nie użyć> instrumentów pochodnych drugiego rzędu?

Częściowo dlatego, że (dotyczy to również drugiego rzędu, ale o tym za chwilę):

Metody wyższego rzędu zazwyczaj zbiegają się szybciej, gdy są bliskie optimum .

Z drugiej strony wybuchają łatwiej, gdy są dalej od optymalnego!

(Oczywiście nie zawsze jest to prawdą; np. Kwadratyka zbiegnie się w 1 kroku metodą Newtona. Ale w przypadku dowolnych funkcji w świecie rzeczywistym, które nie mają ładnych właściwości, jest to na ogół prawda).

Oznacza to, że gdy znajdujesz się dalej od optymalnego, zazwyczaj potrzebujesz metody niskiego rzędu (czytaj: pierwszego rzędu). Dopiero gdy jesteś blisko, chcesz zwiększyć kolejność metody.

Po co więc zatrzymywać się na drugim rzędzie, gdy jesteś blisko korzenia?

Ponieważ „kwadratowe” zachowanie konwergencji jest naprawdę „wystarczająco dobre”!

Aby zrozumieć, dlaczego, musisz najpierw zrozumieć, co oznacza „konwergencja kwadratowa” .

Z matematycznego punktu widzenia konwergencja kwadratowa oznacza, że ​​jeśli jest twoim błędem w iteracji , to w końcu dla niektórych stałych :$\epsilon_k$$k$$c$

$$\lvert\epsilon_{k+1}\rvert \leq c\ \lvert\epsilon_{k}\rvert^2$$

Mówiąc wprost, oznacza to, że gdy znajdziesz się w pobliżu optymalnego (ważne!), Każdy dodatkowy krok podwaja liczbę cyfr dokładności .

Czemu? Łatwo to zobaczyć na przykładzie: dla i masz , itd., Co jest absurdalnie szybkie . (Jest to wykładniczy !)$c = 1$$\lvert\epsilon_1\rvert = 0.1$$\lvert\epsilon_2\rvert \leq 0.01$$\lvert\epsilon_3\rvert \leq 0.0001$

Dlaczego nie zatrzymać się na pierwszym zamówieniu, a nie na drugim?

W rzeczywistości ludzie często to robią, gdy instrumenty pochodne drugiego rzędu stają się zbyt drogie. Ale liniowa konwergencja może być bardzo powolna. np. jeśli masz , to potrzebujesz 10 000 000 iteracji ze zbieżnością liniową, aby uzyskać , ale tylko 23 iteracje ze zbieżnością kwadratową. Możesz więc zobaczyć, dlaczego istnieje drastyczna różnica między zbieżnością liniową i kwadratową. Nie dotyczy to na przykład konwergencji drugiego i trzeciego rzędu (patrz następny akapit).$\epsilon_k = 0.9999999$$\lvert\epsilon\rvert < 0.5$

W tym momencie, jeśli znasz się na informatyce, rozumiesz, że dzięki konwergencji drugiego rzędu problem został już rozwiązany . Jeśli nie rozumiesz dlaczego, oto dlaczego: nie ma nic praktycznego do zyskania dzięki potrojeniu liczby cyfr w każdej iteracji zamiast jej podwojeniu - co ci kupi? Wszakże w komputerze nawet doubledokładna liczba ma 52 bity precyzji, czyli około 16 cyfr dziesiętnych. Może to zmniejszy liczbę wymaganych kroków z 16 do 3 ... co brzmi świetnie, dopóki nie zdasz sobie sprawy, że przychodzi to za cenę obliczania trzecich pochodnych przy każdej iteracji, czyli tam, gdzie przekleństwo wymiarowościuderza cię mocno. W przypadku problemu wymiarowego właśnie zapłaciłeś współczynnik aby uzyskać współczynnik , co jest głupie. A w prawdziwym świecie problemy mają co najmniej setki wymiarów (a nawet tysiące, a nawet miliony), a nie tylko ! Więc zyskujesz współczynnik może 20, płacąc współczynnik, powiedzmy, 20 000 ... nie jest to rozsądny kompromis.$6$$6$$\approx 5$$6$

Ale znowu: pamiętaj, że przekleństwo wymiarowości to połowa historii .

Druga połowa polega na tym, że zazwyczaj gorsze zachowanie jest dalekie od optymalnego, co ogólnie negatywnie wpływa na liczbę iteracji, które musisz wykonać.

Wniosek

W ogólnym ustawieniu metody wyższego rzędu niż 2 są złym pomysłem. Oczywiście, jeśli można przynieść dodatkowe pomocne założeń do tabeli (na przykład dane może nie przypominać wysoki stopień wielomianu, lub masz sposoby ograniczające położenie optimum, etc.), a następnie być może okaże się, że są one dobry pomysł - ale będzie to decyzja związana z konkretnym problemem, a nie ogólna zasada życia.

Nawet obliczanie Hesjan jest dość pracochłonne:

$$H = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}.$$

Zobaczmy teraz, jak wygląda trzecia pochodna: Jest to macierz trójwymiarowa. Oto jak wyglądają jego elementy:

$$\partial H/\partial x=\begin{bmatrix} \dfrac{\partial H}{\partial x_1}\\ \dfrac{\partial H}{\partial x_2}\\ \vdots\\ \dfrac{\partial H}{\partial x_n} \end{bmatrix}$$ $$(\partial H/\partial x)_{ijk}=\dfrac{\partial^3 f}{\partial x_i\partial x_j\partial x_k}$$

Pochodną szóstą będzie macierz :

$$\dfrac{\partial^6 f}{\partial x_i\partial x_j\partial x_k\partial x_l\partial x_m\partial x_n}$$

Zwykle kompromis nie jest korzystny, jeśli chodzi o wyższe niż Heskie. Mam na myśli kompromis między potencjalnym przyrostem prędkości poprzez zastosowanie aproksymacji wyższych rzędów a wzmocnieniem szumu. Zawsze masz szum na wejściu, ponieważ mówimy o zastosowaniach statystycznych. Ten hałas zostanie wzmocniony przez pochodne.

Jeśli grasz w golfa, analogia w optymalizacji polega na tym, aby najpierw uderzyć próbując dostać się do zieleni, nie martw się zbytnio o dołek. Kiedyś na zieleni postawimy celowanie dołka.

Zazwyczaj, gdy analizujesz skuteczność takich algorytmów, znajdziesz wyniki, takie jak jeden krok algorytmu czwartego rzędu mający mniej więcej taką samą skuteczność jak dwa kroki algorytmu drugiego rzędu.

Zatem wybór używanego algorytmu jest stosunkowo prosty: jeśli jeden krok algorytmu czwartego rzędu zajmuje dwa razy więcej pracy lub więcej niż jeden krok algorytmu drugiego rzędu, zamiast tego należy użyć tego drugiego.

Jest to typowa sytuacja dla tego rodzaju metod: klasyczny algorytm ma optymalny stosunek wydajności do wydajności dla ogólnych problemów. Chociaż zdarzają się czasem problemy, w których podejście wyższego rzędu jest niezwykle łatwe do obliczenia i może przewyższyć klasyczny wariant, są one stosunkowo rzadkie.

Kolejność pochodnych można traktować jako kolejność wielomianowego przybliżenia do funkcji. Większość procedur optymalizacji opiera się na wypukłości. Kwadratowy wielomian będzie wszędzie wypukły / wklęsły, podczas gdy wielomian trzeciego rzędu lub wyższy nie będzie wszędzie wypukły. Z tego powodu większość procedur optymalizacji opiera się na kolejnych aproksymacjach funkcji wypukłych z kwadratami. Kwadratowe przybliżenie, które jest wypukłe, wymaga nałożenia warunku dodatniej pozytywności, aby kwadrat był wypukły.

Pozwól mi być tutaj jedyną broniącą metod 3-go rzędu dla konwergencji SGD, ale zdecydowanie nie w całej przestrzeni, co wymagałoby współczynników, ale np. Tylko w jednym kierunku, który potrzebuje tylko jednego dodatkowego współczynnika, jeśli mając już model drugiego rzędu w tym kierunku.$\approx dim^3/6$

Dlaczego jednokierunkowy model trzeciego rzędu może być korzystny? Na przykład ponieważ blisko zera druga pochodna w tym kierunku w zasadzie oznacza dwa alternatywne scenariusze: plateau lub punkt przegięcia - tylko pierwszy wymaga większej wielkości kroku, a trzecia pochodna pozwala je rozróżnić.

Wierzę, że pójdziemy w kierunku hybrydowych metod wielopoziomowych: metody drugiego rzędu w podprzestrzeni o niskim wymiarze np. Z PCA ostatnich gradientów, co wciąż pozwala na swobodne równoczesne opadanie pierwszego rzędu w kierunku części gradientu prostopadłego do tej podprzestrzeni ... i dodatkowo Dodałbym np. Model trzeciego rzędu dla jednego najbardziej odpowiedniego kierunku.