ЕМ-алгоритм

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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. Процитовано 2009-03-22. 
  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. 

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