Skip to content
Назад к результатам поиска

Алгоритм EM

Автор метода
Dempster, Laird & Rubin
Год
1977
Тип
Iterative optimization algorithm
Семейство
Estimation

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Алгоритм Expectation-Maximization (EM) — это итеративная процедура оптимизации для нахождения оценок максимального правдоподобия или максимальной апостериорной вероятности параметров в статистических моделях со скрытыми переменными или пропущенными данными.

Представленный Демпстером, Лэрдом и Рубином в их основополагающей статье 1977 года, EM чередует вычисление ожидаемого логарифма полного правдоподобия данных (E-шаг) и его максимизацию относительно параметров (M-шаг), гарантируя монотонное неубывание правдоподобия на каждой итерации.

Интуиция метода

Представьте, что вы пытаетесь изучить правила игры, наблюдая за игроками, чьи карты вы не видите. В каждом раунде вы предполагаете, какие карты они, вероятно, держат, исходя из того, что вы наблюдаете, а затем обновляете свою модель правил, предполагая, что эти предположения верны. EM делает именно это: E-шаг вероятностно заполняет недостающую информацию, используя текущие оценки параметров, а M-шаг перестраивает модель так, как если бы эти заполненные значения были реальными наблюдениями.

История

Алгоритм был формально унифицирован и назван Артуром Демпстером, Нэн Лэрд и Дональдом Рубином в их статье в JRSS-B 1977 года, которая остается одной из самых цитируемых статистических статей за всю историю. Статья обобщила более ранние процедуры частных случаев, разработанные независимо для конкретных проблем пропущенных данных. Последующие десятилетия привели к многочисленным расширениям, включая алгоритмы ECM, ECME, AECM и SEM, расширяя применимость и ускоряя сходимость во многих практических случаях.

Когда применять

Используйте алгоритм EM, когда данные содержат пропущенные значения, скрытые состояния или скрытые переменные, и вам нужны оценки максимального правдоподобия. Он хорошо подходит для гауссовских смешанных моделей, скрытых марковских моделей, факторного анализа и импутации пропущенных данных. Ключевые предположения включают то, что пропущенные данные являются пропущенными случайным образом (MAR) и что модель полных данных решаема. Ограничения включают чувствительность к инициализации, возможную сходимость к локальным максимумам и медленную сходимость вблизи седловых точек. Альтернативы включают градиентную оптимизацию с численным интегрированием, вариационное выведение или методы MCMC.

Ограничения и замечания

  • Сходимость к локальному максимуму, а не к глобальному максимуму, когда поверхность правдоподобия мультимодальна
  • Может демонстрировать очень медленную (линейную) сходимость, когда доля пропущенной информации велика
  • Требует от аналитика указания модели полных данных и распределения скрытых переменных
  • Стандартный EM не предоставляет напрямую ковариационную матрицу оценок для наблюдаемых данных; для стандартных ошибок требуется дополнительный шаг (например, метод Луи или алгоритм SEM)

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Гарантированное монотонное увеличение правдоподобия наблюдаемых данных на каждой итерации, обеспечивающее стабильную сходимость
  • Преобразует сложную проблему пропущенных данных в последовательность решаемых оптимизаций полных данных
  • Широко применим к моделям экспоненциального семейства, смешанным моделям и моделям со скрытыми переменными
  • Для многих стандартных моделей доступны обновления M-шага в замкнутой форме, что делает реализацию эффективной

Применение

  • Подгонка гауссовских смешанных моделей для кластеризации и оценки плотности
  • Обучение скрытых марковских моделей для распознавания речи и анализа биологических последовательностей
  • Множественная импутация и анализ пропущенных данных в клинических и социальных науках
  • Оценка параметров в факторном анализе и анализе латентных классов
  • Сегментация и реконструкция изображений в медицинской визуализации

Как это работает

Как это работает

1

Перед началом итераций аналитик выбирает начальные значения для неизвестных параметров, обозначаемых theta-0. Их можно выбрать случайным образом, из упрощенной подгонки или на основе знаний о предметной области. Качество инициализации может повлиять на то, к какому локальному максимуму сойдется алгоритм, поэтому частой практикой является многократный случайный перезапуск.

Формула
\text{Choose initial parameter estimates } \theta^{(0)}
2

При заданном текущем значении оценки параметра theta-t, E-шаг вычисляет Q — ожидаемое значение логарифма полного правдоподобия данных по распределению ненаблюдаемых скрытых переменных Z, обусловленное наблюдаемыми данными X. Это ожидание фактически заменяет неизвестные величины их вероятностными оценками, не привязываясь к одному конкретному импутированному значению.

Формула
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]
3

M-шаг максимизирует функцию Q из E-шага относительно theta, получая обновленную оценку theta-(t+1). Поскольку максимизировать логарифм полного правдоподобия данных часто проще, чем маргинальное правдоподобие наблюдаемых данных, этот шаг часто является решаемым, даже когда прямое максимальное правдоподобие невозможно.

Формула
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

E- и M-шаги повторяются попеременно. После каждого полного цикла оценивается логарифм правдоподобия наблюдаемых данных. Итерации прекращаются, когда изменение логарифма правдоподобия (или вектора параметров) становится меньше заданного пользователем порога epsilon. Демпстер и др. доказали, что каждый цикл не может уменьшить правдоподобие наблюдаемых данных, обеспечивая стабильную сходимость.

Формула
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon

Частые ошибки

  • Использование одной случайной инициализации рискует привести к плохой локальной максимизации; всегда выполняйте несколько перезапусков и выбирайте решение с наивысшим конечным логарифмом правдоподобия
  • Слишком раннее объявление сходимости путем мониторинга только изменения параметров, а не логарифма правдоподобия наблюдаемых данных, может привести к неточным оценкам
  • Применение EM, когда данные являются пропущенными не случайным образом (MNAR) без корректировки модели, может внести систематическую ошибку в оценки
  • Игнорирование проблемы переключения меток в смешанных моделях приводит к неинтерпретируемым назначениям компонентов даже после правильной сходимости

Часто задаваемые вопросы

Всегда ли алгоритм EM сходится к глобальному максимуму?

Нет. EM гарантированно находит только локальный максимум (или седловую точку) правдоподобия наблюдаемых данных. Когда поверхность правдоподобия имеет несколько мод, конечное решение зависит от инициализации. Стандартным практическим решением является запуск алгоритма из нескольких различных начальных точек и сохранение решения с наивысшим логарифмом правдоподобия.

Чем EM отличается от прямой оптимизации максимального правдоподобия?

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

Когда следует предпочесть импутацию MICE алгоритму EM?

MICE (Multiple Imputation by Chained Equations) предпочтительнее, когда данные включают переменные смешанных типов, нелинейные отношения или сложные структуры взаимодействий, которые трудно закодировать в единой параметрической модели полных данных. EM более естественен, когда существует хорошо специфицированная совместная модель для всех переменных, а вывод нацелен на параметры модели, а не на импутированные наборы данных.

Похожие методы

Источники

  1. Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.

    Открыть ссылку DOI
    Скопировано.