Dlaczego wymagane jest zejście gradientowe?

10

Kiedy możemy rozróżnić funkcję kosztu i znaleźć parametry, rozwiązując równania uzyskane przez częściowe różnicowanie w odniesieniu do każdego parametru i dowiedzieć się, gdzie funkcja kosztu jest minimalna. Myślę też, że można znaleźć wiele miejsc, w których pochodne są zerowe, dzięki czemu możemy sprawdzić wszystkie takie miejsca i znaleźć globalne minima

dlaczego zamiast tego wykonuje się opadanie gradientu?

Niranjan Kotha
źródło
2
Jak generalnie ustawić pochodne na 0 dla funkcji? Z algorytmami, takimi jak opadanie gradientu.
Cliff AB
3
Możesz myśleć o spadku gradientu jako o metodzie stosowanej do rozwiązywania równań, o których mówisz. Jeśli nie wierzysz, że możesz generalnie rozwiązać takie równania za pomocą sprytnej manipulacji algebraicznej, zapraszam do spróbowania tego dla regresji logistycznej.
Matthew Drury
3
Prawdopodobne rozwiązywanie
Glen_b
nie możesz rozwiązać wszystkiego analitycznie. Nawet gdybyś mógł, powiedzmy, niezliczoną liczbę zer, zajęłoby dużo czasu sprawdzenie wszystkich punktów krytycznych.
Pinokio

Odpowiedzi:

8

Nawet w przypadku, powiedzmy, modeli liniowych, w których masz rozwiązanie analityczne, nadal może być najlepszym rozwiązaniem zastosowanie takiego rozwiązania iteracyjnego.

Przykładowo, jeśli weźmiemy pod uwagę regresję liniową, jawne rozwiązanie wymaga odwrócenia macierzy o złożoności . Staje się to wygórowane w kontekście dużych zbiorów danych.O(N3)

Ponadto wiele problemów w uczeniu maszynowym jest wypukłych, więc użycie gradientów gwarantuje, że dojdziemy do skrajności.

Jak już wspomniano, nadal istnieją istotne problemy niewypukłe, takie jak sieci neuronowe, w których metody gradientu (propagacja wsteczne) zapewniają skuteczne rozwiązanie. Ponownie jest to szczególnie istotne w przypadku głębokiego uczenia się.

jpmuc
źródło
2
Odwracanie macierzy jest tu trochę słomką, ponieważ rozkład QR z częściowym przechylaniem jest dokładniejszy i szybszy, ale tak, QR wciąż jest . Zgadzam się, że w przypadku wystarczająco dużych systemów (np.> 10 000 zmiennych), które mogą stać się problemem. Nowoczesne, zaawansowane technologicznie podejście polega następnie na zbliżeniu rozwiązania za pomocą iteracyjnych metod podprzestrzeni Kryłowa (np. Gradient sprzężony, GMRES). O(n3)
Matthew Gunn
1
Moim zdaniem niektórzy mogą pomylić to, w jaki sposób rozwiązanie systemu liniowego jest problemem optymalizacyjnym? Odpowiedzią jest oczywiście to, że rozwiązanie układu liniowego można przeformułować jako minimalizujące cel kwadratowy. Niektóre iteracyjne metody rozwiązywania układów liniowych są łatwiejsze do zrozumienia z perspektywy, że minimalizują kwadratowy cel w sposób iteracyjny. (Np. Metoda podprzestrzeni Kryłowa sprzęga kierunek kroku gradientu na podstawie gradientu ... jest to luźno związane z opadaniem gradientu.)
Matthew Gunn
12

Spadek gradientu nie jest wymagany. Okazuje się, że opadanie gradientu jest często okropnie nieefektywnym algorytmem optymalizacji! W przypadku metod iteracyjnych często można znaleźć lepszy kierunek ruchu niż tam, gdzie gradient jest najbardziej stromy.

To trochę krótka odpowiedź. Twoje pytanie powinno naprawdę brzmieć: „dlaczego potrzebujemy metod iteracyjnych?” Na przykład. dlaczego nie przejść od razu do rozwiązania, jeśli problem jest wypukły, utrzymuje się stan Slatera, a warunki pierwszego rzędu są konieczne i wystarczające dla optymalnego? To znaczy, kiedy rozwiązanie można opisać jako rozwiązanie układu równań, dlaczego po prostu nie rozwiązać układu? Odpowiedź brzmi:

  • W przypadku kwadratowego problemu optymalizacji warunkiem pierwszego rzędu jest układ równań liniowych i możemy przejść prawie bezpośrednio do rozwiązania, ponieważ układy liniowe można skutecznie rozwiązać! My nie używać pierwszych warunków zamówienia i rozwiązać układ (np. Z rozkładu QR, caveat poniżej).
  • Mówiąc bardziej ogólnie, warunki pierwszego rzędu definiują nieliniowy układ równań, a układ nieliniowy może być dość trudny do rozwiązania! W rzeczywistości sposób, w jaki często rozwiązujesz układ równań nieliniowych numerycznie, polega na przeformułowaniu go jako problemu optymalizacji ...
  • W przypadku bardzo dużych układów liniowych rozwiązanie układu bezpośrednio z rozkładem QR i częściowym obróceniem staje się niemożliwe. Co robią ludzie?! Metody iteracyjne! (np. iteracyjne metody podprzestrzeni Kryłowa ...)
Matthew Gunn
źródło
7

W rachunku 101 dowiedzieliśmy się, jak zoptymalizować funkcję za pomocą „metody analitycznej”: wystarczy pobrać pochodną funkcji kosztu i ustawić pochodną na 0, a następnie rozwiązać równanie. To naprawdę problem z zabawkami i prawie nigdy nie zdarzy się w prawdziwym świecie.

W świecie rzeczywistym wiele funkcji kosztów nie ma pochodnych (funkcja kosztu może być dyskretna i w ogóle nie może zawierać pochodnych). Ponadto, nawet jeśli potrafisz obliczyć pochodną, ​​nie możesz po prostu rozwiązać równania analitycznie (na przykład zastanów się, jak rozwiązać analitycznie? Mogę powiedzieć, że odpowiedź liczbowa to , ale nie znam rozwiązania analitycznego). Musimy zastosować pewne metody numeryczne (sprawdź dlaczego tutaj na przypadkach wielomianowych Twierdzenie Abla Ruffina ).x7+x352+ex+log(x+x2)+1/x=0x=1.4786

Metody iteracyjne są świetne w użyciu i bardzo intuicyjne w zrozumieniu. Załóżmy, że chcesz zoptymalizować jedną funkcję, zamiast rozwiązać równanie i uzyskać odpowiedź, próbujesz poprawić swoją odpowiedź o liczbę iteracji / kroków po wystarczającej iteracji, otrzymasz odpowiedź zbliżoną do „prawdziwej odpowiedzi”. Powiedzmy, że jeśli użyjesz rachunku różniczkowego do zminimalizowania , otrzymasz bezpośrednio , ale stosując metody numeryczne, możesz otrzymać .f(x)=x2x=0x=1.1234×1020

Ważne jest, aby zrozumieć, jak działają te metody iteracyjne. Kluczową koncepcją jest wiedza o tym, jak zaktualizować parametry wejściowe, aby uzyskać lepsze rozwiązanie. Załóżmy, że chcesz zminimalizować(zauważ, że ta funkcja kosztu nie jest wszędzie różna, ale różniczkowalność ma w „większości miejsc”, jest to dla nas wystarczająco dobre, ponieważ wiemy, jak aktualizować w „większości miejsc”.), obecnie jesteś w , a koszt wynosi , teraz chcesz zaktualizować aby zmniejszyć funkcję celu. Jak byś to zrobił? Możesz powiedzieć, że chcę zmniejszyć zarówno , ale dlaczego? W rzeczywistości używasz niejawnief(x1,x2)=x12+x22+|x1+x2|(1,1)4.0(x1,x2)x1 x2pojęcie gradientu „zmiana małej ilości , co stanie się na ”. xy. W pochodna wynosi , więc ujemny gradient razy szybkość uczenia się mówi , wynosi , więc zaktualizowaliśmy nasze rozwiązanie z do które mają lepszy koszt.(1,1)(3,3)α=0.001(0.003,0.003)1,1(0.997,0.997)

Haitao Du
źródło
więcej informacji można znaleźć w pokrewnym poście
Haitao Du
4

Podane przez ciebie podejście można zastosować tylko do rozwiązania zestawu równań liniowych, na przykład w przypadku regresji liniowej, ale powiedzmy, że do rozwiązania zestawu równań nieliniowych, w przypadkach takich jak sieci neuronowe z aktywacjami sigmoidalnymi, podejściem zejściem gradientowym jest podejście iść po. Zatem zejście gradientowe jest bardziej ogólne.

Nawet w przypadku równań liniowych wielkość macierzy podana przez zbiór równań liniowych jest ogromna i może być trudne ograniczenie wymagań dotyczących pamięci.

Amitoz Dandiana
źródło