13.3. Kilógó adatok

A hiányzó adatok mellett igen sok problémát okoznak a zajok vagy a mérési hibák miatt fellépő, a valós adatoktól erősen eltérő, úgynevezett kilógó adatok (outliers) is. Ebben az alfejezetben alapvetően az adatok minősítésével foglalkozunk; hogyan lehet felismerni, modellezni, hogy az adathalmazból melyeket tekintsünk kilógóknak, melyek tekinthetők "csupán" a szokásos módon zajosnak. A következő alfejezetben ismertetett, hiányzó adatok pótlására szolgáló eljárások alkalmasak lehetnek arra, hogy javítsuk az adatbázisunkat. A detektált kilógó adatokat ugyanis egyszerűen úgy tekinthetjük, hogy ezekben a pontokban hiányzik a releváns információ.

Kézi adatrögzítés esetén tipikus "mérési hiba" az adatrögzítés hibája, pl. rossz helyre tett tizedesvessző. A hatásuk több szempontból is káros. Egyrészt a tanítás folyamatában az impulzuszajoknál (lásd 13.1.1) ismertetett eredményre vezethetnek (a modellben általában nem impulzusszerű, de egy tágabb környezetben elkent torzítást okozhatnak). Másrészt tönkretehetik az előfeldolgozásnál nagyon gyakran alkalmazott és rendkívül hasznos normalizálási lépést. Az 13.6 ábrán egy zajmentes, [-1,1] tartományra normált szinuszjel és hisztogramja látható.

13.6. ábra - Egy [-1,1]-re normalizált szinuszjel, és hisztogramja
Egy [-1,1]-re normalizált szinuszjel, és hisztogramja

A következő ábra azt mutatja, hogy ha valamilyen okból a jel egyetlen pontjában egy erősen hibás (kilógó) értéket mérünk, akkor az a normalizáláskor összenyomja a hasznos jeltartományt. Ha ezzel a normalizált paraméterrel tanítunk egy hálót, akkor azt "sugalljuk", hogy lényegében +1 és -1 értékek fordulnak elő ezen a bemenetén (a +1-es érték csak egyszer, a -1 körüli értékek sokszor), mintha bináris jelünk lenne. Természetesen a háló képes lehet ezt kiküszöbölni, de minden "félrevezetés" rontja a megoldás minőségét és a tanulás konvergencia sebességét.

13.7. ábra - Egyetlen kilógó értékkel terhelt szinuszjel [-1,1]-re normalizálva, és a normált jel hisztogramja
Egyetlen kilógó értékkel terhelt szinuszjel [-1,1]-re normalizálva, és a normált jel hisztogramja

13.3.1. Kilógó értékek modellezése klaszterezéssel, az EM algoritmus

A kilógó értékek káros hatását csökkentő eljárások alapvető problémája, hogy honnan vesszük észre egy adatról, hogy az alapvetően használt jelmodellünknek megfelel-e, ami lehet valamilyen szokásos mértékben zaj által torzított adat, vagy valamilyen rendkívüli, nagymértékű torzítás történt.

Az egyik lehetőség az adatok nemellenőrzött tanítással történő osztályozása, klaszterezése. (Ellenőrzött tanítás nem jöhet szóba, hiszen nem tudjuk az egyes adatokról, hogy melyik csoportba tartoznak.)

Feltételezhetjük, hogy ha a torzítás nagymértékű, akkor az adatok osztályozása során a kilógó adatok a tipikusaktól eltérő klaszterbe kerülnek. Elvileg nincs más dolgunk, mint klaszterezni és eldönteni, hogy melyik klaszter tartalmazza a normál és melyik vagy melyek a kilógó adatokat. Általában azzal az egyszerű feltételezéssel élünk, hogy a normál adatok vannak többségben, és a nagy elemszámú csoportokat (klasztereket) normálként kezeljük. Ugyanakkor a helyzet különösen problematikus akkor, ha nagyon összetett (sokdimenziós) adatokat használunk, és a kilógó adat sokféleképpen jöhet létre. A következő ábrán demonstráljuk a problémát egy kétváltozós adathalmazon.

Látható, hogy ha a kétváltozós adathalmazunk mindkét paraméterére egyszerre hat a nagymértékű torzítás, amely kilógó adatokat eredményez, akkor két klaszter jött létre: egy a normál adatokból és egy a kilógókból. Amennyiben a torzítás hol ezt, hol azt a paramétert éri (pl. hol az egyik, hol a másik adatot regisztrálják hibásan), akkor 3 klaszter alakul ki. Ez azért fontos kérdés, mert a klaszterezési eljárásaink nagy része kötött, előre rögzített számú klaszter esetén működik jól. Ha felülbecsüljük a klaszterek számát, és pl. a 13.8 (a) ábrában 3 klasztert keresünk, akkor fennáll a veszély, hogy a normál adatok egy részét is leválasztjuk és kilógónak tekintjük. Ha viszont alulbecsüljük a klaszterek számát, pl. a 13.8 (b) ábrában 2 klasztert keresünk, akkor jó eséllyel az egyik kilógó csoportot normálnak fogjuk tekinteni.

13.8. ábra - A kilógó adatokat mindkét paraméterre egyszerre (a), illetve külön-külön ható (b) torzítás hozta létre (mindkét ábrán a vízszintes tengelyen az egyik, a függőleges tengelyen a másik paraméter értéke látható)
A kilógó adatokat mindkét paraméterre egyszerre (a), illetve külön-külön ható (b) torzítás hozta létre (mindkét ábrán a vízszintes tengelyen az egyik, a függőleges tengelyen a másik paraméter értéke látható)

A feladatunk tehát abban áll, hogy önszerveződő osztályozással, klaszterezéssel eltérő paramétereloszlású csoportokat keresünk, és ennek alapján döntjük el, hogy melyik adat kilógó és melyik normál adat.

Az EM-algoritmus

Az EM-algoritmust (expectation-maximization algorithm) először általánosságban tárgyaljuk, majd konkretizáljuk egy olyan feladatra, amely kevert minták szétválasztását célozza[9].

Általánosságban az EM-algoritmust olyan feladatok megoldására fejlesztették ki, amelyekben ismeretlen, de konkrét, elvileg rögzített paraméterek becslését szeretnénk meghatározni valamilyen adathalmaz alapján úgy, hogy bizonyos adatelemeket nem ismerünk (pl. nem tudjuk ezeket mérni), csak valószínűség-eloszlásukról van információnk [Dem77], [Mit97].

Az EM-algoritmus szemléltetésére több példa is felhozható. Első példánk legyen a következő: meg akarjuk becsülni egy sokdimenziós adathalmaz átlagát úgy, hogy az adataink hiányosak, bizonyos adatvektorok egy vagy több komponense hiányzik. (Pl. egy – valamilyen elektromos vagy elektronikus berendezésekből álló – termékhalmazon mérték a termék áramfelvételét, két meghibásodás közötti időt stb., de néhány terméknél egyik-másik adat hiányzik, elveszett stb.) Egy másik lehetséges példa, amelyet későbbiekben részletesebben is tárgyalunk a következő: van egy adatsorunk, melyben az adatok több eloszlásból származhatnak. Az adatok alapján szeretnénk megbecsülni az egyes eloszlások várható értékét, de anélkül, hogy tudnánk, hogy az egyes adatok melyik eloszlásból származnak. Egy hétköznapi példaként gondoljunk arra, hogy az amerikaiak magasság, vérnyomás stb. adatai alapján azt szeretnénk megmondani, hogy az amerikaiakon belül az egyes népcsoportok (fehér, néger, mexikói, ázsiai) átlagmagassága, vérnyomásának átlaga és szórása stb. mekkora. Mindezt azonban úgy szeretnénk meghatározni, hogy az egyes méréseknél nem lett feljegyezve, hogy ki melyik népcsoportba tartozik. Van tehát egy olyan adathalmazunk, mely pl. a magasságértékeket tartalmazza, de az egyes értékek mellett nincs meg az az információ, hogy melyik magasságérték melyik népcsoportba tartozó ember magassága, vagyis hiányos adatokkal van dolgunk. Itt az ismeretlen paraméter, a hiányzó adat az, hogy melyik adat melyik csoportból származik, a keresett paramétervektor pedig a csoportok átlagos magasságából képzett vektor. (Természetesen ennek a demográfiai illetve népegészségügyi példának számos műszaki analógiáját lehet találni, de ez talán egy könnyen érthető példa.)

Az EM-algoritmust általános formájában a következőképpen szokták megfogalmazni (pl. [Mit97]). Egy valószínűség eloszlás valamilyen θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ paramétervektorát akarjuk becsülni csupán részlegesen megfigyelhető adatok alapján. Legyen X={x1, x2, …, xL} a megfigyelt adatkomponensek halmaza és Z={z1, z2, …, zL} azon adatkomponensek halmaza, amelyeket nem tudtunk megfigyelni. Tehát az Y=XZMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamywaiabg2da9iaadIfacqGHQicYcaWGAbaaaa@3AA9@ lenne a teljes adathalmaz, és ha mind X, mind Z ismert volna a feladatot könnyen meg lehetne oldani. Minthogy Z-t nem ismerjük, ezt hiányzó ismeretnek nevezzük. A nem ismert Z komponenseket valószínűségi változóként kezelhetjük, amelyek eloszlása az ismeretlen θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ paramétervektortól függ. Hasonlóképpen Y is valószínűségi változó, hiszen X és Z segítségével definiáltuk. A Z hiányzó adatokat jellemző valószínűség eloszlás függ a keresett paramétertől. Ha ismernénk Z valószínűség eloszlását, akkor az X megfigyelt adatok alapján a θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ paramétervektor becslését meg tudnánk határozni. Ugyanis a θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ paramétervektor becsléséhez Z teljes ismerete nem szükséges Z várható értéke alapján a becslés meghatározható (Meg tudnánk fogalmazni egy maximum likelihood becslési feladatot, melynek megoldásaként θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ olyan becslését határozhatnánk meg, mely mellett a megfigyléseink a legnagyobb valószínűségűek.) A θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ becslés segítségével a hiányzó adatok valószínűség eloszlását pontosabban meg tudjuk adni, ami (a maximum likelihood becslésen keresztül) a θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ paraméter jobb becslését eredményezi. Az eljárást folytatva a paramétervektor egyre jobb becslését kapjuk. Megfelelő feltételek mellett ez az iteratív eljárás konvergens és a θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ becslések sorozata a valódi θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ paraméterhez konvergál [Dem77].

Általánosabban az eljárást a következőképpen fogalmazhatjuk meg. Van egy kiinduló hipozézisünk az ismeretlen paraméterről. Jelöljük ezt h-val. A h aktuális hipotézis megad egy aktuálisan igaznak tartott paramétervektort. Egy iteráció során egy új hipotézist, h’-t állítunk fel, mely a paramétervektor egy jobb becslését adja. Olyan új hipotézist keresünk, mely mellett a (teljes) megfigyeléseinkre vonatkozó P(Y|h)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabmaabaGaamywamaaeeaabaGabmiAayaafaaacaGLhWoaaiaawIcacaGLPaaaaaa@3B32@ feltételes sűrűségfüggvény maximumát a tényleges adatainknál veszi fel. Ez egy maximum likelihood becslési feladat lenne, ahol a feltételes sűrűségfüggvény a likelihood függvény. Azonban mivel az Y teljes adathalmazt nem ismerjük, a P(Y|h)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabmaabaGaamywamaaeeaabaGabmiAayaafaaacaGLhWoaaiaawIcacaGLPaaaaaa@3B32@ likelihood függvény maximumát biztosító hipotézist sem tudjuk meghatározni. Meghatározhatjuk azonban a P(Y|h)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabmaabaGaamywamaaeeaabaGabmiAayaafaaacaGLhWoaaiaawIcacaGLPaaaaaa@3B32@ likelihood függvény várhatóértékét E{P(Y|h)}MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyramaacmaabaGaamiuamaabmaabaGaamywamaaeeaabaGabmiAayaafaaacaGLhWoaaiaawIcacaGLPaaaaiaawUhacaGL9baaaaa@3E2D@ -t, és a várhatóérték alapján fogalmazhatunk meg egy maximum likelihood becslési feladatot. Az E{P(Y|h)}MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyramaacmaabaGaamiuamaabmaabaGaamywamaaeeaabaGabmiAayaafaaacaGLhWoaaiaawIcacaGLPaaaaiaawUhacaGL9baaaaa@3E2D@ meghatározásához az Y teljes adatok ismeretére nincs szükségünk, elegendő, ha Y eloszlása ismert, ami azt jelenti, hogy a hiányzó adatok ismerete nélkül, de a hiányzó adatok eloszásának ismeretében a várhatóérték likelihood függvény megfogalmazható. A várhatóértéket az Y-t generáló valószínűségi eloszlás felett képezzük, amelyet viszont a θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ paramétervektor határoz meg. Az aktuális hipoztézis (az ehhez tartozó aktuális paraméterbecslés) alapján meghatározható a várhatóérték likelihood függvény, E{P(Y|h)}MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyramaacmaabaGaamiuamaabmaabaGaamywamaaeeaabaGabmiAayaafaaacaGLhWoaaiaawIcacaGLPaaaaiaawUhacaGL9baaaaa@3E2D@ , majd az ennek maximumát biztosító új hipotézis. (Legtöbbször praktikus okokból e helyett az E{log(P(Y|h))}MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyramaacmaabaGaaeiBaiaab+gacaqGNbWaaeWaaeaacaWGqbWaaeWaaeaacaWGzbWaaqqaaeaaceWGObGbauaaaiaawEa7aaGaayjkaiaawMcaaaGaayjkaiaawMcaaaGaay5Eaiaaw2haaaaa@4281@ -t maximáljuk, de ez a lényegen nem változtat, a két kifejezés maximuma egybeesik.)

Definiáljunk egy Q(h|h)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyuamaabmaabaGabmiAayaafaWaaqqaaeaacaWGObaacaGLhWoaaiaawIcacaGLPaaaaaa@3B42@ függvényt, ami E{log(P(Y|h))}MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyramaacmaabaGaaeiBaiaab+gacaqGNbWaaeWaaeaacaWGqbWaaeWaaeaacaWGzbWaaqqaaeaaceWGObGbauaaaiaawEa7aaGaayjkaiaawMcaaaGaayjkaiaawMcaaaGaay5Eaiaaw2haaaaa@4281@ -t mint h’ függvényét adja meg azzal a feltételezéssel, hogy az aktuális hipotézisünk, h szerint a paramétervektor értéke θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ , valamint, hogy az adataink megfigyelhető része X:

Q(h|h)=E{P(Y|h) | h,X}MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyuamaabmaabaGabmiAayaafaWaaqqaaeaacaWGObaacaGLhWoaaiaawIcacaGLPaaacqGH9aqpcaWGfbWaaiWaaeaacaWGqbWaaeWaaeaacaWGzbWaaqqaaeaaceWGObGbauaaaiaawEa7aaGaayjkaiaawMcaaiaabccadaabbaqaaiaabccacaWGObGaaiilaiaadIfaaiaawEa7aaGaay5Eaiaaw2haaaaa@4A60@ (13.14)

Ezekután az EM-algoritmus az alábbi két lépést ismétli, amíg a konvergencia be nem következik:

E-lépés: várhatóérték-képzés (expectation). Meghatározzuk a Q(h|h)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyuamaabmaabaGabmiAayaafaWaaqqaaeaacaWGObaacaGLhWoaaiaawIcacaGLPaaaaaa@3B42@ függvényt a jelenlegi h hipotézis ( θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ paramétervektor) és a megfigyelt X adathalmaz alapján, az Y felett nyert valószínűségi eloszlás várható értékét képezve:

Q(h|h)E{P(Y|h) | h,X}MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyuamaabmaabaGabmiAayaafaWaaqqaaeaacaWGObaacaGLhWoaaiaawIcacaGLPaaacqGHqgcRcaWGfbWaaiWaaeaacaWGqbWaaeWaaeaacaWGzbWaaqqaaeaaceWGObGbauaaaiaawEa7aaGaayjkaiaawMcaaiaabccadaabbaqaaiaabccacaWGObGaaiilaiaadIfaaiaawEa7aaGaay5Eaiaaw2haaaaa@4B43@ (13.15)

M-lépés: maximumkeresés (maximization). A h hipotézist javítjuk, megkeressük azt a h’-t (a paramétervektor θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGabCiUdyaafaaaaa@36B9@ új becslését), amely maximálja az E-lépés során nyert Q-t:

hargmaxh'Q(h|h)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiAaiabgcziSoaaxababaGaaeyyaiaabkhacaqGNbGaaeyBaiaabggacaqG4baaleaacaWGObGaai4jaaqabaGccaWGrbWaaeWaaeaaceWGObGbauaadaabbaqaaiaadIgaaiaawEa7aaGaayjkaiaawMcaaaaa@4585@ (13.16)

Az M-lépés után az új paramétervektorral újra meghatározzuk az Y feletti eloszlás (amely változott a paramétervektor változása miatt) várható értékét, majd újra maximáljuk a Q-t stb.

Az általános bemutatás után szemléltessük az EM-algoritmust a fent már említett, legismertebb alkalmazási példájával, a kevert eloszlások paraméterbecslésével. Tegyük fel, hogy L darab többdimenziós mintánk van X={x1, x2, …, xL}, amelyek K különböző eloszlásból származnak a következő módon. Először valamilyen valószínűséggel eldől, hogy melyik eloszlásból jön a következő minta (bár mi ezeket a valószínűségeket nem ismerjük). Azt az eseményt, hogy a k-dik eloszlásból származik a következő minta, jelölje ωk, ennek a priori bekövetkezési valószínűsége P(ωk). Ezt követően az adott, k-dik eloszlásra jellemző p(x|ωk,θk)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaabmaabaGaaCiEamaaeeaabaGaeqyYdC3aaSbaaSqaaiaadUgaaeqaaOGaaiilaiaahI7adaWgaaWcbaGaam4AaaqabaaakiaawEa7aaGaayjkaiaawMcaaaaa@4089@ valószínűségeloszlás alapján előáll az adott érték. A θkk=1,2,...,KMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdmaaBaaaleaacaWGRbaabeaakiaaysW7caWGRbGaeyypa0JaaGymaiaacYcacaaMc8UaaGOmaiaaykW7caGGSaGaaiOlaiaac6cacaGGUaGaaiilaiaadUeaaaa@44D9@ ismeretlen paramétervektorok együtt adják az összetett eloszlás θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ ismeretlen eredő paramétervektorát, amely meghatározza a minták eredő eloszlását.

Egy adott − bár ismeretlen − paramétersor (paramétervektor) esetén a kevert eloszlást a következő összefüggés írja le:

p(x|θ)=k=1Kp(x|ωk,θk) P(ωk)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaabmaabaWaaqGaaeaacaWH4baacaGLiWoacaWH4oaacaGLOaGaayzkaaGaeyypa0ZaaabCaeaacaWGWbWaaeWaaeaacaWH4bWaaqqaaeaacqaHjpWDdaWgaaWcbaGaam4AaaqabaGccaGGSaGaaCiUdmaaBaaaleaacaWGRbaabeaaaOGaay5bSdaacaGLOaGaayzkaaaaleaacaWGRbGaeyypa0JaaGymaaqaaiaadUeaa0GaeyyeIuoakiaabccacaWGqbWaaeWaaeaacqaHjpWDdaWgaaWcbaGaam4AaaqabaaakiaawIcacaGLPaaaaaa@53A9@ (13.17)

A rögzített, de ismeretlen θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ mellett a mért adathalmazunk valószínűségét a következő összefüggés, az úgynevezett likelihood függvény adja meg, ami nem más, mint az egyes értékek valószínűségeinek szorzata:

p(X|θ)=j=1Lp(xj|θ)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaabmaabaGaamiwamaaeeaabaGaaCiUdaGaay5bSdaacaGLOaGaayzkaaGaeyypa0ZaaebCaeaacaWGWbWaaeWaaeaacaWH4bWaaSbaaSqaaiaadQgaaeqaaOWaaqqaaeaacaWH4oaacaGLhWoaaiaawIcacaGLPaaaaSqaaiaadQgacqGH9aqpcaaIXaaabaGaamitaaqdcqGHpis1aaaa@49D0@ (13.18)

A θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ ismeretlen paramétervektor maximum likelihood (ML) becslése az a θ^MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGabCiUdyaajaaaaa@36BD@ becslő, amely a p(X|θ)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaabmaabaGaamiwamaaeeaabaGaaCiUdaGaay5bSdaacaGLOaGaayzkaaaaaa@3B9C@ -t maximálja.

θ^=argmaxθp(X|θ)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGabCiUdyaajaGaeyypa0ZaaCbeaeaacaqGHbGaaeOCaiaabEgacaqGTbGaaeyyaiaabIhaaSqaaiaahI7aaeqaaOGaaGjbVlaadchadaqadaqaaiaadIfadaabbaqaaiaahI7aaiaawEa7aaGaayjkaiaawMcaaaaa@469C@ (13.19)

Ez az összefüggés azt fejezi ki, hogy a ténylegesen mért adatsor a különböző θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ -k esetén különböző valószínűségű, és érthető módon azt a θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ -t választjuk ezek közül, amely mellett a mért adatsor a legvalószínűbb. Tegyük fel, hogy p(X|θ)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaabmaabaGaamiwamaaeeaabaGaaCiUdaGaay5bSdaacaGLOaGaayzkaaaaaa@3B9C@ differenciálható θMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaCiUdaaa@36AD@ szerint, jelöljük a likelihood logaritmusát