EM-алгоритм

Частина з циклу
Машинне навчання
та добування даних
Ілюстрація нейронної мережі з темним
Навчання з людьми
Діагностування моделей
  • Крива спроможності навчатися[en]
Математичні засади
Місця машинного навчання
Пов'язані статті
  • п
  • о
  • р

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

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

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

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

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

p ( T | X , Θ ) = p ( X , T | Θ ) p ( X | Θ ) = p ( X | T , Θ ) p ( T | Θ ) ∫ p ( X | T ^ , Θ ) p ( T ^ | Θ ) d T ^ {\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}} }}} ,

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

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

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

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

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

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

тобто умовне математичне сподівання log ⁡ p ( X , T | Θ ) {\displaystyle \log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right)} при умові Θ {\displaystyle \Theta } .

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

Q ( Θ ) = E T [ log ⁡ p ( X , T | Θ ) | X ] = ∫ − ∞ ∞ p ( T | X , Θ n ) log ⁡ p ( X , T | Θ ) d T {\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] Розглянемо функцію:

F ( q , θ ) = E q ⁡ [ log ⁡ L ( θ ; x , Z ) ] + H ( q ) = − D KL ( q ‖ p Z | X ( ⋅ | x ; θ ) ) + log ⁡ L ( θ ; x ) {\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; pZ|X(· |x;θ) — умовний розподіл неспостережуваних змінних при фіксованих спостережуваних x і параметрах розподілення ймовірностей неспостережуваних змінних θ; H — ентропія і DKL — відстань Кульбака — Лейблера.

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

E(xpectation) крок: Вибираємо q, щоб максимізувати F:
q ( t ) = * ⁡ a r g m a x q   F ( q , θ ( t ) ) {\displaystyle q^{(t)}=\operatorname {*} {arg\,max}_{q}\ F(q,\theta ^{(t)})}
M(aximization) крок: Вибираємо θ, щоб максимізувати F:
θ ( t + 1 ) = * ⁡ arg m a x θ   F ( q ( t ) , θ ) {\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