Algoritme de Baum-Welch

En ingenieria elèctrica, informàtica estadística i bioinformática, el algoritme de Baum-Welch és un cas especial del algoritme d'maximización d'expectatives utilisat per a trobar els paràmetros desconeguts d'un model amagat de Markov (HMM). Utilisa l'algoritme d'alvanç-reculada per a calcular les estadístiques del pas d'expectativa.

Introducció

Un dels problemes relacionats en els Models Amagats de Márkov (MOM) és el de trobar un model ___MATH_0___ que maximizar la provabilitat d'una seqüència d'observacions ___MATH_1___, és dir, determinar el model que millor explica tal seqüència. El problema és que no és possible trobar tal model analíticamente i per això és necessari un algoritme iterativo com el de Baum i Welch, que permet estimar els paràmetros d'un model que fan màxima la provabilitat d'una seqüència d'observables.

L'algoritme de Baum i Welch

Donada una seqüència d'observacions ___MATH_2___, l'algoritme de Baum i Welch permet estimar els paràmetros ___MATH_3___ d'un Model amagat de Márkov (MOM) que maximizar la provabilitat de dita seqüència, és dir, ___MATH_4___.

Valors esperats

Abans de descriure el procés d'estimació, necessitem conéixer:

• el número esperat de transicions des de l'estat ___MATH_5___ en ___MATH_6___ i
• el número esperat de transicions des de l'estat ___MATH_7___ a l'estat ___MATH_8___ en ___MATH_9___

Per a això definim prèviament ___MATH_10___ com la provabilitat d'estar en l'estat ___MATH_11___ en l'instant ___MATH_12___ i en l'estat ___MATH_13___ en l'instant ___MATH_14___, donat una observació ___MATH_15___ i el model ___MATH_16___.

___MATH_17___

___MATH_18___

___MATH_19___

a on els valors ___MATH_20___ i ___MATH_21___ es poden calcular eficientemente en l'algoritme d'alvanç-reculada.

___MATH_22___

___MATH_23___

La figura mostra un esquema parcial dels elements necessaris per al càlcul de ___MATH_24___.

Definim també ___MATH_25___ com la provabilitat d'estar en l'estat ___MATH_26___ en l'instant ___MATH_27___,

___MATH_28___

Sumant cada ___MATH_29___ en cada instant de temps, obtenim:

• el número esperat de transicions des de l'estat ___MATH_30___ en l'observació ___MATH_31___

___MATH_32___

i fent lo mateix en cada ___MATH_33___, obtenim:

• el número esperat de transicions des de l'estat ___MATH_34___ a l'estat ___MATH_35___ en l'observació ___MATH_36___

___MATH_37___

Reestimación

El funcionament del procediment iterativo és bàsicament el següent:

1. Es partix d'un model inicial que es pot seleccionar aleatoriamente.
2. Es realisa el càlcul de les transicions i símbols d'emissió que són més provables segons el model inicial triat.
3. Es construïx un nou model en el que s'incrementa la provabilitat de les transicions i símbols determinats en el pas anterior. Per a la seqüència d'observables en qüestió, el model tindrà ara una provabilitat major que el model anterior.

Este procés d'entrenament es repetix vàries voltes fins que no existixca millora entre un model i el següent revisat.

Provabilitat d'estar en l'estat ___MATH_38___ en l'instant de temps ___MATH_39___:

___MATH_40___

___MATH_41___

Reestimación de les provabilitats de transició. El numerador representa el número esperat de transicions de ___MATH_42___ a ___MATH_43___, i el denominador representa el número esperat de transicions des de ___MATH_44___:

___MATH_45___

___MATH_46___, ___MATH_47___

Reestimación de les provabilitats d'emissió. El numerador representa el número esperat de voltes que es passa per l'estat ___MATH_48___ i s'observa ___MATH_49___, i el denominador representa el número esperat de voltes que es passa per l'estat ___MATH_50___:

___MATH_51___

___MATH_52___, ___MATH_53___