Координатний спуск — Вікіпедія

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

В іншому мовному розділі є повніша стаття Coordinate descent(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (грудень 2019) Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.

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

Опис[ред. | ред. код]

Координатний спуск заснований на ідеї, що мінімізація багатоваріантної функції ${\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 .}$

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

Диференційований випадок[ред. | ред. код]

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

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}}$), або за традиційними критеріями пошуку рядків.^[1]

Обмеження[ред. | ред. код]

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

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

Застосування[ред. | ред. код]

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

Див. також[ред. | ред. код]

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

Примітки[ред. | ред. код]