Algorisme de maximització d'expectativa

Agrupació EM de dades d'erupció Old Faithful. El model inicial aleatori (que, a causa de les diferents escales dels eixos, sembla ser dues el·lipses molt planes i amples) s'ajusta a les dades observades. En les primeres iteracions, el model canvia substancialment, però després convergeix als dos modes del guèiser. Visualitzat amb ELKI.

En estadístiques, un algorisme de maximització d'expectativa (EM) és un mètode iteratiu per trobar estimacions de màxima probabilitat (local) o màxim a posteriori (MAP) de paràmetres en models estadístics, on el model depèn de variables latents no observades. La iteració EM alterna entre la realització d'un pas d'expectativa (E), que crea una funció per a l'expectativa de la probabilitat logarítmica avaluada utilitzant l'estimació actual dels paràmetres, i un pas de maximització (M), que calcula els paràmetres maximitzant el logaritme esperat. probabilitat que es troba al pas E. Aquestes estimacions de paràmetres s'utilitzen llavors per determinar la distribució de les variables latents en el següent pas E.

Història

L'algoritme EM va ser explicat i donat el seu nom en un article clàssic de 1977 d' Arthur Dempster, Nan Laird i Donald Rubin. Van assenyalar que el mètode havia estat "proposat moltes vegades en circumstàncies especials" per autors anteriors. Un dels primers és el mètode de recompte de gens per estimar les freqüències d'al·lels de Cedric Smith. Un altre va ser proposat per HO Hartley el 1958, i Hartley i Hocking el 1977, d'on es van originar moltes de les idees del document Dempster–Laird–Rubin. Un altre de SK Ng, Thriyambakam Krishnan i GJ McLachlan el 1977. Les idees de Hartley es poden ampliar a qualsevol distribució discreta agrupada. Un tractament molt detallat del mètode EM per a famílies exponencials va ser publicat per Rolf Sundberg en la seva tesi i diversos articles, després de la seva col·laboració amb Per Martin-Löf i Anders Martin-Löf. El document Dempster–Laird–Rubin de 1977 va generalitzar el mètode i va esbossar una anàlisi de convergència per a una classe més àmplia de problemes. El document Dempster-Laird-Rubin va establir el mètode EM com una eina important d'anàlisi estadística. Vegeu també Meng i van Dyk (1997).

L'anàlisi de convergència de l'algoritme Dempster–Laird–Rubin va ser errònia i CF Jeff Wu va publicar una anàlisi de convergència correcta el 1983. La prova de Wu va establir la convergència del mètode EM també fora de la família exponencial, tal com afirma Dempster–Laird–Rubin.

Introducció

L'algorisme EM s'utilitza per trobar paràmetres de màxima versemblança (local) d'un model estadístic en els casos en què les equacions no es poden resoldre directament. Normalment, aquests models impliquen variables latents, a més de paràmetres desconeguts i observacions de dades conegudes. És a dir, o bé existeixen valors que falten entre les dades, o el model es pot formular de manera més senzilla assumint l'existència de punts de dades addicionals no observats. Per exemple, un model de barreja es pot descriure de manera més senzilla assumint que cada punt de dades observat té un punt de dades no observat corresponent, o variable latent, especificant el component de la barreja al qual pertany cada punt de dades.

Descripció

Els símbols

Donat el model estadístic que genera un conjunt $\mathbf {X}$ de dades observades, un conjunt de dades latents no observades o valors que falten $\mathbf {Z}$, i un vector de paràmetres desconeguts ${\boldsymbol {\theta }}$, juntament amb una funció de versemblança $L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})$, l' estimació de màxima probabilitat (MLE) dels paràmetres desconeguts es determina maximitzant la probabilitat marginal de les dades observades

$L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} \mid {\boldsymbol {\theta }})=\int p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z} =\int p(\mathbf {X} \mid \mathbf {Z} ,{\boldsymbol {\theta }})p(\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z}$No obstant això, aquesta quantitat sovint és intractable des de llavors $\mathbf {Z}$ no s'observa i la distribució de $\mathbf {Z}$ es desconeix abans d'aconseguir ${\boldsymbol {\theta }}$.

L'algorisme EM

L'algorisme EM busca trobar el MLE de la probabilitat marginal aplicant iterativament aquests dos passos:

Pas d'expectativa (pas E): Definir com el valor esperat de la funció de probabilitat logarítmica de , respecte a la distribució condicional actual de donat i les estimacions actuals dels paràmetres :

Pas de maximització (pas M) : Trobeu els paràmetres que maximitzen aquesta quantitat:

${\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\,$

Més succintament, podem escriure-ho com una equació:

$${\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\operatorname {E} _{\mathbf {Z} \sim p(\cdot |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}\left[\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})\right]\,$$

Applications

L'EM s'utilitza freqüentment per a l'estimació de paràmetres de models mixts, sobretot en genètica quantitativa.

En psicometria, l'EM és una eina important per estimar els paràmetres d'ítem i les habilitats latents dels models de teoria de resposta a l'ítem.

Amb la capacitat de fer front a les dades que falten i d'observar variables no identificades, EM s'està convertint en una eina útil per valorar i gestionar el risc d'una cartera.

L'algoritme EM (i la seva variant més ràpida de maximització de l'expectativa del subconjunt ordenat) també s'utilitza àmpliament en la reconstrucció d'imatges mèdiques, especialment en la tomografia per emissió de positrons, la tomografia computada per emissió d'un sol fotó i la tomografia computada de raigs X. Vegeu a continuació altres variants més ràpides d'EM.

En enginyeria estructural, l'algoritme d'identificació estructural mitjançant la maximització de les expectatives (STRIDE) és un mètode només de sortida per identificar les propietats de vibració natural d'un sistema estructural mitjançant dades de sensors (vegeu Anàlisi modal operativa).

EM també s'utilitza per agrupar dades. En el processament del llenguatge natural, dos exemples destacats de l'algorisme són l' algorisme de Baum-Welch per als models de Markov ocults i l'algoritme interior-exterior per a la inducció no supervisada de gramàtiques probabilistes sense context.

En l'anàlisi dels temps d'espera entre operacions, és a dir, el temps entre les operacions posteriors d'accions en una borsa de valors, l'algorisme EM ha demostrat ser molt útil.