EM-алгоритм

(Перенаправлено з ЕМ-алгоритм)

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

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

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

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

Покладемо   — густину імовірності (в безперервному випадку) або функція ймовірностей (в дискретному випадку) повного набору даних з параметрами  :   Цю функцію можна розуміти як правдоподібність всієї моделі, якщо розглядати її як функцію параметрів  . Зауважимо, що умовний розподіл прихованої компоненти при деякому спостереженні та фіксованому наборі параметрів може бути вираженим так:

 ,

використовуючи розширену формулу Байеса і формулу повної ймовірності. Таким чином, нам необхідно знати тільки розподіл спостережуваної компоненти при фіксованій прихованій   і ймовірності прихованих даних  .

EM-алгоритм ітеративно покращує початкову оцінку  , обчислюючи нові значення оцінок   і так далі. На кожному кроці перехід до   від   виконується таким чином:

 

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

  обчислюється таким чином:

 

тобто умовне математичне сподівання   при умові  .

Іншими словами,   — це значення, максимізуючи (M) умовне математичне сподівання (E) логарифма правдоподібності при даних значеннях спостережуваних змінних і попередньому значенні параметрів. У безперервному випадку значення   вираховується так:

 

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

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

 

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

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

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

Примітки ред.

  1. Neal, Radford; Hinton, Geoffrey (1999). A view of the EM algorithm that justifies incremental, sparse, and other variants. У Michael I. Jordan (ред.). Learning in Graphical Models (Cambridge, MA: MIT Press): 355–368. ISBN 0262600323. Архів оригіналу за 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. 

Посилання ред.