Алгоритм ММ

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

Алгоритм ожидания-максимизации можно рассматривать как частный случай алгоритма ММ. Однако в алгоритме EM обычно используются условные ожидания , тогда как в алгоритме MM основное внимание уделяется выпуклости и неравенствам, и в большинстве случаев его легче понять и применить.

История

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

Алгоритм

Алгоритм ММ

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

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

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

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

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

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

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

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

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

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

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

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

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