Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto

Modello di Markov nascosto, i tre problemi secondo Rabiner, algoritmo forward, algoritmo di Viterbi, decodifica a posteriori e algoritmo di Baum-Welch — su un casinò che di tanto in tanto sostituisce di nascosto il dado con uno truccato.

14 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 39 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Nella parte precedente vedevamo lo stato della catena: oggi c’è il sole, domani piove. Spesso però ne vediamo solo gli effetti. Un microfono capta un’onda sonora, non la parola che l’ha prodotta. Un sequenziatore legge le lettere del DNA, non il punto in cui comincia un gene. E al casinò vediamo che numero è uscito, non con quale dado sta lanciando il croupier. I modelli di Markov nascosti sono catene i cui stati non vediamo — insieme agli algoritmi che permettono comunque di capire che cosa succede all’interno. Per decenni il riconoscimento vocale si è basato su di loro.

Questa parte prosegue l’articolo Catene di Markov.

1. Il casinò disonesto

Un classico esempio da manuale (Durbin et al., 1998): il croupier lancia un dado onesto oppure uno truccato, sul quale il sei esce con probabilità 1/2 e ciascuno degli altri numeri con 1/10. Dopo ogni lancio, con probabilità 0,05 sostituisce il dado onesto con quello truccato e con probabilità 0,1 rimette quello onesto al posto del truccato. Lo scambio non lo vediamo. Vediamo solo una serie di numeri — nel nostro esperimento 300 lanci, che cominciano così:

163665521623524236522511663566613666222461626262162666626516…

Ci chiediamo: qui si gioca onestamente? E se no, quando esattamente era in gioco il dado truccato?

2. Modello di Markov nascosto

Definizione — modello di Markov nascosto

Un modello di Markov nascosto (HMM) λ = (π, A, B) ha stati nascosti 1, …, N e simboli osservabili 1, …, M:

• gli stati nascosti X₁, X₂, … formano una catena di Markov con distribuzione iniziale π e matrice di transizione A, a_ij = P(X_t+1 = j | X_t = i);
• in ogni istante lo stato X_t = i genera un’osservazione O_t secondo le probabilità di emissione b_i(o) = P(O_t = o | X_t = i), indipendentemente da tutto il resto.

Dalla definizione segue quanto è probabile una particolare «storia»: una sequenza di dadi x = (x₁, …, x_T) insieme ai lanci O = (O₁, …, O_T).

P(x, O | λ) = π_x1 b_x1(O₁) · ∏_t=2^T a_{xt−1 xt} b_xt(O_t)

π_x1

il primo dado non ha un predecessore da cui ci si sia passati — la sua probabilità la dà la distribuzione iniziale

a_{xt−1 xt}

ogni dado successivo dipende solo da quello precedente (proprietà di Markov), quindi per ogni passo basta un solo numero della matrice A

b_xt(O_t)

il lancio dipende solo dal dado con cui si sta lanciando in quel momento — prendiamo la probabilità del numero effettivamente uscito

∏_t=2^T

in generale si moltiplicherebbero probabilità condizionate a tutto il passato (regola della catena); le due ipotesi di indipendenza della definizione le riducono a questi numeri locali, ed è per questo che il tutto è un semplice prodotto

Esempio — due storie dei primi tre lanci

La nostra serie comincia con i lanci 1, 6, 3. Indichiamo con O il dado onesto e con T quello truccato. La storia «tre volte truccato»:

P(TTT, 1, 6, 3) = 0,5 · 0,1 · 0,9 · 0,5 · 0,9 · 0,1 = 0,002025,

la storia «tre volte onesto»:

P(OOO, 1, 6, 3) = 0,5 · ¹/₆ · 0,95 · ¹/₆ · 0,95 · ¹/₆ = 0,002089.

La storia onesta risulta di un soffio più probabile: il sei sul dado truccato ottiene sì 0,5 invece di ¹/₆, ma l’uno e il tre solo 0,1 invece di ¹/₆. (Nella simulazione, in realtà, tutti e tre i lanci sono stati fatti con il dado truccato — da tre lanci non lo si può capire.)

Lawrence Rabiner, nella sua celebre rassegna del 1989, ha riassunto ciò che si può fare con un modello del genere in tre problemi: valutazione (quanto è probabile la serie osservata?), decodifica (quali stati nascosti c’erano più probabilmente dietro?) e apprendimento (quali parametri ha il modello, se conosciamo solo le osservazioni?). Per ciascuno esiste un algoritmo elegante.

3. Quanto è probabile la serie: l’algoritmo forward

La probabilità della serie osservata è una somma su tutte le possibili sequenze di stati nascosti. Per 300 lanci e due dadi sono 2³⁰⁰ ≈ 2 · 10⁹⁰ — più degli atomi nell’universo. Sommarle direttamente non si può. La proprietà di Markov però permette di calcolare un passo alla volta.

Esempio — la probabilità di tre lanci come somma su tutte le storie

La probabilità delle osservazioni è la somma della probabilità congiunta su tutte le storie possibili: P(O | λ) = ∑_x P(x, O | λ). Per i lanci 1, 6, 3 sono 2³ = 8:

Storia	P(x, O)
OOO	0,002089
OOT	0,000066
OTO	0,000035
OTT	0,000188
TOO	0,000132
TOT	0,000004
TTO	0,000375
TTT	0,002025
somma	0,004913

Ogni storia costa 2T − 1 = 5 moltiplicazioni, in tutto 8 · 5 = 40. Per T lanci sono (2T − 1) · 2^T — con 300 lanci un numero inimmaginabile.

Algoritmo — algoritmo forward

Sia α_t(j) = P(O₁, …, O_t, X_t = j). Allora

α₁(j) = π_j b_j(O₁),   α_t+1(j) = [∑_i α_t(i) a_ij] b_j(O_t+1),   P(O | λ) = ∑_j α_T(j).

Il calcolo richiede O(N² T) invece di O(N^T). Perché i numeri non vadano in underflow, α_t si normalizza a ogni passo e si sommano i logaritmi delle costanti di normalizzazione.

α_t+1(j) = ∑_i α_t(i) a_ij · b_j(O_t+1)

α_t(i)

tutto ciò che sappiamo del passato: la probabilità dei lanci finora e del fatto che adesso sia in gioco il dado i; in questo solo numero sono fuse tutte le storie che finiscono in i

a_ij

un passo della catena da i a j; grazie alla proprietà di Markov non importa come siamo arrivati in i

∑_i

non sappiamo con quale dado si è lanciato la volta prima, e a j si può arrivare da uno qualsiasi — per questo sommiamo su tutte le possibilità (le storie sono eventi mutuamente esclusivi)

b_j(O_t+1)

il nuovo lancio deve generarlo davvero il dado j; non dipende da i, e quindi si può portare fuori dalla somma

Esempio — l’algoritmo forward sui lanci 1, 6, 3

Inizio: α₁(O) = 0,5 · ¹/₆ = 0,0833, α₁(T) = 0,5 · 0,1 = 0,0500. Il secondo lancio è un sei:

α₂(O) = (0,0833 · 0,95 + 0,0500 · 0,1) · ¹/₆ = 0,0140,
α₂(T) = (0,0833 · 0,05 + 0,0500 · 0,9) · 0,5 = 0,0246.

t	lancio	αt(O)	αt(T)	somma = P(O1, …, Ot)	ct
1	1	0,0833	0,0500	0,133333	0,1333
2	6	0,0140	0,0246	0,038611	0,2896
3	3	0,0026	0,0023	0,004913	0,1273

La somma nell’ultima riga è esattamente la somma delle otto storie dell’esempio precedente, solo che invece di 40 moltiplicazioni ne sono bastate 2 + 2 · 6 = 14. L’ultima colonna c_t = P(O_t | O₁, …, O_t−1) è la costante di normalizzazione del riscalamento: quanto era probabile il lancio t dati quelli precedenti. Il loro prodotto è P(O | λ), quindi log P(O | λ) = ∑_t log c_t.

Perché i logaritmi? Con 3 000 lanci P(O | λ) risulta intorno a 10^−2 278, e il più piccolo numero positivo che un computer può memorizzare nella normale doppia precisione (IEEE 754) è circa 4,9 · 10⁻³²⁴. Senza riscalamento α andrebbe in underflow fino a zero.

def dopredu(hody, pi, A, B):
    alfa = pi * B[:, hody[0]]
    logP = 0.0
    for t in range(len(hody)):
        if t > 0:
            alfa = (alfa @ A) * B[:, hody[t]]       # somma su i, poi emissione
        c = alfa.sum()                              # c_t = P(O_t | O_1, …, O_t−1)
        alfa = alfa / c                             # riscalamento: ora α_t somma a 1
        logP += np.log(c)
    return logP                                     # log P(O | λ)

Per i nostri 300 lanci risulta P(lanci | modello del casinò) ≈ 10^−230,03. Se per tutto il tempo si fosse giocato onestamente, la probabilità sarebbe (1/6)³⁰⁰ ≈ 10^−233,45. Il modello con un dado truccato usato di tanto in tanto spiega i lanci osservati circa 2 600 volte meglio — una prova forte che qui si bara, anche se nessun singolo lancio rivela l’imbroglio.

Definizione — rapporto di verosimiglianza (fattore di Bayes)

Per due modelli M₁, M₂ e dati O, il fattore di Bayes è K = P(O | M₁) / P(O | M₂). Dal teorema di Bayes (scritto per entrambi i modelli e diviso) segue:

P(M₁ | O) / P(M₂ | O) = P(O | M₁) / P(O | M₂) · P(M₁) / P(M₂)

P(M₁ | O) / P(M₂ | O)

il rapporto di probabilità a posteriori — ciò che ci interessa: quanto più crediamo all’imbroglio che al gioco onesto, dopo aver visto i lanci

P(O | M₁) / P(O | M₂)

il fattore di Bayes — l’unico punto da cui i dati entrano nella formula; entrambe le verosimiglianze le calcola l’algoritmo forward. Il denominatore P(O) del teorema di Bayes si semplifica nella divisione, ed è per questo che non serve conoscerlo

P(M₁) / P(M₂)

il rapporto di probabilità a priori — chi si fida del casinò in partenza ha bisogno di una prova più forte; i dati lo moltiplicano soltanto

Calcolo. log₁₀ K = −230,03 − (−233,45) = 3,42 (dai valori non arrotondati 3,413), quindi K ≈ 10^3,413 ≈ 2 590, arrotondato 2 600. Se in partenza consideravi l’imbroglio e il gioco onesto ugualmente probabili, dopo 300 lanci le probabilità sono circa 2 600 : 1 a favore dell’imbroglio. Secondo la scala di Kass e Raftery (1995), di uso comune, un fattore di Bayes superiore a 150 è una prova «molto forte».

4. Quando si barava: l’algoritmo di Viterbi

Algoritmo — algoritmo di Viterbi (1967)

Cerchiamo la sequenza di stati più probabile argmax_x P(x, O | λ). Sia δ_t(j) la probabilità del cammino migliore che all’istante t termina nello stato j:

δ₁(j) = π_j b_j(O₁),   δ_t+1(j) = max_i [δ_t(i) a_ij] · b_j(O_t+1),

e per ogni δ_t+1(j) ricorda da quale i è arrivato. Alla fine scegli lo stato migliore e torna indietro seguendo i riferimenti memorizzati. Si calcola nei logaritmi; il tempo è di nuovo O(N² T).

δ_t+1(j) = max_i δ_t(i) a_ij · b_j(O_t+1),   ψ_t+1(j) = argmax_i δ_t(i) a_ij

δ_t(i)

la probabilità della storia migliore che all’istante t termina con il dado i; le storie peggiori verso i non ci servono più — se il cammino completo migliore passasse per i, proseguirebbe da quella migliore

a_ij

il costo della transizione da i a j; il piccolo a_OT = 0,05 è il motivo per cui Viterbi non ha voglia di cambiare per un solo sei

max_i, ψ_t+1(j)

a differenza dell’algoritmo forward non sommiamo, ma scegliamo il predecessore migliore — vogliamo un solo cammino, non la probabilità di tutti; ψ ricorda chi ha vinto (nel traliccio le frecce color ambra), così che alla fine il cammino si possa ricostruire all’indietro

b_j(O_t+1)

quanto bene il dado j spiega il nuovo lancio — come per α

Su dodici lanci si vede come decide Viterbi. I primi sei lanci (5, 2, 2, 5, 1, 1) sembrano onesti. Poi escono due sei di fila e altri due poco più in là — e il cammino migliore passa al dado truccato. In realtà il croupier ha cambiato dado solo quattro lanci dopo; due sei di fila escono anche con un dado onesto.

Esempio — Viterbi passo per passo sui lanci 1, 6, 3

L’inizio è lo stesso di α: δ₁(O) = 0,0833, δ₁(T) = 0,0500. Per il sei del secondo lancio:

δ₂(O) = max(0,0833 · 0,95; 0,0500 · 0,1) · ¹/₆ = 0,0792 · ¹/₆ = 0,0132   (vince O),
δ₂(T) = max(0,0833 · 0,05; 0,0500 · 0,9) · 0,5 = 0,0450 · 0,5 = 0,0225   (vince T).

t	lancio	δt(O)	ψt(O)	δt(T)	ψt(T)
1	1	0,083333	—	0,050000	—
2	6	0,013194	O	0,022500	T
3	3	0,002089	O	0,002025	T

Alla fine vince O (0,002089 > 0,002025) e tornando indietro lungo i riferimenti ψ si ottiene il cammino OOO — esattamente la storia del primo esempio, che era la più probabile di tutte e otto. L’algoritmo forward però per il terzo lancio dà P(T | O₁, O₂, O₃) = 0,002283 / 0,004913 = 0,465. Il cammino migliore e lo stato più probabile qui coincidono (O), ma la «vittoria» è di misura e tre lanci non bastano per esserne certi. In generale non devono coincidere — ci torneremo con la decodifica a posteriori.

import numpy as np

def viterbi(hody, pi, A, B):
    T, N = len(hody), len(pi)
    delta = np.log(pi) + np.log(B[:, hody[0]])
    odkud = np.zeros((T, N), dtype=int)
    for t in range(1, T):
        kandidati = delta[:, None] + np.log(A)       # da ogni i a ogni j
        odkud[t] = kandidati.argmax(axis=0)
        delta = kandidati.max(axis=0) + np.log(B[:, hody[t]])
    cesta = [int(delta.argmax())]
    for t in range(T - 1, 0, -1):                     # indietro lungo i riferimenti vincenti
        cesta.append(odkud[t][cesta[-1]])
    return cesta[::-1]

5. Tutti i 300 lanci

Il dado truccato è stato in gioco 88 volte, in nove tratti. Viterbi ha segnato come truccati 62 lanci, di cui 56 correttamente, e in totale ha individuato il dado giusto nell’87,3 % dei lanci. Ha trovato i lunghi tratti di imbroglio, ma quelli brevi li ha mancati o fusi insieme — invece di nove tratti ne vede due. In un tratto breve semplicemente non escono abbastanza sei da giustificare un «costoso» cambio di dado (la probabilità di cambio è solo 0,05).

Definizione — probabilità a posteriori di uno stato

L’algoritmo forward-backward calcola in più β_t(i) = P(O_t+1, …, O_T | X_t = i) a partire dalla fine e da entrambi ottiene γ_t(i) = P(X_t = i | O) ∝ α_t(i) β_t(i).

γ_t(i) = α_t(i) · β_t(i) / P(O | λ),   β_t(i) = ∑_j a_ij b_j(O_t+1) β_t+1(j),   β_T(i) = 1

γ_t(i)

la probabilità che all’istante t fosse in gioco il dado i, conoscendo tutti i lanci — per il dado truccato è la curva rossa nella figura

α_t(i)

gli indizi dal passato: i lanci da 1 a t e lo stato i all’istante t

β_t(i)

gli indizi dal futuro: quanto bene lo stato i spiega i lanci da t + 1 a T. Si calcola a partire dalla fine con lo stesso trucco di α — un passo della catena, l’emissione, il resto del futuro. Moltiplicare α e β è lecito perché, noto lo stato X_t, i lanci passati e futuri sono indipendenti

P(O | λ)

il prodotto α·β è la probabilità congiunta P(X_t = i, O); dividendo per la probabilità di tutti i lanci la rendiamo condizionata. È lo stesso numero dato dall’algoritmo forward, e vale ∑_i α_t(i) β_t(i) = P(O | λ) per ogni t

Esempio — il secondo lancio: che cosa aggiunge il futuro

Restiamo sui lanci 1, 6, 3 e chiediamoci del secondo lancio (il sei). Il passo all’indietro da β₃ = 1 con il terzo lancio (il tre):

β₂(O) = 0,95 · ¹/₆ + 0,05 · 0,1 = 0,1633,   β₂(T) = 0,1 · ¹/₆ + 0,9 · 0,1 = 0,1067.

γ₂(T) = 0,024583 · 0,106667 / 0,004913 = 0,534.

Se conoscessimo solo i primi due lanci, avremmo P(T | O₁, O₂) = α₂(T) / (α₂(O) + α₂(T)) = 0,637. Il tre uscito dopo è meno probabile sul dado truccato, e così abbassa a posteriori il sospetto sul secondo lancio a 0,534.

Definizione — decodifica a posteriori e accuratezza

La decodifica a posteriori sceglie in ogni istante separatamente x̂_t = argmax_i γ_t(i). L’accuratezza di una decodifica x̂ rispetto agli stati reali x è la frazione di coincidenze (1/T) ∑_t [x̂_t = x_t], dove [·] vale 1 se l’affermazione è vera, altrimenti 0.

La decodifica a posteriori massimizza il numero atteso di lanci individuati correttamente, Viterbi la probabilità che sia corretto l’intero cammino in una volta. Per questo la sequenza a posteriori può contenere perfino una transizione che nel modello ha probabilità zero — nel casinò non ce ne sono, ma in generale può succedere.

Se per ogni lancio scegliessimo il dado con la probabilità a posteriori maggiore, indovineremmo l’87,7 % — di un soffio più di Viterbi (263 lanci su 300 contro 262, la differenza di un solo lancio). (Viterbi cerca il miglior cammino intero, la decodifica a posteriori la migliore stima di ogni lancio separatamente; non è la stessa cosa.) E attenzione a una sola simulazione: in dodici esperimenti diversi l’accuratezza dell’algoritmo di Viterbi è variata dal 73,3 al 90,0 %, in media l’83,4 %. Dipende da quanto lunghi sono i tratti di imbroglio che produce il caso.

6. Apprendimento: l’algoritmo di Baum-Welch

Finora conoscevamo i parametri del casinò. E se sapessimo solo che i dadi sono due, e tutto il resto andasse ricavato dai lanci?

Algoritmo — algoritmo di Baum-Welch

È un algoritmo EM (Baum et al., intorno al 1970). Ripeti:

1. passo E: con i parametri attuali calcola con l’algoritmo forward-backward γ_t(i) e i conteggi attesi delle transizioni ξ_t(i, j) = P(X_t = i, X_t+1 = j | O);
2. passo M: nuovo a_ij = ∑_t ξ_t(i, j) / ∑_t γ_t(i), nuovo b_i(o) = quota di γ negli istanti in cui è uscito o.

La verosimiglianza P(O | λ) non diminuisce in nessuna iterazione; l’algoritmo converge a un massimo locale.

Il numero atteso di transizioni si calcola dagli stessi α e β di γ, solo inserendo tra loro un passo della catena:

ξ_t(i, j) = α_t(i) a_ij b_j(O_t+1) β_t+1(j) / P(O | λ)

α_t(i)

i lanci fino all’istante t e il dado i all’istante t — l’estremo sinistro della transizione

a_ij

la transizione i → j stessa, di cui stimiamo la frequenza

b_j(O_t+1)

il lancio t + 1 deve generarlo il nuovo dado j

β_t+1(j)

il resto dei lanci da t + 2 in poi, spiegato a partire dal dado j — l’estremo destro della transizione

P(O | λ)

dividendo, dalla probabilità congiunta «transizione e tutti i lanci» otteniamo quella condizionata «transizione, noti i lanci»

â_ij = ∑_t=1^T−1 ξ_t(i, j) / ∑_t=1^T−1 γ_t(i)

â_ij

la nuova stima della probabilità di transizione — una frequenza relativa, come se contassimo delle tacche

∑ ξ_t(i, j)

il numero atteso di transizioni i → j; invece di «c’è stata una transizione o no» (1 o 0) sommiamo probabilità, perché gli stati non li vediamo

∑ γ_t(i)

il numero atteso di uscite dallo stato i; si somma solo fino a T − 1, perché dall’ultimo stato non parte più alcuna transizione. Grazie a questo ogni riga della nuova matrice somma a 1

ripeti (qui 100 volte):
    α, β, P(O) ← algoritmo forward-backward con π, A, B attuali
    # passo E: conteggi morbidi
    per ogni t, i:            γ[t][i]    ← α[t][i] · β[t][i] / P(O)
    per ogni t < T, i, j:     ξ[t][i][j] ← α[t][i] · a[i][j] · b[j](O[t+1]) · β[t+1][j] / P(O)
    # passo M: frequenze relative
    π[i]    ← γ[1][i]
    a[i][j] ← ∑_{t<T} ξ[t][i][j] / ∑_{t<T} γ[t][i]
    b[i](o) ← ∑_{t: O[t]=o} γ[t][i] / ∑_t γ[t][i]

Siamo partiti da una stima sbagliata: i dadi quasi non differiscono e vengono scambiati spesso. Da 300 lanci Baum-Welch è arrivato a un modello che non scambia quasi mai i dadi e dà al dado truccato il sei con probabilità di appena 0,39 — per una stima affidabile 300 lanci sono pochi. Da 3 000 lanci (un’altra simulazione dello stesso casinò) è risultato molto vicino alla verità:

Perché 300 lanci non bastano lo mostra la verosimiglianza. In 100 iterazioni sui nostri 300 lanci è salita da 10^−231,26 a 10^−227,14 — ed è più dei 10^−230,03 del vero modello del casinò. Il modello appreso spiega quindi proprio questi lanci meglio della verità: si è adattato anche alle fluttuazioni casuali di questi dati concreti. La stima di massima verosimiglianza si avvicina alla verità solo man mano che i dati aumentano.

7. I modelli di Markov nascosti nella pratica

• Riconoscimento vocale. Dagli anni Ottanta fino all’arrivo delle reti profonde intorno al 2010, quasi tutti i sistemi si basavano sugli HMM: gli stati nascosti sono parti di fonemi, le osservazioni brevi tratti dello spettro sonoro, e Viterbi cerca la sequenza di parole più probabile.
• Lingua. Etichettatura delle parti del discorso: lo stato nascosto è la parte del discorso, l’osservazione la parola. «Porta» può essere un sostantivo o un verbo — decide il contesto.
• Bioinformatica. Ricerca dei geni nel DNA (le regioni codificanti e non codificanti sono gli stati nascosti) o profile HMM per le famiglie di proteine nella banca dati Pfam.
• Stati continui. Quando lo stato nascosto non è «dado A o B» ma una posizione e una velocità, al posto di un HMM si usa il filtro di Kalman — che nel programma ha una parte tutta sua.

8. Riepilogo

• Un modello di Markov nascosto è una catena di Markov di stati nascosti di cui vediamo solo le emissioni; lo determinano π, A e B.
• L’algoritmo forward calcola la probabilità delle osservazioni in tempo O(N²T) invece di sommare su 2³⁰⁰ cammini; il casinò che bara spiega i nostri lanci circa 2 600 volte meglio del gioco onesto.
• L’algoritmo di Viterbi trova il cammino di stati nascosti più probabile con la programmazione dinamica — nella nostra simulazione ha individuato il dado giusto nell’87,3 % dei lanci, ma ha mancato i tratti brevi.
• L’algoritmo forward-backward dà la probabilità a posteriori dello stato in ogni istante.
• L’algoritmo di Baum-Welch apprende i parametri dalle sole osservazioni — ma ha bisogno di abbastanza dati: 300 lanci non sono bastati, 3 000 sì.

Vuoi toccarlo con mano? Fai addestrare a un agente IA un HMM a due stati sui rendimenti giornalieri di un indice azionario — e guarda se trova da solo i periodi «calmi» e quelli «turbolenti» del mercato.

La vedi diversamente? Scrivi a support@coden-app.com.