Dlaczego metoda Newtona nie jest szeroko stosowana w uczeniu maszynowym?

131

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?

Fei Yang
źródło
23
W przypadku sieci neuronowych sekcja deeplearningbook.org Sekcja „8.6 Przybliżone metody drugiego rzędu” zawiera ładny przegląd. Podsumowując: „Oprócz wyzwań związanych z niektórymi cechami funkcji celu, takimi jak punkty siodłowe, zastosowanie metody Newtona do szkolenia dużych sieci neuronowych jest ograniczone przez znaczne obciążenie obliczeniowe”. Istnieją alternatywy, które próbują uzyskać niektóre zalety metody Newtona, omijając przeszkody obliczeniowe, ale mają swoje własne problemy.
Franck Dernoncourt
1
zobacz to powiązane pytanie i komentarze, stats.stackexchange.com/questions/232305/…
Haitao Du
1
Należy zauważyć, że pozostałe komentarze mają szersze zastosowanie w uczeniu maszynowym niż tylko „głębokie uczenie się”. Jednak chociaż wszystkie problemy związane z ML mogą mieć charakter „dużych zbiorów danych”, nie wszystkie problemy z ML są koniecznie „dużymi cechami” (tj. Wieloma parametrami do dostrojenia), choć niezmiennie głębokie uczenie się.
GeoMatt22,
1
Warto zauważyć, że w uczeniu maszynowym poza głębokim uczeniem się, L-BFGS (który w przybliżeniu przybliża metodę Newtona) jest dość powszechnym algorytmem optymalizacji.
Dougal
2
Metoda Newtona zakłada wypukłość, współczesne problemy ML (sieci neutralne) prawdopodobnie nie są prawie wypukłe, choć niewątpliwie jest to obszar otwartych badań. Dlatego metoda Newtona jest prawdopodobnie tak samo zła jak estymator jak liniowa w dowolnym miejscu, ale w pobliżu punktu obliczeniowego. Prawdopodobnie zyskasz bardzo niewiele za kwadratowy wzrost obliczeń. To powiedziawszy, na niedawnej konferencji w Berkeley prezenter nadal wykazywał postępy w stosowaniu metod drugiego rzędu, więc w żadnym wypadku nie jest martwy.
David Parks

Odpowiedzi:

95

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)

jwimberley
źródło
5
Warto zauważyć, że (rzeczy oparte na) metoda Gaussa-Newtona jest prawdopodobnie bardziej powszechna. Jest to specjalizacja Newtona do nieliniowych najmniejszych kwadratów.
GeoMatt22,
4
Nie nazwałbym Gaussa-Newtona specjalizacją Newtona dla nieliniowych najmniejszych kwadratów. Nazwałbym to druzgoceniem aproksymacji Newtona dla nieliniowych najmniejszych kwadratów, która wykorzystuje bardziej niedokładne aproksymacje Hesji, im większe są resztki w dopasowanych równaniach, a zatem tym bardziej argument jest oparty na optymalności.
Mark L. Stone,
1
@ MarkL.Stone uczciwy punkt, starałem się nie wchodzić w szczegóły techniczne :) Prawdą jest, że metody w stylu Gaussa-Newtona próbują „sfałszować” drugie zamówienie z informacjami tylko pierwszego rzędu. Osobiście nigdy nie korzystałem z metod Newtona do optymalizacji, tylko metod Gaussa-Newtona (lub LM lub ~ podobnych UKF) lub DFO-SQP (np. BOBYQA ). „Optymalność” jest trudnym pytaniem, które powiedziałbym ... w przypadku problemu ML, w porównaniu do problemu inżynieryjnego optymalizacji projektu, niezawodność / informatywność „lokalnego Hesji” może być wątpliwa. Być może nielokalny DFO-SQP to „stochastyczny Newton”? (np. „online”)
GeoMatt22
1
Z drugiej strony podejścia DFO-SQP wydają się być nielokalne w przestrzeni parametrów , a nie w partiach danych. UKF może być najbliższy w smaku do „stochastycznego Newtona”, ponieważ jest on-line w / ograniczonej pamięci ... ale skutecznie zakłada pozytywny-definitywna Hesji (tj Gaussa ok.).
GeoMatt22,
1
W rzeczywistości jest to mylący powód, ponieważ istnieją metody drugiego rzędu, takie jak CG, które nie wymagają obliczania hessian. k iteracje CG będą kosztować tylko kN. To prawda, że ​​CG teoretycznie pasowałby do Newtona tylko przy k = N, ale tak naprawdę nie potrzebujesz tak wielu iteracji.
user25322,
40

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.

Nick Alger
źródło
2
Myślę, że jesteśmy w brutalnej umowie ze sobą, nie ze wszystkimi innymi.
Mark L. Stone,
1
To tak, jakby porównać, czy Wielka Brytania lub USA produkują lepszych matematyków badawczych, porównując zdolności matematyczne 26-letnich uczniów szkół średnich uzależnionych od narkotyków, a nie porównując najwyższy poziom wśród absolwentów matematyki pochodzących z najlepszych szkół w każdym kraju. Papier jest podpisany, zapieczętowany i dostarczony, nikt, i mam na myśli, że nikt go teraz nie zmienia ani nie wycofuje. Niewzruszony.
Mark L. Stone,
3
@ MarkL.Stone Wygląda na to, że rozmowa miała miejsce tutaj i została usunięta, gdy mnie nie było. W każdym razie myślę, że masz rację, że zgadzamy się ze sobą i nikim innym. Wydaje mi się, że należy tego oczekiwać w oparciu o nasze pochodzenie w porównaniu z innymi osobami tutaj. Jak zapewne się spodziewasz, nie myślę zbyt wiele o powiązanym dokumencie. Z drugiej strony wydaje mi się, że metoda rozmaitości Riemanniana oparta na rozmaitości Newtona , w której wykonuje się geodezyjną trajektorię w kierunku poszukiwań Newtona, jest techniką z dużą szansą na bardzo trudne problemy.
Nick Alger,
2
Jak poradziłbyś sobie z dużym zestawem treningowym? Jeśli masz np. 1 milion próbek treningowych, to tylko ocena bieżącego celu optymalizacji wymaga przetestowania 1 miliona próbek. I musisz to zrobić wiele razy podczas wyszukiwania linii. Tak więc, zanim zrobisz 1 krok Newtona, Stochastic Gradient Descent wykona kilka milionów aktualizacji.
nikie
2
Nick i @ MarkL.Stone: Czy mówisz o takim podejściu ? Jest to coś, co było na krótko popularne w głębokim uczeniu się, szczególnie w sieciach nawracających, ale od tego czasu wyszło mi z założenia, że ​​zakładam, że po prostu nie działało empirycznie o wiele lepiej niż metody gradientu adaptacyjnego. Jeśli po prostu robią coś złego, a ty naprawisz cokolwiek to jest i pokażesz, że ogólnie przewyższa obecny standardowy wariant SGD Adam, możesz wywrzeć duży wpływ: artykuł Adama miał 1345 cytowań w ciągu dwóch lat ....
Dougal
33

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 .

Rzeczywiście stosunek liczby punktów siodłowych do lokalnych minimów rośnie wykładniczo wraz z wymiarowością N.

Podczas gdy dynamika opadania gradientu jest odpychana od punktu siodłowego do mniejszego błędu przez kierowanie się ujemnymi krzywiznami, ... metoda Newtona nie traktuje odpowiednio punktów siodłowych; jak argumentowano poniżej, punkty siodłowe stają się atrakcyjne pod dynamiką Newtona.

Cam.Davidson.Pilon
źródło
3
Czy możesz dodać wyjaśnienie, dlaczego tak jest? Teoretycznie metoda Newtona wykonuje ważone opadanie gradientu o „optymalnych” wagach dla każdego z wektorów własnych.
nbubis
4
To, co mówi ten artykuł o metodach Newtona „chcących” zejść się do punktów siodłowych, dotyczy tylko śmieciowych implementacji metody Newtona.
Mark L. Stone,
Artykuł ponownie parametryzuje problem pod względem wartości własnych i wektorów własnych i wykorzystuje to, aby pokazać, że spadek gradientu oddala się od punktu siodłowego: porusza się w kierunku punktu siodłowego w kierunku ujemnych wektorów elektronicznych, ale oddala się w kierunku pozytywne wektory elektroniczne, więc ostatecznie opuszcza punkt siodłowy. Z drugiej strony Newton nie ma takiej gwarancji.
Elizabeth Santorella,
Jednak nowym algorytmem, który popierają w tym artykule, jest (wariant) metody Newtona. jest to w zasadzie metoda Newtona dla kierunków krzywizny dodatniej i ujemna metoda Newtona dla kierunków krzywizny ujemnej.
Nick Alger
26

Połączenie dwóch powodów:

  • Metoda Newtona przyciąga do punktów siodłowych;
  • punkty siodłowe są powszechne w uczeniu maszynowym lub w rzeczywistości przy optymalizacji wielu zmiennych.

fa=x2)-r2)
wprowadź opis zdjęcia tutaj

xn+1=xn-[H.fa(xn)]-1fa(xn)

H.=[2)fax12)2)fax1x2)2)fax1xn2)fax2)x12)fax2)2)2)fax2)xn2)faxnx12)faxnx2)2)faxn2)].

H.=[2)00-2)]

[H.fa]-1=[1/2)00-1/2)]

fa=[2)x-2)r]

[xr]n+1=[xr]n-[1/2)00-1/2)][2)xn-2)rn]=[xr]n-[xr]n=[00]

x=0,r=0

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.

Aksakal
źródło
1
Dzięki tobie właściwie zrozumiałem, jak ta metoda działa od A do Z, więc bardzo dziękuję za ten jasny przykład!
greenoldman
Jaki byłby tutaj ulubiony punkt?
Ben
14

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.

H.O(N.2))N.solO(N.)H.-1solO(N.3))wyliczyć, określić, skalkulować. Tak więc, podczas gdy obliczanie Hesji jest drogie, odwracanie go lub rozwiązywanie najmniejszych kwadratów jest często jeszcze gorsze. (Jeśli masz rzadkie cechy, asymptotyki wyglądają lepiej, ale inne metody również działają lepiej, więc rzadkość nie czyni Newtona względnie bardziej atrakcyjnym.)

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:

  • H.-1

  • O(N.2))

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

Elizabeth Santorella
źródło
(+1) Warto zauważyć, że L-BFGS ma ten sam rząd złożoności co opadanie gradientu w odniesieniu do liczby parametrów. Nie dotyczy to BFGS. Więc nie tylko ograniczona pamięć L-BFGS czyni ją atrakcyjną.
Cliff AB
12

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.

Nat
źródło
3
Chłopcze, musisz użyć okropnych implementacji Newtona i Quasi-Newtona. Jeśli używasz albo z nie dodatnim określonym Hesjanem, albo użyj regionów zaufania lub przeszukaj linię wzdłuż kierunku (-ów) ujemnej krzywizny. Jeśli tak, są WIĘCEJ niezawodne niż najbardziej strome zejście (tj. Zejście gradientowe z wyszukiwaniem linii lub regionem zaufania). Krótko mówiąc, opadanie stopni jest znacznie mniej niezawodne niż poprawnie zaimplementowana metoda Quasi-Newtona, która jest mniej niezawodna niż poprawnie zaimplementowana metoda Newtona. Czas obliczeń i wymagania dotyczące pamięci na iterację to jednak inna sprawa.
Mark L. Stone,
4
Myślę, że masz na myśli idealnie kwadratową funkcję. Oznacza to, że metoda Newtona zbiega się w jednej iteracji z kwadratową funkcją celu, która ma liniowy gradient.
Elizabeth Santorella
1
@ElizabethSantorella: Tak, masz rację! Zaktualizowałem odpowiedź.
Nat
2
1/2)xT.x
1
Zrobiłem moją sprawę. jeśli chcesz myśleć o najbardziej stromym zejściu, zjazd w gradiencie jest wspaniały, szczególnie w przypadku źle wychowanych funkcji, to twoja sprawa. Ogłusz się.
Mark L. Stone,
7

H.re=sol

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.

copper.hat
źródło
0

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ń?),

  • H.-1λ=0

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

Jarek Duda
źródło