Algorisme avenç-retrocés

L'esquema mostra els estats i les probabilitats necessàries per al càlcul de α4 (3)

L'algorisme avenç-retrocés és un algorisme d'inferència per a models de Markov ocults que calcula els marginals posteriors de totes les variables d'estat ocultes donades una seqüència d'observacions/emissions. $o_{1:T}:=o_{1},\dots ,o_{T}$, és a dir, calcula, per a totes les variables d'estat ocultes $X_{t}\in \{X_{1},\dots ,X_{T}\}$, la distribució $P(X_{t}\ |\ o_{1:T})$. Aquesta tasca d'inferència normalment s'anomena suavització. L'algorisme fa ús del principi de programació dinàmica per calcular de manera eficient els valors necessaris per obtenir les distribucions marginals posteriors en dos passos. La primera passada va endavant en el temps mentre que la segona va enrere en el temps; d'aquí el nom d'algoritme endavant-enrere.El terme algorisme endavant-enrere també s'utilitza per referir-se a qualsevol algorisme pertanyent a la classe general d'algorismes que operen en models de seqüència d'una manera avançada-enrere. En aquest sentit, les descripcions de la resta d'aquest article es refereixen només a una instància específica d'aquesta classe.

En la primera passada, l'algoritme cap endavant-enrere calcula un conjunt de probabilitats cap endavant que proporcionen, per a tots els $t\in \{1,\dots ,T\}$, la probabilitat d'acabar en un estat determinat donat el primer $t$ observacions en la seqüència, és a dir $P(X_{t}\ |\ o_{1:t})$. En el segon pas, l'algorisme calcula un conjunt de probabilitats endarrerides que proporcionen la probabilitat d'observar les observacions restants donat qualsevol punt de partida. $t$, és a dir $P(o_{t+1:T}\ |\ X_{t})$. Aquests dos conjunts de distribucions de probabilitat es poden combinar per obtenir la distribució sobre estats en qualsevol moment específic donat tota la seqüència d'observació:

$P(X_{t}\ |\ o_{1:T})=P(X_{t}\ |\ o_{1:t},o_{t+1:T})\propto P(o_{t+1:T}\ |\ X_{t})P(X_{t}|o_{1:t})$

L'últim pas es desprèn d'una aplicació de la regla de Bayes i la independència condicional de $o_{t+1:T}$ i $o_{1:t}$ donat $X_{t}$ .

Tal com s'ha indicat anteriorment, l'algorisme inclou tres passos:

1. càlcul de probabilitats anticipades
2. calcular probabilitats endarrerides
3. calcular valors suavitzats.

Els passos cap endavant i cap enrere també es poden anomenar "passa de missatge cap endavant" i "passa de missatge cap enrere": aquests termes es deuen al pas de missatges utilitzat en els enfocaments generals de propagació de creences. A cada observació de la seqüència, es calculen les probabilitats que s'utilitzaran per als càlculs a la següent observació. El pas de suavització es pot calcular simultàniament durant el pas enrere. Aquest pas permet que l'algoritme tingui en compte qualsevol observació passada de la sortida per calcular resultats més precisos.

L'algoritme cap endavant-enrere es pot utilitzar per trobar l'estat més probable per a qualsevol moment. No obstant això, no es pot utilitzar per trobar la seqüència d'estats més probable (vegeu algorisme de Viterbi).