Алгоритм MM - MM algorithm

В Алгоритм MM это итеративный оптимизация метод, который использует выпуклость функции, чтобы найти ее максимум или минимум. MM означает «Majorize-Minimization» или «Minorize-Maximization», в зависимости от того, является ли желаемая оптимизация максимизацией или минимизацией. Сама по себе ММ - это не алгоритм, а описание того, как построить алгоритм оптимизации.

В алгоритм ожидания – максимизации можно рассматривать как частный случай алгоритма ММ.^[1][2]Однако в алгоритме EM условные ожидания обычно задействованы, тогда как в алгоритме MM выпуклость и неравенства являются основным направлением, и его легче понять и применить в большинстве случаев.^{[требуется разъяснение ]}

История

Историческую основу алгоритма MM можно отнести к 1970 году, когда Ортега и Райнбольдт проводили исследования, связанные с линейный поиск методы.^[3] Одна и та же концепция продолжала появляться в разных областях в разных формах. В 2000 году Хантер и Ланге выдвинули «ММ» в качестве общей основы.^[4] Недавние исследования^{[ВОЗ? ]} применили метод в широком диапазоне предметных областей, таких как математика, статистика, машинное обучение и инженерное дело.^{[нужна цитата ]}

Алгоритм

Алгоритм MM работает, находя суррогатную функцию, которая минимизирует или увеличивает целевую функцию. Оптимизация суррогатной функции либо улучшит значение целевой функции, либо оставит его без изменений.

Взяв версию с минимизацией максимизации, пусть ${\displaystyle f(\theta )}$ - целевая вогнутая функция, которую нужно максимизировать. На м шаг алгоритма, ${\displaystyle m=0,1...}$, построенная функция ${\displaystyle g(\theta |\theta _{m})}$ будет называться минорной версией целевой функции (суррогатной функцией) в ${\displaystyle \theta _{m}}$ если

${\displaystyle g(\theta |\theta _{m})\leq f(\theta ){\text{ for all }}\theta }$

${\displaystyle g(\theta _{m}|\theta _{m})=f(\theta _{m})}$

Затем максимизируйте ${\displaystyle g(\theta |\theta _{m})}$ вместо ${\displaystyle f(\theta )}$, и разреши

${\displaystyle \theta _{m+1}=\arg \max _{\theta }g(\theta |\theta _{m})}$

Вышеупомянутый итерационный метод гарантирует, что ${\displaystyle f(\theta _{m})}$ будет сходиться к локальному оптимуму или седловой точке как м уходит в бесконечность.^[5] По приведенной выше конструкции

${\displaystyle f(\theta _{m+1})\geq g(\theta _{m+1}|\theta _{m})\geq g(\theta _{m}|\theta _{m})=f(\theta _{m})}$

Поход ${\displaystyle \theta _{m}}$ а суррогатные функции относительно целевой функции показаны на рисунке.

Алгоритм MM

Majorize-Minimization - это та же процедура, но с выпуклой целью, которую нужно минимизировать.

Построение суррогатной функции

Можно использовать любое неравенство для построения желаемой мажоритарной / минорной версии целевой функции. Типичный выбор включает

• Неравенство Дженсена
• Неравенство выпуклости
• Неравенство Коши – Шварца
• Неравенство средних арифметических и геометрических
• Квадратичное мажорирование / мининоризация второго порядка Расширение Тейлора дважды дифференцируемых функций ограниченной кривизны.

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

1. Ланге, Кеннет. «Алгоритм ММ» (PDF).
2. Кеннет Ланге: «Алгоритмы оптимизации MM», SIAM, ISBN  978-1-611974-39-3 (2016).
3. Ортега, J.M .; Райнбольдт, W.C. (1970). Итерационные решения нелинейных уравнений с несколькими переменными. Нью-Йорк: Академ. стр.253 –255. ISBN  9780898719468.
4. Хантер, Д.Р .; Ланге, К. (2000). «Квантильная регрессия с помощью алгоритма ММ». Журнал вычислительной и графической статистики. 9 (1): 60–77. CiteSeerX  10.1.1.206.1351. Дои:10.2307/1390613. JSTOR  1390613.
5. Ву, К.Ф. Джефф (1983). «О свойствах сходимости EM-алгоритма». Анналы статистики. 11 (1): 95–103. Дои:10.1214 / aos / 1176346060. JSTOR  2240463.