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

Математический алгоритм

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

Описание

Координатный спуск основан на идее о том, что минимизации функции многих переменных можно достичь, минимизируя ее по одному направлению за раз, т. е. решая одномерные (или, по крайней мере, гораздо более простые) задачи оптимизации в цикле. ^[1] В простейшем случае циклического спуска по координатам происходит циклическое перебор направлений по одному, минимизируя целевую функцию по отношению к каждому направлению координат за раз. То есть начиная с начальных значений переменных ${\displaystyle F(\mathbf {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})}$^[2]

для каждой переменной , от 1 до . ${\displaystyle x_{i}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle i}$ ${\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 .}$

Можно показать, что эта последовательность имеет те же свойства сходимости, что и наискорейший спуск. Отсутствие улучшения после одного цикла поиска линии по направлениям координат означает достижение стационарной точки.

Этот процесс проиллюстрирован ниже.

Дифференцируемый случай

В случае непрерывно дифференцируемой функции F алгоритм спуска по координатам можно представить следующим образом: ^[1]

• Выберите начальный вектор параметров x .
• До тех пор, пока не будет достигнута сходимость, или в течение некоторого фиксированного количества итераций:
  • Выберите индекс i от 1 до n .
  • Выберите размер шага α .
  • Обновить x _i до x _i − α∂ Ф/∂ х _я( Икс ) .

Размер шага можно выбрать различными способами, например, путем поиска точного минимизатора f ( x _i ) = F ( x ) (т. е. F со всеми переменными, кроме x _i, фиксированными) или с помощью традиционных критериев поиска строки. ^[1]

Ограничения

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

Другая проблема — сложность параллелизма. Поскольку природа координатного спуска заключается в циклическом переборе направлений и минимизации целевой функции по отношению к каждому координатному направлению, координатный спуск не является очевидным кандидатом на массовый параллелизм. Недавние исследовательские работы показали, что массивный параллелизм применим к спуску по координатам за счет ослабления изменения целевой функции по отношению к каждому направлению координат. ^{[4] [5] [6]}

Приложения

Алгоритмы координатного спуска популярны среди практиков благодаря своей простоте, но это же свойство привело к тому, что исследователи оптимизации в значительной степени игнорировали их в пользу более интересных (сложных) методов. ^[1] Раннее применение оптимизации координатного спуска было в области компьютерной томографии ^[7] , где было обнаружено, что она имеет быструю сходимость ^[8] и впоследствии использовалась для клинической многосрезовой КТ-реконструкции со спиральным сканированием. ^[9] Алгоритм спуска циклических координат (CCD) применялся для предсказания структуры белка. ^[10] Более того, возрос интерес к использованию координатного спуска с появлением крупномасштабных задач в машинном обучении , где координатный спуск оказался конкурентоспособным по сравнению с другими методами применительно к таким задачам, как обучение машин с линейными опорными векторами ^{[10] 11]} (см. LIBLINEAR ) и неотрицательную матричную факторизацию . ^[12] Они привлекательны для задач, где вычисление градиентов невозможно, возможно, потому, что необходимые для этого данные распределены по компьютерным сетям. ^[13]

Смотрите также

• Адаптивный спуск по координатам
• Сопряженный градиент
• Градиентный спуск
• Поиск линии
• Математическая оптимизация
• метод Ньютона
• Стохастический градиентный спуск - использует один пример за раз, а не одну координату.

Рекомендации

1. Райт, Стивен Дж. (2015). «Алгоритмы координатного спуска». Математическое программирование . 151 (1): 3–34. arXiv : 1502.04759 . дои : 10.1007/s10107-015-0892-3. S2CID  15284973.
2. https://www.cs.cmu.edu/~ggordon/10725-F12/slides/25-coord-desc.pdf ^{[ пустой URL-адрес PDF ]}
3. Сполл, JC (2012). «Циклический качающийся процесс для оптимизации и идентификации». Журнал теории оптимизации и приложений . 154 (1): 187–208. дои : 10.1007/s10957-012-0001-1. S2CID  7795605.
4. Чжэн, Дж.; Сакиб, СС; Зауэр, К.; Бауман, Калифорния (01 октября 2000 г.). «Параллелизуемые алгоритмы байесовской томографии с быстрой гарантированной сходимостью». Транзакции IEEE при обработке изображений . 9 (10): 1745–1759. Бибкод : 2000ITIP....9.1745Z. CiteSeerX 10.1.1.34.4282 . дои : 10.1109/83.869186. ISSN  1057-7149. ПМИД  18262913. 
5. Фесслер, Дж. А.; Фикаро, EP; Клинторн, Нью-Хэмпшир; Ланге, К. (1 апреля 1997 г.). «Алгоритмы подъема по сгруппированным координатам для восстановления изображений передачи с штрафной вероятностью». Транзакции IEEE по медицинской визуализации . 16 (2): 166–175. дои : 10.1109/42.563662. hdl : 2027.42/86021 . ISSN  0278-0062. PMID  9101326. S2CID  1523517.
6. Ван, Сяо; Сабне, Амит; Киснер, Шерман; Рагунатан, Ананд; Боуман, Чарльз; Мидкифф, Сэмюэл (1 января 2016 г.). «Высокопроизводительная реконструкция изображений на основе моделей». Материалы 21-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования. ППоПП '16. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 2:1–2:12. дои : 10.1145/2851141.2851163. ISBN 9781450340922. S2CID  16569156.
7. Зауэр, Кен; Бауман, Чарльз (февраль 1993 г.). «Стратегия локального обновления для итеративной реконструкции на основе прогнозов» (PDF) . Транзакции IEEE по обработке сигналов . 41 (2): 534–548. Бибкод : 1993ITSP...41..534S. CiteSeerX 10.1.1.135.6045 . дои : 10.1109/78.193196. 
8. Ю, Чжоу; Тибо, Жан-Батист; Боуман, Чарльз; Зауэр, Кен; Се, Цзян (январь 2011 г.). «Быстрая реконструкция рентгеновской компьютерной томографии на основе модели с использованием пространственно-неоднородной оптимизации ICD» (PDF) . Транзакции IEEE при обработке изображений . 20 (1): 161–175. Бибкод : 2011ИТИП...20..161Г. дои : 10.1109/TIP.2010.2058811. PMID  20643609. S2CID  9315957.
9. Тибо, Жан-Батист; Зауэр, Кен; Боуман, Чарльз; Се, Цзян (ноябрь 2007 г.). «Трехмерный статистический подход к улучшению качества изображений для многосрезовой спиральной КТ» (PDF) . Медицинская физика . 34 (11): 4526–4544. Бибкод : 2007MedPh..34.4526T. дои : 10.1118/1.2789499. ПМИД  18072519.
10. Канутеску, А.А.; Данбрэк, РЛ (2003). «Циклический спуск по координатам: робототехнический алгоритм замыкания белковой петли». Белковая наука . 12 (5): 963–72. дои : 10.1110/ps.0242703. ПМК 2323867 . ПМИД  12717019. 
11. Се, CJ; Чанг, КВ; Лин, CJ; Кирти, СС; Сундарараджан, С. (2008). «Метод спуска по двойным координатам для крупномасштабной линейной SVM» (PDF) . Материалы 25-й международной конференции по машинному обучению ICML '08 . п. 408. дои : 10.1145/1390156.1390208. ISBN 9781605582054. S2CID  7880266.
12. Се, CJ; Диллон, Исландия (2011). Методы быстрого координатного спуска с выбором переменных для факторизации неотрицательной матрицы (PDF) . Материалы 17-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных - KDD '11. п. 1064. дои : 10.1145/2020408.2020577. ISBN 9781450308137.
13. Нестеров, Юрий (2012). «Эффективность методов координатного спуска в крупномасштабных задачах оптимизации» (PDF) . СИАМ Дж. Оптим . 22 (2): 341–362. CiteSeerX 10.1.1.332.3336 . дои : 10.1137/100802001. 

• Бездек, Дж. К.; Хэтэуэй, Р.Дж.; Ховард, RE; Уилсон, Калифорния; Виндхэм, член парламента (1987), «Локальный анализ сходимости версии координатного спуска с сгруппированными переменными», Журнал теории оптимизации и приложений , Kluwer Academic/Plenum Publishers, vol. 54, нет. 3, стр. 471–477, номер документа : 10.1007/BF00940196, S2CID  120052975.
• Берцекас, Дмитрий П. (1999). Нелинейное программирование, второе издание Athena Scientific, Белмонт, Массачусетс. ISBN 1-886529-00-0 . 
• Ло, Чжицюань; Ценг, П. (1992), «О сходимости метода координатного спуска для выпуклой дифференцируемой минимизации», Журнал теории оптимизации и приложений , Kluwer Academic/Plenum Publishers, vol. 72, нет. 1, стр. 7–35, doi : 10.1007/BF00939948, hdl : 1721.1/3164 , S2CID  121091844..
• Ву, ТонгТонг; Ланге, Кеннет (2008), «Алгоритмы спуска по координатам для регрессии с штрафом по Лассо», Анналы прикладной статистики , Институт математической статистики, том. 2, нет. 1, стр. 224–244, arXiv : 0803.3876 , doi : 10.1214/07-AOAS147, S2CID  16350311.
• Рихтарик, Питер; Такач, Мартин (апрель 2011 г.), «Сложность итерации рандомизированных методов блочно-координатного спуска для минимизации сложной функции», Mathematical Programming , Springer, vol. 144, нет. 1–2, стр. 1–38, arXiv : 1107.2848 , doi : 10.1007/s10107-012-0614-z, S2CID  16816638.
• Рихтарик, Питер; Такач, Мартин (декабрь 2012 г.), «Методы параллельного спуска по координатам для оптимизации больших данных», ArXiv:1212.0873 , arXiv : 1212.0873.