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

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

Опис

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

${𝐱}^0=(x_1^0,\dots ,x_n^0),$

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

$x_i^{k+1}=\underset{y\in ℝ}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}f(x_1^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^k,\dots ,x_n^k)$

для кожної змінної $x_i$ з $𝐱$ для $i$ від 1 до $n$.

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

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

$F({𝐱}^0)\ge F({𝐱}^1)\ge F({𝐱}^2)\ge \dots .$

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

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

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

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

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

Обмеження

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

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

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

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

Див. також

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