EM-алгоритм

Шаблон:Машинне навчання EM-алгоритм (Шаблон:Lang-en) — алгоритм, що використовується в математичній статистиці для знаходження оцінок максимальної схожості параметрів ймовірних моделей, у випадку, коли модель залежить від деяких прихованих змінних. Кожна ітерація алгоритму складається з двох кроків. На E-кроці (expectation) вираховується очікуване значення функції правдоподібності, при цьому приховані змінні розглядаються як спостережувані. На M-кроці (maximization) вираховується оцінка максимальної схожості, таким чином збільшується очікувана схожість, вирахувана на E-кроці. Потім це значення використовується для E-кроку на наступній ітерації. Алгоритм виконується до збіжності.

Часто EM-алгоритм використовують для розділення суміші функції Гауса.

Опис алгоритму

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

Покладемо $p$ — густину імовірності (в безперервному випадку) або функція ймовірностей (в дискретному випадку) повного набору даних з параметрами $\mathrm{\Theta }$: $p(𝐗,𝐓|\mathrm{\Theta }).$ Цю функцію можна розуміти як правдоподібність всієї моделі, якщо розглядати її як функцію параметрів $\mathrm{\Theta }$. Зауважимо, що умовний розподіл прихованої компоненти при деякому спостереженні та фіксованому наборі параметрів може бути вираженим так:

$p(𝐓|𝐗,\mathrm{\Theta })=\frac{p(𝐗,𝐓|\mathrm{\Theta })}{p(𝐗|\mathrm{\Theta })}=\frac{p(𝐗|𝐓,\mathrm{\Theta })p(𝐓|\mathrm{\Theta })}{\int p(𝐗|\widehat{𝐓},\mathrm{\Theta })p(\widehat{𝐓}|\mathrm{\Theta })d\widehat{𝐓}}$,

використовуючи розширену формулу Байеса і формулу повної ймовірності. Таким чином, нам необхідно знати тільки розподіл спостережуваної компоненти при фіксованій прихованій $p(𝐗|𝐓,\mathrm{\Theta })$ і ймовірності прихованих даних $p(𝐓|\mathrm{\Theta })$.

EM-алгоритм ітеративно покращує початкову оцінку ${\mathrm{\Theta }}_0$, обчислюючи нові значення оцінок ${\mathrm{\Theta }}_1,{\mathrm{\Theta }}_2,$ і так далі. На кожному кроці перехід до ${\mathrm{\Theta }}_{n+1}$ від ${\mathrm{\Theta }}_n$ виконується таким чином:

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

де $Q(\mathrm{\Theta })$ — математичне сподівання логарифма правдоподібності. Іншими словами, ми не можемо відразу обчислити точну правдоподібність, але за відомими даними ($X$) ми можемо знайти апостеріорну оцінку ймовірностей для різних значень прихованих змінних $T$. Для кожного набору значень $T$ і параметрів $\mathrm{\Theta }$ ми можемо обчислити математичне сподівання функції правдоподібності з даного набору $X$. Воно залежить від попереднього значення $\mathrm{\Theta }$, бо це значення впливає на ймовірності прихованих змінних $T$.

$Q(\mathrm{\Theta })$ обчислюється таким чином:

$Q(\mathrm{\Theta })=E_{𝐓}[\log p(𝐗,𝐓|\mathrm{\Theta })|𝐗]$

тобто умовне математичне сподівання $\log p(𝐗,𝐓|\mathrm{\Theta })$ при умові $\mathrm{\Theta }$.

Іншими словами, ${\mathrm{\Theta }}_{n+1}$ — це значення, максимізуючи (M) умовне математичне сподівання (E) логарифма правдоподібності при даних значеннях спостережуваних змінних і попередньому значенні параметрів. У безперервному випадку значення $Q(\mathrm{\Theta })$ вираховується так:

$Q(\mathrm{\Theta })=E_{𝐓}[\log p(𝐗,𝐓|\mathrm{\Theta })|𝐗]=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}p(𝐓|𝐗,{\mathrm{\Theta }}_n)\log p(𝐗,𝐓|\mathrm{\Theta })d𝐓$

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

За певних обставин зручно розглядати EM-алгоритм як два чергуються кроку максимізації. Розглянемо функцію:

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

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

Тоді кроки EM-алгоритму можна показати як:

E(xpectation) крок: Вибираємо q, щоб максимізувати F:

$q^{(t)}=\mathrm{*}{argmax}_{q}F(q,{\theta }^{(t)})$

M(aximization) крок: Вибираємо θ, щоб максимізувати F:

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

Посилання

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