Algoritam opadajućeg gradijenta

S 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 | uredi izvor]

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

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

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

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

bude minimalna

Pseudo kod[uredi | uredi izvor]

Ponavljaj dok konvergira

Izvorni kod (Octave)[uredi | uredi izvor]

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

  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.

Литература[uredi | uredi izvor]