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

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

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

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

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

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

за довољно мало $\gamma$ па је $F(a)\geq F(b)$.

Генерално, алгоритам почиње са случајно одабраном вредношћу $x_{0}$ из чега се добија низ елемената $x_{1},x_{2},x_{3},x_{4},....$ тако да важи:

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

па је онда

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

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

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

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

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

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

Примена

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

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

Један од кључних проблема линеарне регресије у машинском учењу је како одабрати параметре $\theta _{0},\theta _{1}$ тако да функција

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

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

Псеудо код

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

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

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

Литература

• 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. стр. 536—538.