Jakie są alternatywy Gradient Descent?

46

Zejście z gradientem ma problem z utknięciem w lokalnych minimach. Musimy uruchomić czasy wykładnicze spadku gradientu, aby znaleźć globalne minima.

Czy ktoś może mi powiedzieć o jakichkolwiek alternatywach gradientu zejścia stosowanych w uczeniu się sieci neuronowej, a także o ich zaletach i wadach.

Tropa
źródło

Odpowiedzi:

38

Jest to bardziej problem ze zminimalizowaniem funkcji niż zastosowana metoda, jeśli znalezienie prawdziwego globalnego minimum jest ważne, zastosuj metodę o takim symulowanym wyżarzaniu . Będzie to w stanie znaleźć globalne minimum, ale może to zająć bardzo dużo czasu.

W przypadku sieci neuronowych lokalne minima niekoniecznie stanowią tak duży problem. Niektóre lokalne minima wynikają z faktu, że można uzyskać funkcjonalnie identyczny model, dopuszczając jednostki ukrytej warstwy lub negując wagi wejściowe i wyjściowe sieci itp. Również jeśli lokalne minima są tylko nieznacznie nieoptymalne, to różnica w wydajności będzie minimalna, więc nie będzie miała znaczenia. Wreszcie, i jest to ważny punkt, kluczowym problemem przy dopasowywaniu sieci neuronowej jest nadmierne dopasowanie, więc agresywne poszukiwanie globalnych minimów funkcji kosztu prawdopodobnie doprowadzi do nadmiernego dopasowania i modelu, który działa słabo.

Dodanie terminu regularyzacji, np. Zaniku masy ciała, może pomóc w wygładzeniu funkcji kosztów, co może nieco zmniejszyć problem lokalnych minimów i jest to coś, co i tak poleciłbym jako sposób na uniknięcie przeregulowania.

Najlepszym sposobem uniknięcia lokalnych minimów w sieciach neuronowych jest jednak zastosowanie modelu Procesu Gaussa (lub sieci neuronowej Radial Basis Function), które mają mniej problemów z lokalnymi minimami.

Dikran Torbacz
źródło
9
Bardzo prawdziwe. Problem nieosiągnięcia globalnego minimum jest przereklamowany.
bayerj
2
Przeregulowanie ma miejsce, gdy używasz wielu parametrów w modelu (typowy przypadek użycia NN), nie jest to związane z lokalnymi minimami - przynajmniej nie w oczywisty sposób. Możesz utknąć w złym lokalnym minimum, nawet z niewielkim NN, tj. Z bardzo małą liczbą wolnych parametrów.
carlosayam
1
L(ω)=(x(1)ω)2+(x(2)ω)2x(1),x(2)ω. Łatwo zauważyć, że między dwoma kolejnymi punktami istnieje lokalne minimum, tj. Im więcej danych, tym więcej lokalnych minimów! Globalny jest osiągany między najbliższymi punktami zestawu danych. To ekstremalne, wiem, ale widziałem podobne zachowanie rozwiązujące problemy z punktem zmiany.
carlosayam
1
@DikranMarsupial - Nie miałem wystarczająco dużo znaków, aby dokończyć zdanie :) Widziałem podobne zachowanie rozwiązujące problemy z punktem zmiany ... za pomocą sieci neuronowych. W tego rodzaju problemach lokalne minimum jest zwykle złe; więc nie zgadzam się, że ten problem jest przereklamowany.
carlosayam
1
@carlosayam „przereklamowany” nie oznacza „nieważny”, tylko że jest to problem z zawyżonymi sieciami neuronowymi. Zawsze będzie problem ze wszystkimi metodami uczenia się, nie ma panaceum na wszystko i zawsze trzeba zdiagnozować problemy z dowolnym modelem.
Dikran Marsupial
24

Spadek gradientu jest algorytmem optymalizacji .

Istnieje wiele algorytmów optymalizacji, które działają na stałej liczbie od rzeczywistych wartości , które są skorelowane ( nierozłączne ). Możemy je z grubsza podzielić na 2 kategorie: optymalizatory gradientowe i optymalizatory bez pochodnych. Zwykle chcesz użyć gradientu do optymalizacji sieci neuronowych w nadzorowanym ustawieniu, ponieważ jest to znacznie szybsze niż optymalizacja bez pochodnych. Istnieje wiele algorytmów optymalizacji opartych na gradiencie, które zostały wykorzystane do optymalizacji sieci neuronowych:

  • Stochastic Gradient Descent (SGD) , minibatch SGD, ...: Nie musisz oceniać gradientu dla całego zestawu treningowego, ale tylko dla jednej próbki lub minibatchu próbek, jest to zwykle znacznie szybsze niż opadanie gradientu serii. Minibatche zostały użyte do wygładzenia gradientu i zrównoleglenia propagacji do przodu i do tyłu. Zaletą wielu innych algorytmów jest to, że każda iteracja ma wartość O (n) (n to liczba wag w Twojej NN). SGD zwykle nie utknie w lokalnych minimach (!), Ponieważ jest stochastyczny.
  • Nieliniowy gradient koniugatu : wydaje się być bardzo skuteczny w regresji, O (n), wymaga gradientu partii (stąd może nie być najlepszym wyborem dla dużych zestawów danych)
  • L-BFGS : wydaje się być bardzo skutecznym w klasyfikacji, wykorzystuje przybliżenie Hesji, wymaga gradientu partii
  • Algorytm Levenberga-Marquardta (LMA) : To właściwie najlepszy algorytm optymalizacji, jaki znam. Wadą jest to, że jego złożoność wynosi w przybliżeniu O (n ^ 3). Nie używaj go do dużych sieci!

Zaproponowano wiele innych algorytmów optymalizacji sieci neuronowych, możesz znaleźć w Google optymalizację bez Hesji lub v-SGD (istnieje wiele rodzajów SGD z adaptacyjnymi wskaźnikami uczenia się, patrz np. Tutaj ).

Optymalizacja pod kątem NN nie jest rozwiązanym problemem! Z moich doświadczeń wynika, że ​​największym wyzwaniem nie jest znalezienie dobrego lokalnego minimum. Wyzwanie polega jednak na wydostaniu się z bardzo płaskich regionów, radzeniu sobie ze źle uwarunkowanymi funkcjami błędów itp. Z tego powodu LMA i inne algorytmy wykorzystujące aproksymacje Hesji zwykle działają tak dobrze w praktyce, a ludzie próbują opracować wersje stochastyczne wykorzystujące informacje drugiego rzędu o niskiej złożoności. Jednak często bardzo dobrze dostrojony zestaw parametrów dla minibatch SGD jest lepszy niż jakikolwiek złożony algorytm optymalizacji.

Zwykle nie chcesz znaleźć globalnego optimum. Ponieważ zwykle wymaga to przeregulowania danych treningowych.

alfa
źródło
16

Interesującą alternatywą dla spadku gradientu są oparte na populacji algorytmy szkoleniowe, takie jak algorytmy ewolucyjne (EA) i optymalizacja roju cząstek (PSO). Podstawową ideą podejścia opartego na populacjach jest to, że tworzona jest populacja rozwiązań kandydujących (wektory wagowe NN), a rozwiązania kandydujące iteracyjnie badają przestrzeń wyszukiwania, wymieniając informacje, a ostatecznie zbliżając się do minimów. Ponieważ stosuje się wiele punktów początkowych (rozwiązania kandydujące), szanse na zbliżenie się do globalnych minimów są znacznie zwiększone. Wykazano, że PSO i EA działają bardzo konkurencyjnie, często (choć nie zawsze), osiągając lepsze wyniki niż gradient gradientu w złożonych problemach treningowych NN.

anna-earwen
źródło
+1 Warto jednak pamiętać, że agresywna optymalizacja kryterium szkolenia może doprowadzić do przeszacowania, chyba że zostaną podjęte kroki, aby temu zapobiec, więc unikałbym PSO i EA, chyba że kryterium szkolenia obejmuje pewną formę regularyzacji lub innej złożoności rzut karny.
Dikran Torbacz
5
@ Anna-Earwen, czy możesz podać referencje, w których PSO działa konkurencyjnie w porównaniu do SGD?
emrea
8

Wiem, że ten wątek jest dość stary, a inni wykonali świetną robotę, tłumacząc pojęcia takie jak lokalne minima, nadmierne dopasowanie itp. Jednak, ponieważ OP szukało alternatywnego rozwiązania, postaram się je wnieść i mam nadzieję, że zainspiruje to bardziej interesujące pomysły.

Chodzi o zastąpienie każdej wagi w do w + t, gdzie t jest liczbą losową po rozkładzie Gaussa. Końcowa moc wyjściowa sieci jest wówczas średnią mocą wyjściową dla wszystkich możliwych wartości t. Można to zrobić analitycznie. Następnie możesz zoptymalizować problem za pomocą spadku gradientu lub LMA lub innych metod optymalizacji. Po zakończeniu optymalizacji masz dwie opcje. Jedną z opcji jest zmniejszenie sigmy w rozkładzie Gaussa i wykonywanie optymalizacji raz za razem, aż sigma osiągnie wartość 0, wtedy będziesz mieć lepsze lokalne minimum (ale potencjalnie może to spowodować przeregulowanie). Inną opcją jest używanie tej z losową liczbą w wagach, zwykle ma lepszą właściwość uogólnienia.

Pierwsze podejście to sztuczka optymalizacyjna (nazywam to tunelowaniem splotowym, ponieważ używa splotu parametrów do zmiany funkcji docelowej), wygładza powierzchnię krajobrazu funkcji kosztu i pozbywa się niektórych lokalnych minimów, a tym samym ułatwi znalezienie globalnego minimum (lub lepszego lokalnego minimum).

Drugie podejście wiąże się z iniekcją hałasu (odważników). Zauważ, że odbywa się to analitycznie, co oznacza, że ​​końcowy wynik to jedna sieć zamiast wielu sieci.

Poniżej przedstawiono przykładowe dane wyjściowe dla problemu dwóch spiral. Architektura sieci jest taka sama dla wszystkich trzech: istnieje tylko jedna ukryta warstwa 30 węzłów, a warstwa wyjściowa jest liniowa. Zastosowanym algorytmem optymalizacji jest LMA. Lewy obraz służy do ustawienia wanilii; środek stosuje pierwsze podejście (mianowicie wielokrotnie redukuje sigma do 0); trzeci używa sigma = 2.

Wynik problemu dwóch spiral przez trzy podejścia

Widać, że najgorsze jest rozwiązanie waniliowe, tunelowanie splotowe działa lepiej, a wstrzykiwanie hałasu (z tunelowaniem splotowym) jest najlepsze (pod względem właściwości uogólniającej).

Zarówno tunelowanie splotowe, jak i analityczny sposób wprowadzania hałasu to moje oryginalne pomysły. Może są alternatywą, którą ktoś może być zainteresowany. Szczegóły można znaleźć w moim artykule Łączenie nieskończonej liczby sieci neuronowych w jedną całość . Ostrzeżenie: nie jestem zawodowym pisarzem akademickim i artykuł nie jest recenzowany. Jeśli masz pytania dotyczące podejść, o których wspomniałem, zostaw komentarz.

Bo Tian
źródło
1

Extreme Learning Machines Zasadniczo są to sieci neuronowe, w których wagi łączące wejścia z ukrytymi węzłami są przypisywane losowo i nigdy nie są aktualizowane. Wagi między ukrytymi węzłami a wyjściami są poznawane w jednym kroku poprzez rozwiązanie równania liniowego (macierz odwrotna).

alex
źródło
0

Jeśli chodzi o zadania globalnej optymalizacji (tj. Próby znalezienia globalnego minimum funkcji celu), możesz rzucić okiem na:

  1. {vi}
  2. Algorytm genetyczny, który wykorzystuje pojęcie mutacji, krzyżowania i selekcji do zdefiniowania populacji punktów, które zostaną ocenione przy następnej iteracji optymalizacji.
  3. Optymalizacja roju cząstek, która definiuje zestaw cząstek, które „przechodzą” przez przestrzeń w poszukiwaniu minimum.
  4. Optymalizacja zastępcza, która wykorzystujemodel zastępczy do przybliżenia funkcji celu. Metodę tę można zastosować, gdy ocena funkcji celu jest kosztowna.
  5. Optymalizacja wielozadaniowa (znana również jako optymalizacja Pareto ), której można użyć w przypadku problemu, którego nie można wyrazić w postaci, która ma funkcję jednego celu (a raczej wektor celów).
  6. Symulowane wyżarzanie , które wykorzystuje koncepcję wyżarzania (lub temperatury) do kompromisu poszukiwanie i eksploatację. Proponuje nowe punkty do oceny przy każdej iteracji, ale wraz ze wzrostem liczby iteracji „temperatura” spada, a algorytm coraz rzadziej eksploruje przestrzeń, „tym samym” zbliżając się do swojego najlepszego najlepszego kandydata.

Jak wspomniano powyżej, symulowane wyżarzanie, optymalizacja roju cząstek i algorytmy genetyczne są dobrymi algorytmami optymalizacji globalnej, które dobrze poruszają się w ogromnych przestrzeniach wyszukiwania iw przeciwieństwie do zejścia gradientu nie potrzebują żadnych informacji o gradiencie i mogą być z powodzeniem stosowane z funkcjami i problemami obiektywnymi czarnej skrzynki które wymagają uruchomienia symulacji.

Tomasz Bartkowiak
źródło