EM-алгоритм

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

История

EM-алгоритм был впервые формально описан и назван в 1977 году в статье «Maximum Likelihood from Incomplete Data via the EM Algorithm» американскими статистиками Артуром Демпстером, Наном Лэрдом и Дональдом Рубином. Однако, идеи, лежащие в его основе, использовались и ранее в различных областях. Например, ещё в 1950-х годах метод применялся в генетике для оценки частот аллелей, а в 1960-х — в обработке сигналов и анализе изображений. Работа Демпстера, Лэрда и Рубина обобщила разрозненные подходы, предложив единую теоретическую базу и доказав сходимость алгоритма. С тех пор EM-алгоритм стал одним из ключевых инструментов в статистике, биоинформатике, компьютерном зрении и других дисциплинах.

Основная идея и принцип работы

EM-алгоритм предназначен для ситуаций, когда наблюдаемые данные \( X \) можно интерпретировать как неполные, а полные данные \( (X, Z) \) включают также ненаблюдаемые (скрытые) переменные \( Z \). Целью является максимизация логарифмической функции правдоподобия наблюдаемых данных: \( \log p(X | \theta) \), где \( \theta \) — оцениваемые параметры. Прямая максимизация часто сложна, так как требует суммирования или интегрирования по всем возможным значениям \( Z \).

Алгоритм решает эту проблему итеративно, чередуя два шага:

1. E-шаг (Expectation, ожидание): На основе текущей оценки параметров \( \theta^{(t)} \) вычисляется математическое ожидание логарифма функции правдоподобия полных данных по распределению скрытых переменных \( Z \), при условии наблюдаемых данных \( X \). Фактически, на этом шаге «дооцениваются» недостающие данные.

\[ Q(\theta | \theta^{(t)}) = E_{Z | X, \theta^{(t)}} [ \log p(X, Z | \theta) ] \]

1. M-шаг (Maximization, максимизация): Находится новая оценка параметров \( \theta^{(t+1)} \), которая максимизирует функцию \( Q \), полученную на E-шаге.

\[ \theta^{(t+1)} = \arg\max_{\theta} Q(\theta | \theta^{(t)}) \]

Эти два шага повторяются до тех пор, пока изменение значения функции правдоподобия или самих параметров не станет меньше заданного порога (критерий сходимости). Важно, что на каждом M-шаге значение функции правдоподобия наблюдаемых данных \( \log p(X | \theta) \) не уменьшается, что гарантирует сходимость алгоритма к локальному максимуму.

Применение

EM-алгоритм широко применяется в задачах, где данные имеют сложную структуру или содержат пропуски. Ниже приведены основные области использования.

Кластеризация и смеси распределений

Наиболее известное применение — оценка параметров смеси гауссовых распределений (Gaussian Mixture Model, GMM). В этой модели предполагается, что данные порождены несколькими гауссовыми компонентами, но для каждого наблюдения неизвестно, к какой именно компоненте оно относится (это и есть скрытая переменная). EM-алгоритм позволяет одновременно оценить параметры каждой компоненты (среднее, ковариационную матрицу) и веса смеси. Этот подход лежит в основе многих методов кластеризации, в том числе мягкой кластеризации (fuzzy clustering).

Обработка пропущенных данных

Если в наборе данных часть значений признаков отсутствует, EM-алгоритм может быть использован для их восстановления. Он моделирует распределение данных с учётом пропусков и на каждой итерации «дозаполняет» пропущенные значения их наиболее вероятными оценками на основе текущей модели.

Биоинформатика и генетика

EM-алгоритм применяется для:

• Оценки частот аллелей: В популяционной генетике, когда генотипы не полностью наблюдаемы (например, из-за доминантности).
• Филогенетического анализа: Для оценки эволюционных расстояний и построения деревьев.
• Анализа экспрессии генов: Для идентификации различных состояний клеток на основе данных RNA-seq.

Обработка сигналов и изображений

В этой области алгоритм используется для:

• Разделения источников сигнала: Например, в задаче «слепого разделения» аудиосигналов.
• Сегментации изображений: Отнесение каждого пикселя к одному из классов (например, фон, объект) на основе его цвета или текстуры.
• Томографической реконструкции: Восстановление изображения по проекциям в медицинской визуализации (PET, SPECT).

Машинное обучение

EM-алгоритм является основой для обучения многих вероятностных моделей, включая:

• Скрытые марковские модели (HMM): Используются в распознавании речи, анализе последовательностей (например, генов), обработке естественного языка (POS-теггинг). Алгоритм Баума-Уэлча — это частный случай EM для HMM.
• Факторные модели: Например, факторный анализ и анализ главных компонент (PCA) могут быть реализованы через EM.
• Обучение с частичным привлечением учителя (semi-supervised learning): Когда лишь малая часть данных размечена, EM позволяет дообучить модель, используя информацию из неразмеченных данных.

Разновидности и обобщения

За десятилетия использования было разработано множество модификаций EM-алгоритма, направленных на ускорение сходимости, повышение точности или адаптацию к специфическим задачам:

• Обобщённый EM (GEM): На M-шаге параметры обновляются не до глобального максимума функции \( Q \), а до значения, которое её увеличивает. Это упрощает вычисления в сложных моделях.
• Стохастический EM (SEM): На E-шаге вместо вычисления математического ожидания производится случайная выборка скрытых переменных из их апостериорного распределения. Это позволяет избежать локальных максимумов и ускорить работу на больших данных.
• Вариационный EM (VBEM): Используется, когда апостериорное распределение скрытых переменных не может быть вычислено аналитически. Вводится аппроксимирующее распределение, и максимизируется нижняя граница правдоподобия (ELBO). Этот подход лежит в основе вариационных автокодировщиков (VAE).
• EM с моментумом (Momentum EM): Вводится инерция (моментум) при обновлении параметров на M-шаге, что часто ускоряет сходимость.

Преимущества и недостатки

Преимущества

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

Недостатки

• Сходимость к локальному максимуму: Как и многие градиентные методы, EM может найти только локальный, а не глобальный максимум функции правдоподобия. Результат сильно зависит от начального приближения параметров.
• Медленная сходимость: Вблизи максимума скорость сходимости может быть линейной, что приводит к большому числу итераций. В некоторых случаях сходимость может быть крайне медленной (например, в задачах с сильно коррелированными параметрами).
• Требования к модели: Необходимо уметь вычислять апостериорное распределение скрытых переменных. В сложных моделях это может быть вычислительно дорого.
• Чувствительность к размерности: При большом количестве скрытых переменных или параметров E-шаг становится ресурсоёмким.

Сравнение с другими методами

EM-алгоритм часто сравнивают с другими методами оптимизации, используемыми в статистике и машинном обучении:

• Градиентный спуск: EM не требует вычисления градиента функции правдоподобия, что упрощает реализацию для некоторых моделей. Однако градиентный спуск (особенно стохастический) может быть быстрее на очень больших наборах данных.
• Метод Ньютона: EM менее требователен к вычислительным ресурсам на одну итерацию, но сходится медленнее (линейная сходимость против квадратичной у метода Ньютона). Метод Ньютона также требует вычисления и обращения матрицы Гессе, что может быть проблематично.
• Метод Монте-Карло (MCMC): MCMC-методы (например, сэмплер Гиббса) используются для байесовского вывода, когда требуется полное апостериорное распределение, а не только точечная оценка. EM даёт только точечную оценку (моду апостериорного распределения), но часто значительно быстрее.

Пример: смесь гауссовых распределений

Рассмотрим задачу оценки параметров смеси двух одномерных гауссовых распределений. Наблюдаемые данные — \( x_1, x_2, ..., x_n \). Скрытая переменная \( z_i \in \{1, 2\} \) указывает, к какой компоненте принадлежит \( x_i \). Параметры модели: \( \theta = (\mu_1, \sigma_1, \mu_2, \sigma_2, \pi) \), где \( \pi \) — вероятность принадлежности к первой компоненте.

E-шаг: Для каждого наблюдения \( x_i \) вычисляется апостериорная вероятность (ответственность) принадлежности к первой компоненте: \[ \gamma_i^{(t)} = p(z_i = 1 | x_i, \theta^{(t)}) = \frac{\pi^{(t)} \cdot \mathcal{N}(x_i | \mu_1^{(t)}, \sigma_1^{(t)})}{\pi^{(t)} \cdot \mathcal{N}(x_i | \mu_1^{(t)}, \sigma_1^{(t)}) + (1-\pi^{(t)}) \cdot \mathcal{N}(x_i | \mu_2^{(t)}, \sigma_2^{(t)})} \]

M-шаг: Обновляются параметры с использованием взвешенных средних: \[ \mu_1^{(t+1)} = \frac{\sum_{i=1}^{n} \gamma_i^{(t)} x_i}{\sum_{i=1}^{n} \gamma_i^{(t)}}, \quad \mu_2^{(t+1)} = \frac{\sum_{i=1}^{n} (1-\gamma_i^{(t)}) x_i}{\sum_{i=1}^{n} (1-\gamma_i^{(t)})} \] \[ \sigma_1^{(t+1)} = \sqrt{\frac{\sum_{i=1}^{n} \gamma_i^{(t)} (x_i - \mu_1^{(t+1)})^2}{\sum_{i=1}^{n} \gamma_i^{(t)}}}, \quad \sigma_2^{(t+1)} = \sqrt{\frac{\sum_{i=1}^{n} (1-\gamma_i^{(t)}) (x_i - \mu_2^{(t+1)})^2}{\sum_{i=1}^{n} (1-\gamma_i^{(t)})}} \] \[ \pi^{(t+1)} = \frac{1}{n} \sum_{i=1}^{n} \gamma_i^{(t)} \]

Итерации повторяются до сходимости. Этот пример наглядно демонстрирует, как EM-алгоритм «дооценивает» скрытые переменные (принадлежность к компоненте) и на их основе уточняет параметры модели.

Источники

• 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 (Methodological), 39(1), 1-22.
• Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
• McLachlan, G. J., & Krishnan, T. (2007). The EM Algorithm and Extensions (2nd ed.). Wiley-Interscience.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer.
• Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT Press.