Spadek gradientowy — algorytm, współczynnik uczenia i warianty

Spadek gradientowy to algorytm minimalizacji funkcji różniczkowalnej przez wykonywanie kolejnych kroków w kierunku, który lokalnie najszybciej ją zmniejsza. Jeśli szukasz odpowiedzi na pytanie „co to jest spadek gradientowy”, podstawowa idea jest prosta: oblicz nachylenie, wykonaj mały krok w dół i powtarzaj.

Jest szeroko stosowany w optymalizacji opartej na rachunku różniczkowym oraz w uczeniu maszynowym. Metoda działa najlepiej wtedy, gdy można obliczyć pochodną lub gradient i dobrać współczynnik uczenia na tyle mały, by zachować stabilność, ale na tyle duży, by robić postęp.

W przypadku jednej zmiennej reguła aktualizacji ma postać

$$x_{k+1} = x_k - \eta f'(x_k),$$

a dla wielu zmiennych przyjmuje postać

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \eta \nabla f(\mathbf{x}_k),$$

gdzie $\eta > 0$ jest współczynnikiem uczenia. Współczynnik uczenia kontroluje długość każdego kroku, więc bezpośrednio wpływa na to, czy algorytm zbiega, zatrzymuje się, czy przeskakuje minimum.

Intuicja spadku gradientowego

Gradient wskazuje kierunek wzrostu funkcji. Jeśli celem jest minimalizacja, naturalnym lokalnym ruchem jest pójście w przeciwną stronę.

Ta lokalna reguła nie gwarantuje najlepszego możliwego wyniku w każdym problemie. Dla funkcji wypukłej spadek gradientowy może prowadzić do minimum globalnego. Dla funkcji niewypukłej może zatrzymać się w minimum lokalnym, na płaskim obszarze albo w innym punkcie stacjonarnym.

Jak działa algorytm spadku gradientowego

Każda iteracja wykorzystuje informację o bieżącym nachyleniu, aktualizuje punkt i sprawdza, czy należy kontynuować.

1. Zacznij od początkowego przybliżenia $x_0$ albo $\mathbf{x}_0$.
2. Oblicz pochodną lub gradient w bieżącym punkcie.
3. Zaktualizuj punkt, odejmując $\eta$ razy tę pochodną lub gradient.
4. Zatrzymaj się, gdy gradient jest mały, aktualizacje stają się bardzo małe albo zostanie osiągnięty ustalony limit iteracji.

Standardowa reguła aktualizacji zakłada, że funkcja celu jest różniczkowalna w punktach, w których ją stosujesz. Niektóre metody optymalizacji używają subgradientów dla problemów z funkcjami nieróżniczkowalnymi, ale to inna sytuacja.

Dlaczego współczynnik uczenia ma znaczenie w spadku gradientowym

Współczynnik uczenia $\eta$ to długość kroku.

Jeśli $\eta$ jest zbyt małe, spadek gradientowy zwykle porusza się we właściwym kierunku, ale może działać bardzo wolno. Jeśli $\eta$ jest zbyt duże, aktualizacje mogą przeskakiwać minimum, oscylować albo nawet się rozbiegać.

Ten kompromis dobrze widać na funkcji kwadratowej, gdzie nachylenie staje się większe wraz z oddalaniem się od minimum. Długość kroku, która wydaje się bezpieczna w jednym miejscu, może być zbyt agresywna w innym.

Przykład: spadek gradientowy dla funkcji kwadratowej

Rozważ

$$f(x) = (x-3)^2.$$

Ta funkcja ma minimum w punkcie $x=3$. Jej pochodna wynosi

$$f'(x) = 2(x-3).$$

Zastosuj spadek gradientowy ze współczynnikiem uczenia $\eta = 0.1$ i punktem startowym $x_0 = 0$.

Wtedy reguła aktualizacji ma postać

$$x_{k+1} = x_k - 0.1 \cdot 2(x_k-3) = x_k - 0.2(x_k-3).$$

Zaczynając od $x_0 = 0$:

$$x_1 = 0 - 0.2(0-3) = 0.6.$$

Następnie

$$x_2 = 0.6 - 0.2(0.6-3) = 1.08.$$

oraz

$$x_3 = 1.08 - 0.2(1.08-3) = 1.464.$$

Każdy krok przybliża wynik do $3$, a wartość funkcji za każdym razem maleje. To najważniejszy wzorzec, który warto zauważyć: spadek gradientowy nie przeskakuje od razu do odpowiedzi. Poprawia przybliżenie przez kolejne lokalne korekty.

Typowe warianty spadku gradientowego

Batch gradient descent

Batch gradient descent wykorzystuje cały zbiór danych do obliczenia każdej aktualizacji. Dla ustalonej funkcji celu daje to deterministyczny krok, ale może być kosztowne przy dużych zbiorach danych.

Stochastic gradient descent

Stochastic gradient descent aktualizuje parametry na podstawie jednej próbki naraz. Każdy krok jest tańszy, ale bardziej zaszumiony. Ten szum może pomagać metodzie iść dalej, ale sprawia też, że trajektoria jest mniej gładka.

Mini-batch gradient descent

Mini-batch gradient descent używa małej grupy próbek w każdym kroku. Często jest to praktyczny kompromis, ponieważ zmniejsza szum w porównaniu z czysto stochastycznymi aktualizacjami, a jednocześnie pozostaje znacznie tańszy niż pełny batch.

Te warianty mają największe znaczenie w uczeniu maszynowym, gdzie funkcja celu jest często średnią stratą z wielu przykładów treningowych.

Typowe błędy przy stosowaniu spadku gradientowego

Traktowanie współczynnika uczenia jako drobnego szczegółu

Zmiana $\eta$ zmienia zachowanie samego algorytmu. Metoda, która zbiega dla jednego współczynnika uczenia, może zawodzić dla innego.

Zakładanie, że spadek gradientowy zawsze znajduje minimum globalne

Taki wniosek wymaga dodatkowych warunków. Na przykład wypukłość daje znacznie silniejsze gwarancje niż ogólny krajobraz funkcji niewypukłej.

Ignorowanie skali cech w problemach praktycznych

W problemach optymalizacyjnych ze źle przeskalowanymi zmiennymi jeden kierunek może zmieniać się znacznie szybciej niż inny. Wtedy spadek gradientowy może poruszać się zygzakiem i zbiegać wolno, chyba że problem zostanie przekształcony albo staranniej przeskalowany.

Zatrzymywanie się tylko dlatego, że gradient nie jest dokładnie równy zeru

Algorytmy numeryczne rzadko czekają na idealne zero. W praktyce kryteria zatrzymania zwykle sprawdzają, czy norma gradientu, zmiana parametrów albo zmiana wartości funkcji są dostatecznie małe.

Kiedy stosuje się spadek gradientowy

Spadek gradientowy jest używany w optymalizacji numerycznej, statystyce i uczeniu maszynowym. Jest szczególnie powszechny wtedy, gdy dokładne rozwiązanie w postaci zamkniętej nie istnieje albo jego bezpośrednie obliczenie jest zbyt kosztowne.

W małych problemach z prostymi wzorami rachunek różniczkowy może dać minimum dokładnie. Spadek gradientowy staje się bardziej użyteczny wtedy, gdy przestrzeń parametrów jest duża, funkcja celu ma wiele zmiennych albo strata pochodzi z dużych zbiorów danych.

Spróbuj podobnego zadania

Wypróbuj własną wersję dla $f(x) = (x-5)^2$ i punktu startowego $x_0 = 12$. Przeprowadź jeden przypadek z $\eta = 0.1$, a drugi z $\eta = 1.2$. Zobaczenie jednego stabilnego przebiegu i jednego niestabilnego dużo lepiej pokazuje rolę współczynnika uczenia niż sam wzór.