CHAINE DE MARKOV CACHEE
CMC
Exemple
Exemple : On dispose de 3 urnes contenant des boules blanches, noires et grises dans des proportions diffrentes. On note par P(B/ui), P(N/ui), P(G/ui) les probabilits de tirer une boule blanche, noir ou grise de lurne ui (i=1,2,3). Un oprateur invisible choisi, des instants rguliers, une urne et tire une boule de cette urne et annonce la couleur. Sil choisi T urnes il annoncera ( un observateur) la squence des T couleurs tirs note OT. Ainsi, au temps t, loprateur choisi une urne ut et tire une boule de couleur ot de cette urne. On suppose que le tirage dune boule au temps t est indpendant du tirage de la boule au temps t-1.
Exemple (suite)
On fait lhypothse que loprateur choisi la squence des urnes suivant un modle dune chane de Markov ayant pour paramtres {!, A} et dont les tats sont les urnes. Cette chane sera dite cache (puisque loprateur est invisible) . Ainsi : La squence UT=[Link] sera dite la squence des tats cache (car invisible) et elle est gnre par la chane de Markov cache. La squence OT=[Link] sera dite la squence observations qui sera annonce lobservateur. des
CMC : dfinition
! ! ! ! ! ! M : le nombre des symboles observables. N : le nombre des tats caches. V={v1,v2,,vM} : lensemble des symboles observables. Q={q1,q2,,qN} : lensemble des tats caches. "=[!i] : la table de probabilits de ltat initial de la CM. A=[aij] : matrice N*N des probabilits de transition de la CM. ! B=[bi(vk)] : matrice N*M avec bi(vk)=P(vk/qi) (probabilit de lmission de ltat vk par ltat qi). ! T : taille dune squence dobservations. Notation : les paramtres du modle seront nots par : #=(! , A , B)
chane de Markov
Gnration dune squence dobservations
Une squence dobservations OT=o1o2oT est gnre de la manire suivante : 1.! Faire t=1, choisir un tat initial i1 selon la distribution ". Choisir o1 selon la table de probabilit de lmission de ltat i1 (la table bi1() ). 2.! Choisir ltat selon les probabilits de transitions , it tant lindice de ltat au temps t, choisir ot+1 selon la table de probabilit de lmission de ltat dindice it (la table bit+1() ). Faire t=t +1. 3.! Si t<T alors retourner ltape 2 sinon Fin.
IT=i1i2iT : la squence des indices des tats caches. OT=o1o2oT : la squence des symboles observs
Trois problmes
Problme 1 : Etant donn la squence dobservations OT=o1o2oT et le modle (de CMC) de paramtre #=(!,A,B), comment calculer P(OT/#) ? Problme 2 : Etant donn la squence dobservations OT=o1o2oT comment choisir la squence des tats sous-jacentes i1i2iT et qui est optimal suivant un certain critre ? Problme 3 : Comment ajuster les paramtres #=(!,A,B) afin de maximiser P (OT/#) ?
Problme 1 Calcule de P(OT/#)
Une manire immdiate pour calculer cette probabilit est dnumrer toutes le squences IT=i1i2iT dtats possibles et de calculer :
Chane de Markov Avec : Indpendance des observations
Do
Mais cette formule est trs coteuse en temps de calcule. Ordre de calcule 2TNT
Mthodes Forward et Backward
Ces deux mthodes utilisent implicitement le graphe suivant :
qn
qn
qn
qn
qn
.. .. ..
q2 q1
t=1
q2 q1
t=2
q2 q1
q2 q1
t=3
q2 q1
t=T
L arc qi!qj existe si et seulement si aij>0, il sera valu par aij
Calcule de P(OT/#) Mthode Forward
Observations partielles
On dfinit $t(i)=P(o1o2ot, it=i /#)
Calcule de $t 1.! $1(i)= !ibi(o1) pour i=1,,N 2.! Pour t=1,2,,T-1 et pour j=1,,N
a2i $t(2) $t(1) a1i $t(N) aNi
Calcule de P(OT/#) Mthode Backward
Observations partielles
On calcule %t(i)=P(ot+1ot+2oT / it=i,#) Calcule de $t 1.! %T(i)=1 pour i=1,,N 2.! Pour t=T-1,,1 et pour i=1,2,,N %t+1(N)bN(ot+1)
aiN ai2 ai1
%t+1(2)b2(ot+1) %t+1(1)b1(ot+1)
Calcule de p(OT/#)
On a :
Pour tout t
Problme 2 : Dcodage
Dtermination de la squence cache optimale
Trouver la squence des tats caches qui explique au mieux la squence des observations. Dterminer :
Or Dterminer Algorithme de Viterbi
Problme 2 : Algorithme de Viterbi
On dfinit : La squence des tats cachs i1i2it-1qui maximise la probabilit davoir observ : ! les observations jusquau temps t-1 ! ltat au temps t ! lobservation au temps t
Par dfinition :
Problme 2 : Algorithme de Viterbi
Etape 1 : pour i=1,,N &1(i)=!ibi(o1) et '1(i)=0 Etape 2: Pour t=2 T faire
FIN Etape 3 : On tire
Etape 4 : (reconstitution de la squence) Pour t=T-1,, 1
Problme 3
Dtermination des paramtres
Etant donn un modle et une squence dobservation, modifier les paramtres du modle afin de reproduire au mieux les observations. On dfinit : La probabilit de passer de ltat qi ltat qj au temps t
Probabilit dtre ltat qi au temps t
Problme 3
Dtermination des paramtres
Reprsente la frquence relative des transitions travers ltat qi
Reprsente la frquence relative des transitions de ltat qi ltat qj
Problme 3 (suit)
Dtermination des paramtres
Algorithme -! Initialiser les paramtres #0=("0,A0,B0) -! Rpter ltape itrative suivante : Les paramtres courants #=(",A,B) permettent de calculer les nouveaux paramtres par : 1. 2. 3.
