Statistique pour la bio-informatique
6
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
6
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Statistique pour la bio-informatique
Seance 9-10 - Decembre 2003
Chaˆ nes de Markov cachees
1 Chaˆnes de Markov cachees et applications
Les modeles a donnees latentes (ou manquantes ou cachees) constituent des outils
puissants pour modeliser des systemes dont la dynamique e ectue des transitions entre
di erents etats impossible a observer directement. Dans une chaˆ ne de Markov cachee,
lesdi erentsetatsd’unsystemepeuventˆetrecaracterisesparunnombre nidevaleurs.
Onpassealorsdel’etats al’etats aveclaprobabilitep lorsd’unetransition.Dansi j s ,si j
chaque etat, le systeme est susceptible emettre un symbole o pris dans un alphabet O
ni ( O pour observable). La probabilite d’emission du symbole o peut dependre de
l’etat s. Nous la notons q .s,o
Les algorithmes dedies aux chaˆ nes de Markov cachees sont des algorithmes d’es-
timation statistique. Etant donnee une suite d’observations de longueur T, o ,...,o ,1 T
ils ont pour objectif typique d’estimer la suite d’etats s ,...,s la plus probable. Pour1 n
cela, il faudra ajuster correctement les parametres du modeles P = (p ) et Q = (q )s ,s soi j
a partir d’un ensemble de n sequences dont les etats sont connus.
Le premier objectif est generalement rempli par l’algorithme deViterbi. Le second
objectif est rempli par l’algorithme EM, dont la version speci que aux CMC s’appelle
algorithme de Baum-Welch.
1.1 Applications
Les applications des CMC (ou d’autres modeles a structure latente comme les
reseaux de neurones) sont tres ...
Voir
Seance 9-10 - Decembre 2003
Chaˆ nes de Markov cachees
1 Chaˆnes de Markov cachees et applications
Les modeles a donnees latentes (ou manquantes ou cachees) constituent des outils
puissants pour modeliser des systemes dont la dynamique e ectue des transitions entre
di erents etats impossible a observer directement. Dans une chaˆ ne de Markov cachee,
lesdi erentsetatsd’unsystemepeuventˆetrecaracterisesparunnombre nidevaleurs.
Onpassealorsdel’etats al’etats aveclaprobabilitep lorsd’unetransition.Dansi j s ,si j
chaque etat, le systeme est susceptible emettre un symbole o pris dans un alphabet O
ni ( O pour observable). La probabilite d’emission du symbole o peut dependre de
l’etat s. Nous la notons q .s,o
Les algorithmes dedies aux chaˆ nes de Markov cachees sont des algorithmes d’es-
timation statistique. Etant donnee une suite d’observations de longueur T, o ,...,o ,1 T
ils ont pour objectif typique d’estimer la suite d’etats s ,...,s la plus probable. Pour1 n
cela, il faudra ajuster correctement les parametres du modeles P = (p ) et Q = (q )s ,s soi j
a partir d’un ensemble de n sequences dont les etats sont connus.
Le premier objectif est generalement rempli par l’algorithme deViterbi. Le second
objectif est rempli par l’algorithme EM, dont la version speci que aux CMC s’appelle
algorithme de Baum-Welch.
1.1 Applications
Les applications des CMC (ou d’autres modeles a structure latente comme les
reseaux de neurones) sont tres ...
Statistique pour la bio-informatique S´eance9-10-Decembre2003 ChaıˆnesdeMarkovcach´ees
1ChaıˆnesdeMarkovcach´eesetapplications Lesmode`lesa`donne´eslatentes(oumanquantesoucache´es)constituentdesoutils puissantspourmod´eliserdessyste`mesdontladynamiqueeffectuedestransitionsentre diffe´rentse´tatsimpossible`aobserverdirectement.DansunechaˆınedeMarkovcache´e, lesdiff´erents´etatsd’unsyst`emepeuventeˆtrecaracte´ris´esparunnombrefinidevaleurs. Onpassealorsdel’´etatsitate´’la`sjt´libibaroapclveaepsi,sjlors d’une transition. Dans chaque´etat,lesyst`emeestsusceptiblee´mettreunsymboleopris dans un alphabetO fini (Obarolibiedt´em’´issiudnobmyselopouorsbreavlb)eL.paodeenerd´dpeeptu l’´etats. Nous la notonsqs,o. Lesalgorithmesd´edi´esauxchaˆınesdeMarkovcach´eessontdesalgorithmesd’es-timationstatistique.Etantdonn´eeunesuited’observationsdelongueurT,o1, . . . , oT, ilsontpourobjectiftypiqued’estimerlasuited’´etatss1, . . . , snla plus probable. Pour cela,ilfaudraajustercorrectementlesparam`etresdumod`elesP= (psi,sj) etQ= (qso) a`partird’unensembledenonntnluess.´etuaetnscsoenstdco´sqe Lepremierobjectifestg´en´eralementrempliparl’algorithmedeViterbi. Le second objectifestrempliparl’algorithmeEM,dontlaversionsp´ecifiqueauxCMCs’appelle algorithme deBaum-Welch.
1.1 Applications LesapplicationsdesCMC(oud’autresmode`lesa`structurelatentecommeles re´seauxdeneurones)sonttr`esnombreusesenbio-informatique.Nousillustronscette approchea`l’aidedel’exempleclassiquelarecherchedege`nesquenoussimplifierons`a l’extreˆme(cflogicielgenscande Burge et Karlin, 1997).
1.2AlgorithmiquedeschaıˆnesdeMarkovcach´ees Dans cette section, nous notonsSchcatsta´eesedblsnmele’tese´Steassoci´eenıˆahcal ∀s1, s2∈ S, ps1,s2= P(St+1=s2|St=s1). 1
Nous notonsπla loi initiale de la chaˆıne πs= P(S1=s). Nous notonsO`amentesedblemns’elbaelesvrstboe´atelleionnndits.CoSt=s´neeadon,l Xtest donc issue de la loi ∀o∈ O,P(Xt=o|St=s) =qs,o. Ayantobserv´eunes´equencedelongueurT,o1, . . . , oTarvamesinalbudecer`mtea,plar multidimensionnel θ= (π, P, Q) este´galea` L(θ) = P(o1, . . . , oT;θ). 1.2.1 Algorithmeforward La vraisemblanceL(θvrlaseaipoes`and)rroceinclamb`eplomncomnu’deta`ele`d donne´esmanquantes X L(θ) =P(o1, . . . , oT|s1, . . . , sT;Q) P(s1, . . . , sT; (π, P)). s1,...,sT Pr´ecisement,nousavons X L(θ) =p qπ q∙ ∙ ∙.p q s1s1,o1s1,s2s2,o2sT−1,sTsT,oT s1,...,sT Cetteformulesugge`reunalgorithmedecalculna¨ıf,dontlacomplexit´edel’ordre T O(T(#Sgo-unalpadimeneelocuˆrtrendrait))eivo’dtnitulrpnof.tisoLarotpbihi rithme de programmation dynamique. Il repose sur le calcul de la grandeur ∀s∈ S, αt(s) = P(o1, . . . , ot, St=s). Cettegrandeurrepr´esentelaprobabilite´d’observero1, . . . , otveclauatate´’spmett, St=s.
Proposition 1.1Algorithme forward.Soito1, . . . , oTune suite d’observations provenant d’une CMC. Posons ∀s∈ S, α1(s) =πsqs,o1 2
et, pour toutt= 2, . . . , T, X ∀st∈ S, αt(st) =αt−1(s)ps,stqst,ot. s Nous avons X L(θ) =αT(s) s∈S 2 L’algorithmedecalculassocie´estdecomplexit´edel’ordredeO(T(#S) ).
De´monstration.
Demani`ereunpeumoinsnaturelle,maiscomple`temente´quivalente,nouspouvons consid´ererunevariablequiremontelesensdutemps.Cettevariableestappele´eva-riable backward ∀s∈ S, βt(s) = P(ot+1, . . . , oT|St=s). Cettegrandeurrepre´sentelaprobabilit´ed’observeroT, . . . , ot+1`antmeleelnntioiocdn St=s.
Proposition 1.2Algorithme backward.Soito1, . . . , oTune suite d’observations provenant d’une CMC. Posons ∀s∈ S, βT(s) = 1 et, pour toutt= 1, . . . , T−1, X ∀st∈ S, βt(st) =βt+1(s)pst,sqs,ot+1. s Nous avons X L(θ) =πsβ1(s)qs,o1 s∈S 2 L’algorithmedecalculassocie´estdecomplexite´del’ordredeO(T(#S) ).
De´monstration.
3
1.2.2 Algorithmede Viterbi L’algorithmedeViterbipermetdecalculerlasuited’e´tatscache´slaplusprobable vu les observationso1, . . . , oT ∗ ∗ s ,. . . , s= a 1Trg maxP(o1, . . . , oT∩s1, . . . , sT;θ) Notonsquelavaleurmaxestappel´eescore de Viterbi. On l’obtient formellement enrempla¸cantlasommeparlemaximumdansl’expressiondelavraisemblancein-compl`eteL(θdnoc`tiuareenhtc´reeneulma´meriaxtuimvdemmena`irene)¨.aRveıcmhe unalgorithmedecomplexite´exponentiellementcroissanteenlalongueurdesobserva-T tions (O(T(#Snuetsnoriuruvposcone,ntusno´rcee´edestcoipnmedansla))).Com 2 algorithmecomplexit´equadratiqueO(T(#S) ). Cet algorithme, ditalgorithme de Viterbipmalc¸naltsamoemparlemax.o’seitbsintlempntmereen
Proposition 1.3Algorithme de Viterbi.Soito1, . . . , oTune suite d’observa-tions provenant d’une CMC. Posons ∀s∈ S, v(s) =π q 1s s,o1 et, pour toutt= 2, . . . , n, ∀st∈ S, vt(st) = max{vt−1(s)ps,stqst,ot}. s Nous avons ∗ smax= argvT(s) T s et, pour toutt=T−1, . . . ,1,
D´emonstration.
1.2.3 Exercices
∗ s=axargm{vt(s)ps,s}. ∗ tt+1 s
Exercice 1.On pose ∀s∈ S, γt(s) = P(St=s|o1, . . . , oT;θ). 4
