Algoritmo forward-backward

L'algoritmo forward–backward è un algoritmo inferenziale per modelli di Markov nascosti che calcola la probabilità a posteriori marginale di tutte le variabili di stato nascoste data una successione di osservazioni $o_{1:t}:=o_{1},\dots ,o_{t}$, cioè essa calcola, per tutte le variabili di stato nascoste $X_{k}\in \{X_{1},\dots ,X_{t}\}$, la distribuzione $P(X_{k}\ |\ o_{1:t})$. Questo compito inferenziale è solitamente detto smoothing. L'algoritmo fa un uso del principio di programmazione dinamica in due passaggi per calcolare efficientemente i valori che sono richiesti per ottenere le distribuzioni marginali a posteriori. Il primo passaggio va in avanti nel tempo mentre il secondo va indietro; da qui il nome forward–backward, avanti-indietro, dell'algoritmo.

Il termine algoritmo forward–backward è usato come riferimento ad un algoritmo appartenente alla classe generica degli algoritmi che operano su successioni di modelli in maniera alternata relativamente al parametro adottato per l'evoluzione, generalmente il tempo. In questo senso, il resto di questa voce fa riferimento all'algoritmo nella sua veste generica e non ad un particolare esempio di questa classe.

Panoramica

Come primo passo, l'algoritmo forward–backward calcola un insieme di probabilità "in avanti" che fornisce, per tutti i $k\in \{1,\dots ,t\}$, la probabilità di finire in qualche stato particolare date le prime $k$ osservazioni nella successione, ossia $P(X_{k}\ |\ o_{1:k})$. Come secondo passo, l'algoritmo calcola un insieme di probabilità "all'indietro" che fornisce la probabilità di osservare le osservazioni rimanenti dato qualche punto di partenza $k$, ossia $P(o_{k+1:t}\ |\ X_{k})$. Questi due insiemi di distribuzioni di probabilità possono allora essere combinati per ottenere la distribuzione sopra gli stati in corrispondenza di qualche specifico punto nel tempo data l'intera successione di osservazioni:

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

dove l'ultimo passaggio segue dall'applicazione della regola di Bayes e dall'indipendenza condizionale di $o_{k+1:t}$ e di $o_{1:k}$ dato $X_{k}$.

Come sopra delineato, l'algoritmo implica tre passaggi:

1. calcolo delle probabilità "in avanti"
2. calcolo delle probabilità "all'indietro"
3. calcolo dei valori essenziali, o smoothed values, ossia dei valori che riassumono l'andamento principale o generale dell'insieme dei valori o di una parte di esso.

I passi in avanti e all'indietro possono essere chiamati anche "passaggio di messaggio in avanti" e "passaggio di messaggio all'indietro) - questi termini sono generalmente legati al passaggio di messaggio usato negli approcci di propagazione di credenza (belief propagation). Ad ogni singola osservazione nella successione, vengono calcolate le probabilità che sono impiegate per il calcolo all'osservazione successiva. Durante il passaggio all'indietro può essere eseguito anche il calcolo dei valori essenziali (smoothing step). Questo passo permette all'algoritmo di tener conto dei risultati precedenti per calcolare in maniera più accurata quelli nuovi.

L'algoritmo forward–backward può essere usato per trovare lo stato più probabile per qualsiasi punto nel tempo. Tuttavia non può essere usato per trovare la successione di stati più probabile (cfr. l'algoritmo di Viterbi).

Probabilità in avanti

La seguente descrizione utilizzerà matrici di valori di probabilità piuttosto che distribuzioni di probabilità, anche se in generale l'algoritmo forward-backward può essere applicato a modelli di probabilità sia continui che discreti.

Trasformiamo le distribuzioni di probabilità collegate ad un dato modello di Markov nascosto in notazione matriciale come segue. Le probabilità di transizione $\mathbf {P} (X_{t}\mid X_{t-1})$ di una data variabile casuale $X_{t}$, rappresentante tutti gli stati possibili nel modello di Markov nascosto, saranno rappresentate mediante la matrice $\mathbf {T}$ dove l'indice di riga, i, rappresenterà lo stato di partenza e l'indice di colonna, j, lo stato di arrivo. L'esempio sotto rappresenta un sistema dove la probabilità di rimanere nel medesimo stato dopo ogni passo è del 70% e quella di transizione ad un altro stato è del 30%. La matrice di transizione è:

$\mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

In un tipico modello di Markov noi moltiplicheremmo un vettore di stato per la matrice sopra per ottenere le probabilità per i successivi stati. In un modello di Markov nascosoto lo stato è sconosciuto e quello che osserviamo sono invece eventi associati con stati possibili. Una matrice evento della forma:

$\mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}$

fornisce le probabilità di osservare degli eventi a partire da uno stato particolare. Nell'esempio precedente l'evento 1 sarà osservato il 90% del tempo se partiamo dallo stato 1 mentre l'evento 2 ha un 10% di probabilità di manifestarsi partendo sempre dallo stato 1. Al contrario, l'evento 1 sarà osservato solo il 20% del tempo se partiamo dallo stato 2 e l'evento 2 ha l'80% di probabilità di manifestarsi. Dato un vettore di stato ($\mathbf {\pi }$), la probabilità di osservare l'evento j è allora:

$\mathbf {P} (O=j)=\sum _{i}\pi _{i}b_{i,j}$

Questo può essere rappresentato in forma matriciale moltiplicando il vettore di stato ($\mathbf {\pi }$) per la matrice di osservazione ($\mathbf {O_{1}}$) contenente solo elementi lungo la diagonale. Ogni elemento è la probabilità dell'evento osservato dato ogni stato. Continuando l'esempio precedente, un'osservazione dell'evento 1 sarebbe:

$\mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}$

Questo permette di calcolare le probabilità associate alla transizione ad un nuovo stato, ed osservare un dato evento come:

$\mathbf {f_{0:1}} =\mathbf {\pi } \mathbf {T} \mathbf {O_{1}}$

Il risultante vettore di probabilità contiene elementi che indicano la probabilità di transizione ad ogni stato ossia l'osservazione di un dato evento. Questo processo può essere ulteriormente portato avanti con osservazioni aggiuntive usando:

$\mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{t}}$

Questo valore è il vettore di probabilità in avanti. La sua i-esima componente fornisce:

$\mathbf {f_{0:t}} (i)=\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } )$

Solitamente il vettore di probabilità non rimane normalizzato ad ogni passaggio in modo che le sue componenti sommino ad 1. Un fattore di scala è perciò introdotto ad ogni passaggio in modo che:

$\mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\ \mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}}$

dove $\mathbf {{\hat {f}}_{0:t-1}}$ rappresenta il vettore scalato dal precedente passaggio e $c_{t}$ rappresenta il fattore di scala grazie al quale le componenti del vettore risultante sommano ad 1. Il prodotto dei fattori di scala è la probabilità totale di osservare gli eventi dati a prescindere dagli stati finali:

$\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } )=\prod _{s=1}^{t}c_{s}$

Questo permette di interpretare il vettore di probabilità scalato come:

$\mathbf {{\hat {f}}_{0:t}} (i)={\frac {\mathbf {f_{0:t}} (i)}{\prod _{s=1}^{t}c_{s}}}={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } )}{\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } )}}=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{t},\mathbf {\pi } )$

Troviamo perciò che il prodotto dei fattori di scala ci fornisce la probabilità totale di osservare una data successione fino al tempo t e che il vettore di probabilità scalato ci fornisce la probabilità di essere in ogni stato in quell'istante.

Probabilità all'indietro

Una procedura simile può essere costruita per trovare probabilità all'indietro. Queste forniscono le probabilità:

$\mathbf {b_{t:T}} (i)=\mathbf {P} (o_{t+1},o_{t+2},\dots ,o_{T}|X_{t}=x_{i})$

Questo vale a dire che assumendo di partire in uno stato particolare ($X_{t}=x_{i}$), siamo ora interessati alla probabilità di osservare tutti i futuri eventi da questo stato. Poiché lo stato iniziale è assunto come dato (cioè la probabilità a priori di questo stato è uguale al 100%), cominciamo con:

$\mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}$

Si noti che ora stiamo impiegando un vettore colonna mentre le probabilità in avanti sfruttano vettori riga. Possiamo allora lavorare all'indietro usando:

$\mathbf {b_{t-1:T}} =\mathbf {T} \mathbf {O_{t}} \mathbf {b_{t:T}}$

Nonostante potessimo normalizzare questo vettore in modo tale che le sue componenti sommino ad 1, questo solitamente non viene fatto. Notando che ogni componente contiene la probabilità della successione di eventi futuri dato uno stato iniziale particolare, normalizzare questo vettore sarebbe equivalente ad applicare il teorema di Bayes per trovare la verosimiglianza di ogni stato iniziale dati gli eventi futuri (assumendo distribuzioni a priori uniformi per il vettore di stato finale). Tuttavia, è più comune scalare questo vettore usando le medesime costanti $c_{t}$ usate nei calcoli della probabilità in avanti. $\mathbf {b_{T:T}}$ non è scalato, ma le operazioni successive usano:

$\mathbf {{\hat {b}}_{t-1:T}} =c_{t}^{-1}\mathbf {T} \mathbf {O_{t}} \mathbf {{\hat {b}}_{t:T}}$

dove $\mathbf {{\hat {b}}_{t:T}}$ rappresenta il precedente vettore scalato. Questo risultato significa che il vettore di probabilità scalato e collegato alle probabilità all'indietro da:

$\mathbf {{\hat {b}}_{t:T}} (i)={\frac {\mathbf {b_{t:T}} (i)}{\prod _{s=t+1}^{T}c_{s}}}$

Questo è utile in quanto ci permette di trovare la probabilità totale di essere in ogni stato ad un certo istante, t, moltiplicando tramite questi valori:

$\mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{T},\mathbf {\pi } )={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{T},X_{t}=x_{i}|\mathbf {\pi } )}{\mathbf {P} (o_{1},o_{2},\dots ,o_{T}|\mathbf {\pi } )}}={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{\prod _{s=1}^{T}c_{s}}}=\mathbf {{\hat {f}}_{0:t}} (i)\cdot \mathbf {{\hat {b}}_{t:T}} (i)$

Per comprendere questo, notiamo che $\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)$ fornisce la probabilità di osservare gli eventi dati in una maniera che passa attraverso lo stato $x_{i}$ al tempo t. Questa probabilità include le probabilità in avanti coprenti tutti gli eventi fino al tempo t così come le probabilità all'indietro che includono tutti gli eventi futuri. Questo è il numeratore che stavamo cercando per la nostra equazione, e lo dividiamo per la probabilità totale della successione di osservazioni per normalizzarlo ed estraiamo solamente la probabilità per cui $X_{t}=x_{i}$. Questi valori sono chiamati talvolta "valori riassuntivi" (smoothed values) in quanto essi combinano le probabilità in avanti e indietro per calcolare una probabilità finale.

I valori $\mathbf {\gamma _{t}} (i)$ forniscono perciò la probabilità di essere in ogni stato al tempo t. Come tali essi sono utili per determinare lo stato più probabile in qualsiasi istante di tempo. Si dovrebbe notare però che il termine "stato più probabile" è in qualche modo ambiguo. Mentre lo stato più probabile è il più favorevole ad essere quello corretto in un dato punto, la successione di singoli stati probabili non è detto che sia la successione più probabile. Questo perché le probabilità per ciascun punto sono calcolate indipendentemente da ogni altro. Essi non tengono da conto le probabilità di transizione tra stati, ed è perciò possibile ottenere stati in due tempi (t e t+1) che sono entrambi più probabili in quegli istanti ma che hanno una probabilità veramente piccola di accadere assieme, cioè $\mathbf {P} (X_{t}=x_{i},X_{t+1}=x_{j})\neq \mathbf {P} (X_{t}=x_{i})\mathbf {P} (X_{t+1}=x_{j})$. La più probabile successione di stati che produce una successione di osservazioni può essere trovata usando l'algoritmo di Viterbi.

Esempio

Questo esempio considera come riferimento il mondo degli ombrelli in Russel & Norvig 2003 pp. 540 nel quale noi vorremmo inferire le condizioni atmosferiche data l'osservazione di un uomo che porta o meno con sé un ombrello. Assumiamo due possibili stati per le condizioni atmosferiche: stato 1 = pioggia, stato 2 = nessuna pioggia. Assumiamo che le condizioni atmosferiche abbiano un 70% di probabilità di rimanere invariate durante ogni giorno e un 30% di probabilità di cambiare. Le probabilità di transizione sono allora:

$\mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

Assumiamo inoltre che ognuno dei due stati delle condizioni atmosferiche generi due eventi: evento 1 = ombrello, evento 2 = nessun ombrello. Le probabilità condizionate che questi eventi si manifestino in ognuno degli stati sono date dalla matrice di probabilità:

$\mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}$

Supponiamo allora di osservare la seguente successione di eventi: {ombrello, ombrello, nessun ombrello, ombrello, ombrello}. Questa verrà rappresentata nei nostri calcoli come:

$\mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{2}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{3}} ={\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}~~\mathbf {O_{4}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{5}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}$

Si noti che l'elemento $\mathbf {O_{3}}$ differisce dagli altri a causa dell'osservazione "nessun ombrello".

Per calcolare le probabilità in avanti cominciamo con:

$\mathbf {f_{0:0}} ={\begin{pmatrix}0.5&0.5\end{pmatrix}}$

il quale è il nostro vettore di stato a priori indicante che noi non conosciamo lo stato delle condizioni atmosferiche prima delle nostre osservazioni. Mentre il vettore di stato dovrebbe essere dato come un vettore riga, noi useremo la trasposta della matrice in modo tale che i calcoli seguenti sia più facilmente leggibili. I nostri calcoli allora sono scritti nella forma:

$(\mathbf {{\hat {f}}_{0:t}} )^{T}=c^{-1}\mathbf {O_{t}} (\mathbf {T} )^{T}(\mathbf {{\hat {f}}_{0:t-1}} )^{T}$

invece che

$\mathbf {{\hat {f}}_{0:t}} =c^{-1}\mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}}$

Si noti che anche la matrice di trasformazione è trasposta, ma nel nostro esempio la trasposta è uguale alla matrice originale. Eseguendo questi calcoli e normalizzando i risultati otteniamo:

$(\mathbf {{\hat {f}}_{0:1}} )^{T}=c_{1}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}=c_{1}^{-1}{\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:2}} )^{T}=c_{2}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}=c_{2}^{-1}{\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:3}} )^{T}=c_{3}^{-1}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}=c_{3}^{-1}{\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:4}} )^{T}=c_{4}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}=c_{4}^{-1}{\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:5}} )^{T}=c_{5}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}=c_{5}^{-1}{\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}$

Per le probabilità all'indietro cominciamo con:

$\mathbf {b_{5:5}} ={\begin{pmatrix}1.0\\1.0\end{pmatrix}}$

Siamo quindi in grado di calcolare (usando le osservazioni in ordine inverso e normalizzando con costanti differenti):

$\mathbf {{\hat {b}}_{4:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.6900\\0.4100\end{pmatrix}}={\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}$

$\mathbf {{\hat {b}}_{3:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4175\\0.2215\end{pmatrix}}={\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}$

$\mathbf {{\hat {b}}_{2:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1289\\0.2138\end{pmatrix}}={\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}$

$\mathbf {{\hat {b}}_{1:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.2745\\0.1889\end{pmatrix}}={\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}$

$\mathbf {{\hat {b}}_{0:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}$

Infine, calcoleremo i valori di probabilità smoothed. Anche questo risultato deve essere scalato in modo tale che le sue componenti sommino ad 1. Questo in quanto non scaliamo le probabilità all'indietro con le $c_{t}$ precedentemente trovate. Perciò i precedenti vettori di probabilità all'indietro rappresentano in effetti la verosimiglianza di ogni stato al tempo t date le osservazioni future. Poiché questi vettori sono proporzionali alle effettive probabilità all'indietro, il risultato deve essere scalato ancora una volta.

$(\mathbf {\gamma _{0}} )^{T}=\alpha {\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}\times {\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}=\alpha {\begin{pmatrix}0.3235\\0.1765\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}$

$(\mathbf {\gamma _{1}} )^{T}=\alpha {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}\times {\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.4846\\0.0741\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}$

$(\mathbf {\gamma _{2}} )^{T}=\alpha {\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}\times {\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.3324\\0.0728\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}$

$(\mathbf {\gamma _{3}} )^{T}=\alpha {\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}\times {\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1246\\0.2806\end{pmatrix}}={\begin{pmatrix}0.3075\\0.6925\end{pmatrix}}$

$(\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\times {\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4584\\0.1003\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}$

$(\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\times {\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}$

Si noti che il valore di $\mathbf {\gamma _{0}}$ è uguale a $\mathbf {{\hat {b}}_{0:5}}$ e che $\mathbf {\gamma _{5}}$ è uguale a $\mathbf {{\hat {f}}_{0:5}}$. Naturalmente questo consegue perché sia $\mathbf {{\hat {f}}_{0:5}}$ che $\mathbf {{\hat {b}}_{0:5}}$ iniziano con distribuzioni a priori uniformi sopra i vettori di stato iniziale e finale rispettivamente e tengono d'acconto di tutte le osservazioni. Tuttavia, $\mathbf {\gamma _{0}}$ sarà solo uguale a $\mathbf {{\hat {b}}_{0:5}}$ quando il nostro vettore di stato iniziale rappresenta una distribuzione a priori uniforme (cioè una con tutti gli elementi identici tra loro). Quando questo non è il caso, è necessario combinare $\mathbf {{\hat {b}}_{0:5}}$ con il vettore di stato iniziale per trovare lo stato iniziale più probabile. Perciò scopriamo che le probabilità in avanti per sé stesse sono sufficienti per calcolare lo stato finale più probabile. Analogamente, le probabilità all'indietro possono essere combinate con il vettore di stato iniziale per fornire lo stato iniziale più probabile date le osservazioni. Le probabilità in avanti e all'indietro richiedono solo di essere combinate per poter inferire gli stati più probabili tra i punti iniziale e finale.

I calcoli sopra rivelano che lo stato delle condizioni atmosferiche più probabile per ogni giorno, eccetto che per il terzo, è "pioggia". Inoltre ci dicono di più, in quanto tali calcoli ora ci forniscono un modo per quantificare le probabilità di ogni stato ad istanti differenti. Maggiormente importante, il nostro valore a $\mathbf {\gamma _{5}}$ quantifica la nostra conoscenza del vettore di stato alla fine della successione di osservazioni. Possiamo usarlo infatti per predire la probabilità dei vari stati delle condizioni atmosferiche di domani così come la probabilità di osservare un ombrello.

Prestazioni

La procedura più diretta per la soluzione di questo problema è la generazione di tutte le possibili successioni di stati $N^{T}$ e il calcolo della probabilità congiunta di ogni successione di stati con la serie osservata di eventi. Questo approccio ha complessità temporale $O(T\cdot N^{T})$, dove $T$ è la lunghezza delle successioni e $N$ è il numero di simboli nell'alfabeto dello stato. Operando in questo modo i problemi reali diventano intrattabili in quanto il numero di possibili successioni di nodi nascosti tipicamente è estremamente elevato. Tuttavia, l'algoritmo di forward–backward ha complessità temporale $O(N^{2}T)\,$.

Sono noti vari miglioramenti dell'algoritmo di forward–backward che permettono al calcolo di collocarsi in uno spazio costante. Inoltre, nel tempo sono stati sviluppati algoritmi per calcolare efficientemente $\mathbf {f_{0:t+1}}$ tramite uno smoothing in linea (online smoothing) dei dati come l'algoritmo FLS (fixed-lag smoothing) Russel & Norvig 2003 pp. 552.

Pseudo-codice

ForwardBackward(guessState, sequenceIndex):
    if sequenceIndex is past the end of the sequence, return 1
    if (guessState, sequenceIndex) has been seen before, return saved result
    result = 0
    for each neighboring state n:
        result = result + (transition probability from guessState to n given observation element at sequenceIndex)
                        * ForwardBackward(n, sequenceIndex+1)
    save result for (guessState, sequenceIndex)
    return result

Esempio in Python

Dato il modello di Markov nascosto (come nell'algoritmo di Viterbi) qui rappresentato nel linguaggio di programmazione Python:

states = ('Healthy', 'Fever')
end_state = 'E'
 
observations = ('normal', 'cold', 'dizzy')
 
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
 
transition_probability = {
   'Healthy' : {'Healthy': 0.69, 'Fever': 0.3, 'E': 0.01},
   'Fever' : {'Healthy': 0.4, 'Fever': 0.59, 'E': 0.01},
   }
 
emission_probability = {
   'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
   'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
   }

Possiamo scriverne un'implementazione tipo questa:

def fwd_bkw(x, states, a_0, a, e, end_st):
    L = len(x)

    fwd = []
    # Run forward
    for i, x_i in enumerate(x):
        f_curr = {}
        for st in states:
            if i == 0:
                # Initialize base fwd cases
                prev_f_sum = a_0[st]
            else:
                prev_f_sum = sum(f_prev[k]*a[k][st] for k in states)

            f_curr[st] = e[st][x_i] * prev_f_sum

        fwd.append(f_curr)
        f_prev = f_curr

    p_fwd = sum(f_curr[k]*a[k][end_st] for k in states)

    bkw = []
    # Run bkw
    for i, x_i_plus in enumerate(reversed(x[1:]+(None,))):
        b_curr = {}
        for st in states:
            if i == 0:
                # Initialize base bkw cases
                b_curr[st] = a[st][end_st]
            else:
                b_curr[st] = sum(a[st][l]*e[l][x_i_plus]*b_prev[l] for l in states)

        bkw.insert(0,b_curr)
        b_prev = b_curr

    p_bkw = sum(a_0[l] * e[l][x[0]] * b_curr[l] for l in states)

    posterior = {}
    for st in states:
        posterior[st] = [fwd[i][st]*bkw[i][st]/p_fwd for i in xrange(L)]

    assert p_fwd == p_bkw
    return fwd, bkw, posterior

La funzione fwd_bkw ammette i seguenti argomenti: x è la successione di osservazioni, ad esempio ['normal', 'cold', 'dizzy']; states è l'insieme degli stati nascosti; a_0 è la probabilità iniziale; a sono le probabilità di transizione; ed e sono le probabilità di emissione ossia di finire un certo stato.

Per mantenere semplice il codice, assumiamo che la successione di osservazioni x sia non vuota e che le componenti a[i][j] ed e[i][j] siano definite per tutti gli stati i,j.

Nell'esempio l'algoritmo forward-backward è impiegato come segue:

def example():
    return fwd_bkw(observations,
                   states,
                   start_probability,
                   transition_probability,
                   emission_probability,
                   end_state)
for line in example():
    print ' '.join(map(str, line))

Bibliografia

• Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286, February 1989. 10.1109/5.18626
• Lawrence R. Rabiner, B. H. Juang, An introduction to hidden Markov models, in IEEE ASSP Magazine, gennaio 1986, pp. 4–15.
• Eugene Charniak, Statistical Language Learning, Cambridge, Massachusetts, MIT Press, 1993, ISBN 978-0-262-53141-2.
• Stuart Russell and Peter Norvig, Artificial Intelligence A Modern Approach 2nd Edition, Upper Saddle River, New Jersey, Pearson Education, 2003, ISBN 0-13-080302-2.

Voci correlate

• algoritmo di Baum-Welch
• algoritmo di Viterbi
• algoritmo BCJR

Collegamenti esterni

• An interactive spreadsheet for teaching the forward–backward algorithm (spreadsheet and article with step-by-step walk-through)
• Tutorial of hidden Markov models including the forward–backward algorithm, su cs.brown.edu.
• Collection of AI algorithms implemented in Java (including HMM and the forward–backward algorithm)