Modèles de Markov Cachés

Adapté de source glanées sur l’Internet :Yannis Korilis, Christian St-Jean, Dave DeBarr, Bob Carpenter, Jennifer Chu-Carroll et plusieurs autres

Modèles de Markov Cachés

La séquence observée est l’évidence d’une chaîne de Markov sous-jacente cachée

s1 s2 s1 s3 s2 s2 s1Etat interne

(caché)

Observations PS NS PS S

L’émission d’un état observé n’est pas déterministe ! Chaque état caché émet, de manière aléatoire, un parmi N symboles d’un alphabet

Exemple Trames sonores représentatives de trois mots

différents

pad

bad

spat

Mot sous jacent signal sonore observable

Composantes d’un MMC (« HMM »)

Les probabilités initiales des états cachés ={i=P(si)}

Le modèle de transition des états cachés L’alphabet ={s1,...,sm} décrivant les états cachés

La matrice des probabilités de transitions entre eux A={aij= P(sj|si)}

Le modèle d’observation des symboles émis par les états cachés L’alphabet ={o1,...,ok} des symboles émis par les si pour un HMM discret

Les probabilités d’émission B={bi(ok)=P(ok|si)}

s2s1

s3

A

b1(.) 

b2(.)

b3(.)

On suppose généralement un processus stationnaire (les probabilités ne dépendent pas du temps)

Exemple de HMM

Printemps Hiver

Eté

0.25

0.25

0.25

États : ={‘Printemps’, ‘Été ’,‘Automne’, ‘Hiver’} A={aij}

Symboles observables émis par chaque état ={‘N’, ‘P ’, ‘S’} B={bj(.)} : loi multinomiale

Automne

0.25

N=0.1P=0.45S=0.45

N=0.2P=0.5S=0.3

N=0.01P=0.13S=0.86

N=0.05P=0.55S=0.4

Que peut-on faire avec un HMM ?

Évaluation d’un modèle proposé pour expliquer une séquence d’observations

Explication d’une séquence d’observation par un modèle donné

Modélisation d’un processus (caractérisation d’un HMM)

Évaluation de modèle

Quel HMM ={,,,A,B} est le plus probable d’avoir donné lieu à une séquence d’observations O=o1,...,on ?

Il faut trouver le maximum de P(O|) : • Calcul direct• Algorithme Forward-Backward

Explication d’un séquence d’observations

Connaissant un HMM , quelle séquence d’états S=s1,...,sn est la plus probable d’avoir donné lieu à une séquence d’observations O=o1,...,on ?

Il faut trouver le maximum de P(S|O,) : Calcul direct L’algorithme de Viterbi

Modélisation (Apprentissage)

Partant d’un ensemble d’observations O, comment régler les paramètres d’un HMM pour maximiser la vraisemblance de P(O|) ?

L’entraînement de Viterbi L’algorithme de Baum-Welch

Reconnaissance de formes Reconnaissance de la

parole Traitement de la langue

naturelle Commande automatique Traitement du signal Analyse des séquences

biologiques Économie

Quelques domaines d’application Analyse géopolitique Robotique Diagnostic Etc.

Avec les SVM, les HMM sont les méthodes statistiques les plus efficaces en dehors des approches neuro-mimétiques

Évaluation de modèle Étant donné un modèle HMM ={,,,A,B} et une

séquence d’observations O, quelle est la probabilité que O soit dû à , P(O|) ? Supposons que O est généré par la séquence

d’états Si = si(1),…,si(n) :

P(Si|)=P(si(1),…,si(n)|)=i(1)*ai(1),i(2)*ai(2),i(3)*…*ai(n-1),i(n)

P(O|Si ,)=P(O| si(1),…,si(n),)=bi(1)(o1)* bi(2)(o2)*…* bi(n)(on)

Par conséquent :

)(*)(**...*)(**

)(),()(

)(1)1()(),1(1)1()2(),1()1( nninnininii

iiii

iii

obobaoba

SPSOPOP

Si Si génère n observations, il faut 2n-1 multiplications, chacune portant sur un état possible; pour m états Complexité computationnelle : o(2n*mn) !

Th. de Bayes

Indép. des observations

Th. de Bayes

De nombreuses multiplications sont répétées (portions de sous-séquences communes => Calculer P(O|) de manière incrémentale Soit t(i)=P(o1, o2…ot, Si(t)=si| ) la probabilité d’avoir O=o1,…,ot

avec la dernière observation émise par l’état si , on a :

s1

sj

sm

si

Forward

bi(ot)

Pour n observations et m états, on a 2m2 multiplications à chaque étape Complexité computationnelle o(2m2n) au lieu de o(n*mn)

m

1it )i()O(P

Chacun de s1..sm aurait pu

émettre ot

)o(b*a)j()i(

)o(b*)i(

1ti

m

1jijt1t

1ii1

Probabilité que si complète la sous-

séquence finissant à t

Par induction :

Évaluation de modèle : L’algorithme forward-backward

Soit t(i)=P(ot+1, ot+2…on|Si(t)=si, ) la probabilité d’observer la sous- séquence ot+1,…,on en partant de l’état Si(t)=si; partant de t=1, on a :

m

1i11ii )i()o(b)O(P

Pour m état et n observations, on a 2m2 multiplications à chaque étape Complexité o(2m2n) en temps, o(m) en espace (idem pour l ’algorithme forward)

s1

si

sm

sj

Backward

ai,j

b1(ot+1)

bj(ot+1)bm(ot+1)

t+1(m)

t+1(1)

t+1(j)Chacun de s1..sm

aurait pu émettre o1

)(*)()(

1)(

11

1

1

iobai

i

t

m

jtjijt

On part toujours d’un étant initial

Probabilité que si

précède la sous-séquence qui suit à t+1

Par induction :

L’algorithme forward-backward (suite)

Explication

s? s? s? s?

Observations o1 o2 on-1 on

On veut identifier la séquence d’états Si=si(1),…,si(n) ayant la probabilité maximale d’avoir généré O=o1,...,on

Il faut trouver :

ou, de manière équivalente :),|( max OSP i

i),( max i

iSOP

…

…

Explication : L’algorithme de Viterbi

),( max ii

SOP

s2s1

s3

A

b1(.) 

b2(.)

b3(.)

Recherche parmi tous les chemins possibles : o(mn) !

Algorithme de Viterbi (ou règle du petit poucet ) : Chaque symbole est émis par un seul état caché La séquence d’états la plus probable pour expliquer la

séquence d’observations à l’instant t dépend seulement de la séquence la plus probable à t-1 On peut trouver la séquence en procédant de proche en proche !

Algorithme de Viterbi(suite)

Le séquence d’etats optimale est la somme des meilleurs segments en allant de gauche à droite d(si,t,sj,t+1)=ai,j*bj(ot+1)

s2

s1

sn-1

sn

si

s2

s1

sn-1

sn

si

s2

s1

sn-1

sn

si

s2

s1

sn-1

sn

si

s2

s1

sn-1

sn

si

o1 o2 o3 on-1 on

Résultat final: Prendre le chemin qui maximise =>Complexité en o(m2*n) en temps, o(m*N) en espace (un chemin par état)

Algorithme de Viterbi (fin)

Soit la probabilité du meilleur état finissant la sous-séquence o1,…,ot à l’instant t

),,...,,(max)( )(21 ititi

t ssoooPi

Règle d’induction:

On mémorise, à chaque t, l’état optimal sj menant à si au temps t+1

On garde trace ainsi des n-1 meilleurs états successifs du parcours

)(in

jitmj

jt aji *)(maxarg)(..1

1

)(**)(max)(

)(*)(

1..1

1

11

tiijtmj

t

ii

obaji

obi

1. Initialisation : Pour t=1 et

1 i m ,

2. Récurrence :

Pour t = 2,…,n,

et 1 i m ,

3. Terminaison : s(n) = argmaxi

4. Retour en arrière :

Pour t = n-1,…,1, s(t) = Ψt+1(s(t+1))

L’algorithme de Viterbi

)(**)(..1

max)(1 1,

tiijt obaj

mji

t

)i(T

)*)((..1

maxarg)( ,1 ijtj ajmj

it

)(*)(1 1obi ii

0)(1 i

Une personne en vacances envoie une carte postale mentionnant les activités suivantes : jour 1: plage ; jour 2 : magasinage ; jour 3 : sieste.

On veut en déduire la séquence météorologique sous-jacente probable sachant que : Les conditions météorologiques suivent une chaîne de

Markov à 2 états : Pluie et soleil On possède des statistiques sur le comportement des

touristes selon les états

Exemple

A = B= =

Transition d’état émission de symboles par les états état initial ={pluie=1, soleil=2}, ={magasinage=1, plage=2, sieste=3}

Modèle HMM

0.7 0.3

0.4 0.6

0.4 0.3

0.1 0.6

0.5 0.1

0.6

0.4

Séquence d’observations : O = 2,1,3 Probabilité du meilleur chemin menant à l’état j au temps t :

État optimal à l’instant t-1 pour aboutir à l’état j au temps t :),,...,,(max)( )(21 jtit

It sSoooPj

)*)((..1

maxarg)( ,1 ijtj ajmj

it

Étape 1 1(1) = π1*b1(2) = 0.6*0.1 = 0.06, 1(2) = π2*b2(2) = 0.4*0.6 = 0.24, Ψ1(1) = Ψ1(2)=0

Étape 2 t = 2

2(1) = maxj (1(j)*aj 1)*b1(1)

= max {0.06*0.7, 0.24*0.4}*0.4 = 0.0384=> Ψ2(1) = argmaxj (1(j)*aj 1)= 2

2(2) = maxj (1(j)*aj2)*b2(1)

= max{0.06*0.3, 0.24*0.6}*0.3 = 0.0432=> Ψ2(2) = 2

Calculs)o(b*)i(

1 1ii

)o(b*a*)j(2..1j

max)i(1t 1tii,jt

3,1,2O

)a*)j((m..1j

maxarg)i(t i,j1tj

t = 3 3(1) = maxj (2(j)*aj1)*b1(3)

= max{0.0384*0.7, 0.0432*0.4}*0.5 = 0.01344=> Ψ3(1) = 1

3(2) = maxj (2(j)*aj2)*b2(3) = max{0.0384*0.3, 0.0432*0.6}*0.1 = 0.002592

=> Ψ3(2) = 2

Étape 3 : s(3) = argmax {3(1), 3(2)} = 1

Étape 4 : s(2) = Ψ3(s(3)) = 1, s(1) = Ψ2(s(2)) = 2

La séquence d’états cachés la plus probable est 2,1,1, avec une vraisemblance P(O|λ) = 0.01344.

)o(b*a*)j(2..1j

max)i(1t 1tii,jt

3,1,2O

Vérification par la force brute !

P(s1=i,s2=j,s3=k,o1=2,o2=1,o3=3|)=i*bi(2)*aij*bj(1)*ajk*bk(3)

S πi bi aij bj ajk bk P

1,1,1 0.6 0.1 0.7 0.4 0.7 0.5 0.005880

1,1,2 0.6 0.1 0.7 0.4 0.3 0.1 0.000504

1,2,1 0.6 0.1 0.3 0.3 0.4 0.5 0.001080

1,2,2 0.6 0.1 0.3 0.3 0.6 0.1 0.000324

2,1,1 0.4 0.6 0.4 0.4 0.7 0.5 0.01344

2,1,2 0.4 0.6 0.4 0.4 0.3 0.1 0.001152

2,2,1 0.4 0.6 0.6 0.3 0.4 0.5 0.008640

2,2,2 0.4 0.6 0.6 0.3 0.6 0.1 0.002592

Caractérisation d’un HMM par apprentissage

Partant d’un ensemble de séquences d’observations O={O1,...,OT}, comment ajuster =<,,,A,B> pour maximiser P(O|) ?

Choix du nombre d’états (fixé, automatique (critères globaux, fusions d’états))

Choix de la fonction d’émission (loi multinomiale, normale, Student)

Méthodes d’apprentissage (Viterbi, Baum-Welch, NN)

Choix du nombre d’états

Si on est chanceux, on peut associer une sémantique aux états. Ex :

Article Adjectif Verbe

1

Nom

le=0.4la=0.4du=0.2

bon:0.1optimal:0.5grand:0.4

possède:0.3permet:0.4travaille:0.3

modèle:0.3ouvrier:0.1choix:0.6

0 0

0

Choix du nombre d ’états

On peut aussi partir d’observations Exemple d’un HMM continu gaussien en 2D, bi() ~ N(,)

1,1

3,3

2,2

Nombre de composantes dans le mélange ~ Nombre d ’états dans le HMM

Observations Etats

Entraînement de Viterbi

On dispose d’un ensemble d’observations O={O1,...,OT}

Principe du max. de vraisemblance:

Max. de vraisemblance suivant les chemins de Viterbi:

T

1i

i )(P)(P

T

1i

ii )V,(P)V,(P

- Approche moins rigoureuse+ Hypothèse de Viterbi: « Tous les autres chemins ont une

probabilité nulle ou négligeable »

+ Algorithme optimal

)V,(P)(P

Entraînement de Viterbi

bj() : loi multinomiale sur l’alphabet

)(**...*)(**),( )()(),1(1)1()2(),1()1( nnininiiiiii obaobaSOP Rappel :

: Nombre d’émissions de ol par sj pour la séquence Si

: Nombre de transitions de sj à sk pour la séquence Si

ijkN

ijlM

im

j

m

k

ijk

m

j l

ijl NMi

1 ,1 11 1

Ss Ss

Nk,j

o

Mlj)1(i

ii

j k

ijk

l

ijl a)o(b*)V,(P

Entraînement de Viterbi

Ss Ss

N

k,jo

M

ljPj

j k

jk

l

jlj a)o(b)V,(P

: Nombre de passages sj en sk pour l ’ensemble des séquences

: Nombre d’émissions du symbole ol par sj pour l ’ensemble des séquences

: Nombre de fois où sj est premier dans le chemin de Viterbi

jkN

jlM

jP

Maximiser cette formule <=> Maximiser les 3 sous-produits

m

iil

jlljm

iji

jkkj

jj

M

M(ob

N

Na

T

P

11

, )ˆ ,ˆ ,̂

1. Choix du paramétrage initial du HMM2. Répéter

· Initialiser les compteurs à 0· Pour chaque séquence d’observations Oi

· Calculer le chemin de Viterbi pour le HMM courant· Mettre à jour des compteurs

Fin pour· Re-estimer les paramètres du HMM avec les formules

précédentesJusqu’à stabilité des paramètres;

Entraînement de Viterbi

jkN jlM jP

jkN jlM jP

),,...,()( 1 HiiooPi tntt

Algorithme de Baum-Welch

),,...,()( )(1 HssooPi itktt

T

1i

i )(P On veut toujours estimer , mais sans connaissance de chemin !!

),,(),( )1()( k

jtkitkt OsSsSPji

Probabilité dans de passer par si à t et sj à t+1 pour l’a séquence observations Ok :

Avec la règle de Bayes:

)(

),,(),( )1()(

k

kjtkitk

t OP

OssssPji si sj

aij

ot+1

)(

)(*)(**)(),( 11,

k

ttjjitt OP

jobaiji

Algorithme de Baum-Welch (2)

Conséquences pour une séquence d’observations donnée :

m

jtt jii

1

),()( : Probabilité dans de se retrouver à l’instant t dans l’état si

: Espérance du nombre de transitions par sj à l’instant t

: Espérance du nombre total de passages par si

1

1

)(n

tt i

=> on aboutit à des estimateurs simples ...

1

1

),(n

tt ji

Algorithme de Baum-Welch (3)

1

1

1

1,

)(

),(ˆ

n

tt

n

tt

ji

i

jia

n

tt

n

ttt

j

j

oj

1

1

)(

)(ˆ

n

tt

n

tjt

Tjtt

j

j

ooj

1

1

)(

)ˆ()ˆ)((ˆ

)(ˆ 1 ii

spar passages de nombredu Espérance

s verss de ns transitiode nombredu Espérance

i

ji

Formules à étendre pour T séquences !

Algorithme de Baum-Welch (fin)

· Choix du paramétrage initial du HMM· Répéter

· Pour chaque séquence Oi

· Calculer avec l ’algorithme forward· Calculer avec l ’algorithme backward· Calculer · Calculer

· Fin pour· Ré estimer les paramètres du HMM avec les formules

précédentes· Jusqu ’à stabilité des paramètres;

)( jit

)( jit

)( jit

)( jit

Croissance monotone de la vraisemblance => optimum local