Forward Algorithm: una spiegazione pratica

Quando si studiano gli Hidden Markov Model, il Forward Algorithm viene spesso presentato come una sequenza di formule. In realtà nasce per risolvere un problema molto concreto:

quanto è probabile che una certa sequenza di osservazioni sia stata prodotta dal sistema che stiamo modellando?

Immaginiamo di osservare soltanto alcuni segnali provenienti da un sistema, senza poter vedere direttamente il suo stato interno.

Un esempio quotidiano

Supponiamo di osservare ogni mattina una persona che esce di casa.

Le osservazioni possibili sono:

• Ombrello (O)
• Nessun ombrello (N)

Lo stato reale del tempo, invece, è nascosto:

• Pioggia (P)
• Sole (S)

Noi non vediamo il meteo. Vediamo solo se la persona porta l’ombrello.

Dopo tre giorni osserviamo:

(O, O, N)

La domanda è:

Quanto è compatibile questa sequenza con il modello meteorologico che abbiamo costruito?

Il problema dell’esplosione combinatoria

Per rispondere dovremmo considerare tutti i possibili stati nascosti.

Per tre giorni abbiamo:

[math]2^3 = 8[/math] possibili sequenze:

PPP, PPS, PSP, PSS, SPP, SPS, SSP, SSS

Per ciascuna dovremmo:

• calcolare la probabilità del percorso;
• calcolare la probabilità delle osservazioni;
• moltiplicare tutto;
• sommare i risultati.

Con tre giorni è facile.

Con trenta giorni avremmo:

[math]2^{30} = 1.073.741.824[/math] percorsi.

Diventa impossibile.

L’idea geniale del Forward Algorithm

Il Forward Algorithm evita di analizzare ogni percorso separatamente.

Invece di chiedersi:

“Quali percorsi possono aver generato le osservazioni?”

si chiede:

“Qual è la probabilità complessiva di arrivare in ciascuno stato dopo aver osservato i dati fino a questo momento?”

Tutta la storia precedente viene riassunta in pochi numeri.

Questi numeri sono le quantità forward:

[math]\alpha_t(i)[/math]

che rappresentano:

la probabilità di aver osservato la sequenza fino al tempo [math]t[/math] e di trovarsi nello stato [math]i[/math].

Come ragiona l’algoritmo

Torniamo all’esempio della batteria.

Osserviamo:

(A, B, A)

dove:

• A = tensione alta
• B = tensione bassa

Dopo la prima osservazione l’algoritmo calcola:

• probabilità di essere in H
• probabilità di essere in L

tenendo conto delle probabilità iniziali e delle emissioni.

Passo successivo

Quando arriva la seconda osservazione non ricomincia da zero.

Utilizza i risultati già calcolati.

Per sapere quanto è probabile essere nello stato H al tempo successivo:

• considera tutte le strade che arrivano in H;
• somma i contributi;
• moltiplica per la probabilità di osservare il simbolo corrente.

In altre parole:

Tutti i percorsi che terminano in H
        ↓
somma delle probabilità
        ↓
emissione del simbolo osservato
        ↓
nuova probabilità forward

Un’analogia con la navigazione stradale

Immaginiamo una rete di città collegate.

Per sapere quanti modi esistono per raggiungere Milano dopo tre tappe non serve memorizzare tutti gli itinerari.

È sufficiente sapere:

• quanti percorsi arrivano oggi a Torino;
• quanti arrivano oggi a Bologna;
• quanti arrivano oggi a Genova.

Domani potremo usare questi numeri per calcolare rapidamente le nuove possibilità.

Il Forward Algorithm fa esattamente questo con le probabilità.

Perché è così importante

L’algoritmo trasforma un problema con crescita esponenziale in uno con crescita molto più contenuta.

Senza Forward:

[math]O(N^T)[/math]

dove:

• [math]N[/math] = numero di stati
• [math]T[/math] = lunghezza della sequenza

Con Forward:

[math]O(N^2 T)[/math]

Per questo motivo è possibile utilizzare gli HMM su:

• registrazioni vocali lunghe minuti;
• genomi con milioni di basi;
• dati finanziari;
• sensori industriali;
• sistemi di monitoraggio IoT.

Il Forward Algorithm non cerca lo stato nascosto più probabile.

Non cerca nemmeno il percorso nascosto migliore.

Risponde a una domanda diversa:

“Se il mondo funzionasse secondo questo modello, quanto sarebbe plausibile osservare questa sequenza di dati?”

È il primo dei tre grandi problemi degli Hidden Markov Model e rappresenta il fondamento su cui si costruiscono gli algoritmi successivi, come Viterbi e Baum-Welch.

Per questo motivo il Forward Algorithm è spesso il punto in cui si comprende davvero la forza degli Hidden Markov Model: non tenta di indovinare ciò che è nascosto, ma misura quanto bene il modello riesce a spiegare ciò che osserviamo.

Ora che abbiamo compreso l’intuizione, vediamo come applicarla a un caso reale.

Errori tipici nel calcolo del Forward Algorithm

Quando si affrontano per la prima volta gli Hidden Markov Model, alcuni errori ricorrono molto frequentemente.

Riconoscerli in anticipo aiuta a evitare risultati errati e a comprendere meglio il significato dell’algoritmo.

Errore 1 – Confondere [math]\alpha[/math] con la probabilità dello stato

Uno degli errori più comuni consiste nel pensare che

[math]\alpha_t(i)[/math]

rappresenti la probabilità di trovarsi nello stato [math]i[/math] al tempo [math]t[/math>.

Non è così.

La quantità forward rappresenta invece:

[math]\alpha_t(i) = P(O_0, \dots, O_t, q_t = i)[/math]

cioè la probabilità congiunta di:

• aver osservato tutta la sequenza fino all’istante [math]t[/math];
• trovarsi nello stato [math]i[/math] al tempo [math]t[/math].

Per ottenere la probabilità dello stato dato ciò che abbiamo osservato occorre normalizzare i valori [math]\alpha[/math]:

[math]P(q_t = i \mid O) = \frac{\alpha_t(i)}{\sum_j \alpha_t(j)}[/math]

💡 Suggerimento: [math]\alpha[/math] contiene sia l’informazione sullo stato sia quella sulle osservazioni accumulate fino a quel momento.

Errore 2 – Dimenticare la probabilità di emissione

Dopo aver calcolato la somma delle transizioni, molti studenti si fermano.

Ad esempio:

[math](0.56 \cdot 0.9) + (0.04 \cdot 0.3) = 0.516[/math]

e scrivono immediatamente:

[math]\alpha_1(H) = 0.516[/math]

Errore.

Manca ancora la probabilità che lo stato H produca l’osservazione effettivamente registrata.

Bisogna moltiplicare per:

[math]e_H(B) = 0.3[/math]

ottenendo:

[math]\alpha_1(H) = 0.516 \cdot 0.3 = 0.1548[/math]

💡 Regola pratica: ogni passo dell’algoritmo Forward termina sempre con una probabilità di emissione.

Errore 3 – Invertire righe e colonne della matrice di transizione

Supponiamo di avere:

[math]T = \begin{pmatrix} 0.9 & 0.1 \\ 0.3 & 0.7 \end{pmatrix}[/math]

Nel nostro modello:

• le righe rappresentano lo stato corrente;
• le colonne rappresentano lo stato successivo.

Quindi:

[math]T_{H \to L} = 0.1[/math]

e non [math]0.3[/math].

Invertire questa convenzione porta a risultati completamente diversi.

💡 Suggerimento: prima di iniziare i calcoli, annota sempre il significato di righe e colonne.

Errore 4 – Sommare invece di moltiplicare le probabilità

Le probabilità di eventi consecutivi devono essere moltiplicate.

Ad esempio:

[math]P(H \to H \text{ e } A) = P(H \to H) \cdot P(A \mid H)[/math]

Non:

[math]P(H \to H) + P(A \mid H)[/math]

Questo errore compare spesso quando si passa dalla teoria alle prime implementazioni in Python.

Errore 5 – Dimenticare la somma finale

L’algoritmo non termina con l’ultimo valore [math]\alpha[/math].

La probabilità della sequenza osservata è:

[math]P(O \mid \lambda) = \sum_{i} \alpha_T(i)[/math]

Nel nostro esempio:

[math]P(O \mid \lambda) = 0.111636 + 0.012504 = 0.124140[/math]

Se si considera soltanto l’ultimo valore associato allo stato H oppure L si ottiene una probabilità errata.

Un controllo rapido prima di consegnare

Prima di considerare concluso l’esercizio verifica sempre che:

✅ ogni [math]\alpha[/math] sia stato ottenuto sommando i contributi di tutti gli stati precedenti;

✅ sia stata applicata la probabilità di emissione;

✅ righe e colonne delle matrici siano state interpretate correttamente;

✅ la probabilità finale sia la somma degli [math]\alpha[/math] dell’ultimo istante;

✅ il risultato finale sia compreso tra 0 e 1.

# Esercizio 1 - HMM: problema di valutazione (forward)
# Calcolare P(O | lambda) per O = (A, B, A)

# Definizione del modello
states = ['H', 'L']                # Stati nascosti: Carica alta (H), Carica bassa (L)
obs_symbols = ['A', 'B']           # Osservazioni: Tensione alta (A), bassa (B)

# Distribuzione iniziale pi
pi = {'H': 0.8, 'L': 0.2}

# Matrice di transizione T: riga = stato corrente, colonna = stato successivo
T = {
    'H': {'H': 0.9, 'L': 0.1},
    'L': {'H': 0.3, 'L': 0.7}
}

# Matrice di emissione E: riga = stato, colonna = osservazione
E = {
    'H': {'A': 0.7, 'B': 0.3},
    'L': {'A': 0.2, 'B': 0.8}
}

# Sequenza di osservazioni
O = ['A', 'B', 'A']   # indice temporale: 0 -> A, 1 -> B, 2 -> A

# ---------- Algoritmo forward ----------
# Inizializzazione (t = 0)
alpha = []  # conterrà i dizionari alpha[t][state]

alpha0 = {}
for s in states:
    alpha0[s] = pi[s] * E[s][O[0]]
alpha.append(alpha0)

print("t = 0")
for s in states:
    print(f"  alpha[{s}] = {alpha0[s]:.6f}")

# Induzione (t = 1, 2)
for t in range(1, len(O)):
    prev_alpha = alpha[t-1]
    curr_alpha = {}
    for curr_state in states:
        # Somma su tutti gli stati precedenti
        total = 0.0
        for prev_state in states:
            total += prev_alpha[prev_state] * T[prev_state][curr_state]
        curr_alpha[curr_state] = total * E[curr_state][O[t]]
    alpha.append(curr_alpha)
    
    print(f"\nt = {t}  (osservazione {O[t]})")
    for s in states:
        print(f"  alpha[{s}] = {curr_alpha[s]:.6f}")

# Termine: probabilità totale = somma degli alpha all'ultimo tempo
prob_O = sum(alpha[-1].values())
print(f"\nP(O | lambda) = {prob_O:.6f}")

t = 0
  alpha[H] = 0.560000
  alpha[L] = 0.040000

t = 1  (osservazione B)
  alpha[H] = 0.154800
  alpha[L] = 0.067200

t = 2  (osservazione A)
  alpha[H] = 0.111636
  alpha[L] = 0.012504

P(O | lambda) = 0.124140

L’output riproduce fedelmente i calcoli manuali dell’esercizio.

Ecco il significato di ogni blocco:

t = 0 (osservazione A)

• [math]\alpha[H] = 0.56[/math] = probabilità congiunta che al tempo 0 lo stato sia H e si osservi A.
  Calcolata come [math]\pi(H) \cdot e_H(A) = 0.8 \cdot 0.7[/math].
• [math]\alpha[L] = 0.04[/math] = probabilità congiunta che lo stato sia L e si osservi A ([math]0.2 \cdot 0.2[/math]).

La somma [math]0.56 + 0.04 = 0.60[/math] rappresenta la probabilità di osservare A al tempo 0 (marginalizzando sugli stati), ma in forward la usiamo solo come passo intermedio.

t = 1 (osservazione B)

Vengono aggiornate le [math]\alpha[/math] usando la ricorrenza:

[math]\alpha_1(j) = \left[ \sum_{i} \alpha_0(i) \cdot T_{i \to j} \right] \cdot e_j(B)[/math]

• [math]\alpha[H] = 0.1548[/math].
  Spiegazione: la probabilità di arrivare in H al tempo 1 viene da H→H ([math]0.56 \cdot 0.9 = 0.504[/math]) o da L→H ([math]0.04 \cdot 0.3 = 0.012[/math]). Totale [math]0.516[/math]. Moltiplicato per [math]e_H(B) = 0.3 \to 0.1548[/math].
• [math]\alpha[L] = 0.0672[/math].
  Proveniente da H→L ([math]0.56 \cdot 0.1 = 0.056[/math]) e L→L ([math]0.04 \cdot 0.7 = 0.028[/math]) → somma [math]0.084[/math], per [math]e_L(B) = 0.8 \to 0.0672[/math].

La somma [math]0.1548 + 0.0672 = 0.2220[/math] è la probabilità della sottosequenza (A,B). Si noti che è più bassa di 0.60 perché l’osservazione B è meno probabile quando lo stato è H, e H è ancora favorito.

t = 2 (osservazione A)

Allo stesso modo:

• [math]\alpha[H] = 0.111636[/math] – calcolata a partire dalle [math]\alpha_1[/math] con le transizioni e poi [math]e_H(A) = 0.7[/math].
• [math]\alpha[L] = 0.012504[/math] – con [math]e_L(A) = 0.2[/math].

Termine
[math]P(O \mid \lambda) = 0.124140[/math] = somma delle [math]\alpha[/math] allo stato finale.
Questo numero è la verosimiglianza della sequenza (A,B,A) dato il modello.

💡 Osservazioni:

La probabilità è relativamente bassa (circa il 12,4%) perché la sequenza A,B,A non è molto tipica per questo modello: lo stato H (più probabile inizialmente) emette A con alta probabilità (0.7) ma B con bassa probabilità (0.3); inoltre, per passare a L e tornare a H servono transizioni meno probabili. L’algoritmo tiene conto di tutti i possibili percorsi nascosti in modo efficiente.

Confronta con il calcolo esaustivo: avremmo dovuto sommare i prodotti di probabilità su tutti gli 8 percorsi nascosti. Il forward fa la stessa cosa in [math]O(L \cdot N^2)[/math] operazioni, evitando l’esplosione combinatoria.

L’output mostra come ogni [math]\alpha(t)[/math] incorpori la storia delle osservazioni fino a quel momento. È la base anche per il filtraggio (stima dello stato corrente dato il passato).