EM algoritmus

EM-algorithm ( angl. Expectation-maximization (EM) algorithm ) je algoritmus používaný v matematické statistice k nalezení odhadů maximální věrohodnosti pro parametry pravděpodobnostních modelů v případě, kdy model závisí na nějakých skrytých proměnných . Každá iterace algoritmu se skládá ze dvou kroků. V E-kroku (očekávání) se vypočítá očekávaná hodnota věrohodnostní funkce , zatímco latentní proměnné jsou považovány za pozorovatelné . V M-kroku (maximalizace) se vypočítá odhad maximální věrohodnosti, čímž se zvýší očekávaná pravděpodobnost počítaná v E-kroku. Tato hodnota se pak použije pro E-krok v další iteraci. Algoritmus se provádí až do konvergence.

K oddělení směsi Gaussiánů se často používá EM algoritmus .

Popis algoritmu

Nechť jsou některé z hodnot pozorovaných proměnných a jsou skryté proměnné. Společně tvoří kompletní datovou sadu. Obecně může existovat nějaká nápověda, která usnadní řešení problému, pokud je známa. Pokud například existuje směs distribucí , lze věrohodnostní funkci snadno vyjádřit pomocí parametrů jednotlivých distribucí směsi. ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {T}}$

Předpokládejme, že se jedná o hustotu pravděpodobnosti (ve spojitém případě) nebo pravděpodobnostní funkci (v diskrétním případě) úplného souboru dat s parametry : Tuto funkci lze chápat jako pravděpodobnost celého modelu, pokud ji považujeme za funkce parametrů . Všimněte si, že podmíněné rozdělení skryté komponenty při určitém pozorování a pevné sadě parametrů lze vyjádřit následovně: $p$ $\Theta$ $p({\mathbf X},{\mathbf T}|\Theta).$ $\Theta$

p(\mathbf {T} |\mathbf {X} ,\Theta )={\frac {p(\mathbf {X} |\mathbf {T} ,\Theta )p(\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} } }}

pomocí rozšířeného Bayesova vzorce a vzorce celkové pravděpodobnosti . Potřebujeme tedy znát pouze rozložení pozorované složky pro pevný latent a pravděpodobnost latentních dat . $p({\mathbf X}|{\mathbf T},\Theta )$ $p({\mathbf T}|\Theta)$

Algoritmus EM iterativně zlepšuje počáteční skóre výpočtem nových hodnot skóre a tak dále. V každém kroku se přechod do z provede následovně: $\Theta _{0}$ $\Theta _{1},\Theta _{2},$ $\Theta _{{n+1}}$ $\Opalování$

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

kde je očekávaný logaritmus pravděpodobnosti. Jinými slovy, nemůžeme okamžitě vypočítat přesnou pravděpodobnost, ale ze známých dat ( ) můžeme najít posteriori odhad pravděpodobností pro různé hodnoty latentních proměnných . Pro každou sadu hodnot a parametrů můžeme vypočítat očekávání pravděpodobnostní funkce pro tuto sadu . Závisí na předchozí hodnotě , protože tato hodnota ovlivňuje pravděpodobnosti latentních proměnných . $Q(\Theta)$ $X$ $T$ $T$ $\Theta$ $X$ $\Theta$ $T$

$Q(\Theta)$ se počítá následovně:

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

to znamená, že se jedná o podmíněné očekávání pod podmínkou . $\log p\left({\mathbf X},{\mathbf T}\,|\,\Theta \right)$ $\mathbf {X}$

Jinými slovy, je hodnota, která maximalizuje (M) podmíněný průměr (E) logaritmické pravděpodobnosti pro dané hodnoty pozorovaných proměnných a předchozí hodnotu parametrů. Ve spojitém případě se hodnota vypočítá takto: $\Theta _{{n+1}}$ $Q(\Theta)$

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}

Alternativní popis

Za určitých okolností je vhodné uvažovat o EM algoritmu jako o dvou střídajících se maximalizačních krocích. [1] [2] Zvažte funkci:

F(q,\theta )=\jméno operátora {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)

kde q je rozdělení pravděpodobnosti nepozorovaných proměnných Z ; p Z | X ( · | x ; θ ) je podmíněné rozdělení nepozorovaných proměnných pro pevné pozorovatelné x a parametry θ ; H je entropie a D KL je Kullback-Leiblerova vzdálenost .

Potom lze kroky EM algoritmu reprezentovat jako:

E (očekávání) krok : Zvolte q pro maximalizaci F :

q^{(t)}=\jméno operátora {*} {\arg \,\max }_{q}\ F(q,\theta ^{(t)})

M (aximizační) krok : Zvolte θ pro maximalizaci F :

\theta ^{(t+1)}=\jméno operátora {*} {\arg \,\max }_{\theta }\ F(q^{(t)},\theta )

Příklady použití

k-means - shlukovací algoritmus postavený na myšlence EM algoritmu
Metoda elastických map pro redukci nelineárních rozměrů dat
Baum-Welsh algorithm - algoritmus pro odhad parametrů skrytých Markovových modelů

Poznámky

↑ Radford; Neal; Hinton, Geoffrey . Pohled na EM algoritmus, který ospravedlňuje inkrementální, řídké a další varianty // Learning in Graphical Models : journal / Michael I. Jordan . - Cambridge, MA: MIT Press, 1999. - S. 355-368 . — ISBN 0262600323 .
↑ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome. 8.5 Algoritmus EM // Prvky statistického učení (neopr.) . - New York: Springer, 2001. - S. 236-243. — ISBN 0-387-95284-5 .

Odkazy

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-síť Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-learning SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Teorie počítačového učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG