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

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

Опис

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

${\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 .}$

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

Диференційований випадок

У випадку неперервно диференційованої функції ${\displaystyle F}$, алгоритм координатного спуску може бути представлений як:

1. Виберіть початковий параметричний вектор ${\displaystyle X}$.
2. До тих пір, поки не буде досягнута збіжність або для певної кількості ітерацій:
3. Виберіть індекс ${\displaystyle i}$ від 1 до ${\displaystyle n}$.
4. Виберіть розмір кроку ${\displaystyle a}$.
5. Оновлюйте ${\displaystyle {x_{i}}}$ до ${\displaystyle {x_{i}-\alpha {\dfrac {dF}{dx_{i}}}(X)}.}$

Розмір кроку може бути вибраний різними способами, наприклад, шляхом вирішення точного мінімізатора ${\displaystyle f(x_{i})=F(x)}$ (тобто, ${\displaystyle F}$ зі всіма змінними, але фіксованими ${\displaystyle x_{i}}$), або за традиційними критеріями пошуку рядків.

Обмеження

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

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

Застосування

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

Див. також

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

Примітки

1. Wright, Stephen J. (2015-06). Coordinate descent algorithms. Mathematical Programming (англ.). Т. 151, № 1. с. 3—34. doi:10.1007/s10107-015-0892-3. ISSN 0025-5610. Процитовано 23 грудня 2019.
2. Spall, James C. (2012-07). Cyclic Seesaw Process for Optimization and Identification. Journal of Optimization Theory and Applications (англ.). Т. 154, № 1. с. 187—208. doi:10.1007/s10957-012-0001-1. ISSN 0022-3239. Процитовано 23 грудня 2019.
3. Zheng, J.; Saquib, S.S.; Sauer, K.; Bouman, C.A. (2000). Parallelizable Bayesian tomography algorithms with rapid, guaranteed convergence. IEEE Transactions on Image Processing. Т. 9, № 10. с. 1745—1759. doi:10.1109/83.869186. ISSN 1057-7149. Процитовано 23 грудня 2019.
4. Fessler, J.A.; Ficaro, E.P.; Clinthorne, N.H.; Lange, K. (1997-04). Grouped-coordinate ascent algorithms for penalized-likelihood transmission image reconstruction. IEEE Transactions on Medical Imaging. Т. 16, № 2. с. 166—175. doi:10.1109/42.563662. ISSN 0278-0062. Процитовано 23 грудня 2019.
5. Sabne, Amit; Wang, Xiao; Kisner, Sherman J.; Bouman, Charles A.; Raghunathan, Anand; Midkiff, Samuel P. (2017). Model-based Iterative CT Image Reconstruction on GPUs. Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP '17. ACM Press. doi:10.1145/3018743.3018765. ISBN . Процитовано 23 грудня 2019.
6. Sauer, K.; Bouman, C. (1993). A local update strategy for iterative reconstruction from projections. IEEE Transactions on Signal Processing. Т. 41, № 2. с. 534—548. doi:10.1109/78.193196. ISSN 1053-587X. Процитовано 23 грудня 2019.
7. Yu, Zhou; Thibault, Jean-Baptiste; Bouman, Charles A.; Sauer, Ken D.; Hsieh, Jiang (2011-01). Fast Model-Based X-Ray CT Reconstruction Using Spatially Nonhomogeneous ICD Optimization. IEEE Transactions on Image Processing. Т. 20, № 1. с. 161—175. doi:10.1109/tip.2010.2058811. ISSN 1057-7149. Процитовано 23 грудня 2019.
8. Thibault, Jean-Baptiste; Sauer, Ken D.; Bouman, Charles A.; Hsieh, Jiang (29 жовтня 2007). A three-dimensional statistical approach to improved image quality for multislice helical CT. Medical Physics. Т. 34, № 11. с. 4526—4544. doi:10.1118/1.2789499. ISSN 0094-2405. Процитовано 23 грудня 2019.
9. Hsieh, Cho-Jui; Chang, Kai-Wei; Lin, Chih-Jen; Keerthi, S. Sathiya; Sundararajan, S. (2008). A dual coordinate descent method for large-scale linear SVM. Proceedings of the 25th international conference on Machine learning - ICML '08. ACM Press. doi:10.1145/1390156.1390208. ISBN . Процитовано 23 грудня 2019.
10. Hsieh, Cho-Jui; Dhillon, Inderjit S. (2011). Fast coordinate descent methods with variable selection for non-negative matrix factorization. Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11. ACM Press. doi:10.1145/2020408.2020577. ISBN . Процитовано 23 грудня 2019.
11. Nesterov, Yu. (2012-01). Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems. SIAM Journal on Optimization. Т. 22, № 2. с. 341—362. doi:10.1137/100802001. ISSN 1052-6234. Процитовано 23 грудня 2019.