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-алгоритм как два чередующихся шага максимизации. Рассмотрим функцию:

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

Ссылки

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