www.wikidata.uk-ua.nina.az

Градієнтний спуск Ця стаття про алгоритм оптимізації Про метод наближення інтегралів у математичному аналізі див Метод п

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

Ця стаття про алгоритм оптимізації. Про метод наближення інтегралів у математичному аналізі див. Метод перевалу[en]

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

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

Опис Редагувати

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

Градієнтний спуск ґрунтується на тому спостереженні, що якщо функція кількох змінних[en] є визначеною[en] та диференційовною в околі точки , то зменшується найшвидше, якщо йти від в напрямку, протилежному градієнтові в , . З цього випливає, що якщо

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

Ми маємо

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

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

Приклади Редагувати

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

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

«Зиґзаґоподібна» природа цього методу також є очевидною нижче, де градієнтний спуск застосовано до .

Обмеження Редагувати

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

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

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

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

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

В традиційному методі найменших квадратів для дійсних та використовується евклідова норма, і в цьому випадку

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

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

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

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

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

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

де

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

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

Ми знаємо, що

де

Матриця Якобі

Потім обчислімо ці члени в

Отже,

та

Анімація, яка показує перші 83 ітерації градієнтного спуску, що застосовується до цього прикладу. Поверхні є ізоповерхнями на поточному припущенні , а стрілки показують напрямок спуску. З причини малого та незмінного кроку збігання є повільним.

Тепер мусить бути знайдено придатний , такий що . Це можна зробити за допомогою будь-якого з безлічі алгоритмів лінійного пошуку. Можна також просто припустити , що дає

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

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

Коментарі Редагувати

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

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

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

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

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

Обчислювальні приклади Редагувати

Python Редагувати

Алгоритм градієнтного спуску застосовується для знаходження локального мінімуму функції f(x)=x4−3x3+2 з похідною f'(x)=4x3−9x2. Ось реалізація мовою програмування 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 демонструє конкретне рішення для розв'язання системи нелінійних рівнянь, представленої в попередньому розділі: 

% Багатовимірна вектор-функція 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))

Розширення Редагувати

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

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

Інше розширення градієнтного спуску виникло завдяки Юрієві Нестерову[en] 1983 року, і було згодом узагальнене. Він пропонує просту видозміну цього алгоритму, яка уможливлює швидке збігання для опуклих задач. А саме, якщо функція є опуклою, а є ліпшицевою, і немає припущення, що є сильно опуклою, то похибку цільового значення, породжувану методом градієнтного спуску на кожному кроці , буде обмежено . Із застосуванням методики прискорення Нестерова похибка знижується до .

Метод імпульсу Редагувати

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

Див. також Редагувати

Примітки Редагувати

  1. Kiwiel, Krzysztof C. (2001). Convergence and efficiency of subgradient methods for quasiconvex minimization. Mathematical Programming (Series A) 90 (1) (Berlin, Heidelberg: Springer). с. 1–25. ISSN 0025-5610. MR 1819784. doi:10.1007/PL00011414.  (англ.)
  2. Yuan, Ya-xiang (1999). Step-sizes for the gradient method. AMS/IP Studies in Advanced Mathematics (Providence, RI: American Mathematical Society) 42 (2): 785.  (англ.)
  3. G. P. Akilov, L. V. Kantorovich, Functional Analysis, Pergamon Pr; 2 Sub edition, ISBN 0-08-023036-9, 1982 (англ.)
  4. 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 (англ.)
  5. 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. (англ.)
  6. P. L. Combettes and J.-C. Pesquet, «Proximal splitting methods in signal processing» [ 7 липня 2011 у Wayback Machine.], in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, (H. H. Bauschke, R. S. Burachik[en], P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, Editors), pp. 185—212. Springer, New York, 2011. (англ.)
  7. Yu. Nesterov, «Introductory Lectures on Convex Optimization. A Basic Course» (Springer, 2004, ISBN 1-4020-7553-7) (англ.)
  8. Fast Gradient Methods [ 24 грудня 2012 у Wayback Machine.], lecture notes by Prof. Lieven Vandenberghe for EE236C at UCLA (англ.)
  9. Qian, Ning (January 1999). . Neural Networks[en] 12 (1): 145–151. Архів оригіналу за 8 травня 2014. Процитовано 17 жовтня 2014.  (англ.)
  10. . Willamette University[en]. Архів оригіналу за 21 жовтня 2014. Процитовано 17 жовтня 2014.  (англ.)
  11. Geoffrey Hinton; Nitish Srivastava; Kevin Swersky. . YouTube. Архів оригіналу за 10 травня 2015. Процитовано 18 жовтня 2014.  Частина з серії лекцій для онлайн-курсу Coursera Neural Networks for Machine Learning [ 29 червня 2016 у Wayback Machine.]. (англ.)

Джерела Редагувати

Посилання Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Cya stattya pro algoritm optimizaciyi Pro metod nablizhennya integraliv u matematichnomu analizi div Metod perevalu en Gradiye ntnij spusk angl gradient descent ce iteracijnij algoritm optimizaciyi pershogo poryadku v yakomu dlya znahodzhennya lokalnogo minimumu funkciyi zdijsnyuyutsya kroki proporcijni protilezhnomu znachennyu gradiyentu abo nablizhenogo gradiyentu funkciyi v potochnij tochci Yaksho natomist zdijsnyuyutsya kroki proporcijno samomu znachennyu gradiyentu to vidbuvayetsya nablizhennya do lokalnogo maksimumu ciyeyi funkciyi i cya procedura todi vidoma yak gradiye ntnij pidjo m angl gradient ascent Gradiyentnij spusk vidomij takozh yak najshvi dshij spusk angl steepest descent abo me tod najshvi dshogo spu sku angl method of steepest descent Gradiyentnij spusk ne slid plutati z metodom perevalu en dlya nablizhennya integraliv Zmist 1 Opis 1 1 Prikladi 1 2 Obmezhennya 2 Rozv yazannya linijnoyi sistemi 3 Rozv yazannya nelinijnoyi sistemi 4 Komentari 5 Obchislyuvalni prikladi 5 1 Python 5 2 MATLAB 6 Rozshirennya 6 1 Shvidkij proksimalnij gradiyentnij metod 6 2 Metod impulsu 7 Div takozh 8 Primitki 9 Dzherela 10 PosilannyaOpis Redaguvati nbsp Ilyustraciya metodu najshvidshogo spusku na ryadi mnozhin rivniv Gradiyentnij spusk gruntuyetsya na tomu sposterezhenni sho yaksho funkciya kilkoh zminnih en F x displaystyle F mathbf x nbsp ye viznachenoyu en ta diferencijovnoyu v okoli tochki a displaystyle mathbf a nbsp to F x displaystyle F mathbf x nbsp zmenshuyetsya najshvidshe yaksho jti vid a displaystyle mathbf a nbsp v napryamku protilezhnomu gradiyentovi F displaystyle F nbsp v a displaystyle mathbf a nbsp F a displaystyle nabla F mathbf a nbsp Z cogo viplivaye sho yaksho b a g F a displaystyle mathbf b mathbf a gamma nabla F mathbf a nbsp dlya dostatno malogo g displaystyle gamma nbsp to F a F b displaystyle F mathbf a geq F mathbf b nbsp Inshimi slovami chlen g F a displaystyle gamma nabla F mathbf a nbsp vidnimayetsya vid a displaystyle mathbf a nbsp oskilki mi hochemo ruhatisya proti gradiyentu tobto vniz do minimumu Vrahovuyuchi ce sposterezhennya pochinayut z pripushennya x 0 displaystyle mathbf x 0 nbsp pro lokalnij minimum F displaystyle F nbsp i rozglyadayut taku poslidovnist x 0 x 1 x 2 displaystyle mathbf x 0 mathbf x 1 mathbf x 2 dots nbsp sho x n 1 x n g n F x n n 0 displaystyle mathbf x n 1 mathbf x n gamma n nabla F mathbf x n n geq 0 nbsp Mi mayemo F x 0 F x 1 F x 2 displaystyle F mathbf x 0 geq F mathbf x 1 geq F mathbf x 2 geq cdots nbsp i tomu spodivayemosya sho poslidovnist x n displaystyle mathbf x n nbsp zbigayetsya do bazhanogo lokalnogo minimumu Zauvazhte sho znachennya rozmiru kroku angl step size g displaystyle gamma nbsp dozvoleno zminyuvati na kozhnij iteraciyi Dlya deyakih pripushen stosovno funkciyi F displaystyle F nbsp napriklad sho F displaystyle F nbsp ye opukloyu a F displaystyle nabla F nbsp zadovolnyaye umovi Lipshicya i pevnih variantah viboru g displaystyle gamma nbsp napriklad yaksho jogo vibirayut linijnim poshukom yakij zadovolnyaye umovi Volfe zbizhnist do lokalnogo minimumu mozhe buti garantovano Yaksho funkciya F displaystyle F nbsp ye opukloyu to vsi lokalni minimumi ye takozh i globalnimi minimumami tomu v takomu vipadku gradiyentnij spusk mozhe zbigatisya do globalnogo rozv yazku Cej proces proilyustrovano na zobrazhenni pravoruch Tut pripuskayetsya sho F displaystyle F nbsp viznacheno na ploshini i sho yiyi grafik maye formu chashi Sini krivi ye izoliniyami tobto oblastyami v yakih znachennya F displaystyle F nbsp ye stalim Chervoni strilki yaki vihodyat z tochok pokazuyut napryam protilezhnij gradiyentovi v cij tochci Zauvazhte sho anti gradiyent u tochci ye ortogonalnim do izoliniyi yaka prohodit ciyeyu tochkoyu Vidno sho spusk gradiyentom vede nas do dna chashi tobto do tochki v yakij znachennya funkciyi F displaystyle F nbsp ye minimalnim Prikladi Redaguvati Gradiyentnij spusk maye problemi z patologichnimi funkciyami takimi yak pokazana tut funkciya Rozenbroka f x 1 x 2 1 x 1 2 100 x 2 x 1 2 2 displaystyle f x 1 x 2 1 x 1 2 100 x 2 x 1 2 2 quad nbsp Funkciya Rozenbroka maye vuzku vignutu dolinu yaka mistit minimum Dno ciyeyi dolini ye duzhe pologim Cherez vignutist pologoyi dolini optimizaciya povilno ruhayetsya v napryamku minimumu zigzagom krokami malogo rozmiru nbsp Zigzagopodibna priroda cogo metodu takozh ye ochevidnoyu nizhche de gradiyentnij spusk zastosovano do F x y sin 1 2 x 2 1 4 y 2 3 cos 2 x 1 e y displaystyle F x y sin left frac 1 2 x 2 frac 1 4 y 2 3 right cos 2x 1 e y nbsp nbsp nbsp Obmezhennya Redaguvati Dlya deyakih iz navedenih vishe prikladiv gradiyentnij spusk ye vidnosno povilnim poblizu minimumu z tehnichnoyi tochki zoru jogo asimptotichnij temp zbigannya postupayetsya bagatom inshim metodam Dlya nevdalo obumovlenih opuklih zadach gradiyentnij spusk zigzaguye vse bilshe koli gradiyent vkazuye majzhe ortogonalno do najkorotshogo napryamu do tochki minimumu Dokladnishe div komentari nizhche Dlya nediferencijovnih funkcij gradiyentni metodi ye nedostatno viznachenimi Dlya lokalno lipshicevih zadach ta osoblivo dlya zadach opukloyi optimizaciyi cilkom viznachenimi ye v yazkovi metodi spusku Takozh mozhut zastosovuvatisya ne spuskovi metodi taki yak metodi subgradiyentnoyi proyekciyi 1 Ci metodi zazvichaj ye povilnishimi za gradiyentnij spusk Inshoyu alternativoyu dlya nediferencijovnih funkcij ye zgladzhuvannya cih funkcij abo obmezhennya funkciyi gladkoyu funkciyeyu Za cogo pidhodu rozv yazuyut zgladzhenu zadachu v nadiyi sho vidpovid dlya neyi ye blizkoyu do vidpovidi na nezgladzhenu zadachu inodi ce mozhe buti zrobleno strogim Rozv yazannya linijnoyi sistemi RedaguvatiGradiyentnij spusk mozhe zastosovuvatisya dlya rozv yazannya sistemi linijnih rivnyan pereformulovanogo yak zadacha kvadratichnoyi minimizaciyi napriklad iz zastosuvannyam metodu najmenshih kvadrativ Rozv yazok A x b 0 displaystyle A mathbf x mathbf b 0 nbsp u sensi metodu najmenshih kvadrativ viznachayetsya yak minimizaciya funkciyi F x A x b 2 displaystyle F mathbf x A mathbf x mathbf b 2 nbsp V tradicijnomu metodi najmenshih kvadrativ dlya dijsnih A displaystyle A nbsp ta b displaystyle mathbf b nbsp vikoristovuyetsya evklidova norma i v comu vipadku F x 2 A T A x b displaystyle nabla F mathbf x 2A T A mathbf x mathbf b nbsp V takomu vipadku minimizaciya linijnim poshukom yaka znahodit na kozhnij iteraciyi lokalno optimalnij rozmir kroku g displaystyle gamma nbsp mozhe vikonuvatisya analitichno i yavni formuli lokalno optimalnogo g displaystyle gamma nbsp ye vidomimi 2 Dlya rozv yazannya linijnih rivnyan gradiyentnij spusk zastosovuyetsya ridko a odniyeyu z najpopulyarnishih alternativ ye metod spryazhenih gradiyentiv Shvidkist zbigannya gradiyentnogo spusku zalezhit vid maksimalnogo ta minimalnogo vlasnih znachen A displaystyle A nbsp todi yak shvidkist zbigannya spryazhenih gradiyentiv maye skladnishu zalezhnist vid cih vlasnih znachen i mozhe otrimuvati korist vid peredobumovlyuvannya en Gradiyentnij spusk takozh otrimuye korist vid peredobumovlyuvannya ale ce ne roblyat tak poshireno Rozv yazannya nelinijnoyi sistemi RedaguvatiGradiyentnij spusk mozhe takozh zastosovuvatisya i do rozv yazannya sistem nelinijnih rivnyan Nizhche navedeno priklad yak zastosovuvati gradiyentnij spusk dlya rozv yazannya dlya troh nevidomih zminnih x1 x2 ta x3 Cej priklad pokazuye odnu iteraciyu gradiyentnogo spusku Rozglyanmo sistemu nelinijnih rivnyan 3 x 1 cos x 2 x 3 3 2 0 4 x 1 2 625 x 2 2 2 x 2 1 0 exp x 1 x 2 20 x 3 10 p 3 3 0 displaystyle 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 nbsp pripustimo sho mi mayemo funkciyu 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 p 3 3 displaystyle 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 nbsp de x x 1 x 2 x 3 displaystyle mathbf x begin bmatrix x 1 x 2 x 3 end bmatrix nbsp ta cilovu funkciyu F x 1 2 G T x G x 1 2 3 x 1 cos x 2 x 3 3 2 2 4 x 1 2 625 x 2 2 2 x 2 1 2 exp x 1 x 2 20 x 3 1 3 10 p 3 2 displaystyle 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 nbsp z pochatkovim pripushennyam x 0 x 1 x 2 x 3 0 0 0 displaystyle mathbf x 0 begin bmatrix x 1 x 2 x 3 end bmatrix begin bmatrix 0 0 0 end bmatrix nbsp Mi znayemo sho x 1 x 0 g 0 F x 0 displaystyle mathbf x 1 mathbf x 0 gamma 0 nabla F mathbf x 0 nbsp de F x 0 J G x 0 T G x 0 displaystyle nabla F mathbf x 0 J G mathbf x 0 mathrm T G mathbf x 0 nbsp Matricya Yakobi J G x 0 displaystyle J G mathbf x 0 nbsp J G 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 displaystyle J G begin bmatrix 3 amp sin x 2 x 3 x 3 amp sin x 2 x 3 x 2 8x 1 amp 1250x 2 2 amp 0 x 2 exp x 1 x 2 amp x 1 exp x 1 x 2 amp 20 end bmatrix nbsp Potim obchislimo ci chleni v x 0 displaystyle mathbf x 0 nbsp J G x 0 3 0 0 0 2 0 0 0 20 G x 0 2 5 1 10 472 displaystyle J G left mathbf x 0 right begin bmatrix 3 amp 0 amp 0 0 amp 2 amp 0 0 amp 0 amp 20 end bmatrix qquad G mathbf x 0 begin bmatrix 2 5 1 10 472 end bmatrix nbsp Otzhe x 1 0 g 0 7 5 2 209 44 displaystyle mathbf x 1 0 gamma 0 begin bmatrix 7 5 2 209 44 end bmatrix nbsp ta F x 0 0 5 2 5 2 1 2 10 472 2 58 456 displaystyle F left mathbf x 0 right 0 5 left 2 5 2 1 2 10 472 2 right 58 456 nbsp nbsp Animaciya yaka pokazuye pershi 83 iteraciyi gradiyentnogo spusku sho zastosovuyetsya do cogo prikladu Poverhni ye izopoverhnyami F x n displaystyle F mathbf x n nbsp na potochnomu pripushenni x n displaystyle mathbf x n nbsp a strilki pokazuyut napryamok spusku Z prichini malogo ta nezminnogo kroku zbigannya ye povilnim Teper musit buti znajdeno pridatnij g 0 displaystyle gamma 0 nbsp takij sho F x 1 F x 0 displaystyle F mathbf x 1 leq F mathbf x 0 nbsp Ce mozhna zrobiti za dopomogoyu bud yakogo z bezlichi algoritmiv linijnogo poshuku Mozhna takozh prosto pripustiti g 0 0 001 displaystyle gamma 0 0 001 nbsp sho daye x 1 0 0075 0 002 0 20944 displaystyle mathbf x 1 begin bmatrix 0 0075 0 002 0 20944 end bmatrix nbsp Pri obchislenni na comu znachenni F x 1 0 5 2 48 2 1 00 2 6 28 2 23 306 displaystyle F left mathbf x 1 right 0 5 left 2 48 2 1 00 2 6 28 2 right 23 306 nbsp Zmenshennya z F x 0 58 456 displaystyle F mathbf x 0 58 456 nbsp do znachennya nastupnogo kroku F x 1 23 306 displaystyle F mathbf x 1 23 306 nbsp ye vidchutnim zmenshennyam cilovoyi funkciyi Podalshi kroki znizhuvatimut yiyi znachennya doti doki ne bude znajdeno rozv yazok sistemi Komentari RedaguvatiGradiyentnij spusk pracyuye v prostorah z bud yakim chislom vimiriv navit u neskinchennovimirnih V ostannomu vipadku prostir poshuku zazvichaj ye prostorom funkcij en i dlya viznachennya napryamku spusku zdijsnyuyetsya obchislennya pohidnoyi Gato funkcionalu yakij minimizuyut 3 Yaksho krivina zadanoyi funkciyi duzhe riznitsya v riznih napryamkah to gradiyentnomu spuskovi mozhe znadobitisya bagato iteracij dlya obchislennya lokalnogo minimumu z potribnoyu tochnistyu Dlya takih funkcij povilne zbigannya likuyetsya peredobumovlyuvannyam en yake zminyuye geometriyu prostoru tak shobi nadati mnozhinam rivniv funkciyi formi koncentrichnih kil Prote pobudova ta zastosuvannya peredobumovlyuvannya mozhut buti obchislyuvalno vitratnimi Gradiyentnij spusk mozhna poyednuvati z linijnim poshukom yakij na kozhnij iteraciyi shukaye lokalno optimalnij rozmir kroku g displaystyle gamma nbsp Vikonannya linijnogo poshuku mozhe buti vitratnim za chasom Z inshogo boku zastosuvannya nezminnogo malogo g displaystyle gamma nbsp mozhe davati poganu zbizhnist Krashimi alternativami mozhut buti metodi na osnovi metodu Nyutona ta obernennya gessianu iz zastosuvannyam metodik spryazhenih gradiyentiv 4 5 Zagalom taki metodi zbigayutsya za menshu kilkist iteracij ale vartist kozhnoyi iteraciyi ye vishoyu Prikladom ye Metod BFGSh yakij skladayetsya z obchislennya na kozhnomu kroci matrici na yaku mnozhitsya vektor gradiyentu shobi jti v najkrashomu napryamku poyednanogo zi skladnishim algoritmom linijnogo poshuku dlya znahodzhennya najkrashogo znachennya g displaystyle gamma nbsp Dlya nadzvichajno velikih zadach u yakih dominuyut pitannya komp yuternoyi pam yati zamist BFGSh abo najshvidshogo spusku povinni zastosovuvatisya metodi z obmezhenoyu pam yattyu taki yak O BFGSh en Gradiyentnij spusk mozhe rozglyadatisya yak metod Ejlera dlya rozv yazannya zvichajnih diferencijnih rivnyan x t f x t displaystyle x t nabla f x t nbsp potoku gradiyenta Obchislyuvalni prikladi RedaguvatiPython Redaguvati Algoritm gradiyentnogo spusku zastosovuyetsya dlya znahodzhennya lokalnogo minimumu funkciyi f x x4 3x3 2 z pohidnoyu f x 4x3 9x2 Os realizaciya movoyu programuvannya Python Vihodyachi z obchislen mi ochikuyemo sho lokalnij minimum matime misce v x 9 4 x old 0 Ce znachennya ne vazhlive oskilki abs x new x old gt precision x new 6 Algoritm startuye z x 6 gamma 0 01 rozmir kroku precision 0 00001 def f derivative x return 4 x 3 9 x 2 while abs x new x old gt precision x old x new x new x old gamma f derivative x old print Lokalnij minimum maye misce v x new Navedenij vishe fragment kodu maye buti zmineno po vidnoshennyu do rozmiru kroku vidpovidno do sistemi yaka ye pid rukami a zbizhnist mozhe buti zrobleno shvidshoyu shlyahom zastosuvannya adaptivnogo rozmiru kroku V navedenomu vishe vipadku rozmir kroku ne ye adaptivnim Vin zalishayetsya na rivni 0 01 v usih napryamkah sho mozhe inodi prizvoditi do nevdachi metodu za rahunok vidhilennya vid minimumu MATLAB Redaguvati Nastupnij kod MATLAB demonstruye konkretne rishennya dlya rozv yazannya sistemi nelinijnih rivnyan predstavlenoyi v poperednomu rozdili 3 x 1 cos x 2 x 3 3 2 0 4 x 1 2 625 x 2 2 2 x 2 1 0 exp x 1 x 2 20 x 3 10 p 3 3 0 displaystyle 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 nbsp Bagatovimirna vektor funkciya 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 Yakobian 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 Cilova funkciya F x yaku potribno minimizuvati shobi rozv yazati G x 0 F x 0 5 sum G x 2 Gradiyent F chastkovi pohidni dF x JG x G x Parametri GAMMA 0 001 rozmir kroku temp navchannya MAX ITER 1000 maksimalne chislo iteracij FUNC TOL 0 1 kinceve dopustime vidhilennya F x fvals zberigannya znachen F x protyagom iteracij progress iter x fprintf iter 3d x 32s F x f n iter mat2str x 6 F x Iteruvannya iter 1 lichilnik iteracij x 0 0 0 pochatkove pripushennya fvals iter F x progress iter x while iter lt MAX ITER amp amp fvals end gt FUNC TOL iter iter 1 x x GAMMA dF x gradiyentnij spusk fvals iter F x obchisliti cilovu funkciyu progress iter x pokazati perebig end Nakresliti plot 1 iter fvals LineWidth 2 grid on title Objective Function xlabel Iteration ylabel F x Obchisliti kincevij rozv yazok sistemi rivnyan G x 0 disp G x disp G x Vivedennya 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 zbiglosya za 188 iteracij pislya perevishennya kincevogo dopustimogo vidhilennya F x Rozshirennya RedaguvatiGradiyentnij spusk mozhe buti rozshireno dlya pidtrimki obmezhen shlyahom vklyuchennya proyekciyi na mnozhinu obmezhen Cej metod pidhodit lishe todi koli cya proyekciya ye efektivno obchislyuvanoyu na komp yuteri Za zruchnih pripushen cej metod zbigayetsya Cej metod ye okremim vipadkom poslidovno zvorotnogo algoritmu dlya monotonnih vklyuchen yakij vklyuchaye opukle programuvannya ta variacijni nerivnosti en 6 Shvidkij proksimalnij gradiyentnij metod Redaguvati Inshe rozshirennya gradiyentnogo spusku viniklo zavdyaki Yuriyevi Nesterovu en 1983 roku 7 i bulo zgodom uzagalnene Vin proponuye prostu vidozminu cogo algoritmu yaka umozhlivlyuye shvidke zbigannya dlya opuklih zadach A same yaksho funkciya F displaystyle F nbsp ye opukloyu a F displaystyle nabla F nbsp ye lipshicevoyu i nemaye pripushennya sho F displaystyle F nbsp ye silno opukloyu to pohibku cilovogo znachennya porodzhuvanu metodom gradiyentnogo spusku na kozhnomu kroci k displaystyle k nbsp bude obmezheno O 1 k displaystyle mathcal O 1 k nbsp Iz zastosuvannyam metodiki priskorennya Nesterova pohibka znizhuyetsya do O 1 k 2 displaystyle mathcal O 1 k 2 nbsp 8 Metod impulsu Redaguvati She odnim rozshirennyam yake znizhuye rizik zastryagnuti v lokalnomu minimumi a takozh istotno priskoryuye zbizhnist u vipadkah koli inakshe proces bi silno zigzaguvav ye metod impulsu angl momentum method yakij vikoristovuye chlen impulsu po analogiyi z masoyu nyutonovih chastinok yaki ruhayutsya v yazkim seredovishem u konservativnomu silovomu poli 9 Cej metod chasto vikoristovuyut yak rozshirennya algoritmiv zvorotnogo poshirennya sho zastosovuyutsya dlya trenuvannya shtuchnih nejronnih merezh 10 11 Div takozh RedaguvatiMetod spryazhenogo gradiyenta Metod proksimalnogo gradiyenta Stohastichnij gradiyentnij spusk Rprop en Delta pravilo Umovi Volfe Peredobumovlyuvannya en Metod BFGSh Metod Neldera Mida Algoritm Frank VulfaPrimitki Redaguvati Kiwiel Krzysztof C 2001 Convergence and efficiency of subgradient methods for quasiconvex minimization Mathematical Programming Series A 90 1 Berlin Heidelberg Springer s 1 25 ISSN 0025 5610 MR 1819784 doi 10 1007 PL00011414 angl Yuan Ya xiang 1999 Step sizes for the gradient method AMS IP Studies in Advanced Mathematics Providence RI American Mathematical Society 42 2 785 angl G P Akilov L V Kantorovich Functional Analysis Pergamon Pr 2 Sub edition ISBN 0 08 023036 9 1982 angl 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 angl 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 angl P L Combettes and J C Pesquet Proximal splitting methods in signal processing Arhivovano 7 lipnya 2011 u Wayback Machine in Fixed Point Algorithms for Inverse Problems in Science and Engineering H H Bauschke R S Burachik en P L Combettes V Elser D R Luke and H Wolkowicz Editors pp 185 212 Springer New York 2011 angl Yu Nesterov Introductory Lectures on Convex Optimization A Basic Course Springer 2004 ISBN 1 4020 7553 7 angl Fast Gradient Methods Arhivovano 24 grudnya 2012 u Wayback Machine lecture notes by Prof Lieven Vandenberghe for EE236C at UCLA angl Qian Ning January 1999 On the momentum term in gradient descent learning algorithms Neural Networks en 12 1 145 151 Arhiv originalu za 8 travnya 2014 Procitovano 17 zhovtnya 2014 angl Momentum and Learning Rate Adaptation Willamette University en Arhiv originalu za 21 zhovtnya 2014 Procitovano 17 zhovtnya 2014 angl Geoffrey Hinton Nitish Srivastava Kevin Swersky 6 3 The momentum method YouTube Arhiv originalu za 10 travnya 2015 Procitovano 18 zhovtnya 2014 Chastina z seriyi lekcij dlya onlajn kursu Coursera Neural Networks for Machine Learning Arhivovano 29 chervnya 2016 u Wayback Machine angl Dzherela RedaguvatiMordecai Avriel 2003 Nonlinear Programming Analysis and Methods Dover Publishing ISBN 0 486 43227 0 angl 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 angl 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 Arhivovano 11 grudnya 2018 u Wayback Machine angl Cauchy Augustin 1847 Methode generale pour la resolution des systemes d equations simultanees s 536 538 Arhiv originalu za 13 zhovtnya 2016 Procitovano 31 lipnya 2016 fr Enciklopediya kibernetiki u 2 t za red V M Glushkova Kiyiv Gol red Ukrayinskoyi radyanskoyi enciklopediyi 1973 Polyak R A Primak M E t 2 st 64 Posilannya RedaguvatiZastosuvannya gradiyentnogo spusku v C Boost Ublas dlya linijnoyi regresiyi Arhivovano 22 lipnya 2013 u Wayback Machine Otrimano z https uk wikipedia org w index php title Gradiyentnij spusk amp oldid 39706979