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 {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 \Theta }$.

Іншими словами, ${\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 )}$

Примітки

1. Neal, Radford; Hinton, Geoffrey (1999). Michael I. Jordan (ред.). A view of the EM algorithm that justifies incremental, sparse, and other variants (PDF). Learning in Graphical Models. Cambridge, MA: MIT Press: 355—368. ISBN 0262600323. Архів оригіналу (PDF) за 7 червня 2020. Процитовано 22 березня 2009.
2. Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2001). 8.5 The EM algorithm. The Elements of Statistical Learning. New York: Springer. с. 236–243. ISBN 0-387-95284-5.

Посилання

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