Zrozumienie stochastycznego średniego gradientu

Gradient descent jest najpopularniejszą techniką optymalizacji w modelowaniu uczenia maszynowego (ML). Algorytm minimalizuje błąd między przewidywanymi wartościami a prawdą. Ponieważ technika ta bierze pod uwagę każdy punkt danych, aby zrozumieć i zminimalizować błąd, jej wydajność zależy od rozmiaru danych treningowych. Techniki takie jak stochastyczny gradient zejścia (SGD) są zaprojektowane w celu poprawy wydajności obliczeń, ale kosztem dokładności konwergencji.

Stochastic Average Gradient równoważy klasyczne podejście, znane jako Full Gradient Descent i SGD, i oferuje obie korzyści. Ale zanim będziemy mogli użyć algorytmu, musimy najpierw zrozumieć jego znaczenie dla optymalizacji modelu.

Optymalizacja celów uczenia maszynowego za pomocą metody gradientu zstępującego

Każdy algorytm ML ma powiązaną funkcję straty, której celem jest minimalizacja lub poprawa wydajności modelu. Matematycznie stratę można zdefiniować jako:

Jest to po prostu różnica między rzeczywistym a przewidywanym wynikiem, a zminimalizowanie tej różnicy oznacza, że nasz model będzie bliższy wartościom prawdy.

Algorytm minimalizacji używa gradientu zstępującego do przejścia przez funkcję straty i znalezienia globalnego minimum. Każdy krok przejścia obejmuje aktualizację wag algorytmu w celu zoptymalizowania wyjścia.

Zwykłe zejście gradientowe

Konwencjonalny algorytm gradientu zstępującego wykorzystuje średnią wszystkich gradientów obliczonych w całym zestawie danych. Cykl życia pojedynczego przykładu szkoleniowego wygląda następująco:

Równanie aktualizacji wagi wygląda następująco:

Gdzie W oznacza wagi modelu, a dJ/dW jest pochodną funkcji straty względem wagi modelu. Konwencjonalna metoda ma wysoką szybkość zbieżności, ale staje się kosztowna obliczeniowo, gdy ma do czynienia z dużymi zbiorami danych obejmującymi miliony punktów danych.

Stochastyczny gradient zejścia (SGD)

Metodologia SGD pozostaje taka sama jak zwykła GD, ale zamiast używać całego zestawu danych do obliczania gradientów, używa małej partii z danych wejściowych. Metoda jest o wiele bardziej wydajna, ale może zbyt mocno przeskakiwać wokół globalnych minimów, ponieważ każda iteracja używa tylko części danych do nauki.

Średni gradient stochastyczny

Podejście Stochastic Average Gradient (SAG) zostało wprowadzone jako rozwiązanie pośrednie między GD i SGD. Wybiera losowy punkt danych i aktualizuje jego wartość na podstawie gradientu w tym punkcie i ważonej średniej poprzednich gradientów zapisanych dla tego konkretnego punktu danych.

Podobnie jak SGD, SAG modeluje każdy problem jako skończoną sumę wypukłych, różniczkowalnych funkcji. W każdej iteracji używa obecnych gradientów i średniej poprzednich gradientów do aktualizacji wagi. Równanie przyjmuje następującą postać:

Współczynnik zbieżności

Spośród dwóch popularnych algorytmów, pełnego gradientu (FG) i stochastycznego spadku gradientu (SGD), algorytm FG ma lepszą szybkość zbieżności, ponieważ podczas każdej iteracji wykorzystuje do obliczeń cały zestaw danych.

Chociaż SAG ma strukturę podobną do SGD, jego szybkość zbieżności jest porównywalna, a czasami lepsza niż podejście pełnego gradientu. Tabela 1 poniżej podsumowuje wyniki eksperymentów Schmidt i in. .

Dalsze modyfikacje

Pomimo niesamowitych osiągów oryginalnego algorytmu SGD zaproponowano kilka modyfikacji mających na celu poprawę jego wydajności.

• Ponowne ważenie we wczesnych iteracjach: konwergencja SAG pozostaje powolna podczas pierwszych kilku iteracji, ponieważ algorytm normalizuje kierunek z n (całkowita liczba punktów danych). Daje to niedokładne oszacowanie, ponieważ algorytm musi jeszcze zobaczyć wiele punktów danych. Modyfikacja sugeruje normalizację przez m zamiast n, gdzie m jest liczbą punktów danych widzianych co najmniej raz do tej konkretnej iteracji.
• Mini-partie: podejście Stochastic Gradient wykorzystuje mini-partie do przetwarzania wielu punktów danych jednocześnie. To samo podejście można zastosować do SAG. Umożliwia to wektoryzację i paralelizację w celu poprawy wydajności komputera. Zmniejsza również obciążenie pamięci, co jest poważnym wyzwaniem dla algorytmu SAG.
• Eksperyment z rozmiarem kroku: Rozmiar kroku wspomniany wcześniej (116L) daje niesamowite rezultaty, ale autorzy eksperymentowali dalej, używając rozmiaru kroku 1L. Ten ostatni zapewnił jeszcze lepszą konwergencję. Jednak autorzy nie byli w stanie przedstawić formalnej analizy poprawionych wyników. Wnioskują, że rozmiar kroku powinien być eksperymentowany, aby znaleźć optymalny dla konkretnego problemu.

Ostatnie przemyślenia

Gradient descent to popularna optymalizacja używana do lokalizowania globalnych minimów podanych funkcji celu. Algorytm wykorzystuje gradient funkcji celu do przechodzenia przez nachylenie funkcji, aż osiągnie najniższy punkt.

Full Gradient Descent (FG) i Stochastic Gradient Descent (SGD) to dwie popularne odmiany algorytmu. FG wykorzystuje cały zestaw danych podczas każdej iteracji i zapewnia wysoką szybkość konwergencji przy wysokim koszcie obliczeniowym. Podczas każdej iteracji SGD wykorzystuje podzbiór danych do uruchomienia algorytmu. Jest on znacznie bardziej wydajny, ale ma niepewną konwergencję.

Stochastic Average Gradient (SAG) to kolejna odmiana, która zapewnia korzyści obu poprzednich algorytmów. Używa średniej z poprzednich gradientów i podzbioru zestawu danych, aby zapewnić wysoką szybkość konwergencji przy niskich obliczeniach. Algorytm można dalej modyfikować, aby poprawić jego wydajność, stosując wektoryzację i mini-partie.