En enginyeria elèctrica, computació estadística i bioinformàtica, l'algorisme de Baum-Welch és un cas especial de l'algorisme d'expectativa-maximització utilitzat per trobar els paràmetres desconeguts d'un model ocult de Markov (HMM). Utilitza l'algorisme endavant-enrere per calcular les estadístiques del pas d'expectativa. L'algorisme de Baum-Welch, el mètode principal per a la inferència en models ocults de Markov, és numèricament inestable a causa del seu càlcul recursiu de probabilitats conjuntes. A mesura que creix el nombre de variables, aquestes probabilitats conjuntes es tornen cada cop més petites, cosa que fa que les recursions directes s'acostin ràpidament a valors per sota de la precisió de la màquina.
Història L'algorisme de Baum-Welch va rebre el nom dels seus inventors, Leonard E. Baum i Lloyd R. Welch. L'algorisme i els models ocults de Markov es van descriure per primera vegada en una sèrie d'articles de Baum i els seus col·legues del Centre IDA per a la Recerca en Comunicacions de Princeton a finals dels anys seixanta i principis dels setanta. Una de les primeres aplicacions importants dels HMM va ser en el camp del processament de la parla. A la dècada del 1980, els HMM van emergir com una eina útil en l'anàlisi de sistemes i informació biològica, i en particular d'informació genètica. Des de llavors s'han convertit en una eina important en la modelització probabilística de seqüències genòmiques.
Descripció Un model ocult de Markov descriu la probabilitat conjunta d'una col·lecció de variables aleatòries discretes "ocultes" i observades. Es basa en la suposició que la i-èsima variable oculta donada la (i − 1)-èsima variable oculta és independent de les variables ocultes prèvies, i les variables d'observació actuals només depenen de l'estat ocult actual.
L'algorisme de Baum-Welch utilitza el conegut algorisme EM per trobar l'estimació de màxima probabilitat dels paràmetres d'un model ocult de Markov donat un conjunt de vectors de característiques observats.
Sigui una variable aleatòria oculta discreta amb valors possibles (és a dir, suposem que hi ha estats en total). Suposem que és independent del temps , la qual cosa porta a la definició de la matriu de transició estocàstica independent del temps
La distribució d'estat inicial (és a dir, quan ) ve donat per
Les variables d'observació pot agafar-ne un valors possibles. També assumim que l'observació donada l'estat "ocult" és independent del temps. La probabilitat d'una determinada observació a l'hora per a l'estat ve donat per
Tenint en compte tots els valors possibles de i , obtenim el matriu on pertany a tots els estats possibles i pertany a totes les observacions.
Una seqüència d'observació ve donada per .
Així podem descriure una cadena de Markov oculta per . L'algorisme de Baum-Welch troba un màxim local per a (és a dir, els paràmetres HMM que maximitzen la probabilitat de l'observació).
Algorisme Conjunt amb condicions inicials aleatòries. També es poden establir utilitzant informació prèvia sobre els paràmetres si està disponible; això pot accelerar l'algorisme i també dirigir-lo cap al màxim local desitjat.
Procediment endavant Sigui , la probabilitat de veure les observacions i estar en estat a l'hora . Això es troba recursivament:
Com que aquesta sèrie convergeix exponencialment a zero, l'algorisme tindrà un desbordament numèric inferior per a seqüències més llargues. Tanmateix, això es pot evitar amb un algorisme lleugerament modificat escalant en la part davantera i en el procediment invers que s'indica a continuació.
Procediment invers Sigui aquesta és la probabilitat de la seqüència parcial final estat inicial donat a l'hora . Calculem com,
Actualització Ara podem calcular les variables temporals, segons el teorema de Bayes:
que és la probabilitat d'estar en l'estat a l'hora donada la seqüència observada i els paràmetres
que és la probabilitat d'estar en l'estat i a vegades i respectivament, donada la seqüència observada i paràmetres .
Els denominadors de i són els mateixos ; representen la probabilitat de fer l'observació donats els paràmetres .
Els paràmetres del model ocult de Markov ara es pot actualitzar:
que és la freqüència esperada de passada en l'estat a l'hora .
que és el nombre esperat de transicions de l'estat i a l'estat j en comparació amb el nombre total esperat de transicions que comencen a l'estat i, incloent-hi des de l'estat i fins a si mateix. El nombre de transicions que comencen a l'estat i és equivalent al nombre de vegades que s'observa l'estat i a la seqüència des de t = 1 a t = T. − 1.
on
és una funció indicadora, i és el nombre esperat de vegades que les observacions de sortida han estat iguals a mentre està a l'estat sobre el nombre total previst de vegades a l'estat .
Aquests passos es repeteixen iterativament fins a assolir el nivell de convergència desitjat.
Nota: És possible sobreajustar un conjunt de dades concret. És a dir, . L'algorisme tampoc garanteix un màxim global.
Seqüències múltiples L'algorisme descrit fins ara assumeix una única seqüència observada . No obstant això, en moltes situacions s'observen diverses seqüències: . En aquest cas, la informació de totes les seqüències observades s'ha d'utilitzar en l'actualització dels paràmetres. , , i . Suposant que has calculat i per a cada seqüència , ara es poden actualitzar els paràmetres:
on
és una funció indicadora
Exemple Suposem que tenim una gallina de la qual recollim ous al migdia cada dia. Ara, si la gallina ha post ous per recollir depèn d'alguns factors desconeguts que estan ocults. Tanmateix (per simplicitat) podem suposar que la gallina sempre es troba en un dels dos estats que influeixen en si la gallina pon ous, i que aquest estat només depèn de l'estat del dia anterior. Ara no coneixem l'estat en el punt de partida inicial, no coneixem les probabilitats de transició entre els dos estats i no coneixem la probabilitat que la gallina posi un ou donat un estat concret. Per començar, primer endevinem les matrius de transició i emissió. +TransicióEstat 1Estat 2Estat 10,50,5Estat 20,30,7+EmissióSense ousOusEstat 10,30,7Estat 20,80,2+InicialEstat 10,2Estat 20,8
Referències
Categoria:Algorismes Categoria:Bioinformàtica