EM-алгоритм

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

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

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

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

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

${\displaystyle p(\mathbf {T} |\mathbf {X} ,\Theta )={\frac {p(\mathbf {X} |\mathbf {T} ,\Theta )p(\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}} }}}$,

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

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

${\displaystyle \Theta _{n+1}=\arg \max _{\Theta }Q(\Theta )}$

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

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

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

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

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

${\displaystyle 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] Рассмотрим функцию:

${\displaystyle 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:

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

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

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

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

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

Примечания

Ссылки

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