La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Statistique pour la bio-informatique

6 pages
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 plus Voir moins
Statistique pour la bio-informatique S´eance9-10-Decembre2003 ChaıˆnesdeMarkovcach´ees
1ChaıˆnesdeMarkovcach´eesetapplications Lesmode`lesa`donne´eslatentes(oumanquantesoucache´es)constituentdesoutils puissantspourmod´eliserdessyste`mesdontladynamiqueeectuedestransitionsentre die´rentse´tatsimpossible`aobserverdirectement.DansunechaˆınedeMarkovcache´e, lesdi´erents´etatsdunsyst`emepeuventeˆtrecaracte´ris´esparunnombrenidevaleurs. 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´eessontdesalgorithmesdes-timationstatistique.Etantdonn´eeunesuitedobservationsdelongueurT,o1, . . . , oT, ilsontpourobjectiftypiquedestimerlasuited´etatss1, . . . , snla plus probable. Pour cela,ilfaudraajustercorrectementlesparam`etresdumod`elesP= (psi,sj) etQ= (qso) a`partirdunensembledenonntnluess.´etuaetnscsoenstdco´sqe Lepremierobjectifestg´en´eralementrempliparlalgorithmedeViterbi. Le second objectifestrempliparlalgorithmeEM,dontlaversionsp´eciqueauxCMCsappelle algorithme deBaum-Welch.
1.1 Applications LesapplicationsdesCMC(oudautresmode`lesa`structurelatentecommeles re´seauxdeneurones)sonttr`esnombreusesenbio-informatique.Nousillustronscette approchea`laidedelexempleclassiquelarecherchedege`nesquenoussimplierons`a lextreˆme(cflogicielgenscande Burge et Karlin, 1997).
1.2AlgorithmiquedeschaıˆnesdeMarkovcach´ees Dans cette section, nous notonsSchcatsta´eesedblsnmeletese´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`amentesedblemnselbaelesvrstboe´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`eplomncomnudeta`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,o2sT1,sTsT,oT s1,...,sT Cetteformulesugge`reunalgorithmedecalculna¨ıf,dontlacomplexit´edelordre T O(T(#Sgo-unalpadimeneelocuˆrtrendrait))eivodtnitulrpnof.tisoLarotpbihi rithme de programmation dynamique. Il repose sur le calcul de la grandeur s∈ S, αt(s) = P(o1, . . . , ot, St=s). Cettegrandeurrepr´esentelaprobabilite´dobservero1, . . . , 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) =αt1(s)ps,stqst,ot. s Nous avons X L(θ) =αT(s) s∈S 2 Lalgorithmedecalculassocie´estdecomplexit´edelordredeO(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´edobserveroT, . . . , 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, . . . , T1, 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 Lalgorithmedecalculassocie´estdecomplexite´delordredeO(T(#S) ).
De´monstration.
3
1.2.2 Algorithmede Viterbi LalgorithmedeViterbipermetdecalculerlasuitede´tatscache´slaplusprobable vu les observationso1, . . . , oT ∗ ∗ s ,. . . , s= a 1Trg maxP(o1, . . . , oTs1, . . . , sT;θ) Notonsquelavaleurmaxestappel´eescore de Viterbi. On l’obtient formellement enrempla¸cantlasommeparlemaximumdanslexpressiondelavraisemblancein-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.oseitbsintlempntmereen
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{vt1(s)ps,stqst,ot}. s Nous avons smax= argvT(s) T s et, pour toutt=T1, . . . ,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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin