Введение

Итеративный метод для нахождения оценок максимального правдоподобия в статистических моделях

В статистике алгоритм "ожидание-максимизация" (EM) — это итеративный метод для нахождения (локальных) оценок максимального правдоподобия или максимальных апостериорных (MAP) оценок параметров в статистических моделях, где модель зависит от ненаблюдаемых латентных переменных. Итерация EM чередуется между выполнением шага ожидания (E), который создает функцию для вычисления математического ожидания логарифмического правдоподобия, используя текущую оценку параметров, и шага максимизации (M), который вычисляет параметры, максимизирующие математическое ожидание логарифмического правдоподобия, полученное на шаге E. Эти оценки параметров затем используются для определения распределения латентных переменных на следующем шаге E. Его можно использовать, например, для оценки смеси гауссиан или для решения задачи множественной линейной регрессии.

Приложения

ЭМ часто используется для оценки параметров смешанных моделей, в особенности в количественной генетике. В психометрии ЭМ является важным инструментом для оценки параметров пунктов и латентных способностей моделей теории отклика на пункты. Благодаря возможности работы с пропущенными данными и ненаблюдаемыми переменными, ЭМ становится полезным инструментом для оценки стоимости и управления рисками портфеля. Алгоритм ЭМ (и его более быстрая разновидность – упорядоченная максимизация ожиданий подмножеств) также широко применяется в медицинской реконструкции изображений, особенно в позитронно-эмиссионной томографии, однофотонной эмиссионной компьютерной томографии и компьютерной рентгеновской томографии. Другие более быстрые варианты ЭМ приведены ниже. В строительной инженерии алгоритм Structural Identification using Expectation Maximization (STRIDE) представляет собой метод, основанный только на выходных данных, для определения собственных колебательных свойств строительной системы с использованием данных датчиков (см. Операционный модальный анализ). ЭМ также используется для кластеризации данных. В области обработки естественного языка двумя заметными примерами применения алгоритма являются алгоритм Баума — Уэлча для скрытых марковских моделей и алгоритм "внутрь-наружу" для неконтролируемой индукции вероятностных контекстно-свободных грамматик. В анализе времени ожидания между сделками, то есть времени между последовательными сделками акциями на бирже, алгоритм ЭМ оказался весьма полезным.

Варианты

Было предложено несколько методов ускорения иногда медленной сходимости алгоритма EM, таких как использование сопряжённого градиента и модифицированных методов Ньютона (Ньютон-Рафсона). Кроме того, EM может использоваться с методами ограниченной оценки. Алгоритм расширенной максимизации ожиданий с расширенными параметрами (PX EM) часто обеспечивает ускорение, «используя корректировку ковариации для исправления анализа шага M, используя дополнительную информацию, содержащуюся в заполненных полных данных». Алгоритм условной максимизации ожиданий (ECM) заменяет каждый шаг M последовательностью шагов условной максимизации (CM), на которых каждый параметр θi максимизируется индивидуально при фиксированных остальных параметрах. Сам алгоритм может быть расширен до алгоритма ожидания и условной максимизации (ECME). Эта идея далее расширяется в алгоритме обобщённой максимизации ожиданий (GEM), в котором ищут только увеличение целевой функции F как на шаге E, так и на шаге M, как описано в разделе «Процедура максимизации-максимизации». Также возможно рассматривать алгоритм EM как подкласс алгоритма MM (Majorize/Minimize или Minorize/Maximize, в зависимости от контекста) и, следовательно, использовать любые механизмы, разработанные в более общем случае.

алгоритм α-EM

Функция Q, используемая в алгоритме EM, основана на логарифме функции правдоподобия. Поэтому он известен как логарифмический алгоритм EM. Использование логарифма функции правдоподобия можно обобщить до отношения логарифмов правдоподобия α. Тогда отношение логарифмов правдоподобия α для наблюдаемых данных может быть точно выражено в виде равенства, используя функцию Q отношения логарифмов правдоподобия α и α-дивергенцию. Получение этой функции Q представляет собой обобщенный шаг E. Его максимизация – обобщенный шаг M. Эта пара называется α EM алгоритмом, который включает в себя логарифмический EM алгоритм как подкласс. Таким образом, α EM алгоритм Ясуо Мацуямы является точным обобщением логарифмического EM алгоритма. Вычисление градиента или гессианской матрицы не требуется. α EM демонстрирует более быструю сходимость, чем логарифмический EM алгоритм, при выборе подходящего значения α. α EM алгоритм приводит к более быстрой версии алгоритма оценки скрытой марковской модели α HMM.

Связь с вариационными методами Байеса

ЭМ – это частично небайесовский метод максимального правдоподобия. Его конечный результат представляет собой распределение вероятностей по скрытым переменным (в байесовском стиле) вместе с точечной оценкой для θ (максимальное правдоподобие или мода апостериорного распределения). Может потребоваться полностью байесовская версия, предоставляющая распределение вероятностей для θ и скрытых переменных. Байесовский подход к выводу заключается в рассмотрении θ как еще одной скрытой переменной. В этой парадигме различие между шагами E и M исчезает. При использовании факторизованного Q-приближения, как описано выше (вариационный вывод), решение можно итеративно уточнять для каждой скрытой переменной (включая теперь θ), оптимизируя их по одной. Теперь требуется k шагов на итерацию, где k – количество скрытых переменных. Для графических моделей это легко реализовать, поскольку новое Q для каждой переменной зависит только от ее марковского окружения, поэтому для эффективного вывода можно использовать передачу локальных сообщений.

Геометрическая интерпретация

В информационной геометрии шаг E и шаг M интерпретируются как проекции, соответствующие двойственным аффинным связностям, называемым e-связностью и m-связностью; дивергенция Кульбака — Лейблера также может быть понята в этих терминах.

Гауссовская смесь

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