EM-ALGORITMUS HIÁNYOS ADATRENDSZEREKRE


1 Süvítenek napjank, a forró sortüzek valamt mnden nap elmulasztunk. Robotolunk lélekszakadva, jóttevőn, s valam...
Author:  Nándor Fekete

0 downloads 1 Views 236KB Size

Recommend Documents


No documents


“S¨ uv´ıtenek napjaink, a forr´ o sort¨ uzek – valamit minden nap elmulasztunk. Robotolunk l´elekszakadva, j´ ottev˝ on, – s valamit minden tettben elmulasztunk...” (V´ aci Mih´ aly: Valami nincs sehol)

´ EM-ALGORITMUS HIANYOS ADATRENDSZEREKRE 1976. december 8-´ an Londonban, a Kir´ alyi Statisztikai T´arsas´ag u ¨l´es´en ´erdekes el˝oad´as hangzott el. Egy olyan algoritmust ismertettek, amelyet k¨ ul¨onb¨oz˝o form´akban a param´eterek maximum likelihood becsl´es´ere m´ ar r´eg´ ota haszn´altak, azonban ilyen ´altal´anos form´aban m´eg soha nem fogalmazt´ak meg. Az algoritmus eredeti le´ır´asa konvergenciabizony´ıt´assal ´es p´eld´akkal [1]-ben tal´alhat´o. Az u ´n. EM-algoritmus c´elja az, hogy becsl´est adjon a h´att´ereloszl´as valamely θ param´eter´ere hi´anyos adatokb´ ol. A param´eter maximum likelihood becsl´ese m´eg teljes adatrendszerb˝ol is bonyolult, sokszor nem is adhat´ o explicit megold´as. Gyakran hi´anyos is az adatrendszer. Az ismertetend˝o algoritmus kihaszn´ alva ezt a k¨or¨ ulm´enyt, megpr´ob´alja rekonstru´alni a hi´anyz´ o adatokat, mik¨ ozben a param´eterre is egyre jobb becsl´est ad. Ez a k´etf´ele t¨orekv´es egy iter´aci´ o k¨ovetkez˝o k´et alapl´ep´es´eben val´ osul meg: 1. E-l´ep´es: a param´eter kor´ abbi becsl´ese alapj´an rekonstru´aljuk a hi´anyz´o adatokat felt´eteles v´arhat´ o ´ert´ek k´epz´essel (E: “Expectation”); 2. M-l´ep´es: az ilyen m´ odon kieg´esz´ıtett teljes adatrendszerb˝ol meghat´arozzuk a likelihood-fv. maximumhely´et θ-ban (M: “Maximization”). A param´eter ´ıgy nyert k¨ ozel´ıt´es´evel u ´jra kezdj¨ uk az E-l´ep´est. T´ag felt´etelek mellett Dempster, Laird ´es Rubin [1] bebizony´ıtott´ak az algoritmus konvergenci´aj´at. Az algoritmus nem csup´an akkor alkalmazhat´ o, amikor bizonyos v´altoz´ok m´er´esei nem ´allnak rendelkez´es¨ unkre, hanem cenzor´ at adatok vagy kever´ekfelbont´as eset´en is. M´eg ´altal´anosabban, az adatrendszert u ´gy is tekinthetj¨ uk hi´ anyosnak, hogy l´atens v´altoz´ok vagy egy rejtett modell h´ uz´odik meg m¨og¨otte (pl. Baum–Welch algoritmus rejtett Markov-modellekre). Ilyenkor a modell param´etereinek becsl´ese a feladat. N´eha csup´an technikai okokb´ol eg´esz´ıtj¨ uk ki adatrendszer¨ unket, mert a kieg´esz´ıtettben k¨ onnyebben v´egre tudjuk hajtani az ML-becsl´est (l. a k¨ovetkez˝o p´elda). T´etelek viszont garant´alj´ak, hogy az iter´aci´o az eredeti (hi´anyos) likelihoodot maximaliz´alja. A hivatkozott cikk jel¨ ol´eseivel: legyen X a teljes, Y pedig a hi´anyos mintat´er, amelyek k¨oz¨ott teh´at l´etezik egy X → Y, x → y(x) megfeleltet´es. Jel¨ olje f (x|θ) ill. g(y|θ) a megfelel˝o eloszl´asok egy¨ uttes s˝ ur˝ us´eg- ill. vsz.ugg (itt f¨ uggv´eny´et, azaz a likelihood-f¨ uggv´enyt, amely a θ ak´ar t¨obbdimenzi´os param´etert˝ol f¨

az abszol´ ut folytonos esetet tekintj¨ uk). K¨oz¨ott¨ uk a Z g(y|θ) = f (x|θ) dx

(1)

X (y)

R P o¨sszef¨ ugg´es k¨ ozvet´ıt (diszkr´et eloszl´ asokn´al az helyett ´ertend˝o), ahol X (y) = {x : y(x) = y}. C´elunk a g(y|θ) hi´ anyos likelihood f¨ uggv´eny maximaliz´al´asa θ-ban az y megfigyel´es alapj´an.

Egy konkr´ et p´ elda Tekints¨ unk egy genetikai p´eld´ at (l. Rao [5], 5.5.g. fejezet)! (AB | ab) genot´ıpus´ u h´ımek ´es ugyanilyen genot´ıpus´ u n˝ ost´enyek keresztez´es´eb˝ol sz´armaz´o 197 ut´od fenot´ıpusa n´egyf´ele lehet: AB, Ab, aB ´es ab. A modell szerint az ut´odok polinomi´alis eloszl´as szerint tartoznak a n´egy fenot´ıpus valamelyik´ehez, az oszt´ alyok val´osz´ın˝ us´egei rendre: 21 + 14 π, 14 − 41 π, 14 − 14 π ´es 14 π; itt π a modell param´etere (Rao p´eld´ aj´ aban π = (1 − θ)2 , ahol θ az u ´n. rekombin´aci´os h´anyados). A megfigyelt (hi´ anyos) adatok: y = (y1 , y2 , y3 , y4 ) = (125, 18, 20, 34). Itt y tulajdonk´eppen egy 4 alternat´ıv´ aj´ u indik´atorv´altoz´o ¨osszegstatisztik´aja, mely polinomi´alis eloszl´ast k¨ovet. A likelihood f¨ uggv´eny teh´at g(y|π) =

(y1 + y2 + y3 + y4 )! 1 1 y1 1 1 y2 1 1 y3 1 y4 ( + π) ( − π) ( − π) ( π) . y1 !y2 !y3 !y4 ! 2 4 4 4 4 4 4

A feladat g maximaliz´ asa π-ben. Ec´elb´ol egy olyan algebrai egyenletet kell megoldani, aminek sz´amos gy¨oke van, k¨ oz¨ ul¨ uk csak kett˝ ot lehet explicit m´odon megadni. A feladat term´eszetesen numerikusan viszonylag egyszer˝ uen megoldhat´o, az al´abbiakban ismertetett elj´ar´as az EM algoritmus egy j´ ol k¨ ovethet˝ o illusztr´ aci´ oja. A fenti adatrendszert technikai okokb´ol hi´anyosnak tekintj¨ uk, amely a val´odi, 5 csoportb´ ol ´all´o adatrendszerb˝ ol u ´gy keletkezett, hogy az els˝o 2 csoport ¨osszevon´odott. A teljes adatrendszer teh´at: x = (x1 , x2 , x3 , x4 , x5 ),

ahol y1 = x1 + x2 ,

y2 = x3 ,

y3 = x4 ,

y4 = x5 .

x nem m´as, mint egy 5 alternat´ıv´ aj´ u indik´atorv´altoz´o ¨osszegstatisztik´aja, melyre fel´ırt polinomi´alis likelihood: f (x|π) = ahol

(x1 + x2 + x3 + x4 + x5 )! x1 x2 x3 x4 x5 p1 p2 p3 p4 p5 , x1 !x2 !x3 !x4 !x5 !

1 1 1 1 p1 = , p2 = π, p3 = p4 = − π, 2 4 4 4 A fenti integr´ alnak diszkr´etben megfelel˝o o¨sszeg: X g(y|π) =

1 p5 = π. 4

x1 +x2 =y1 , x1 ≥0, x2 ≥0 eg´ esz, x3 =y2 , x4 =y3 , x5 =y4

f (x|π).

Ezut´an kezd˝ odj´ek az iter´ aci´ o valamely π (0) kezd˝o´ert´ekkel! Tegy¨ uk fel, hogy az m-edik l´ep´es (m) ut´an m´ar megvan a π k¨ ozel´ıt´es. Az m + 1-edik l´ep´es a k¨ovetkez˝o k´et l´ep´eseb˝ol fog ´allni: 1. E-l´ep´es: az y megfigyel´es alapj´ an rekonstru´aljuk az x adatrendszert azaz meghat´arozzuk x1 ´es x2 – y1 = 125 ´es π = π (m) melletti – felt´eteles v´arhat´o ´ert´ekeit. Mivel x1, illetve x2 a fenti felt´elek mellett – x3 , x4 ´es x5 ´ert´ek´et˝ol f¨ uggetlen¨ ul – Bin125  (m)  Bin125 1 +π1 π(m) eloszl´ as´ u, ez´ert 2

1 2 1 (m) 1 +4π 2

illetve

4

(m)

x1

= 125 ·

1 2

+

1 2 1 (m) 4π

(m)

´es x2 (m)

= 125 ·

1 (m) 4π 1 1 (m) . 2 + 4π

(m)

2. M-l´ep´es: az ilyen m´ odon kieg´esz´ıtett (x1 , x2 , 18, 20, 34) teljes adatrendszerb˝ ol meghat´ arozzuk π maximum likelihood becsl´es´et, ´es ezt π (m+1) -gyel jel¨olj¨ uk. Ec´elb´ol vonjuk ¨ossze maximaliz´ aland´ o f (x|π) likelihood f¨ uggv´eny π (m) -t˝ol nem f¨ ugg˝o t´enyez˝oit egyetlen konstansba:  x(m)  +34  2 1 1 1 18+20 f (x|π) = const · π − π . · 4 4 4 (m)

Ezt a kifejez´est 4x2 alakot ¨ olti:

+34+18+20 -nal

megszorozva a a maximaliz´aland´o f¨ uggv´eny az al´abbi (m)

f˜(x|π) = const · (π)x2

+34

· (1 − π)18+20 ,

ami a Bernoulli eloszl´ as likelihood f¨ uggv´enye, teh´at a maximum´at a (m)

π

(m+1)

=

x2 (m) x2

+ 34

+ 34 + 18 + 20

´ert´eken veszi fel. Ezzel a π (m+1) ´ert´ekkel visszat´er¨ unk az E-l´ep´eshez. Az iter´aci´ot π (0) = 0.5-el ind´ıtva 2-3 l´ep´es ut´an π ´ert´eke 0.6 k¨ or¨ ul stabiliz´ al´ odott.

Elm´ eleti megfontol´ asok Legyen statisztikai mez˝ onk domin´ alt, param´eteres, identifik´alhat´o ´es regul´aris (a Cramer–Rao egyenl˝otlens´egn´el tanult bederiv´ alhat´ os´agi felt´etelek teljes¨ ulnek). Tegy¨ uk fel, hogy mint´ank exponenci´alis eloszl´ ascsal´ adb´ ol sz´ armazik, ahol term´eszetes param´eterez´est v´alasztunk, azaz a s˝ ur˝ us´eg/s´ uly-f¨ uggv´eny Pk f (x|θ) = c(θ) · e j=1 θj tj (x) · h(x) alak´ u, ahol a θ = (θ1 , . . . , θk ) term´eszetes param´etert˝ol val´o f¨ ugg´est felt´etelk´ent jel¨olj¨ uk (nem ok n´elk¨ ul, ui. a Bayes m´ odszer´ehez hasonl´o meggondol´asokat haszn´alunk). Tudjuk, hogy egy

P P X = (X1 , . . . , Xn ) n-elem˝ u minta eset´en t(X) = ( ni=1 t1 (Xi ), . . . , ni=1 tk (Xi )) el´egs´eges, s˝ot – amennyiben a k-dimenzi´ os param´etert´er konvex ´es tartalmaz k-dimenzi´os t´egl´at – teljes is, ´ıgy minim´alis el´egs´eges statisztika, ami ekvivalencia erej´eig egy´ertelm˝ u. Teh´at a realiz´altakkal fel´ırt likelihood-f¨ uggv´eny a k¨ ovetkez˝ o alak´ u: Pk

n

f (x|θ) = c (θ) · e

j=1 θj

Pn

i=1 tj (xi )

·

n Y

h(xi ) =

i=1

ahol a vektorok sorvektorok,

T

1 T · eθ·t (x) · b(x), a(θ)

a transzpon´al´ast jel¨oli ´es Z T eθ·t (x) · b(x) dx. a(θ) =

(2)

X

Jelen esetben az iter´ aci´ o v´egigk¨ ovethet˝o a t minim´alis el´egs´eges statisztik´an kereszt¨ ul a k¨ovetkez˝ok´eppen. Miut´ an Y (a megfigyelt hi´anyos adatrendszer) az X (a posztul´alt teljes adatrendszer) f¨ uggv´enye, X felt´eteles s˝ ur˝ us´ege x-ben az Y = y felt´etel mellett (1) figyelembev´etel´evel f (x|θ) 1 T k(x|y, θ) = = · eθ·t (x) · b(x), (3) g(y|θ) a(θ|y) ahol

Z

T (x)

eθ·t

a(θ|y) =

· b(x) dx.

(4)

X (y)

Azaz a felt´etel n´elk¨ uli ´es a felt´eteles likelihood ugyanazzal a term´eszetes param´eterrel ´es el´egs´eges statisztik´aval ´ırhat´ o fel, a k¨ ul¨ onbs´eg csak az, hogy k¨ ul¨onb¨oz˝o tereken – X -en ill. X (y)-on – vannak ´ertelmezve, ami a (2) ill. (4)-beli s´ ulyf¨ uggv´enyeken is l´atszik. C´elunk az L(θ) := ln g(y|θ) log-likelihood f¨ uggv´eny maximaliz´al´asa θ-ban adott y mellett. (3) miatt L(θ) = − ln a(θ) + ln a(θ|y). (5) A bederiv´alhat´ os´ agi felt´etelek miatt

Hasonl´oan

∂ 1 ln a(θ) = ∂θ a(θ)

Z

∂ 1 ln a(θ|y) = ∂θ a(θ|y)

Z

T (x)

t(x) · eθ·t

· b(x) dx = E(t|θ).

(6)

X

T (x)

t(x) · eθ·t

· b(x) dx = E(t|y, θ).

X (y)

(Ez csak t¨om¨ or jel¨ ol´es: A vektor szerinti deriv´al´as eredmenye a komponensek szerinti parci´alis deriv´altakb´ol ´ all´ o vektor.) Ezek seg´ıts´eg´evel (5) deriv´altja ∂ L(θ) = −E(t|θ) + E(t|y, θ) ∂θ alak´ u, aminek z´erushely´et keress¨ uk. N´ezz¨ uk most a k¨ ovetkez˝ o iter´ aci´ ot, melyben m´ar eljutottunk θ m-edik becsl´es´eig.

(7)

1. E-l´ep´es: a param´eter θ(m) ´ert´eke alapj´an becs¨ ulj¨ uk a teljes adatrendszer t el´egs´eges statisztik´ aj´ at a hi´ anyos adatrendszerb˝ol t(m) := E(t|y, θ(m) )

(8)

a felt´eteles eloszl´ as alapj´ an (a p´eld´aban ezek a binomi´alis eloszl´as´ u v´altoz´ok becsl´esei); 2. M-l´ep´es: meghat´ arozzuk θ(m+1) -et, mint a teljes minta likelihood-egyenlet´enek megold´ as´ at, azaz ∂ ln f (x|θ) = 0. ∂θ Haszn´ alva az exponenci´ alis eloszl´ascsal´ad speci´alis alakj´at, ez nem m´as, mint a −

∂ ln a(θ) + t(m) (x) = 0 ∂θ

(9)

egyenlet, azaz (6) figyelembev´etel´evel az E(t|θ) = t(m)

(10)

egyenlet megold´ asa lesz θ(m+1) . Amennyiben az iter´ aci´ o θ∗ -hoz konverg´al, el´eg nagy m-re θ(m) = θ(m+1) = θ∗ , ´ıgy (8) ´es (10) alapj´an E(t|θ∗ ) = E(t|y, θ∗ ) teljes¨ ul, azaz (7) z´erushely´et kapjuk. Most m´eg ´ altal´ anosabban bel´ atjuk, hogy az iter´aci´o konverg´al. Az ´altal´anoss´ag egyr´eszt azt jelenti, hogy nem csup´ an exponenci´alis eloszl´ascsal´adra szor´ıtkozunk, m´asr´eszt az M-l´ep´es sem felt´etlen¨ ul a teljes likelihood maximaliz´al´as´at jelenti, csak a c´elf¨ uggv´eny n¨ovel´es´et. Mivel inform´aci´oelm´eleti fogalmakat haszn´ alunk, a term´eszetes alap´ u logaritmus helyett 2 alap´ ut haszn´alunk ´es log-gal jel¨ olj¨ uk. Ez nem jelenti az ´altal´anoss´ag megszor´ıt´as´at, hiszen a hi´anyos likelihhoodnak a θ argumentumban val´o maximaliz´al´asa arg max szempontj´ab´ol ekvivalens a likelihood f¨ uggv´eny b´ armely 1-n´el nagyobb alap´ u logaritmus´anak a maximaliz´al´as´aval. ´Igy a tov´abbiakban L(θ) = log g(y|θ) lesz a maximaliz´aland´o log-likelihood f¨ uggv´eny. Tetsz˝oleges θ, θ0 p´ arra vezess¨ uk be a 0

0

Z

Q(θ|θ ) = E(log f (x|θ)|y, θ ) =

log f (x|θ)k(x|y, θ0 ) dx

(11)

X (y)

f¨ uggv´enyt. Ezzel az iter´ aci´ o θ(m) → θ(m+1) f´azisa: 1. E-l´ep´es: kisz´ amoljuk a Q(θ|θ(m) ) f¨ uggv´enyt a (11)-beli felt´eteles v´arhat´o ´ert´ek k´epz´essel (exponenci´ alis eloszl´ ascsal´ adn´ al el´eg volt az el´egs´eges statisztika felt´eteles v´arhat´o ´ert´ek´et venni);

2. M-l´ep´es: maximaliz´ aljuk a Q(θ|θ(m) ) f¨ uggv´enyt θ-ban. Legyen θ(m+1) := arg max Q(θ|θ(m) ) ´es tegy¨ uk fel, hogy θ(m+1) ∈ Θ. megold´ as´ at jelenti.

Exponenci´alis eloszl´ascsal´adn´al ez a (9) egyenlet

Most bel´ atjuk, hogy az algoritmus k¨ovetkez˝o relax´aci´oja is konverg´al: az M-l´ep´esben (m) Q(θ|θ )-et nem felt´etlen¨ uk ´ert´ek´et az el˝oz˝ o ul maximaliz´aljuk θ-ban, hanem csak n¨ovelj¨ iter´aci´obelihez k´epest. Azaz θ(m+1) olyan, hogy Q(θ(m+1) |θ(m) ) ≥ Q(θ(m) |θ(m) ).

(12)

Vezess¨ uk be a 0

0

Z

log k(x|y, θ)k(x|y, θ0 ) dx

H(θ|θ ) = E(log k(x|y, θ)|y, θ ) =

(13)

X (y)

jel¨ol´est. Lemma. H(θ|θ0 ) ≤ H(θ0 |θ0 ) ´es egyenl˝os´eg pontosan akkor ´ all fenn, ha k(x|y, θ) = k(x|y, θ0 ) majdnem biztosan. (Megjegyezz¨ uk, hogy H(θ|θ) a k(x|y, θ) eloszl´as entr´opi´aja.) Bizony´ıt´ as. Alkalmazzuk a Jensen-egyenl˝otlens´eget, melynek ´ertelm´eben tetsz˝oleges h konvex f¨ uggv´enyre ´es els˝ o momentummal rendelkez˝o ξ val´ us´egi v´altoz´ora E(h(ξ)) ≥ h(E(ξ)). Rosz´ın˝ Emiatt az f eloszl´ as relat´ıv entr´ opi´ aja a g eloszl´asra f log fg ≥ 0, ui. alkalmazzuk a Jensenegyenl˝otlens´eget a h(x) = − log(x) konvex f¨ uggv´enyre ´es az f eloszl´as szerinti v´arhat´o ´ert´ekre: Z Z f g g g f log = E(− log ) ≥ − log(E( )) = − log f = − log 1 = 0. (14) g f f f Mivel 0

0

0

Z

H(θ |θ ) − H(θ|θ ) =

log X (y)

k(x|y, θ0 ) k(x|y, θ0 ) dx, k(x|y, θ)

nem m´as, mint a k(x|y, θ0 ) eloszl´ as relat´ıv entr´opi´aja a k(x|y, θ) eloszl´asra n´ezve, ´ıgy a lemma ´ertelm´eben nem-negat´ıv. Az integr´ al pontosan akkor 0, ha a nem-negat´ıv integrandus majdnem biztosan 0, azaz a logaritm´ aland´ o h´ anyados majdnem biztosan 1. Defin´ıci´ o. A θ(m+1) = M (θ(m) ) iter´ aci´o ´ altal´ anos´ıtott EM-algotitmust (GEM) defini´al, ha Q(M (θ)|θ) ≥ Q(θ|θ),

∀θ ∈ Θ.

Teh´at (12) fenn´ all´ asakor GEM algoritmusunk van. T´etel. Tetsz˝ oleges GEM algoritmusra L(M (θ)) ≥ L(θ),

∀θ ∈ Θ,

ahol egyenl˝os´eg pontosan akkor ´ all fenn, ha k(x|y, M (θ)) = k(x|y, θ) ´es Q(M (θ)|θ) = Q(θ|θ) majdnem biztosan teljes¨ ulnek. Bizony´ıt´ as. El˝ osz¨ or is Q(θ|θ0 )−H(θ|θ0 ) = E(log(f (x|θ)−log(k(x|y, θ)|y, θ0 ) = E(log(g(y|θ))|y, θ0 ) = log(g(y|θ)) = L(θ), mivel log(g(y|θ)) m´erhet˝ o y-ra. Ezut´ an L(M (θ)) − L(θ) = [Q(M (θ)|θ) − Q(θ|θ)] + [H(θ|θ) − H(M (θ)|θ)] ≥ 0, mivel az els˝ o []-ben ´ all´ o mennyis´eg nem-negat´ıv a GEM defin´ıci´oja miatt, a m´asodikban ´all´ o pedig a lemma miatt. Ha a likelihood-f¨ uggv´eny korl´ atos, akkor a GEM – mivel minden iter´aci´os l´ep´esben n¨oveli (nem cs¨okkenti) a likelihood-f¨ uggv´eny ´ert´ek´et – konverg´al, ´es exponenci´alis eloszl´ascsal´adn´ al l´attuk, hogy a fixpont a likelihood-egyenlet megold´as´at adja. A likelihood-f¨ uggv´enyre tett tov´abbi folytonoss´ agi ´es differenci´ alhat´os´agi felt´etelek, tov´abb´a a param´etert´er konvexit´asa eset´en bel´athat´ o, hogy az iter´ aci´ o a likelihood-f¨ uggv´eny egy lok´alis maximumhely´ehez konverg´ al Θ-ban, ami egy´ertelm˝ us´eg eset´en glob´ alis maximumhely is. [1] cikkben mondj´ak ki ehhez a pontos felt´eteleket. Ha ilyen felt´etelek nincsenek, [4]-ben p´eld´akat mutatnak egy´eb eshet˝os´egekre (pl. nyeregpont). [6]-ban Csisz´ ar Imre bebizony´ıtja, hogy az EM-algeritmus nem m´as, mint egy altern´alva minimaliz´al´o elj´ ar´ as az I-divergenci´ ara. A P ´es Q eloszl´asok I-divergenci´ aja a (14)-beli relat´ıv entr´opia azzal a k¨ ul¨ onbs´eggel, hogy itt a k´et eloszl´as ugyanazon a v´eges tart´on ´ertelmezett diszkr´et eloszl´ as: X P(a) D(P|Q) = P(a) log . Q(a) a Az I-divergencia nem szimmetrikus az argumantumaiban, viszont az euklideszi t´avols´aghoz hasonl´o tulajdons´ agai vannak. Ezeken alapul az az ´all´ıt´as, hogy az EM-algoritmus sor´an D(P1 |Q0 ) ≥ D(P1 |Q1 ) ≥ D(P2 |Q1 ) ≥ D(P2 |Q2 ) ≥ . . . , ahol a Q0 felvett kezdeti eloszl´ asb´ ol kiindulva Q1 , Q2 , . . . rekonstru´alja a teljes minta ismeretlen eloszl´as´at, m´ıg Pm = EQm−1 (x|y) a teljes minta hi´anyosra vett felt´eteles v´arhat´o ´ert´eke, amennyiben a teljes minta eloszl´ asa Qm−1 . A [6] jegyzetben bebizony´ıtj´ak, hogy a fenti elj´ar´as konverg´al az ismeretlen val´ odi Q eloszl´ ashoz, mivel a nem-negat´ıv I-divergencia minden l´ep´esben cs¨okken (nem n¨ ovekszik). (Itt most ´ altal´anosabban, nem a param´etert becslik, hanem mag´at az ismeretlen eloszl´ ast, azaz az EM algoritmus nem-param´eteres verzi´oj´at kapjuk.)

Adatb´ any´ aszati alkalmaz´ asok Gyakori feladat a t¨ obbdimenzi´ os norm´alis eloszl´as param´etereinek becsl´ese hi´anyos adatokb´ ol. Pl. adatrendszer¨ unk p´ acienseken m´ert folytonos v´altoz´ok ´ert´ekeit tartalmazza (pl. testmagass´ag, tests´ uly, v´ernyom´ as), de bizonyos p´ aciensek bizonyos m´ert ´ert´ekei hi´anyoznak (nem vett´ek fel vagy elvesztek).

1. E-l´ep´es: a param´eter valamely θ(m) ´ert´eke alapj´an becs¨ ulj¨ uk a hi´anyz´o adatokat felt´eteles v´arhat´ o ´ert´ek k´epz´essel. 2. M-l´ep´es: az ´ıgy kieg´esz´ıtett teljes adatrendszerben a j´ol ismert m´odon maximum likelihood becsl´est hajtunk v´egre a param´eterekre (minta´atlag ill. empirikus kovarianciam´atrix). Azonban nem felt´etlen¨ ul a m´er´esek hi´anyosak, lehet, hogy valamit meg sem n´ezt¨ unk, pl. efelejtett¨ uk, hogy a p´ aciensek mely betegcsoportb´ol val´ok, vagy ´eppens´eggel most szeretn´enk u ´j diagnosztiaki csoportokat defini´ alni (a l´atens v´altoz´o v´eges ´ert´ekk´eszlet˝ u). Adatb´any´ aszatban nagy mint´ akn´ al el˝ofordul, hogy a mintaelemek b´ar f¨ uggetlenek, nem azonos eloszl´ as´ uak. Ilyenkor gyakran feltessz¨ uk, hogy nem homog´en mint´ank k¨ ul¨onb¨oz˝ o (param´eter˝ u, de azonos t´ıpus´ u) eloszl´ asok kever´eke, azaz a s˝ ur˝ us´eg/val´osz´ın˝ us´eg-f¨ uggv´eny v´eges sok k¨ ul¨onb¨oz˝ o param´eter˝ u s˝ ur˝ us´eg/val´ osz´ın˝ us´eg-f¨ uggv´eny szuperpozici´oja.

EM-algoritmus norm´ alis eloszl´ asok kever´ ekfelbont´ as´ ara Gyakran folytonos sokas´ agb´ ol sz´ armaz´o mint´ank empirikus s˝ ur˝ us´eghisztogramja t¨obb kiugr´ o cs´ uccsal rendelkezik; u ´gy n´ez ki, mint Gauss-g¨orb´ek szuperpozici´oja. (Pl. foly´ok v´ızszintj´enek tet˝oz´esi ´ert´ekei megfelelhetnek a tavaszi ´es ny´ar eleji ´arhull´amnak; vagy a forgalomban lev˝ o r´eszv´enymennyis´eg a t˝ oszd´en nyit´ as ut´ an ´es z´ar´as el˝ott mutat egy-egy cs´ ucsot, ezeket szeretn´enk sok nap 8-9 ´ or´ as adatai alapj´ an sz´ atv´ alasztani.) Ilyenkor keress¨ uk a komponensek param´etreit ´es ar´any´at. Az EM-algoritmus szeml´eltet´es´eu ¨l egy [2]-beli p´eld´at ismertetek k´et komponens sz´etv´alaszt´as´ ara. H´att´ereloszl´ asunk v´ altoz´ oj´ at jel¨ olje Y , amely az Y1 ´es Y2 Gauss-eloszl´as˝ u v´altoz´ok kever´eke, ahol a kever´esi ar´ anyt a ∆ Bernoulli-eloszl´as´ u h´att´erv´altoz´o jel¨oli. Amennyiben ∆ a 0 ´ert´eket veszi fel, az els˝ o (Y1 ´ altal k´epviselt), amennyiben az 1 ´ert´eket veszi fel, a m´asodik (Y2 ´altal k´epviselt) Gauss-eloszl´ as van ´erv´enyben. Teh´at modell¨ unk a k¨ovetkez˝o: Y = (1 − ∆)Y1 + ∆Y2 , ahol a modell param´eterei: (µj , σj2 ) az j-edik Gauss-eloszl´as param´eterei (j = 1, 2) ´es π a l´atens Bernoulli-v´altoz´ o param´etere (∆ az 1 ert´eket π val´osz´ın˝ us´eggel veszi fel, a 0 ert´eket pedig 1 − π val´osz´ın˝ us´eggel). Azaz θ = (µ1 , σ12 , µ2 , σ22 , π). Y s˝ ur˝ us´egf¨ uggv´enye teh´ at g(y|θ) = (1 − π)f1 (y) + πf2 (y), ahol fj a (µj , σj2 ) param´eter˝ u Gauss-s˝ ur˝ us´eg. Amennyiben n-elem˝ u f¨ uggetlen mint´ank realiz´altja az y1 , . . . , yn m´ert ´ert´ekekb˝ ol ´ all, a likelihood-f¨ uggv´eny g(y|θ) =

n Y i=1

g(yi |θ) =

n Y i=1

[(1 − π)f1 (yi ) + πf2 (yi )]

alak´ u, melyet vagy melynek logaritmus´at maximaliz´alni θ-ban bonyolult feladat. Ez´ert a ¨ k¨ovetkez˝o iter´ aci´ ot hajtjuk v´egre. (Osszhangban az elm´eleti meggondol´asokkal, itt is g a hi´anyos minta likelihoodja. A teljes minta likelihoodja a k´et csoport k´etf´ele likelihoodj´anak a szorzata lenne, de ezt nem tudjuk fel´ırni, mert nem ismerj¨ uk az egyes mintaelemek csoportbatartoz´as´at.) 0. Inicializ´ al´ as. A param´eterekhez kezd˝o´ert´eket rendel¨ unk: (0)

θ(0) = (µ1 , σ12

(0)

(0)

, µ2 , σ22

(0)

, π (0) ).

(Pl. π (0) lehet 1/2, a k´et v´ arhat´ o ´ert´ek lehet k´et sz´els˝os´eges ´ert´ek, a sz´or´asok mindegyike pedig az empirikus.) Teh´ at m := 0 ´es tegy¨ uk fel, hogy m´ar eljutottunk a θ(m) = (m) (m) (m) (m) (µ1 , σ12 , µ2 , σ22 , π (m) ) iter´ altig. A k¨ovetkez˝o l´ep´esben E-M bels˝o ciklus j¨on: 1. E-l´ep´es: kisz´ amoljuk az egyes mintaelemek “r´eszar´any´at” a k´etf´ele eloszl´asban, azaz az E(∆ | Y = yi ) felt´eteles v´ arhat´ o ´ert´eket, ami ∆ Bernoulli-eloszl´asa miatt a P(∆ = 1 | Y = yi ) (m+1) felt´eteles val´ osz´ın˝ us´eggel egyezik meg ´es πi -el jel¨olj¨ uk (i = 1, . . . , n). Mindezt a hi´anyos adatrendszer ´es a param´eter kezdeti eloszl´asa alapj´an tessz¨ uk a Bayes-t´etel seg´ıts´eg´evel: (m)

(m+1)

πi (m)

ahol fj

π (m) f2

= (1 −

(m) π (m) )f1 (yi )

(yi ) (m)

+ π (m) f2

(i = 1, . . . , n), (yi )

jel¨ oli a θ(m) param´eter alapj´ an sz´amolt j-edik Gauss-s˝ ur˝ us´eget (j = 1, 2).

2. M-l´ep´es: k¨ ul¨ on-k¨ ul¨ on maximaliz´aljuk a teljes mint´at jelent˝o k´etf´ele Gauss likelihoodot, aminek megold´ asa j´ ol ismert, csak itt a mintaelemeket r´eszesed´es¨ uk ar´any´aban sz´am´ıtjuk be a k´etf´ele becsl´esbe: Pn Pn (m+1) (m+1) 2 (m+1) )(yi − µ1 ) )yi (m+1) 2 (m+1) i=1 (1 − πi i=1 (1 − πi , σ1 = (i = 1, . . . , n), µ1 = P Pn (m+1) (m+1) n ) ) i=1 (1 − πi i=1 (1 − πi illetve (m+1) µ2

(m+1) yi i=1 πi , Pn (m+1) i=1 πi

Pn =

(m+1) σ22

(m+1) (m+1) 2 (yi − µ2 ) i=1 πi Pn (m+1) i=1 πi

Pn =

(i = 1, . . . , n).

A fenti E-M l´ep´es egy iter´ aci´ os l´ep´est jelentett. Ezut´an legyen n

π (m+1) :=

1 X (m+1) πi n i=1

a Bernoulli-param´eter els˝ o iter´ aci´ os becsl´ese a minta´atlag´aval, m := m + 1 ´es ism´etelj¨ uk meg a fenti 1. ´es 2. l´ep´est. El´eg sokszor ism´etelve az elj´ar´asbeli θ(m) sorozat (m = 1, 2, . . . ) konverg´alni fog, hacsak valami rossz ind´ıt´as miatt nem ragad le r¨ogt¨on az elej´en (pl. a k´et norm´alis param´eterei megegyeznek ´es 1/2–1/2 es´ellyel v´alasztjuk ˝oket). K¨onny˝ u elk´epzelni, hogyan bonthatn´ ank fel mint´ ankat kett˝on´el t¨obb, de adott sz´am´ u norm´alis eloszl´as kever´ek´ere (´altal´aban annyira, ah´ any “p´ up´ u” az empirikus s˝ ur˝ us´eghisztogram).

EM-algoritmus polinomi´ alis eloszl´ asok kever´ ekfelbont´ as´ ara Megfigyel´eseink itt k´et v´eges halmaz elemp´arjaira vonatkoznak. Kis m´odos´ıt´assal a [3]-beli algoritmust ismertetem, melyet ott l´ atens oszt´alyoz´asi modellnek vagy egy¨ uttes filterez´esnek neveznek. A hi´ anyos mintat´er X × Y , ahol X = {x1 , . . . , xn }, Y = {y1 , . . . , ym } ´es az xi , yj p´arokra egy¨ uttes megfigyel´eseink vannak egy n × m-es kontingenciat´abla form´aj´aban, melynek elemei ν(xi , yj ), ezek nem-negat´ıv (nem felt´etlen¨ ul, de ´altal´aban) eg´esz sz´amok. Pl. szemsz´ın – hajsz´ın eset´en ν(xi , yj ) az xi -vel k´ odolt szem- ´es yj -vel k´odolt hajsz´ın˝ u emberek gyakoris´aga a mint´aban; mozibaj´ ar´ ok – mozifilmek eset´en ν(xi , yj ) azt jel¨oli, hogy xi n´ez˝o h´anyszor l´atta az yj filmet (gyakran 0 vagy 1); internetes adatokn´al kulcssz´o – dokumentum, felhaszn´al´o – dokumentum; banki adatokn´ al banki rendszerbe val´o fizikai bel´ep´es id.-je – accountra val´o bel´ep´es id.-je; p´enzforgalmi adatokn´ al lehets´eges ´atutal´ok – lehets´eges kedvezm´enyezettek. Ut´obbi esetben ν(xi , yj ) jel¨ oli az xi ´ altal yj -nek ´ atutalt ¨osszeg nagys´ag´at (pl. ezer Ft-ban) vagy az xi → yj tranzakci´o gyakoris´ ag´ at egy adott id˝ oszakban. Itt X = Y a bank ¨osszes u ¨gyfele, de a kontingenciat´abla ´ altal´ aban ekkor sem szimmetrikus. Teh´at a kontingenciat´ abla adott, azonban a ν(xi , yj ) sz´amok rendszer´et hi´anyos adatrendszernek tekintj¨ uk, mert nem tartalmazza a kapcsolat/tranzakci´o m¨og¨otti sz´and´ekot, melyet l´atens v´altoz´ onak tekint¨ unk. Ez egy diszkr´et h´att´erv´altoz´o a Z = {z1 , . . . , zk } ´ert´ekk´eszlettel, k r¨ogz´ıtett ´es j´ oval kisebb, mint n vagy m. A szemsz´ın – hajsz´ın p´eld´aban adatrendszer¨ unk lehet k¨ ul¨onb¨oz˝o t´ıpus´ u orsz´ agok adatainak kever´eke (pl. skandin´av, k¨oz´ep-eur´opai, mediterr´an); mozibaj´ar´ok – mozifilmek eset´en a l´ atens v´ altoz´o a filmn´ez´es ill. filmek k¨ ul¨onb¨oz˝o fajt´ait jel¨olheti: pl. m˝ uv´esz-, dokumentum-, kommersz filmek ill. ilyen filmekre orient´alt n´ez˝ok (maguk a n´ez˝ok ill. filmek sem egys´egesek, bizonyos ar´ anyban tartalmazz´ak ezeket az orient´aci´okat); a p´enzforgalmi p´eld´aban l´atens v´ altoz´ o lehet az ´ atutal´as sz´and´eka (pl. csal´adi, u ¨zleti vagy p´enzmos´as, ekkor k = 3). C´elunk az, hogy ezen sz´ and´ekok szerint szabdaljuk fel az egyes ´atutal´asokat ´es kisz˝ urj¨ uk a gyan´ us sz´ and´ekokhoz legink´ abb k¨ othet˝o xi , yj p´arokat. A [3] cikk p´eld´aj´aban filmn´ez´esi szok´asokat vizsg´ alnak. Modell¨ unk a k¨ ovetkez˝ o: p(xi , yj ) =

k X

p(xi , yj |zl ) · π(zl ) =

l=1

k X

p(xi |zl ) · p(yj |zl ) · π(zl ),

l=1

ahol a p´anzforgalmi p´ ald´ aval ´elve p(xi , yj ) jel¨oli az xi → yj ´atutal´as val´osz´ın˝ us´eg´et, π(zl ) a zl sz´and´ek a priori val´ osz´ın˝ us´eg´et, ´es feltessz¨ uk, hogy adott sz´and´ek mellett p(xi , yj |zl ) = p(xi |zl ) · p(yj |zl ), ami a k´et ir´ any´ u p´enzforgalom adott sz´and´ek melletti felt´eteles f¨ uggetlens´eg´et jelenti. A modell param´eterei a π(zl ) val´ osz´ın˝ us´egek (l = 1, . . . , k) ´es a p(xi |zl ), p(yj |zl ) felt´eteles val´osz´ın˝ us´egek (i = 1 . . . , n; j = 1, . . . , m; l = 1, . . . , k). Ezeket θ-ban fogjuk ¨ossze. C´elunk a k¨ovetkez˝o hi´ anyos likelihood maximaliz´al´asa, mely polinomi´alis eloszl´asok kever´eke: k X l=1

π(zl ) · cl

n Y m Y

p(xi , yj |zl )ν(xi ,yj |zl ) ,

i=1 j=1

ahol a felt´eteles cellaval´ osz´ın˝ us´egek (melyek a modell szerint szorzat alak´ uak) kitev˝oj´eben a cellagyakoris´ agok adott sz´ and´ek melletti ´ert´eke ´all (nem felt´etlen¨ ul eg´esz sz´amok), cl pedig csak

l-t˝ol f¨ ugg˝o konstans (polinomi´ alis egy¨ utthat´o, vagy nem eg´esz kitev˝ok eset´en Γ-f¨ uggv´enyeket tartalmaz). Becs¨ ulj¨ uk a param´ atereket az EM-algoritmus seg´ıts´eg´evel! 0. Inicializ´ al´ as. A param´eterekhez kezd˝o´ert´eket rendel¨ unk: π (0) (zl ), p(0) (xi |zl ), p(0) (yj |zl ). (t) t:=0, tegy¨ uk fel, hogy m´ ar kez¨ unkben van a θ iter´alt. 1. E-l´ep´es: kisz´ amoljuk a hi´ anyz´ o sz´and´ek felt´eteles v´arhat´o ´ert´ek´et a hi´anyos adatrendszer alapj´an. Ezt a k¨ ovetkez˝ o felt´eteles (a posteriori) val´osz´ın˝ us´egek rendszere defini´alja a Bayest´etellel: p(t) (xi , yj |zl ) · π (t) (zl )

p(t) (xi |zl ) · p(t) (yj |zl ) · π (t) (zl ) = Pk . (t) (t) (t) (t) (t) l0 =1 p (xi , yj |zl0 ) · π (zl0 ) l0 =1 p (xi |zl0 )p (yj |zl0 ) · π (zl0 )

p(t+1) (zl |xi , yj ) = Pk

2. M-l´ep´es: k¨ ul¨ on-k¨ ul¨ on maximaliz´aljuk a k db. polinomi´alis eloszl´as param´etereit, azaz r¨ogz´ıtett l eset´en keress¨ uk a cl

n Y m Y

p(xi , yj |zl )

ν(xi ,yj )·p(t+1) (zl |xi ,yj ) hl

i=1 j=1

f¨ uggv´eny maximum´ at, ahol a felt´eteles cellaval´osz´ın˝ us´egek kitev˝oj´eben a cellagyakoris´agok adott sz´and´ek melletti ´ert´eke ´ all (Bayes-t´etel a gyakoris´agokra), a nevez˝oben ´all´o hl csak l-t˝ol f¨ ugg (a sz´aml´al´obeliek i, j-re vett ¨ osszege). A felt´eteles f¨ uggetlens´eget kihaszn´alva ´es ´atrendezve maximaliz´alni akarjuk a  1 hl n Y m Y (t+1) (z |x ,y ) ν(x ,y )·p l i j  cl  {p(xi |zl ) · p(yj |zl )} i j i=1 j=1

kifejez´est a p(xi |zl ), p(yj |zl ) param´eterekben. R¨ogz´ıtett l-re (l = 1, . . . k) el´eg a sz¨ogletes z´ar´ojelben ´all´ o speci´ alis polinomi´ alis likelihood maximum´at venni. A specialit´as abban ´all, hogy a kapcsos z´ ar´ ojelbe foglalt val´ osz´ın˝ us´egek szorzat alak´ uak ´es a kitev˝obei csonkolt gyako´ ris´agokkal dolgozunk. Atrendezve ´es ismerve a klasszikus polinomi´alis likelihood maximum´at, a param´eterekre a k¨ ovetkez˝ o becsl´es ad´ odik minden l = 1, . . . , k eset´en: Pm (t+1) (z |x , y ) l i j j=1 ν(xi , yj ) · p (t+1) (i = 1, . . . , n) p (xi |zl ) = Pn Pm (t+1) 0 (zl |xi0 , yj ) i0 =1 j=1 ν(xi , yj ) · p illetve p

(t+1)

Pn (t+1) (z |x , y ) l i j i=1 ν(xi , yj ) · p (yj |zl ) = Pn P m (t+1) (z |x , y 0 ) 0 ν(x , y ) · p 0 i j l i j i=1 j =1

(j = 1, . . . , m).

Ezut´an legyen Pn Pm π

(t+1)

(zl ) :=

i=1

j=1 p

(t+1) (z

nm

l |xi , yj )

(l = 1, . . . , k)

a sz´and´ekok val´ osz´ın˝ us´eg´enek k¨ ovetkez˝o iter´aci´os becsl´ese, t := t + 1 ´es u ´jra megtessz¨ uk az 1. (t) ∗ – 2. l´ep´est. Ezt el´eg sokszor ism´etelve a θ sorozat konverg´alni fog θ -hoz b´armely ´ertelmes ´ kezd´es eset´en. (Ertelmetlen kezd´ as, ha az a priori val´osz´ın˝ us´egeket egyenl˝onek v´alasztjuk. Ekkor az els˝o l´ep´esben a margin´ alis val´ osz´ın˝ us´egeket kapjuk, s ezekn´el az iter´aci´o le is ragad.) Ezekut´an – pl. a p´enzforgalmi p´eld´aval ´elve – ha valamely l-re π ∗ (zl ) “kicsi”, de a p∗ (xi |zl ), eteles val´ osz´ın˝ us´egek k¨ ozt vannak szignifik´ansan “nagyok”, akkor ezek az xi , yj p´arok j |zl ) felt´ “gyan´ usak”, ak´ arcsak a hozz´ ajuk tartoz´o zl sz´and´ek. EM-algoritmus gr´ afok klaszterez´ es´ ere p∗ (y

Nem tananyag, de megtekinthet˝ o [7]-ben.

Irodalom [1] Dempster, A. P., Laird, N. M., Rubin, D. B., Maximum likelihood from incomplete data via the EM algorithm, J. R. Statist. Soc. B 39 (1977) 1-38. [2] Hastie, T., Tibshirani, R., Friedman, J., The Elements of Statistical Learning. Data Mining, Inference, and Prediction. Springer, New York (2001). [3] Hofmann, T., Puzicha, J., Latent class models for collaborative filtering, in Proc. of IJCAI’99 [4] McLachlan, G. J., The EM Algorithm and Extensions, Wiley, New York (1997). [5] Rao, C. R., Linear Statistical Inference and Its Applications, Wiley, New York (1965, 1973). [6] Csisz´ar, I., Shields, P., Information Theory and Statistics: A Tutorial, In: Foundations and Trends in Communications and Information Theory, Vol. 1 Issue 4 (2004), Now Publishers, USA. [7] Bolla, M. http://www.math.bme.hu/˜marib/prezentacio/bolla-ASMDApres.pdf

Life Enjoy

" Life is not a problem to be solved but a reality to be experienced! "

Get in touch

Social

© Copyright 2013 - 2019 TIXPDF.COM - All rights reserved.