A klasszikus példa EM algoritmusra

Az EM cikk szerzői is ezt a példát említik elsőként. A hiányos adatrendszerhez tartozó $\boldsymbol{\EuScript Y}$ mintatér legyen olyan $4$ dimenziós nemnegatív egész értékű vektorok halmaza, amelyben a koordináták összege konstans, például $n=197.$ $\boldsymbol{\EuScript B}$ álljon $\boldsymbol{\EuScript Y}$ összes lehetséges részhalmazából, azaz $\boldsymbol{\EuScript B}=2^{\boldsymbol{\EuScript Y}}.$ Legyen $\nu$ a számláló mérték, azaz az egyelemű halmazok mértéke legyen $1$ , a véges halmazok mértéke legyen annyi, ahány elemet tartalmaz, a végtelen halmazok mértéke legyen $\infty.$ Ekkor a $g_{\boldsymbol\theta }$ sűrűségfüggvény egy $\bf y\in \boldsymbol{\EuScript Y}$ ponton megegyezik a $\boldsymbol P_{\boldsymbol\theta }^{\boldsymbol{\EuScript Y}}(\bf y)$ valószínűséggel. Legyen a $\boldsymbol\Theta$ paramétertér a $(0,1)$ nyílt intervallum. Egy ${\bf y}=(y_1,y_2,y_3,y_4)\in\boldsymbol{\EuScript Y}$ valószínűsége legyen

$$g_{\boldsymbol\theta }({\bf y})=\boldsymbol P_{\boldsymbol\theta }^{\boldsymbol{\EuScript Y}}({\bf y})=$$

$$={n!\over {y_1}!{y_2}!{y_3}!{y_4}!} \left({{1\over 2}+{1\over 4}\... ...dsymbol\theta }\right)^{y_3} \left({{1\over 4}\boldsymbol\theta }\right)^{y_4}.$$

Tehát az eloszlás egy multinomiális eloszlás az ${1\over 2}+{1\over 4}\boldsymbol\theta , {{1\over 4}-{1\over 4}\boldsymbol\theta }, {{1\over 4}-{1\over 4}\boldsymbol\theta }$ és ${{1\over 4}\boldsymbol\theta }$ paraméterekkel.

Nem szükséges EM algoritmus a paraméterbecsléshez, amennyiben maximum likelihood módszerrel akarjuk becsülni a paramétert egy konkrét mintából. A maximum likelihood egyenlet explicite megoldható ebben az esetben. Rövidítse a

$${n!\over {y_1}!{y_2}!{y_3}!{y_4}!} \left({1\over 4}\right)^{y_1}\... ...over 4}\right)^{y_2} \left({1\over 4}\right)^{y_3}\left({1\over 4}\right)^{y_4}$$

kifejezést $c(\bf y).$ A $g_{\boldsymbol\theta }$ sűrűségfüggvény log likelihood függvénye

$$L(\boldsymbol\theta )=\log(g_{\boldsymbol\theta })=$$

$$=\log(c({\bf y}))+ {y_1}\log\left({2+\boldsymbol\theta }\right)+ ... ...left({1-\boldsymbol\theta }\right)+ {y_4}\log\left({\boldsymbol\theta }\right).$$

A log likelihood függvény $\boldsymbol\theta$ szerinti deriváltja a $(0,1)$ intervallumban

$${dL(\boldsymbol\theta )\over d\boldsymbol\theta }={y_1\over{2+\bo... ...bol\theta }}-{y_2+y_3\over{1-\boldsymbol\theta }}+{y_4\over\boldsymbol\theta }.$$

A ${dL(\boldsymbol\theta )\over d\boldsymbol\theta }=0$ log likelihood egyenlet a

$$(y_1+y_2+y_3+y_4)\boldsymbol\theta ^2+(2y_2+2y_3+y_4-y_1)\boldsymbol\theta -2y_4=0$$

egyenletre vezet. Mivel a log likelihood függvény második deriváltjának mínusz egyszerese

$$-{d^2L(\boldsymbol\theta )\over d\boldsymbol\theta ^2}={y_1\over(... ... })^2}+{y_2+y_3\over({1-\boldsymbol\theta })^2}+{y_4\over\boldsymbol\theta ^2},$$

ezért nem negatív $y_1,y_2,y_3,y_4$ értékekre, tehát esetünkben, a log likelihood függvény konkáv függvénye a $\boldsymbol\theta$ paraméternek. Ezért mindig egyértelműen létezik megoldása a log likelihood egyenletnek a $(0,1)$ intervallumban, mert a log likelihood deriváltja, amint tartunk a nullába, illetve az egybe tart mínusz végtelenbe, így ott a függvény nem veheti fel maximumát.

Noha létezik explicit megoldás, mégis érdemes megnézni az EM algoritmust ezen a példán, mert itt jól nyomon követhető az algoritmus működése, valamint több dimenziós hiányos adatrendszer esetén már nem lehet explicite megoldani a log likelihood egyenletet, mert az egy magasabbfokú polinom gyökeinek megkeresésére vezet.

Ezt a multinomiális mintát úgy is produkálhatjuk, hogy egymástól függetlenül $n$ alkalommal veszünk egy 4 dimenziós indikátor változóból mintát úgy, hogy az indikátor változó komponenseiben az egyesek valószínűsége a multinomiális eloszlás paramétereinek felel meg, majd összeszámoljuk, hogy az indikátor változó melyik értéke hányszor jött ki, illetve összegezhetjük is az indikátor változókat. Fogalmazhatjuk ezt úgy is, hogy van négy urnánk és ezekbe rendre a multinomiális eloszlás paramétereinek valószínűségével esik egy golyó. Tehát az elsőbe ${{1\over 2}+{1\over 4}\boldsymbol\theta }$ , a másodikba és a harmadikba ${{1\over 4}-{1\over 4}\boldsymbol\theta }$ , a negyedikbe ${{1\over 4}\boldsymbol\theta }$ valószínűséggel esik golyó.

Úgy is elképzelhetjük ezt a szituációt, hogy az első urnát kettévalasztjuk, és úgy gondolunk rá, mintha az egyik részbe konstans $1\over 2$ valószínűséggel esne golyó, a másikba pedig ${{1\over 4}\boldsymbol\theta }$ valószínűséggel esne golyó. Ha tudnánk, hogy az első urna képzeletbeli rekeszeibe a mintavételezés során hány golyó esett, akkor egyszerűen meghatározhatnánk a paraméter maximum likelihood becslését, hiszen ekkor kis átalakítással a binomiális eloszlás paraméterének ismert maximum likelihood becslésére vezethetnénk vissza a problémát. Nem ismerjük a problémát leegyszerűsítő rekesz darabszámokat, ezért mondhatjuk, hogy az eredeti minta egy hiányos adatrendszer. Mivel nem ismerjük, hogy az első urna melyik rekeszébe hány golyó esik, ezért a számolások során csak az ismert golyószámok melletti feltételes várható értékét vehetjük az első urna rekeszeibe eső golyók számának. Az EM algoritmus során fellépő számolásokban a hiányzó golyószámokat lehet helyettesíteni azok feltételes várható értékével. Ez általánosságban nem tehető meg, hanem a log likelihood függvény feltételes várható értékét kell venni.

A teljes adatrendszerhez tartozó $\boldsymbol{\EuScript X}$ mintatér tehát legyen az olyan 5 dimenziós nem negatív értékeket tartalmazó vektorok halmaza, melyekben a komponensek összege $n.$ A mérhető halmazok összessége, $\boldsymbol{\EuScript A}$ legyen az összes részhalmazok halmaza, $2^{\boldsymbol{\EuScript X}}.$ A $\mu$ mérték legyen a számláló mérték, mint a hiányos adatrendszer esetén. Így az $f$ sűrűségfüggvény most is megegyezik a valószínűséggel, és tetszőleges ${\bf x}=(x_{11},x_{12},x_2,x_3,x_4)\in\boldsymbol{\EuScript X}$ vektorra legyen

$$f_{\boldsymbol\theta }({\bf x})=\boldsymbol P_{\boldsymbol\theta }^{\boldsymbol{\EuScript X}}({\bf x})=$$

$$={n!\over {x_{11}}!{x_{12}}!{x_2}!{x_3}!{x_4}!} \left({1\over 2}\... ...dsymbol\theta }\right)^{x_3} \left({{1\over 4}\boldsymbol\theta }\right)^{x_4}.$$

A $\gamma : \boldsymbol{\EuScript X} \rightarrow \boldsymbol{\EuScript Y}$ függvény legyen olyan, hogy $\forall\;{\bf x}=(x_{11},x_{12},x_2,x_3,x_4)\in\boldsymbol{\EuScript X}$ vektorra $\gamma(x_{11},x_{12},x_2,x_3,x_4)=(x_{11}+x_{12},x_2,x_3,x_4).$ Ekkor az EM algoritmusban a $\gamma$ függvényre megkövetelt egyenlőség valóban teljesül, mert tetszőleges ${\bf y}=(y_1,y_2,y_3,y_4)\in\boldsymbol{\EuScript Y}$ elemre

$$\int_{\gamma^{-1}({\bf y})} f_{\boldsymbol\theta }\;d\mu =$$

$$\hskip2em=\hskip -3.5em\int\limits_{\{\,(x_{11},x_{12},y_2,y_3,y_... ...t({{1\over 4}-{1\over 4}\boldsymbol\theta }\right)^{y_2+y_3}\hskip -1.7em d\mu=$$

$$=\hskip -2.5em\sum_{\{\,(x_{11},x_{12})\;\vert\;x_{11}+x_{12}\>=\... ... \left({{1\over 4}-{1\over 4}\boldsymbol\theta }\right)^{y_2+y_3}\hskip -1.7em=$$

$$=\sum_{x_{11}=0}^{y_1} {y_1!\over{x_{11}}!{x_{12}}!} \left({1\ove... ... \left({{1\over 4}-{1\over 4}\boldsymbol\theta }\right)^{y_2+y_3}\hskip -1.7em=$$

$$=\sum_{x_{11}=0}^{y_1} {y_1\choose x_{11}} \left({1\over 2}\right... ... \left({{1\over 4}-{1\over 4}\boldsymbol\theta }\right)^{y_2+y_3}\hskip -1.7em=$$

$$=\left({1\over 2}+{{1\over 4}\boldsymbol\theta }\right)^{y_1} {n!... ... \left({{1\over 4}-{1\over 4}\boldsymbol\theta }\right)^{y_2+y_3}\hskip -1.7em=$$

$$=g_{\boldsymbol\theta }^{\boldsymbol{\EuScript Y}}(\bf y).$$

A

$${n!\over {x_{11}}!{x_{12}}!{x_2}!{x_3}!{x_4}!}\left({1\over 2}\ri... ...over 4}\right)^{x_2} \left({1\over 4}\right)^{x_3}\left({1\over 4}\right)^{x_4}$$

kifejezést jelölje $d(\bf x).$ Az EM algoritmushoz kiszámolandó $\boldsymbol E_{\boldsymbol\theta _n}(\log f_{\boldsymbol\theta }\vert\gamma^{-1}(y))$ feltételes várható érték

$$\boldsymbol E_{\boldsymbol\theta _n}(\log\left( d({\bf x}) \bolds... ...right)^{x_3} \left(\boldsymbol\theta \right)^{x_4}\right) \vert\gamma^{-1}(y))=$$

$$=\boldsymbol E_{\boldsymbol\theta _n}(\log\left( d({\bf x})\right... ...oldsymbol\theta +(x_2+x_3)\log(1-\boldsymbol\theta ))\;\vert\; \gamma^{-1}(y))=$$

$$=\boldsymbol E_{\boldsymbol\theta _n}(\log\left( d({\bf x})\right... ... E_{\boldsymbol\theta _n}(x_{12}\;\vert\;\gamma^{-1}(y))\log\boldsymbol\theta +$$

$$+y_4\log\boldsymbol\theta +(y_2+y_3)\log(1-\boldsymbol\theta )).$$

Az egyenlőség utolsó elemének első tagja egy $\boldsymbol\theta$ szempontjából konstans $C$ . A második tagban diszkrét valószínűségi változók feltételes várható értékét kell venni, ami a feltételes valószínűséggel vett várható érték. Ezért

$$\boldsymbol E_{\boldsymbol\theta _n}(x_{12}\;\vert\;\gamma^{-1}(y))=$$

$$=\sum_{k=0}^{y_1}k {\boldsymbol P_{\boldsymbol\theta _n}^{\boldsy... ...oldsymbol P_{\boldsymbol\theta _n}^{\boldsymbol{\EuScript X}}(\gamma^{-1}(y))}=$$

$$=\sum_{k=0}^{y_1}k {\boldsymbol P_{\boldsymbol\theta _n}^{\boldsy... ...=y_3,x_4=y_4)\over \int_{\gamma^{-1}({\bf y})} f_{\boldsymbol\theta _n}\;d\mu}=$$

$$=\sum_{k=0}^{y_1}k {\boldsymbol P_{\boldsymbol\theta _n}^{\boldsy... ...{11}=y_1-k,x_{12}=k,x_2=y_2,x_3=y_3,x_4=y_4)\over g_{\boldsymbol\theta _n}(y)}=$$

$$=\sum_{k=0}^{y_1}k { {{n!\over (y_1-k)!k!{y_2}!{y_3}!{y_4}!} \lef... ...eta _n}}\right)^{y_3} \left({{1\over 4}{\boldsymbol\theta _n}}\right)^{y_4}} }=$$

$$=\sum_{k=0}^{y_1}k {y_1\choose k}\left({{1\over 2}\over{1\over 2}... ...boldsymbol\theta _n}\over{1\over 2}+{1\over 4}{\boldsymbol\theta _n}}\right)^k=$$

$$=y_1{{1\over 4}{\boldsymbol\theta _n}\over{1\over 2}+{1\over 4}{\boldsymbol\theta _n}}.$$

Ugyanis a legutolsó összeg egy ${\left({{1\over 4}{\boldsymbol\theta _n}}\right)/\left({1\over 2}+{1\over 4}{\boldsymbol\theta _n}\right)}$ és $n$ paraméterű binomiális eloszlású valószínűségi változó várható értéke. Tehát $x_{12}$ és így $x_{11}$ is binomiális eloszlású. Ez szemléletesen is világos, mert az első urnába $1\over 2$ illetve ${1\over 2}+{1\over 4}{\boldsymbol\theta _n}$ valószínűséggel hullanak a golyók, tehát csak erre az urnára leszűkítve a kísérletet a fenti valószínűséggel és egy mínusz annyi valószínűséggel esnek a golyók az egyik, illetve a másik rekeszbe, ami binomiális eloszlást ad.

Összegezve, a maximalizálandó $\boldsymbol E_{\boldsymbol\theta _n}(\log f_{\boldsymbol\theta }\vert\gamma^{-1}(y))$ feltételes várható érték

$$\left(y_1{{1\over 4}{\boldsymbol\theta _n}\over{1\over 2}+{1\over... ...a _n}}+y_4\right)\log\boldsymbol\theta + (y_2+y_3)\log(1-\boldsymbol\theta )+C.$$

Ez a függvény a $\boldsymbol\theta$ paraméterben olyan, mint egy binomiális eloszlású valószínűségi változó log likelihood függvénye azzal a különbséggel, hogy itt a kitevőben nem csak egész számok vannak, hanem egy várható érték is. Ettől függetlenül a $\boldsymbol\theta$ paraméterben maximalizálja

$$\boldsymbol\theta _{n+1}={y_1{{1\over 4}{\boldsymbol\theta _n}\ov... ...symbol\theta _n}\over{1\over 2}+{1\over 4}{\boldsymbol\theta _n}}+y_2+y_3+y_4}.$$

Az EM algoritmus konvergenciája tétel miatt a $\boldsymbol\theta _n$ paraméterértékek sorozata konvergál, méghozzá a hiányos adatrendszerhez tartozó likelihood függvény maximumához, mivel egyértelműen létezik a maximuma. A határérték ki is számolható, mert $\boldsymbol\theta _{n+1}$ folytonos függvénye a $\boldsymbol\theta _n$ paraméternek, és ezért $\boldsymbol\theta _{n+1}$ határértékében írható a benne szereplő $\boldsymbol\theta _n$ helyére és $\boldsymbol\theta _{n+1}$ helyére is a limesz. Így kapunk egy egyenletet a határértékre, ami alapján ellenőrizhető, hogy a példa legelején ugyanazt az egyenletet kellett megoldanunk. A

$$\boldsymbol\theta ={y_1{{1\over 4}{\boldsymbol\theta }\over{1\ove... ...eta }+y_4 \over y_1{\boldsymbol\theta \over 2+\boldsymbol\theta }+y_2+y_3+y_4}=$$

$$={y_1\boldsymbol\theta +y_4(2+\boldsymbol\theta ) \over {y_1\boldsymbol\theta }+(2+\boldsymbol\theta )(y_2+y_3+y_4)}$$

Az egyenlet elejéből és végéből átrendezéssel adódik a

$$(y_1+y_2+y_3+y_4)\boldsymbol\theta ^2+(2y_2+2y_3+y_4-y_1)\boldsymbol\theta -2y_4=0$$

egyenlet.