EM-алгоритм

EM-алгоритм (англ. Expectation-maximization (EM) algorithm) — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.

Часто EM-алгоритм используют для разделения смеси гауссиан.

Описание алгоритма

Пусть $\textbf{X}$ — некоторые из значений наблюдаемых переменных, а $\textbf{T}$ — скрытые переменные. Вместе $\textbf{X}$ и $\textbf{T}$ образуют полный набор данных. Вообще, $\textbf{T}$ может быть некоторой подсказкой, которая облегчает решение проблемы в случае, если она известна. Например, если имеется смесь распределений, функция правдоподобия легко выражается через параметры отдельных распределений смеси.

Положим $p\,$ — плотность вероятности (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами $\Theta$: $p( \mathbf X, \mathbf T | \Theta).$ Эту функцию можно понимать как правдоподобие всей модели, если рассматривать её как функцию параметров $\Theta$. Заметим, что условное распределение скрытой компоненты при некотором наблюдении и фиксированном наборе параметров может быть выражено так:

$p(\mathbf T |\mathbf X, \Theta) = \frac{p(\mathbf X, \mathbf T | \Theta)}{p(\mathbf X | \Theta)} = \frac{p(\mathbf X|\mathbf T, \Theta) p(\mathbf T |\Theta) }{\int p(\mathbf X|\mathbf{\hat{T}}, \Theta) p(\mathbf{\hat{T}} |\Theta) d\mathbf{ \hat{T}}}$,

используя расширенную формулу Байеса и формулу полной вероятности. Таким образом, нам необходимо знать только распределение наблюдаемой компоненты при фиксированной скрытой $p(\mathbf X|\mathbf T, \Theta)$ и вероятности скрытых данных $p(\mathbf T |\Theta)$.

EM-алгоритм итеративно улучшает начальную оценку $\Theta_0$, вычисляя новые значения оценок $\Theta_1, \Theta_2,$ и так далее. На каждом шаге переход к $\Theta_{n+1}\,$ от $\Theta_n\,$ выполняется следующим образом:

$\Theta_{n+1} = \arg\max_{\Theta}Q(\Theta)$

где $Q(\Theta)$ — матожидание логарифма правдоподобия. Другими словами, мы не можем сразу вычислить точное правдоподобие, но по известным данным ($X$) мы пожем найти апостериорную оценку вероятностей для различных значений скрытых переменных $T$. Для каждого набора значений $T$ и параметров $\Theta$ мы можем вычислить матожидание функции правдоподобия по данному набору $X$. Оно зависит от предыдущего значения $\Theta$, потому что это значение влияет на вероятности скрытых переменных $T$.

$Q(\Theta)$ вычисляется следующим образом:

$Q(\Theta) = E_{\mathbf T} \! \! \left[ \log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) \Big| \mathbf X \right]$

то есть это условное матожидание $\log p \left( \mathbf X, \mathbf T \,|\, \Theta \right)$ при условии $\Theta$.

Другими словами, $\Theta_{n+1}$ — это значение, максимизирующее (M) условное матожидание (E) логарифма правдоподобия при данных значениях наблюдаемых переменных и предыдущем значении параметров. В непрерывном случае значение $Q(\Theta)$ вычисляется так:

$Q(\Theta) = E_{\mathbf T} \! \! \left[ \log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) \Big| \mathbf X \right] = \int^\infty _{- \infty} p \left(\mathbf T \,|\, \mathbf X, \Theta_n \right) \log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) d\mathbf T$

Альтернативное описание

При определенных обстоятельствах удобно рассматривать EM-алгоритм как два чередующихся шага максимизации.^[1][2] Рассмотрим функцию:

$F(q,\theta) = \operatorname{E}_q [ \log L (\theta ; x,Z) ] + H(q) = -D_{\text{KL}}\big(q \big\| p_{Z|X}(\cdot|x;\theta ) \big) + \log L(\theta;x)$

где q — распределение вероятностей ненаблюдаемых переменных Z; p_Z|X(· |x;θ) — условное распределение ненаблюдаемых переменных при фиксированных наблюдаемых x и параметрах θ; H — энтропия и D_KL — расстояние Кульбака-Лейблера.

Тогда шаги EM-алгоритма можно представить как:

E(xpectation) шаг: Выбираем q, чтобы максимизировать F:

$q^{(t)} = \operatorname*{arg\,max}_q \ F(q,\theta^{(t)})$

M(aximization) шаг: Выбираем θ, чтобы максимизировать F:

$\theta^{(t+1)} = \operatorname*{\arg\,max}_{\theta} \ F(q^{(t)},\theta)$

Примеры использования

• k-means — алгоритм кластеризации, построенный на идее EM-алгоритма
• Метод упругих карт для нелинейного сокращения размерности данных
• Алгоритм Баума-Велша — алгоритм для оценки параметров скрытых марковских моделей

Примечания

1. ↑ (1999) «A view of the EM algorithm that justifies incremental, sparse, and other variants». Learning in Graphical Models (MIT Press): 355–368. Проверено 2009-03-22.
2. ↑ 8.5 The EM algorithm // The Elements of Statistical Learning. — New York: Springer, 2001. — P. 236–243.

Ссылки

• Демонстрация разделения смеси гауссиан с помощью EM-алгоритма
• Реализация на Java