Algoritme d'alvanç-reculada

Introducció

Un dels problemes bàsics dels Models Amagats de Márkov és el càlcul de la provabilitat d'una seqüència d'observables $O=(o_1,o_2,\dots ,o_T)$ dau un model $\mu =(\pi ,A,B)$. L'objectiu és per tant calcular eficientemente $P(O|\mu )$.

Provabilitat d'una seqüència $S$ d'estats

Supongam una seqüència d'estats $S=(q_1,q_2,\dots ,q_T)$. La provabilitat d'esta seqüència és:

$P(S|\mu )={\pi }_{q_1}{a}_{q_1{q}_2}{a}_{q_2{q}_3}\dots a_{q_{T-1}{q}_T}$

Provabilitat d'una seqüència d'observables $O$ donada una seqüència d'estats $S$

La provabilitat d'observar $O=(o_1,o_2,\dots ,o_T)$ quan es dona precisament esta seqüència d'estats $S$ és:

$P(O|S,\mu )=\prod _{t=1}^{T}P(o_t|q_t,\mu )$

Cada $P(o_t|q_t,\mu )$ correspon en el valor de $b_{q_t}(o_t)$

Provabilitat d'una seqüència d'observables $O$ dau un model $\mu$

Per tant, per a obtindre la provabilitat d'una seqüència $O$ d'observables donat un model $\mu$, deuríem calcular la provabilitat de $O$ per a cada una de les seqüències possibles $S$.

$P(O|\mu )={\sum }^{S}P(S|\mu )P(O|S,\mu )$

El càlcul de $P(O|\mu )$ tal i com es mostra és impracticable; només per a $10$ estats i $10$ observacions seria necessari realisar de l'orde de $10^{11}$ operacions. Per a reduir esta complexitat s'ampren estratègies de programació dinàmica com els algoritmes forward i backward.

Es recomana revisar la formalisació habitual d'un Model Amagat de Márkov per a comprendre cada u dels elements en la formulació d'estos dos procediments.

Procediment cap a avant

Càlcul de ${\alpha }_t(i)$

Considerem la variable ${\alpha }_t(i)$ com:

${\alpha }_t(i)=P(o_1,o_2,\dots ,o_t,q_t=i|\mu )$

Donat el model $\mu$, ${\alpha }_t(i)$ és la provabilitat d'observar $o_1,o_2,\dots ,o_t$ i estar en l'instant de temps $t$ en l'estat $i$.

Càlcul cap a avant de la provabilitat d'una seqüència d'observacions.

Inicialización

${\alpha }_1(i)={\pi }_i{b}_i(o_1),$

$1\le i\le N$

Recurrencia

${\alpha }_{t+1}(j)=\left[\sum _{i=1}^N{\alpha }_t(i)a_{ij}\right]b_j(o_{t+1})$

$t=1,2,\dots ,T-1$, $1\le j\le N$

Terminació

$P(O|\mu )=\sum _{i=1}^N{\alpha }_T(i)$

Eixemple de càlcul de ${\alpha }_4(3)$

L'esquema mostra els estats i provabilitats necessàries per al càlcul de ${\alpha }_4(3)$:

Algoritme forward

${\alpha }_4(3)=\left[\sum _{i=1}^5{\alpha }_3(i)a_{i3}\right]b_3(o_4)$