ЕМ

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

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

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

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

Положим $p\,$ - плотность вероятности (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами Θ: $p( \mathbf X, \mathbf T | \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_{n+1}\,$ от $\Theta_n\,$ выполняется следующим образом:

Θ_{n + 1} = argmax_ΘQ(Θ)

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

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

$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)$ при условии Θ.

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

$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-алгоритма
• Алгоритм Баума-Велша - алгоритм для оценки параметров скрытых марковских моделей

Ссылки

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