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

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

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

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

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

${\displaystyle b=a-\gamma \bigtriangledown F(a)}$

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

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

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

па је онда

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

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

Одабир величине корака γ {\displaystyle \gamma }

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

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

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

Примена

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

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

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

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

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

Псеудо код

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

${\displaystyle \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