Algoritam opadajućeg gradijenta

Ilustracija opadujućeg gradijenta

Opadajući gradijent je optimizacioni algoritam prvog reda. Algoritam opadajućeg gradijenta nalazi lokani minimum funkcije tako što izvršava više koraka proporcionalnih negativnoj vrednosti gradijenta odgovarajuće funkcije. Ukoliko se algoritam zasniva na pozitivnim vrednostima gradijenta onda se nalazi lokalni maksimum i taj pristup se zove rastući gradnijent.

Opis algoritma

Ako je funkcija $F(x)$ definisana i diferencijabilna u okolina tačke $a$ , onda $F(x)$ opada brže u smeru od tačke $a$ ka negativnom gradijentu funkcije $F$ u tački $a$. Iz toga sledi:

$b=a-\gamma \bigtriangledown F(a)$

za dovoljno malo $\gamma$ pa je $F(a)\geq F(b)$.

Generalno, algoritam počinje sa slučajno odabranom vrednošću $x_{0}$ iz čega se dobija niz elemenata $x_{1},x_{2},x_{3},x_{4},....$ tako da važi:

$x_{n+1}=x_{n}-\gamma \bigtriangledown F(x_{n}),n\geq 0$

pa je onda

$F(x_{0})\geq F(x_{1})\geq F(x_{2})\geq ...$

Na osnovu svega toga, niz $x_{n}$ konvergira ka lokalnom minimumu. Primetimo da vrednost koraka $\gamma$ može (a i ne mora) da se menja u svakoj iteraciji. Sa određenim pretpostavkama o funkciji $F$ (na primer, $F$ je konveksno i gradijent od $F$ je Lipšic neprekidna) i sa dobro određenim vrednostima za $\gamma$, konvergencija ka lokalnom minimumu može da bude garantovana. Kada je funkcija konveksna, svi lokalni minimumi su i golobalni, pa u ovom slučaju opadajući gradijent konvergira ka globalnom rešenju.

Odabir veličine koraka $\gamma$

Pogrešno odabrano $\gamma$ može da prouzrokuje da algoritam ne konvergira pa je dobar odabir veličine koraka $\gamma$ izuzetno bitno. Ukoliko je $\gamma$ suviše veliko, algoritam će da divergira a ukoliko je suviše malo konvergencija će biti veoma spora.

Možemo da odaberemo da korak bude fiksne veličine ili da u svakoj iteraciji uzimamo drugačiju vrednost. U praksi, korak $\gamma$ se najčešće određuje tako što se odabere nekoliko mogućih vrednosti iz određenog opsega pa se zatim bira ona vrednost koja nam najviše odgovara.

Takođe postoje i matematički modeli za određivanje koraka γ kao što su: metoda najstrmijeg opadanja, Barzilaj and Borvein metoda itd.

Primena

Ovaj algoritam ima izuzetnu primenu u mašinskom učenju. Različiti problemi mašinskog učenja (regresija, klasifikacija itd) zahtevaju nalaženje optimalnih parametara kako bi se dobilo najpreciznije moguće predviđanje.

Mašinsko učenje

Jedan od ključnih problema linearne regresije u mašinskom učenju je kako odabrati parametre $\theta _{0},\theta _{1}$ tako da funkcija

$J(\theta _{0},\theta _{1})={\dfrac {1}{(2*m)}}\sum \limits _{i=1}^{m}((\theta _{0}+\theta _{1}x)-y)^{2}$

bude minimalna

Pseudo kod

Ponavljaj dok konvergira

$\theta _{j}:=\theta _{j}-\gamma {\frac {\partial {J(\theta _{0},\theta _{1})}}{\partial {\theta _{j}}}}$

Izvorni kod (Octave)

function [theta, J_history] = gradientDescent(X, y, theta, alpha, num_iters)
m = length(y);
J_history = zeros(num_iters, 1);

for iter = 1:num_iters
	temp0 = theta(1,1) - alpha*(1/m)*sum((theta(1,1).*X(:,1)+theta(2,1).*X(:,2))-y);
	temp1 = theta(2,1) - alpha*(1/m)*sum(((theta(1,1).*X(:,1)+theta(2,1).*X(:,2))-y).*X(:,2));
	theta(1,1) = temp0;
	theta(2,1) = temp1;
        J_history(iter) = computeCost(X, y, theta);
end

Literatura

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 978-0-486-43227-4. 
• Jan A. Snyman (2005). Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer Publishing. ISBN 978-0-387-24348-1. 
• Raad Z. Homod, K. S. M. Sahari, H. A.F. Almurib, F. H. Nagi, Gradient auto-tuned Takagi-Sugeno fuzzy forward control of a HVAC system using predicted mean vote index Energy and Buildings, 49 (6) (2012) 254-267
• Cauchy, Augustin (1847). Méthode générale pour la résolution des systèmes d'équations simultanées. str. 536—538.