Координатний спуск

Координатний спуск заснований на ідеї, що мінімізація багатоваріантної функції ${\displaystyle F(x)}$ може бути досягнута шляхом мінімізації її по одному напрямку за один раз, тобто, вирішення одноманітної (або, принаймні, набагато простішої) проблеми оптимізації в циклі.[1] У найпростішому випадку циклічного координатного спуску, він циклічно повторюється через напрямки, по одному, мінімізуючи цільову функцію щодо кожного напрямку координат одночасно. Тобто, починаючи з початкових значень змінних

${\displaystyle \mathbf {x} ^{0}=(x_{1}^{0},\ldots ,x_{n}^{0}),}$

крок ${\displaystyle k+1}$ задає ${\displaystyle \mathbf {x} ^{k+1}}$ з ${\displaystyle \mathbf {x} ^{k}}$ ітеративно розв'язує проблеми оптимізації єдиної змінної

${\displaystyle x_{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^{k},\dots ,x_{n}^{k})}$

для кожної змінної ${\displaystyle x_{i}}$ з ${\displaystyle \mathbf {x} }$ для ${\displaystyle i}$ від 1 до ${\displaystyle n}$.

Таким чином, починаючи з початкової догадки ${\displaystyle \mathbf {x} ^{0}}$ для локального мінімуму функції ${\displaystyle F}$, і отримуючи ітеративно послідовність ${\displaystyle {\mathbf {x} }^{0},{\mathbf {x} }^{1},{\mathbf {x} }^{2},\dots }$

Використовуючи лінійний пошук кожної ітерації, ми автоматично отримуємо, що

${\displaystyle F(\mathbf {x} ^{0})\geq F(\mathbf {x} ^{1})\geq F(\mathbf {x} ^{2})\geq \dots .}$

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

Координатний спуск має дві проблеми. Одна з них — це відсутність гладкої функції багатьох змінних. На наступному малюнку видно, що ітеративний спуск координатами може застрягнути в нестаціонарній точці, якщо криві рівня функції не є гладкими. Припустимо, що алгоритм знаходиться в точці (-2, -2); Тоді є два напрями, орієнтовані на осі, які можна розглянути для кроку, позначені червоними стрілками. Однак кожен крок уздовж цих двох напрямків збільшуватиме значення цільової функції (припускаючи проблему мінімізації), тому алгоритм не зробить жодного кроку, навіть якщо обидва кроки разом наблизили б алгоритм до оптимального. Хоча цей приклад показує, що спуск координатами не обов'язково збігається з оптимальним, можливо виявити формальне зближення при розумних умовах.[2]

Інша проблема — це складність розпаралелювання даного алгоритму. Оскільки суть координатного спуску полягає у проходженні напрямків та мінімізації цільової функції стосовно кожного координатного напрямку, спуск координат не є тривіальною задачею для паралелізму. Останні дослідницькі роботи показали, що паралелізм застосовується для координатного спуску шляхом послаблення зміни цільової функції стосовно кожного координатного напрямку.[3][4][5]

Алгоритми координатного спуску користуються популярністю у практикантів завдяки своїй простоті, але та сама властивість змусила дослідників оптимізації значною мірою ігнорувати їх на користь більш цікавих (складних) методів. Раннє застосування оптимізації методом спуску координат було в області комп'ютерної томографії[6], де було виявлено швидку збіжність[7], а згодом було використано для клінічної реконструкції багатоклітинної спіральної томографії[8]. Крім того, виявився підвищений інтерес до використання координатного спуску з появою масштабних проблем у машинному навчанні, коли спуск координат виявився конкурентоспроможним для інших методів при застосуванні до таких проблем, як навчання лінійних методу опорних векторів[9] і розкладу невід'ємних матриць[10]. Вони привабливі для проблем, коли обчислення градієнтів недосяжно, можливо, тому, що дані, необхідні для цього, поширюються по комп'ютерних мережах.[11]

• Градієнтний спуск
• Метод стохастичного градієнта
• Оптимізація (математика)