Algoritam opadajućeg gradijenta

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu
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.[1][2]

Opis algoritma[uredi]

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

za dovoljno malo pa je .

Generalno, algoritam počinje sa slučajno odabranom vrednošću iz čega se dobija niz elemenata tako da važi:

pa je onda

Na osnovu svega toga, niz konvergira ka lokalnom minimumu. Primetimo da vrednost koraka može (a i ne mora) da se menja u svakoj iteraciji. Sa određenim pretpostavkama o funkciji (na primer, je konveksno i gradijent od je Lipšic neprekidna) i sa dobro određenim vrednostima za , 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 [uredi]

Pogrešno odabrano može da prouzrokuje da algoritam ne konvergira pa je dobar odabir veličine koraka izuzetno bitno. Ukoliko je 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 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[uredi]

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[uredi]

Jedan od ključnih problema linearne regresije u mašinskom učenju je kako odabrati parametre tako da funkcija

bude minimalna

Pseudo kod[uredi]

Ponavljaj dok konvergira

Izvorni kod (Octave)[uredi]

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

Reference[uredi]

  1. ^ W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, 2nd Ed., Cambridge University Press, New York, 1992
  2. ^ T. Strutz: Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond). 2nd edition, Springer Vieweg. 2016. ISBN 978-3-658-11455-8.

Literatura[uredi]