Алгоритам опадајућег градијента

Опадајући градијент је оптимизациони алгоритам првог реда. Алгоритам опадајућег градијента налази локани минимум функције тако што извршава више корака пропорционалних негативној вредности градијента одговарајуће функције. Уколико се алгоритам заснива на позитивним вредностима градијента онда се налази локални максимум и тај приступ се зове растући граднијент.[1][2]

Илустрација опадујућег градијента

Опис алгоритма

уреди

Ако је функција   дефинисана и диференцијабилна у околина тачке   , онда   опада брже у смеру од тачке   ка негативном градијенту функције   у тачки  . Из тога следи:

 

за довољно мало   па је  .

Генерално, алгоритам почиње са случајно одабраном вредношћу   из чега се добија низ елемената   тако да важи:

 

па је онда

 

На основу свега тога, низ   конвергира ка локалном минимуму. Приметимо да вредност корака   може (a и не мора) да се мења у свакој итерацији. Са одређеним претпоставкама о функцији   (на пример,   је конвексно и градијент од   је Липшиц непрекидна) и са добро одређеним вредностима за  , конвергенција ка локалном минимуму може да буде гарантована. Када је функција конвексна, сви локални минимуми су и голобални, па у овом случају опадајући градијент конвергира ка глобалном решењу.

Одабир величине корака

уреди

Погрешно одабрано   може да проузрокује да алгоритам не конвергира па је добар одабир величине корака   изузетно битно. Уколико је   сувише велико, алгоритам ће да дивергира а уколико је сувише мало конвергенција ће бити веома спора.

Можемо да одаберемо да корак буде фиксне величине или да у свакој итерацији узимамо другачију вредност. У пракси, корак   се најчешће одређује тако што се одабере неколико могућих вредности из одређеног опсега па се затим бира она вредност која нам највише одговара.

Такође постоје и математички модели за одређивање корака γ као што су: метода најстрмијег опадања, Барзилај анд Борвеин метода итд.

Примена

уреди

Овај алгоритам има изузетну примену у машинском учењу. Различити проблеми машинског учења (регресија, класификација итд) захтевају налажење оптималних параметара како би се добило најпрецизније могуће предвиђање.

Машинско учење

уреди

Један од кључних проблема линеарне регресије у машинском учењу је како одабрати параметре   тако да функција

 

буде минимална

Псеудо код

уреди

Понављај док конвергира

 

Изворни код (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

Референце

уреди
  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 изд.). 2016. ISBN 978-3-658-11455-8. . , Springer Vieweg.

Литература

уреди