To mnie denerwuje od jakiegoś czasu i nie mogłem znaleźć satysfakcjonujących odpowiedzi online, więc oto:
Po przejrzeniu zestawu wykładów na temat optymalizacji wypukłej metoda Newtona wydaje się znacznie lepszym algorytmem niż zejście gradientu do znajdowania globalnie optymalnych rozwiązań, ponieważ metoda Newtona może zapewnić gwarancję rozwiązania, jest niezmienna afiniczna, a przede wszystkim zbiega się w znacznie mniej kroków. Dlaczego algorytmy optymalizacji drugiego rzędu, takie jak metoda Newtona, nie są tak szeroko stosowane jak stochastyczny spadek gradientu w problemach uczenia maszynowego?
Odpowiedzi:
Spadek gradientu maksymalizuje funkcję, wykorzystując wiedzę o jej pochodnej. Metoda Newtona, algorytm znajdowania pierwiastka, maksymalizuje funkcję, wykorzystując wiedzę o jej drugiej pochodnej. Może to być szybsze, gdy druga pochodna jest znana i łatwa do obliczenia (algorytm Newtona-Raphsona jest stosowany w regresji logistycznej). Jednak analityczne wyrażenie dla drugiej pochodnej jest często skomplikowane lub trudne do rozwiązania, co wymaga wielu obliczeń. Metody numeryczne służące do obliczania drugiej pochodnej wymagają wielu obliczeń - jeśli wartości są potrzebne do obliczania pierwszej pochodnej N 2 wymagane są dla drugiej pochodnej.N. N.2)
źródło
Więcej osób powinno korzystać z metody Newtona w uczeniu maszynowym *. Mówię to jako osoba z doświadczeniem w optymalizacji numerycznej, która od kilku lat zajmuje się uczeniem maszynowym.
Wady w odpowiedziach tutaj (a nawet w literaturze) nie stanowią problemu, jeśli prawidłowo zastosujesz metodę Newtona. Co więcej, wady, które mają znaczenie, również spowalniają opadanie gradientu o tę samą lub więcej, ale przez mniej oczywiste mechanizmy.
Używanie przeszukiwania linii w warunkach Wolfe'a lub używanie lub zaufanie regionów zapobiega zbieżności do punktów siodłowych. Powinno to również robić właściwe wdrożenie spadku gradientu. Papier mowa w odpowiedzi Cam.Davidson.Pilon za wskazuje na problemy z „metody Newtona” w obecności siodło punktów, ale poprawka oni opowiadają się także metoda Newtona.
Zastosowanie metody Newtona nie wymaga zbudowania całego (gęstego) Hesji; możesz zastosować odwrotność Hesjan do wektora za pomocą iteracyjnych metod, które wykorzystują tylko produkty macierz-wektor (np. metody Kryłowa, takie jak gradient sprzężony). Zobacz na przykład metodę regionu zaufania CG-Steihaug.
Możesz efektywnie obliczyć iloczyn macierzowo-wektorowy Hesja, rozwiązując dwa równania przyległe wyższego rzędu w tej samej formie co równanie przyległe, które jest już używane do obliczania gradientu (np. Praca dwóch kroków propagacji wstecznej w szkoleniu sieci neuronowej).
Nieprawidłowe warunkowanie spowalnia konwergencję iteracyjnych solverów liniowych, ale spowalnia jednakowo lub gorzej opadanie gradientu. Zastosowanie metody Newtona zamiast opadania gradientu przesuwa trudność z nieliniowego etapu optymalizacji (gdzie niewiele można zrobić, aby poprawić sytuację) na etap algebry liniowej (gdzie możemy go zaatakować całym arsenałem technik wstępnego warunkowania algebry liniowej).
Ponadto obliczenia zmieniają się z „wielu wielu tanich kroków” na „kilka kosztownych kroków”, otwierając więcej możliwości równoległości na poziomie podetapu (algebra liniowa).
Aby uzyskać podstawowe informacje na temat tych pojęć, polecam książkę „Numerical Optimization” autorstwa Nocedal i Wright.
* Oczywiście, metoda Newtona nie pomoże ci z L1 lub innymi podobnymi skompresowanymi funkcjami wykrywającymi / sparingowymi promującymi kary, ponieważ brakuje im wymaganej gładkości.
źródło
Niedawno się tego nauczyłem - problemem jest rozprzestrzenianie się punktów siodłowych w przestrzeni wielowymiarowej, do którego metody Newtona chcą się zbliżyć. Zobacz ten artykuł: Identyfikacja i atakowanie problemu punktu siodłowego w wielowymiarowej optymalizacji niewypukłej .
źródło
Połączenie dwóch powodów:
Natomiast metoda opadania gradientu nie doprowadzi do punktu siodłowego. Gradient jest zerowy w punkcie siodła, ale niewielki krok odciągnąłby optymalizację, jak widać z gradientu powyżej - jego gradient na zmiennej y jest ujemny.
źródło
Zadaliście dwa pytania: Dlaczego więcej osób nie stosuje metody Newtona i dlaczego tak wiele osób stosuje stochastyczne zejście gradientowe? Te pytania mają różne odpowiedzi, ponieważ istnieje wiele algorytmów, które zmniejszają obciążenie obliczeniowe metody Newtona, ale często działają lepiej niż SGD.
Po drugie, wiele metod, nie tylko spadek gradientu, jest używanych częściej niż Newton; często są one podróbkami metody Newtona w tym sensie, że zbliżają się do kroku Newtona przy niższym koszcie obliczeniowym na krok, ale wymagają większej liczby iteracji w celu uzyskania zbieżności. Kilka przykładów:
Kiedy nie chcesz w ogóle zajmować się przybliżaniem drugich pochodnych, pochylenie gradientu jest atrakcyjne, ponieważ wykorzystuje tylko informacje pierwszego rzędu. Spadek gradientu jest domyślnie zbliżony do odwrotnego Hesji, ponieważ tempo uczenia się pomnożone przez macierz tożsamości. Ja osobiście rzadko używam spadku gradientu: L-BFGS jest równie łatwy do wdrożenia, ponieważ wymaga jedynie określenia funkcji celu i gradientu; ma lepsze odwrotne przybliżenie Hesji niż opadanie gradientu; a ponieważ opadanie gradientu wymaga dostosowania szybkości uczenia się.
Czasami masz bardzo dużą liczbę obserwacji (punktów danych), ale prawie równie dobrze możesz się nauczyć z mniejszej liczby obserwacji. W takim przypadku można użyć „metod wsadowych”, takich jak stochastyczne zejście gradientu, które cyklicznie wykorzystują podzbiory obserwacji.
źródło
Obliczanie kierunku gradientu jest tańsze, a przeszukiwanie linii w tym kierunku jest bardziej niezawodnym i stałym źródłem postępu w kierunku optymalnego. Krótko mówiąc, opadanie gradientu jest względnie niezawodne.
Metoda Newtona jest stosunkowo droga, ponieważ musisz obliczyć Hesję przy pierwszej iteracji. Następnie, przy każdej kolejnej iteracji, możesz albo w pełni ponownie obliczyć Hesję (jak w metodzie Newtona), albo po prostu „zaktualizować” Hesję z poprzedniej iteracji (w metodach quasi-Newtonowych), co jest tańsze, ale mniej niezawodne.
W skrajnym przypadku bardzo dobrze zachowującej się funkcji, zwłaszcza funkcji doskonale kwadratowej, metoda Newtona jest wyraźnym zwycięzcą. Jeśli jest idealnie kwadratowy, metoda Newtona zbiegnie się w jednej iteracji.
W przeciwnym skrajnym przypadku bardzo źle zachowanej funkcji, opadanie gradientu będzie miało tendencję do wygrywania. Wybierze kierunek wyszukiwania, przeszuka ten kierunek i ostatecznie zrobi mały, ale produktywny krok. W przeciwieństwie do tego metoda Newtona może się nie powieść w tych przypadkach, zwłaszcza jeśli spróbujesz użyć przybliżeń quasi-Newtona.
Pomiędzy opadaniem gradientu a metodą Newtona istnieją metody takie jak algorytm Levenberga-Marquardta (LMA), chociaż widziałem, że nazwy są nieco mylone. Istotą jest użycie wyszukiwania opartego na zejściu z pochyłości, gdy sytuacja jest chaotyczna i zagmatwana, a następnie przejście na wyszukiwanie oparte na metodzie Newtona, gdy sytuacja staje się bardziej liniowa i niezawodna.
źródło
Metoda Newtona działa dobrze, gdy jest blisko rozwiązania lub gdy Hesjan powoli się zmienia, ale potrzebuje kilku sztuczek, aby poradzić sobie z brakiem zbieżności i brakiem pewności.
Często szuka się ulepszenia, a nie dokładnego rozwiązania, w którym to przypadku dodatkowy koszt metod Newtona lub podobnych do Newtona nie jest uzasadniony.
Istnieją różne sposoby poprawy powyższego, takie jak zmienna metryka lub metody regionu zaufania.
Na marginesie, w wielu problemach kluczową kwestią jest skalowanie, a Hesjan zapewnia doskonałe informacje o skalowaniu, aczkolwiek kosztem. Jeśli można zbliżyć się do Hesji, często może to znacznie poprawić wydajność. Do pewnego stopnia metoda Newtona zapewnia „najlepsze” skalowanie, ponieważ jest niezmienne afiniczne.
źródło
Istnieje wiele trudności związanych ze stosowaniem metody Newtona w SGD, zwłaszcza:
potrzebuje macierzy Hesji - jak ją oszacować np. na podstawie hałaśliwych gradientów z wystarczającą precyzją przy rozsądnych kosztach?
pełny Hesjan jest zbyt kosztowny - potrzebujemy raczej jego ograniczenia, np. do podprzestrzeni (która podprzestrzeń?),
Metoda Newtona przyciąga bezpośrednio do punktu zerowego z zerowym gradientem ... co zwykle jest tu siodłem. Jak je odeprzeć? Np. Pozbawiony siodła Newton odwraca ujemne kierunki krzywizny, ale wymaga kontrolowania znaków wartości własnych,
dobrze byłoby to zrobić online - zamiast wykonywać wiele obliczeń w jednym punkcie, spróbuj podzielić go na wiele małych kroków wykorzystujących więcej lokalnych informacji.
Możemy przejść od pierwszego rzędu do drugiego rzędu małymi krokami, np. Dodając aktualizację zaledwie 3 średnich do metody pędu, możemy jednocześnie dopasować parabolę MSE w jej kierunku, aby mądrzejszy wybór wielkości kroku ... Modelowanie drugiego rzędu w podprzestrzeni o niskim wymiarze wciąż może używać pozostałych współrzędnych do równoczesnego opadania gradientu.
źródło