EM-алгоритм (англ. Expectation-maximization (EM) algorithm) — алгоритм, що використовується в математичній статистиці для знаходження оцінок максимальної схожості параметрів ймовірних моделей, у випадку, коли модель залежить від деяких прихованих змінних. Кожна ітерація алгоритму складається з двох кроків. На E-кроці (expectation) вираховується очікуване значення функції правдоподібності, при цьому приховані змінні розглядаються як спостережувані. На M-кроці (maximization) вираховується оцінка максимальної схожості, таким чином збільшується очікувана схожість, вирахувана на E-кроці. Потім це значення використовується для E-кроку на наступній ітерації. Алгоритм виконується до збіжності.
Часто EM-алгоритм використовують для розділення суміші функції Гауса.
Опис алгоритму
Нехай — деяке з значень спостережуваних змінних, а
— прихованні змінні. Разом
і
утворюють повний набір даних. Взагалі,
може бути деякою підказкою, яка полегшує рішення проблеми у випадку, якщо вона відома. Наприклад, якщо є , функція правдоподібності легко виражається через параметри відокремлених розподілів суміші.
Покладемо — густину імовірності (в безперервному випадку) або функція ймовірностей (в дискретному випадку) повного набору даних з параметрами
:
Цю функцію можна розуміти як правдоподібність всієї моделі, якщо розглядати її як функцію параметрів
. Зауважимо, що умовний розподіл прихованої компоненти при деякому спостереженні та фіксованому наборі параметрів може бути вираженим так:
,
використовуючи розширену формулу Байеса і формулу повної ймовірності. Таким чином, нам необхідно знати тільки розподіл спостережуваної компоненти при фіксованій прихованій і ймовірності прихованих даних
.
EM-алгоритм ітеративно покращує початкову оцінку , обчислюючи нові значення оцінок
і так далі. На кожному кроці перехід до
від
виконується таким чином:
де — математичне сподівання логарифма правдоподібності. Іншими словами, ми не можемо відразу обчислити точну правдоподібність, але за відомими даними (
) ми можемо знайти апостеріорну оцінку ймовірностей для різних значень прихованих змінних
. Для кожного набору значень
і параметрів
ми можемо обчислити математичне сподівання функції правдоподібності з даного набору
. Воно залежить від попереднього значення
, бо це значення впливає на ймовірності прихованих змінних
.
обчислюється таким чином:
тобто умовне математичне сподівання при умові
.
Іншими словами, — це значення, максимізуючи (M) умовне математичне сподівання (E) логарифма правдоподібності при даних значеннях спостережуваних змінних і попередньому значенні параметрів. У безперервному випадку значення
вираховується так:
Альтернативний опис
За певних обставин зручно розглядати EM-алгоритм як два чергуються кроку максимізації. Розглянемо функцію:
де q — розподіл ймовірностей неспостережуваних змінних Z; pZ|X(· |x;θ) — умовний розподіл неспостережуваних змінних при фіксованих спостережуваних x і параметрах розподілення ймовірностей неспостережуваних змінних θ; H — ентропія і DKL — відстань Кульбака — Лейблера.
Тоді кроки EM-алгоритму можна показати як:
- E(xpectation) крок: Вибираємо q, щоб максимізувати F:
- M(aximization) крок: Вибираємо θ, щоб максимізувати F:
Примітки
- Neal, Radford; Hinton, Geoffrey (1999). (ред.). (PDF). Learning in Graphical Models. Cambridge, MA: MIT Press: 355—368. ISBN . Архів оригіналу (PDF) за 7 червня 2020. Процитовано 22 березня 2009.
- Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2001). 8.5 The EM algorithm. The Elements of Statistical Learning. New York: Springer. с. 236–243. ISBN .
Посилання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
EM algoritm angl Expectation maximization EM algorithm algoritm sho vikoristovuyetsya v matematichnij statistici dlya znahodzhennya ocinok maksimalnoyi shozhosti parametriv jmovirnih modelej u vipadku koli model zalezhit vid deyakih prihovanih zminnih Kozhna iteraciya algoritmu skladayetsya z dvoh krokiv Na E kroci expectation virahovuyetsya ochikuvane znachennya funkciyi pravdopodibnosti pri comu prihovani zminni rozglyadayutsya yak sposterezhuvani Na M kroci maximization virahovuyetsya ocinka maksimalnoyi shozhosti takim chinom zbilshuyetsya ochikuvana shozhist virahuvana na E kroci Potim ce znachennya vikoristovuyetsya dlya E kroku na nastupnij iteraciyi Algoritm vikonuyetsya do zbizhnosti Chasto EM algoritm vikoristovuyut dlya rozdilennya sumishi funkciyi Gausa Opis algoritmuNehaj X displaystyle textbf X deyake z znachen sposterezhuvanih zminnih a T displaystyle textbf T prihovanni zminni Razom X displaystyle textbf X i T displaystyle textbf T utvoryuyut povnij nabir danih Vzagali T displaystyle textbf T mozhe buti deyakoyu pidkazkoyu yaka polegshuye rishennya problemi u vipadku yaksho vona vidoma Napriklad yaksho ye funkciya pravdopodibnosti legko virazhayetsya cherez parametri vidokremlenih rozpodiliv sumishi Poklademo p displaystyle p gustinu imovirnosti v bezperervnomu vipadku abo funkciya jmovirnostej v diskretnomu vipadku povnogo naboru danih z parametrami 8 displaystyle Theta p X T 8 displaystyle p mathbf X mathbf T Theta Cyu funkciyu mozhna rozumiti yak pravdopodibnist vsiyeyi modeli yaksho rozglyadati yiyi yak funkciyu parametriv 8 displaystyle Theta Zauvazhimo sho umovnij rozpodil prihovanoyi komponenti pri deyakomu sposterezhenni ta fiksovanomu nabori parametriv mozhe buti virazhenim tak p T X 8 p X T 8 p X 8 p X T 8 p T 8 p X T 8 p T 8 dT 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 vikoristovuyuchi rozshirenu formulu Bajesa i formulu povnoyi jmovirnosti Takim chinom nam neobhidno znati tilki rozpodil sposterezhuvanoyi komponenti pri fiksovanij prihovanij p X T 8 displaystyle p mathbf X mathbf T Theta i jmovirnosti prihovanih danih p T 8 displaystyle p mathbf T Theta EM algoritm iterativno pokrashuye pochatkovu ocinku 80 displaystyle Theta 0 obchislyuyuchi novi znachennya ocinok 81 82 displaystyle Theta 1 Theta 2 i tak dali Na kozhnomu kroci perehid do 8n 1 displaystyle Theta n 1 vid 8n displaystyle Theta n vikonuyetsya takim chinom 8n 1 arg max8Q 8 displaystyle Theta n 1 arg max Theta Q Theta de Q 8 displaystyle Q Theta matematichne spodivannya logarifma pravdopodibnosti Inshimi slovami mi ne mozhemo vidrazu obchisliti tochnu pravdopodibnist ale za vidomimi danimi X displaystyle X mi mozhemo znajti aposteriornu ocinku jmovirnostej dlya riznih znachen prihovanih zminnih T displaystyle T Dlya kozhnogo naboru znachen T displaystyle T i parametriv 8 displaystyle Theta mi mozhemo obchisliti matematichne spodivannya funkciyi pravdopodibnosti z danogo naboru X displaystyle X Vono zalezhit vid poperednogo znachennya 8 displaystyle Theta bo ce znachennya vplivaye na jmovirnosti prihovanih zminnih T displaystyle T Q 8 displaystyle Q Theta obchislyuyetsya takim chinom Q 8 ET log p X T 8 X displaystyle Q Theta E mathbf T left log p left mathbf X mathbf T Theta right Big mathbf X right tobto umovne matematichne spodivannya log p X T 8 displaystyle log p left mathbf X mathbf T Theta right pri umovi 8 displaystyle Theta Inshimi slovami 8n 1 displaystyle Theta n 1 ce znachennya maksimizuyuchi M umovne matematichne spodivannya E logarifma pravdopodibnosti pri danih znachennyah sposterezhuvanih zminnih i poperednomu znachenni parametriv U bezperervnomu vipadku znachennya Q 8 displaystyle Q Theta virahovuyetsya tak Q 8 ET log p X T 8 X p T X 8n log p X T 8 dT 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 Alternativnij opisZa pevnih obstavin zruchno rozglyadati EM algoritm yak dva cherguyutsya kroku maksimizaciyi Rozglyanemo funkciyu F q 8 Eq log L 8 x Z H q DKL q pZ X x 8 log L 8 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 de q rozpodil jmovirnostej nesposterezhuvanih zminnih Z pZ X x 8 umovnij rozpodil nesposterezhuvanih zminnih pri fiksovanih sposterezhuvanih x i parametrah rozpodilennya jmovirnostej nesposterezhuvanih zminnih 8 H entropiya i DKL vidstan Kulbaka Lejblera Todi kroki EM algoritmu mozhna pokazati yak E xpectation krok Vibirayemo q shob maksimizuvati F q t argmaxq F q 8 t displaystyle q t operatorname arg max q F q theta t dd M aximization krok Vibirayemo 8 shob maksimizuvati F 8 t 1 argmax8 F q t 8 displaystyle theta t 1 operatorname arg max theta F q t theta dd PrimitkiNeal Radford Hinton Geoffrey 1999 red PDF Learning in Graphical Models Cambridge MA MIT Press 355 368 ISBN 0262600323 Arhiv originalu PDF za 7 chervnya 2020 Procitovano 22 bereznya 2009 Hastie Trevor Tibshirani Robert Friedman Jerome 2001 8 5 The EM algorithm The Elements of Statistical Learning New York Springer s 236 243 ISBN 0 387 95284 5 Posilannya