Градієнтний спуск

Градіє́нтний спуск (англ. gradient descent) — це ітераційний алгоритм оптимізації першого порядку, в якому для знаходження локального мінімуму функції здійснюються кроки, пропорційні протилежному значенню градієнту (або наближеного градієнту) функції в поточній точці. Якщо натомість здійснюються кроки пропорційно самому значенню градієнту, то відбувається наближення до локального максимуму цієї функції; і ця процедура тоді відома як градіє́нтний підйо́м (англ. gradient ascent).

Градієнтний спуск відомий також як найшви́дший спуск (англ. steepest descent), або ме́тод найшви́дшого спу́ску (англ. method of steepest descent). Градієнтний спуск не слід плутати з методом перевалу для наближення інтегралів.

Опис

Ілюстрація методу найшвидшого спуску на ряді множин рівнів.

Градієнтний спуск ґрунтується на тому спостереженні, що якщо функція кількох змінних $F(\mathbf {x} )$ є визначеною та диференційовною в околі точки $\mathbf {a}$, то $F(\mathbf {x} )$ зменшується найшвидше, якщо йти від $\mathbf {a}$ в напрямку, протилежному градієнтові $F$ в $\mathbf {a}$, $-\nabla F(\mathbf {a} )$. З цього випливає, що якщо

$\mathbf {b} =\mathbf {a} -\gamma \nabla F(\mathbf {a} )$

для достатньо малого $\gamma$, то $F(\mathbf {a} )\geq F(\mathbf {b} )$. Іншими словами, член $\gamma \nabla F(\mathbf {a} )$ віднімається від $\mathbf {a}$, оскільки ми хочемо рухатися проти градієнту, тобто вниз до мінімуму. Враховуючи це спостереження, починають з припущення $\mathbf {x} _{0}$ про локальний мінімум $F$, і розглядають таку послідовність $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\dots$, що

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$

Ми маємо

$F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,$

і тому сподіваємося, що послідовність $(\mathbf {x} _{n})$ збігається до бажаного локального мінімуму. Зауважте, що значення розміру кроку (англ. step size) $\gamma$ дозволено змінювати на кожній ітерації. Для деяких припущень стосовно функції $F$ (наприклад, що $F$ є опуклою, а $\nabla F$ задовольняє умові Ліпшиця) і певних варіантах вибору $\gamma$ (наприклад, якщо його вибирають лінійним пошуком, який задовольняє умови Вольфе), збіжність до локального мінімуму може бути гарантовано. Якщо функція $F$ є опуклою, то всі локальні мінімуми є також і глобальними мінімумами, тому в такому випадку градієнтний спуск може збігатися до глобального розв'язку.

Цей процес проілюстровано на зображенні праворуч. Тут припускається, що $F$ визначено на площині, і що її графік має форму чаші. Сині криві є ізолініями, тобто областями, в яких значення $F$ є сталим. Червоні стрілки, які виходять з точок, показують напрям, протилежний градієнтові в цій точці. Зауважте, що (анти)градієнт у точці є ортогональним до ізолінії, яка проходить цією точкою. Видно, що спуск градієнтом веде нас до дна чаші, тобто до точки, в якій значення функції $F$ є мінімальним.

Приклади

Градієнтний спуск має проблеми з патологічними функціями, такими як показана тут функція Розенброка.

$f(x_{1},x_{2})=(1-x_{1})^{2}+100(x_{2}-x_{1}^{2})^{2}.\quad$

Функція Розенброка має вузьку вигнуту долину, яка містить мінімум. Дно цієї долини є дуже пологим. Через вигнутість пологої долини оптимізація повільно рухається в напрямку мінімуму зиґзаґом кроками малого розміру.

«Зиґзаґоподібна» природа цього методу також є очевидною нижче, де градієнтний спуск застосовано до $F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos(2x+1-e^{y})$.

Обмеження

Для деяких із наведених вище прикладів градієнтний спуск є відносно повільним поблизу мінімуму: з технічної точки зору, його асимптотичний темп збігання поступається багатьом іншим методам. Для невдало обумовлених опуклих задач градієнтний спуск «зиґзаґує» все більше, коли градієнт вказує майже ортогонально до найкоротшого напряму до точки мінімуму. Докладніше див. коментарі нижче.

Для недиференційовних функцій градієнтні методи є недостатньо визначеними. Для локально ліпшицевих задач, та особливо для задач опуклої оптимізації, цілком визначеними є в'язкові методи спуску. Також можуть застосовуватися не-спускові методи, такі як методи субградієнтної проєкції. Ці методи зазвичай є повільнішими за градієнтний спуск. Іншою альтернативою для недиференційовних функцій є «згладжування» цих функцій, або обмеження функції гладкою функцією. За цього підходу розв'язують згладжену задачу в надії, що відповідь для неї є близькою до відповіді на незгладжену задачу (іноді це може бути зроблено строгим).

Розв'язання лінійної системи

Градієнтний спуск може застосовуватися для розв'язання системи лінійних рівнянь, переформульованого як задача квадратичної мінімізації, наприклад, із застосуванням методу найменших квадратів. Розв'язок

$A\mathbf {x} -\mathbf {b} =0$

у сенсі методу найменших квадратів визначається як мінімізація функції

$F(\mathbf {x} )=\|A\mathbf {x} -\mathbf {b} \|^{2}.$

В традиційному методі найменших квадратів для дійсних $A$ та $\mathbf {b}$ використовується евклідова норма, і в цьому випадку

$\nabla F(\mathbf {x} )=2A^{T}(A\mathbf {x} -\mathbf {b} ).$

В такому випадку мінімізація лінійним пошуком, яка знаходить на кожній ітерації локально оптимальний розмір кроку $\gamma$, може виконуватися аналітично, і явні формули локально оптимального $\gamma$ є відомими.

Для розв'язання лінійних рівнянь градієнтний спуск застосовується рідко, а однією з найпопулярніших альтернатив є метод спряжених градієнтів. Швидкість збігання градієнтного спуску залежить від максимального та мінімального власних значень $A$, тоді як швидкість збігання спряжених градієнтів має складнішу залежність від цих власних значень, і може отримувати користь від передобумовлювання. Градієнтний спуск також отримує користь від передобумовлювання, але це не роблять так поширено.

Розв'язання нелінійної системи

Градієнтний спуск може також застосовуватися і до розв'язання систем нелінійних рівнянь. Нижче наведено приклад, як застосовувати градієнтний спуск для розв'язання для трьох невідомих змінних, x₁, x₂ та x₃. Цей приклад показує одну ітерацію градієнтного спуску.

Розгляньмо систему нелінійних рівнянь

${\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}$

припустімо, що ми маємо функцію

$G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}}$

де

$\mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}$

та цільову функцію

$F(\mathbf {x} )={\tfrac {1}{2}}G^{\mathrm {T} }(\mathbf {x} )G(\mathbf {x} )={\tfrac {1}{2}}\left(\left(3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\left(\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {1}{3}}(10\pi -3)\right)^{2}\right)$

з початковим припущенням

$\mathbf {x} ^{(0)}={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}$

Ми знаємо, що

$\mathbf {x} ^{(1)}=\mathbf {x} ^{(0)}-\gamma _{0}\nabla F(\mathbf {x} ^{(0)})$

де

$\nabla F(\mathbf {x} ^{(0)})=J_{G}(\mathbf {x} ^{(0)})^{\mathrm {T} }G(\mathbf {x} ^{(0)})$

Матриця Якобі $J_{G}(\mathbf {x} ^{(0)})$

$J_{G}={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}$

Потім обчислімо ці члени в $\mathbf {x} ^{(0)}$

$J_{G}\left(\mathbf {x} ^{(0)}\right)={\begin{bmatrix}3&0&0\\0&2&0\\0&0&20\end{bmatrix}},\qquad G(\mathbf {x} ^{(0)})={\begin{bmatrix}-2.5\\-1\\10.472\end{bmatrix}}$

Отже,

$\mathbf {x} ^{(1)}=0-\gamma _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}}$

та

$F\left(\mathbf {x} ^{(0)}\right)=0.5\left((-2.5)^{2}+(-1)^{2}+(10.472)^{2}\right)=58.456$

Анімація, яка показує перші 83 ітерації градієнтного спуску, що застосовується до цього прикладу. Поверхні є ізоповерхнями $F(\mathbf {x} ^{(n)})$ на поточному припущенні $\mathbf {x} ^{(n)}$, а стрілки показують напрямок спуску. З причини малого та незмінного кроку збігання є повільним.

Тепер мусить бути знайдено придатний $\gamma _{0}$, такий що $F(\mathbf {x} ^{(1)})\leq F(\mathbf {x} ^{(0)})$. Це можна зробити за допомогою будь-якого з безлічі алгоритмів лінійного пошуку. Можна також просто припустити $\gamma _{0}=0.001$, що дає

$\mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}$

При обчисленні на цьому значенні

$F\left(\mathbf {x} ^{(1)}\right)=0.5\left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}\right)=23.306$

Зменшення з $F(\mathbf {x} ^{(0)})=58.456$ до значення наступного кроку $F(\mathbf {x} ^{(1)})=23.306$ є відчутним зменшенням цільової функції. Подальші кроки знижуватимуть її значення доти, доки не буде знайдено розв'язок системи.

Коментарі

Градієнтний спуск працює в просторах з будь-яким числом вимірів, навіть у нескінченновимірних. В останньому випадку простір пошуку зазвичай є простором функцій, і для визначення напрямку спуску здійснюється обчислення похідної Гато функціоналу, який мінімізують.

Якщо кривина заданої функції дуже різниться в різних напрямках, то градієнтному спускові може знадобитися багато ітерацій для обчислення локального мінімуму з потрібною точністю. Для таких функцій повільне збігання лікується передобумовлюванням, яке змінює геометрію простору так, щоби надати множинам рівнів функції форми концентричних кіл. Проте побудова та застосування передобумовлювання можуть бути обчислювально витратними.

Градієнтний спуск можна поєднувати з лінійним пошуком, який на кожній ітерації шукає локально оптимальний розмір кроку $\gamma$. Виконання лінійного пошуку може бути витратним за часом. З іншого боку, застосування незмінного малого $\gamma$ може давати погану збіжність.

Кращими альтернативами можуть бути методи на основі методу Ньютона та обернення гессіану із застосуванням методик спряжених градієнтів. Загалом такі методи збігаються за меншу кількість ітерацій, але вартість кожної ітерації є вищою. Прикладом є Метод БФГШ, який складається з обчислення на кожному кроці матриці, на яку множиться вектор градієнту, щоби йти в «найкращому» напрямку, поєднаного зі складнішим алгоритмом лінійного пошуку для знаходження «найкращого» значення $\gamma$. Для надзвичайно великих задач, у яких домінують питання комп'ютерної пам'яті, замість БФГШ або найшвидшого спуску повинні застосовуватися методи з обмеженою пам'яттю, такі як О-БФГШ.

Градієнтний спуск може розглядатися як метод Ейлера для розв'язання звичайних диференційних рівнянь $x'(t)=-\nabla f(x(t))$ потоку градієнта.

Обчислювальні приклади

Python

Алгоритм градієнтного спуску застосовується для знаходження локального мінімуму функції f(x)=x⁴−3x³+2 з похідною f'(x)=4x³−9x². Ось реалізація мовою програмування Python.

# Виходячи з обчислень, ми очікуємо, що локальний мінімум матиме місце в x=9/4

x_old = 0 # Це значення не важливе, оскільки abs(x_new - x_old) > precision
x_new = 6 # Алгоритм стартує з x=6
gamma = 0.01 # розмір кроку
precision = 0.00001

def f_derivative(x):
    return 4 * x**3 - 9 * x**2

while abs(x_new - x_old) > precision:
    x_old = x_new
    x_new = x_old - gamma * f_derivative(x_old)

print("Локальний мінімум має місце в", x_new)

Наведений вище фрагмент коду має бути змінено по відношенню до розміру кроку відповідно до системи, яка є під руками, а збіжність може бути зроблено швидшою шляхом застосування адаптивного розміру кроку. В наведеному вище випадку розмір кроку не є адаптивним. Він залишається на рівні 0.01 в усіх напрямках, що може іноді призводити до невдачі методу за рахунок відхилення від мінімуму.

MATLAB

Наступний код MATLAB демонструє конкретне рішення для розв'язання системи нелінійних рівнянь, представленої в попередньому розділі:

${\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}$

% Багатовимірна вектор-функція G(x)
G = @(x) [
    3*x(1) - cos(x(2)*x(3)) - 3/2           ;
    4*x(1)^2 - 625*x(2)^2 + 2*x(2) - 1      ;
    exp(-x(1)*x(2)) + 20*x(3) + (10*pi-3)/3];

% Якобіан G
JG = @(x) [
    3,                     sin(x(2)*x(3))*x(3),   sin(x(2)*x(3))*x(2) ;
    8*x(1),                -1250*x(2)+2,          0                   ;
    -x(2)*exp(-x(1)*x(2)), -x(1)*exp(-x(1)*x(2)), 20                 ];

% Цільова функція F(x), яку потрібно мінімізувати, щоби розв'язати G(x)=0
F = @(x) 0.5 * sum(G(x).^2);

% Градієнт F (часткові похідні)
dF = @(x) JG(x).' * G(x);

% Параметри
GAMMA = 0.001;    % розмір кроку (темп навчання)
MAX_ITER = 1000;  % максимальне число ітерацій
FUNC_TOL = 0.1;   % кінцеве допустиме відхилення F(x)

fvals = [];       % зберігання значень F(x) протягом ітерацій
progress = @(iter,x) fprintf('iter = %3d: x = %-32s, F(x) = %f\n', ...
    iter, mat2str(x,6), F(x));

% Ітерування
iter = 1;         % лічильник ітерацій
x = [0; 0; 0];    % початкове припущення
fvals(iter) = F(x);
progress(iter, x);
while iter < MAX_ITER && fvals(end) > FUNC_TOL
    iter = iter + 1;
    x = x - GAMMA * dF(x);  % градієнтний спуск
    fvals(iter) = F(x);     % обчислити цільову функцію
    progress(iter, x);      % показати перебіг
end

% Накреслити
plot(1:iter, fvals, 'LineWidth',2); grid on;
title('Objective Function'); xlabel('Iteration'); ylabel('F(x)');

% Обчислити кінцевий розв'язок системи рівнянь G(x)=0
disp('G(x) = '); disp(G(x))

% Виведення:
%
% iter =   1: x = [0;0;0]                         , F(x) = 58.456136
% iter =   2: x = [0.0075;0.002;-0.20944]         , F(x) = 23.306394
% iter =   3: x = [0.015005;0.0015482;-0.335103]  , F(x) = 10.617030
% ...
% iter = 187: x = [0.683335;0.0388258;-0.52231]   , F(x) = 0.101161
% iter = 188: x = [0.684666;0.0389831;-0.522302]  , F(x) = 0.099372
%
% (збіглося за 188 ітерацій після перевищення кінцевого допустимого відхилення F(x))

Розширення

Градієнтний спуск може бути розширено для підтримки обмежень шляхом включення проєкції на множину обмежень. Цей метод підходить лише тоді, коли ця проєкція є ефективно обчислюваною на комп'ютері. За зручних припущень цей метод збігається. Цей метод є окремим випадком послідовно-зворотного алгоритму для монотонних включень (який включає опукле програмування та варіаційні нерівності).

Швидкий проксимальний градієнтний метод

Інше розширення градієнтного спуску виникло завдяки Юрієві Нестерову 1983 року, і було згодом узагальнене. Він пропонує просту видозміну цього алгоритму, яка уможливлює швидке збігання для опуклих задач. А саме, якщо функція $F$ є опуклою, а $\nabla F$ є ліпшицевою, і немає припущення, що $F$ є сильно опуклою, то похибку цільового значення, породжувану методом градієнтного спуску на кожному кроці $k$, буде обмежено ${\mathcal {O}}(1/k)$. Із застосуванням методики прискорення Нестерова похибка знижується до ${\mathcal {O}}(1/k^{2})$.

Метод імпульсу

Ще одним розширенням, яке знижує ризик застрягнути в локальному мінімумі, а також істотно прискорює збіжність у випадках, коли інакше процес би сильно зиґзаґував, є метод імпульсу (англ. momentum method), який використовує член імпульсу по аналогії з «масою ньютонових частинок, які рухаються в'язким середовищем у консервативному силовому полі». Цей метод часто використовують як розширення алгоритмів зворотного поширення, що застосовуються для тренування штучних нейронних мереж.

Див. також

• Метод спряженого градієнта
• Метод проксимального градієнта
• Стохастичний градієнтний спуск
• Rprop
• Дельта-правило
• Умови Вольфе
• Передобумовлювання
• Метод БФГШ
• Метод Нелдера – Міда
• Алгоритм Франк — Вульфа

Джерела

• Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0. (англ.)
• Jan A. Snyman (2005). Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer Publishing. ISBN 0-387-24348-8 (англ.)
• 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 [Архівовано 11 грудня 2018 у Wayback Machine.] (англ.)
• Cauchy, Augustin (1847). Méthode générale pour la résolution des systèmes d'équations simultanées. с. 536—538. Архів оригіналу за 13 жовтня 2016. Процитовано 31 липня 2016. (фр.)
• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973., Поляк Р. А., Примак М. Е., т. 2, ст. 64.

Посилання

• Застосування градієнтного спуску в C++, Boost, Ublas для лінійної регресії [Архівовано 22 липня 2013 у Wayback Machine.]