Hidden Markov Model (HMM)

Un modello di Markov nascosto (HMM) è un modello probabilistico di una sequenza in cui il sistema passa da uno stato all'altro, senza che gli stati siano direttamente osservabili; ogni stato nascosto genera un'osservazione che invece è osservabile. Data una sequenza di osservazioni, come fotogrammi audio o lettere del DNA, un HMM calcola la probabilità di ogni sequenza di stati nascosti, ad esempio dei fonemi corrispondenti all'audio o delle regioni geniche corrispondenti alle lettere. «Markov» si riferisce all'assunzione fondamentale del modello: lo stato successivo dipende solo da quello corrente. Leonard Baum e i suoi collaboratori svilupparono la teoria alla fine degli anni Sessanta; gli HMM sono poi stati alla base del riconoscimento vocale per decenni. Basati interamente su probabilità esplicite, restano uno strumento standard nell'analisi delle serie temporali e nella bioinformatica, nonché un esempio classico di IA statistica.

Componenti di un HMM#

Un HMM con N stati nascosti è definito da tre insiemi di probabilità:

• Probabilità iniziali (π): la probabilità di iniziare in ciascuno stato nascosto.
• Probabilità di transizione (A): una matrice N × N il cui elemento A[i, j] indica la probabilità di passare dallo stato i allo stato j in un passaggio; gli stati nascosti formano così una catena di Markov.
• Probabilità di emissione (B): la probabilità di ciascuna osservazione dato lo stato corrente. Le osservazioni discrete usano una tabella, mentre quelle continue, come le caratteristiche acustiche, usano distribuzioni come le miscele gaussiane.

Due assunzioni mantengono trattabile il modello: ogni stato dipende solo dallo stato precedente e ogni osservazione dipende solo dallo stato corrente. Sviluppato nel tempo, il modello è una catena di stati nascosti, ciascuno dei quali emette un'osservazione:

Tre problemi classici degli HMM#

Nel suo tutorial del 1989, ampiamente citato, Lawrence Rabiner ha organizzato gli usi degli HMM attorno a tre domande. Ognuna ha una soluzione basata sulla programmazione dinamica, con un costo che cresce in proporzione a N² × T per T osservazioni, invece che alle Nᵀ possibili sequenze di stati:

• Valutazione: qual è la probabilità di una sequenza di osservazioni secondo un determinato modello? L'algoritmo forward somma i contributi di tutti i percorsi nascosti; è così che un riconoscitore seleziona il modello di parola che spiega meglio un enunciato.
• Decodifica: quale sequenza di stati nascosti spiega meglio le osservazioni? L'algoritmo di Viterbi, pubblicato da Andrew Viterbi nel 1967 per decodificare codici convoluzionali, trova il percorso singolo più probabile; l'algoritmo forward-backward calcola la probabilità di ciascuno stato a ogni passaggio temporale.
• Apprendimento: quali parametri si adattano meglio a un insieme di sequenze di osservazioni? L'algoritmo di Baum-Welch, un caso di massimizzazione dell'aspettativa, stima π, A e B a partire da sequenze non etichettate. Quando le sequenze di stati sono etichettate, è sufficiente contare le transizioni e le emissioni.

La decodifica di Viterbi si implementa in poche righe di NumPy. In questo modello l'attività di una persona, camminare o correre, è nascosta; un tracker segnala una misurazione della velocità per fotogramma e le attività tendono a persistere da un fotogramma all'altro:

import numpy as np

states = ["walk", "run"]
start = np.array([0.8, 0.2])  # probabilità degli stati iniziali
trans = np.array([[0.9, 0.1], [0.1, 0.9]])  # le attività tendono a persistere tra i fotogrammi
emit = np.array([[0.7, 0.25, 0.05], [0.1, 0.3, 0.6]])  # P(velocità | stato) per lento, medio, veloce
obs = [0, 0, 2, 0, 0, 1, 2, 2, 1, 2]  # misurazioni della velocità per fotogramma

# Viterbi: migliore log-probabilità di raggiungere ogni stato, più puntatori all'indietro
logp = np.log(start) + np.log(emit[:, obs[0]])
back = []
for o in obs[1:]:
    scores = logp[:, None] + np.log(trans)  # righe: stato precedente; colonne: stato successivo
    back.append(scores.argmax(axis=0))
    logp = scores.max(axis=0) + np.log(emit[:, o])

# Ricostruisce all'indietro la sequenza di stati più probabile a partire dal migliore stato finale
path = [int(logp.argmax())]
for pointers in reversed(back):
    path.insert(0, int(pointers[path[0]]))
print("Speeds: ", " ".join(["slow", "medium", "fast"][o] for o in obs))
print("Decoded:", " ".join(states[s] for s in path))

Decodifica walk walk walk walk walk run run run run run. La lettura veloce al fotogramma 3 resta «cammina», perché passare alla corsa e tornare a camminare richiederebbe due transizioni improbabili; le letture medie ai fotogrammi 6 e 9 diventano «corre» grazie ai fotogrammi veloci che le circondano. Un classificatore per fotogramma che ignorasse le transizioni avrebbe etichettato il fotogramma 3 come corsa.

HMM e modelli correlati#

• Filtro di Kalman: esegue la stessa ricorsione di predizione e aggiornamento per stati continui con dinamiche lineari e rumore gaussiano. L'algoritmo forward dell'HMM ne è il corrispettivo per stati discreti.
• Reti bayesiane: un HMM è la rete bayesiana dinamica più semplice, con una variabile nascosta e una osservata per ogni passaggio temporale.
• Processo decisionale di Markov (MDP): aggiunge azioni e ricompense a una catena di Markov con stati osservati; è il quadro alla base dell'apprendimento per rinforzo.
• Reti neurali ricorrenti e transformer: apprendono dipendenze non lineari a lungo raggio da grandi insiemi di dati e hanno sostituito gli HMM nella maggior parte delle attività di linguaggio e riconoscimento vocale. Gli HMM richiedono molti meno dati e consentono di leggere direttamente ciascuna probabilità.
• Modelli a spazio di stato (SSM): livelli di deep learning come Mamba condividono l'idea dello spazio di stato della teoria del controllo e aggiornano un vettore nascosto continuo tramite dinamiche apprese e deterministiche.

Applicazioni nel mondo reale#

• Riconoscimento vocale: dagli anni Ottanta ai primi anni Dieci, la maggior parte dei sistemi di riconoscimento modellava ogni fonema come un piccolo HMM con emissioni a miscela gaussiana. Le reti neurali profonde hanno poi sostituito il modello di emissione nei sistemi ibridi, mentre i modelli end-to-end hanno successivamente eliminato del tutto gli HMM.
• Bioinformatica: gli HMM di profilo descrivono famiglie di sequenze proteiche o di DNA correlate. HMMER li usa per cercare parenti lontani nei database di sequenze e costituisce la base del database di famiglie proteiche Pfam; inoltre, i predittori genici usano HMM per etichettare tratti di un genoma come codificanti o non codificanti.
• Etichettatura delle parti del discorso: le prime applicazioni statistiche dell'elaborazione del linguaggio naturale etichettavano le parole come sostantivi, verbi e altre parti del discorso, decodificando le sequenze di etichette con Viterbi.
• Riconoscimento delle attività: sequenze di pose corporee o letture di sensori indossabili vengono decodificate in attività come stare in piedi, camminare o cadere. La soluzione Ultralytics per il monitoraggio degli allenamenti traccia una sequenza di questo tipo a due stati: in base all'angolo di un'articolazione individuato dai punti chiave della stima della posa di YOLO26, per impostazione predefinita il gomito, etichetta ogni persona come «su» o «giù», passando da uno stato all'altro sopra i 145° e sotto i 90°, e conta una ripetizione a ogni passaggio da su a giù.