Viterbi e decodifica su HMM

Quando un sistema evolve attraverso stati che non vedi e ti lascia solo una scia di osservazioni rumorose, l’algoritmo di Viterbi ricostruisce la sequenza di stati nascosti più probabile — in modo esatto, in tempo polinomiale, dove la forza bruta esploderebbe.

Perché questo capitolo

Nel 1967 un ingegnere delle telecomunicazioni pubblica un paper sui codici di correzione d’errore. Dentro, quasi di passaggio, descrive un metodo per decodificare un flusso di bit ricevuto attraverso un canale rumoroso. Non lo presenta come un grande algoritmo: gli serve per dimostrare un bound sulla probabilità di errore. Mezzo secolo dopo, quello stesso metodo gira dentro praticamente ogni telefono cellulare del pianeta, ha decodificato il parlato in tre decenni di sistemi di riconoscimento vocale, allinea proteine nei database di biologia, e per anni ha etichettato le categorie grammaticali delle parole in ogni frase processata dai sistemi di linguaggio naturale. È stato riscoperto, in modo indipendente, almeno sette volte in domini che non si parlavano.

Questa convergenza non è un caso. L’algoritmo di Viterbi non è il trucco di un campo specifico: è la soluzione naturale di una classe di problemi che ricorre ovunque. Il problema è questo. Hai un sistema che attraversa una sequenza di stati che non puoi osservare direttamente. A ogni passo, lo stato in cui ti trovi produce un segnale osservabile, ma il segnale è ambiguo: lo stesso segnale può venire da stati diversi. Vedi la scia di segnali; vuoi ricostruire la sequenza di stati che l’ha prodotta. Quanti modi ci sono di assegnare stati a una sequenza di osservazioni? Esponenzialmente tanti. Viterbi ne trova il migliore senza enumerarli, sfruttando un’osservazione strutturale sottile ma potente.

Per chi costruisce sistemi di intelligenza artificiale, questo capitolo paga su due fronti. Primo, è un caso di studio limpido di programmazione dinamica: un problema che sembra richiedere ricerca esponenziale collassa a tempo polinomiale grazie a una proprietà di sottostruttura ottima. Capire Viterbi significa capire la programmazione dinamica nella sua forma più elegante. Secondo, Viterbi è l’algoritmo di decodifica dei modelli di Markov nascosti, e i modelli di Markov nascosti sono la spina dorsale di tutto il riconoscimento di sequenze pre-deep-learning — il riconoscimento del parlato, l’etichettatura grammaticale, la bioinformatica delle sequenze — e restano vivi oggi come strato di decoding sopra le reti neurali nei conditional random field. Chi vuole capire come funzionavano i sistemi di linguaggio naturale prima dei transformer, e cosa esattamente i transformer hanno rimpiazzato, deve passare di qui.

Contesto

Il setting è quello degli altri capitoli di ricerca di questa Parte. C’è uno spazio di stati, c’è un grafo di transizioni possibili, c’è una nozione di costo o punteggio lungo i cammini, e c’è l’obiettivo di trovare il cammino migliore. In search-bfs-dfs e in A* gli stati erano configurazioni di un problema e l’obiettivo era raggiungere una meta. In beam-search uno stato era una sequenza parziale costruita finora. In Viterbi uno stato è un assegnamento: a ogni istante di tempo, in quale “modo nascosto” si trova il sistema.

La differenza che separa Viterbi da beam search è la struttura del problema. La beam search lavora dove lo spazio di stati è troppo grande per essere esplorato per intero, e quindi pota: tiene solo le k ipotesi migliori e accetta di poter perdere l’ottimo. Viterbi lavora dove lo spazio di stati per istante è piccolo — decine, centinaia di stati — e quindi può permettersi di non potare niente: esplora tutto, e il risultato è l’ottimo esatto. Sono lo stesso problema, “trova il cammino migliore in un grafo a strati”, risolto con il lusso o senza il lusso della completezza. Torneremo su questa parentela; per ora basti dire che Viterbi sta sul lato esatto, beam search sul lato euristico.

Da dove viene

L’algoritmo nasce nel 1967 da Andrew J. Viterbi, ingegnere statunitense nato a Bergamo nel 1935 ed emigrato bambino negli Stati Uniti. Il paper è “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, pubblicato su IEEE Transactions on Information Theory (vol. 13, pp. 260-269, 1967). Il problema originale non aveva niente a che fare con il machine learning. Era la decodifica dei codici convoluzionali, una tecnica delle comunicazioni digitali.

Vale la pena fissare il problema originale, perché chiarisce la natura dell’algoritmo. Un codice convoluzionale aggiunge ridondanza a un flusso di bit prima di trasmetterlo: invece di mandare i bit nudi, manda combinazioni di bit costruite in modo che il ricevitore, anche se il canale ha introdotto errori, possa risalire al messaggio originale. Decodificare significa risolvere questa domanda: dato il segnale rumoroso che ho ricevuto, qual è la sequenza di bit trasmessa più probabile? Le sequenze possibili sono esponenzialmente tante. Viterbi sviluppò l’algoritmo mentre insegnava un corso sui codici convoluzionali — era nato come strumento didattico per spiegare i bound di errore, non come prodotto da ingegnerizzare.

Fu G. David Forney Jr., ingegnere statunitense della teoria dell’informazione, a riconoscerne la portata generale. Forney capì che l’algoritmo era un’istanza di programmazione dinamica e che risolveva il problema della maximum likelihood sequence estimation — la stima della sequenza più verosimile — in una forma che non aveva nulla di specifico ai codici convoluzionali. Nel paper “The Viterbi Algorithm” (Proceedings of the IEEE, marzo 1973) generalizzò il metodo e gli diede il nome con cui è noto oggi. Nel resoconto storico “The Viterbi Algorithm: A Personal History” (2005) lo stesso Forney documenta che l’algoritmo fu scoperto in modo indipendente almeno sette volte, in domini che non comunicavano: tra gli altri da Needleman e Wunsch nell’allineamento di sequenze biologiche (1970), da Wagner e Fischer per la edit distance fra stringhe, da Vintsyuk nel riconoscimento del parlato.

Sette scoperte indipendenti sono il segno di una cosa: non si tratta di un trucco di dominio, ma della soluzione naturale a una classe di problemi. Ogni volta che qualcuno si è trovato a cercare il cammino ottimo in un grafo a strati, ha riscoperto Viterbi.

Andrew Viterbi co-fondò poi Qualcomm nel 1985, azienda di telecomunicazioni. L’algoritmo che porta il suo nome decodifica oggi i codici convoluzionali negli standard di telefonia mobile (GSM, CDMA), nei modem, nelle comunicazioni satellitari e con le sonde spaziali, nel Wi-Fi 802.11. L’adozione fuori dalle telecomunicazioni arriva negli anni ‘70 e ‘80, in particolare nel riconoscimento del parlato — il gruppo IBM di Frederick Jelinek e Lalit Bahl — e dagli anni ‘90 in bioinformatica e nel linguaggio naturale statistico.

C’è un’ironia che vale la pena notare. Viterbi descrisse l’algoritmo per dimostrare un teorema — un bound sulla probabilità di errore — e non ne previde la fortuna pratica: l’algoritmo era, nelle sue stesse parole riportate da Forney, un sottoprodotto della dimostrazione. Furono altri a vederne il valore operativo, prima Forney sul piano teorico, poi gli ingegneri che lo portarono nell’hardware dei ricevitori. La storia di Viterbi è un caso da manuale di un risultato che vive una seconda vita, più lunga della prima, lontano dal problema per cui era nato. Quando lo incontrerai nel POS tagging o nella bioinformatica, ricorda che nessuna di quelle applicazioni era nella testa di chi lo scrisse.

Dove si colloca nel grafo

Il grafo concettuale, in una riga: Viterbi è l’incrocio tra i modelli di Markov nascosti (la struttura probabilistica che descrive il problema) e la programmazione dinamica (la tecnica algoritmica che lo risolve in fretta). Verso la teoria della probabilità si appoggia a catene-markov e ai processi-stocastici. Verso gli algoritmi è imparentato con programmazione-dinamica e, come vedremo, con beam-search. Verso il machine learning prepara il terreno per i modelli di Markov nascosti completi, di cui Viterbi è solo uno dei tre algoritmi (gli altri due — forward e Baum-Welch — vivranno nel capitolo hmm della Parte sul machine learning, in preparazione).

Una distinzione utile prima di entrare nel merito. Viterbi è un algoritmo di inferenza, non di apprendimento. Riceve un modello già pronto — un modello che sa assegnare probabilità a transizioni ed emissioni — e si limita a interrogarlo: data questa sequenza di osservazioni, qual è la sequenza di stati più probabile? Non addestra niente, non stima parametri. La stima dei parametri del modello è un altro problema, risolto da un altro algoritmo. Tenere separate le due cose evita una confusione frequente: se il cammino di Viterbi è sbagliato, può essere perché il modello che gli abbiamo dato è sbagliato, non perché l’algoritmo ha fallito. L’algoritmo trova sempre l’ottimo — l’ottimo del modello che riceve.

C’è infine una collocazione storica da fissare. Viterbi appartiene alla famiglia di metodi probabilistici che, dagli anni ‘90, ha spostato il baricentro dell’intelligenza artificiale dalla manipolazione di simboli logici alla stima di probabilità. Prima, un sistema di etichettatura grammaticale era un insieme di regole scritte a mano; dopo, era un HMM con parametri contati su un corpus e decodificato con Viterbi. Lo stesso vale per il riconoscimento del parlato. Questo passaggio — la svolta statistica — è il contesto in cui Viterbi smette di essere un algoritmo di telecomunicazioni e diventa uno strumento centrale del linguaggio naturale e del riconoscimento di sequenze. Non è un dettaglio aneddotico: spiega perché lo stesso identico algoritmo compare in capitoli che parlano di cose così diverse.

L’intuizione

Prima di qualsiasi formula, due angoli per guardare lo stesso oggetto.

Angolo 1 — il cammino su un grafo a strati

Immagina una griglia. Sull’asse orizzontale scorre il tempo: istante 1, istante 2, fino all’istante T. Sull’asse verticale stanno gli stati possibili del sistema: N stati, impilati uno sopra l’altro. La griglia ha quindi T colonne e N righe, e ogni cella (t, s) rappresenta l’ipotesi “all’istante t il sistema si trova nello stato s”. Questa griglia ha un nome: trellis, in italiano “graticcio” o “reticolo”.

Ora collega le celle. Da ogni cella della colonna t-1 parte un arco verso ogni cella della colonna t: l’arco rappresenta una transizione di stato, e ha un peso che dice quanto è probabile quella transizione. Una sequenza di stati — un’ipotesi completa su cosa ha fatto il sistema dall’istante 1 all’istante T — è esattamente un cammino nel trellis: tocca una e una sola cella per colonna, da sinistra a destra.

A questo punto il problema “qual è la sequenza di stati nascosti più probabile” diventa “qual è il cammino di peso migliore nel trellis”. È un problema di cammino ottimo su grafo. E i grafi a strati — dove gli archi vanno sempre da una colonna alla successiva, mai indietro, mai dentro la stessa colonna — hanno una proprietà preziosa: si possono attraversare colonna per colonna, una volta sola, da sinistra a destra. È questo che rende il problema trattabile. Il cammino di Viterbi è il cammino migliore in questo grafo.

Angolo 2 — la tabella che si riempie da sola

Cambia prospettiva. Dimentica il grafo, pensa a una tabella e a una domanda ripetuta.

La tabella ha una riga per istante di tempo e una colonna per stato. In ogni cella (t, s) scriveremo un solo numero: la probabilità del miglior cammino che, partendo dall’inizio, arriva nello stato s all’istante t avendo prodotto le osservazioni viste fin lì. Un numero per cella, non una lista di cammini.

La domanda ripetuta è questa. Per riempire la cella (t, s), mi serve sapere: qual è il modo migliore di arrivare nello stato s all’istante t? Per arrivarci, all’istante precedente t-1 dovevo trovarmi in qualche stato — chiamiamolo r. Ma il modo migliore di trovarmi in r all’istante t-1 l’ho già calcolato: è scritto nella cella (t-1, r). Quindi non devo ricostruire niente da zero. Guardo tutte le celle della colonna precedente, per ognuna combino il suo valore con la probabilità di transizione verso s, prendo la combinazione migliore, e la moltiplico per la probabilità che s produca l’osservazione di adesso. Quel numero va nella cella (t, s).

Il punto cruciale è perché posso fidarmi delle celle già scritte. Il miglior cammino fino a s all’istante t ha un prefisso — la sua parte fino all’istante t-1 — e quel prefisso deve essere a sua volta il miglior cammino fino allo stato in cui passa a t-1. Se non lo fosse, potrei sostituirlo con uno migliore e ottenere un cammino complessivo migliore: contraddizione, perché avevo assunto che il cammino complessivo fosse il migliore. Questa proprietà — il meglio si compone di pezzi che sono a loro volta il meglio — si chiama sottostruttura ottima, ed è il cuore di ogni algoritmo di programmazione dinamica. È ciò che mi autorizza a non guardare mai dentro le celle: il numero che contengono basta.

La tabella si riempie colonna per colonna, da sinistra a destra. Quando arrivo all’ultima colonna, la cella con il numero più alto mi dice la probabilità del cammino di Viterbi. Per sapere quale cammino è, serve un piccolo accorgimento in più — i backpointer — che vedremo tra poco.

Angolo 3 — l’esploratore che dimentica i vicoli ciechi

Un terzo modo di guardarla, più operativo. Immagina di avanzare nel trellis colonna per colonna, e a ogni colonna di tenere aggiornato un piccolo taccuino con N righe, una per stato. Su ogni riga scrivi due cose: il punteggio del miglior modo trovato finora di arrivare in quello stato, e una freccia che indica da dove sei arrivato.

Quando passi alla colonna successiva, non porti con te la storia di come hai costruito quei punteggi. Porti solo il taccuino: N numeri e N frecce. Tutto ciò che è successo prima della colonna precedente è già stato compresso in quei numeri. Un cammino sub-ottimo che è arrivato in uno stato r con punteggio peggiore del migliore: dimenticato, scartato per sempre, non lascerà traccia. Non perché sia impossibile che fosse parte di una buona soluzione complessiva — è la sottostruttura ottima a garantire che non lo sia — ma proprio in virtù di quella garanzia.

Questa lente rende chiare due proprietà. La prima: la memoria di Viterbi è costante rispetto al passato. A ogni passo basta la colonna precedente del taccuino, non tutta la tabella; se non serve ricostruire il cammino si può tenere in memoria solo O(N) di stato. La seconda: Viterbi non rivede mai le sue decisioni intermedie. Diversamente da una ricerca con backtracking, non torna indietro a riconsiderare un vicolo cieco — la sottostruttura ottima gli assicura che non ce n’è bisogno. Avanza una volta sola, da sinistra a destra, e alla fine il backtracing legge le frecce all’indietro. Avanzamento in avanti, ricostruzione all’indietro: niente in mezzo.

I tre angoli sono lo stesso oggetto. Il primo lo guarda come grafo e parla di cammini; il secondo lo guarda come tabella e parla di sottoproblemi; il terzo lo guarda come un esploratore con memoria corta. La programmazione dinamica sul trellis è la traduzione esatta di “trova il cammino migliore nel grafo a strati”.

Il modello di Markov nascosto

Per applicare Viterbi serve sapere cosa sia il modello su cui opera. Un modello di Markov nascosto — hidden Markov model, HMM — descrive un sistema con due strati: uno nascosto che evolve, e uno osservabile che ne è il riflesso rumoroso.

Lo strato nascosto è una catena di Markov: una sequenza di stati dove il prossimo stato dipende solo da quello corrente, non da tutta la storia precedente (vedi catene-markov per la trattazione completa). Lo strato osservabile aggiunge una cosa: a ogni istante, lo stato in cui ci si trova emette un simbolo osservabile, in modo probabilistico. Noi vediamo solo i simboli emessi; gli stati restano nascosti, da qui il nome.

Formalmente un HMM è definito da cinque ingredienti.

Un insieme di stati nascosti $S = \{s_1, \dots, s_N\}$ . Sono gli stati della catena di Markov sottostante. Non osservabili.
Un insieme di simboli osservabili, il vocabolario delle emissioni.
Una matrice di transizione $A$ , dove l’elemento $a_{ij}$ è la probabilità di passare dallo stato $s_i$ allo stato $s_j$ : $a_{ij} = P(\text{stato}_t = s_j \mid \text{stato}_{t-1} = s_i)$ . Ogni riga somma a 1, perché da uno stato bisogna pur andare da qualche parte.
Una funzione di emissione $B$ , dove $b_j(o)$ è la probabilità che lo stato $s_j$ produca il simbolo osservato $o$ : $b_j(o) = P(\text{osservazione} = o \mid \text{stato} = s_j)$ .
Una distribuzione iniziale $\pi$ , dove $\pi_i$ è la probabilità che la sequenza cominci nello stato $s_i$ .

Un esempio concreto per ancorare i simboli. Stati nascosti: il tempo meteorologico, $\{\text{Sole}, \text{Pioggia}\}$ . Non possiamo osservarlo — siamo chiusi in una stanza senza finestre. Quello che osserviamo è cosa fa una persona che entra ed esce: $\{\text{ombrello}, \text{occhiali da sole}\}$ . La matrice di transizione $A$ codifica la persistenza del tempo: dopo una giornata di Sole, probabilmente Sole anche domani. La funzione di emissione $B$ codifica il legame osservazione-stato: con la Pioggia è più probabile vedere l’ombrello, con il Sole gli occhiali. La distribuzione $\pi$ dice come è probabile che cominci la sequenza. Dato che ho visto la sequenza di osservazioni [ombrello, ombrello, occhiali], qual è la sequenza di tempo più probabile? Questo è il problema che Viterbi risolve.

Una parola sul significato di “nascosto”, perché è precisa. Non vuol dire “sconosciuto in assoluto”: il modello — le matrici $A$ , $B$ , $\pi$ — è noto. Vuol dire che la realizzazione della catena di Markov, la sequenza concreta di stati che il sistema ha attraversato in questa specifica occasione, non è osservabile direttamente. Vediamo solo la sua ombra: le emissioni. E l’ombra è ambigua, perché la funzione di emissione non è iniettiva — lo stesso simbolo osservabile può essere prodotto da stati diversi, con probabilità diverse. Se ogni stato emettesse un simbolo distinto e inconfondibile, non ci sarebbe nulla da decodificare: leggeremmo gli stati direttamente dalle osservazioni. È proprio la sovrapposizione delle emissioni a rendere il decoding un problema, e Viterbi la sua soluzione.

Va segnalato che a un HMM si associano tre problemi distinti, formalizzati nel tutorial di riferimento di Lawrence Rabiner (“A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Proceedings of the IEEE, 1989):

Evaluation — data la sequenza di osservazioni, quanto è probabile sotto il modello? Lo risolve il forward algorithm.
Decoding — data la sequenza di osservazioni, qual è la sequenza di stati nascosti più probabile? Lo risolve l’algoritmo di Viterbi, l’oggetto di questo capitolo.
Learning — dati solo i dati osservati, stimare $A$ , $B$ , $\pi$ ? Lo risolve il Baum-Welch.

Questo capitolo si concentra sul secondo. Il primo lo incontreremo come termine di paragone, perché Viterbi e forward sono quasi lo stesso algoritmo.

La meccanica

A questo punto abbiamo gli ingredienti — il trellis come grafo a strati, la tabella DP come riassunto, l’HMM come modello — e possiamo mettere insieme l’algoritmo nella sua forma esatta. La descrizione che segue è tutto Viterbi: quattro fasi, niente di più. La parte difficile, perché funziona, l’abbiamo già fatta nelle sezioni precedenti; quella che segue è solo la trascrizione precisa.

Viterbi riempie una tabella V con T righe (gli istanti) e N colonne (gli stati). Il contenuto della cella V[t][s] è, per definizione:

$V[t][s] = \text{probabilità del cammino più probabile che termina nello stato } s \text{ al tempo } t, \text{ avendo prodotto le prime } t \text{ osservazioni}$

In parole povere: il numero in V[t][s] riassume, in un solo valore, il meglio che si può fare per arrivare lì. In parallelo si riempie una seconda tabella, i backpointer bp, dove bp[t][s] registra da quale stato del tempo t-1 proviene quel cammino ottimo. La tabella V serve a calcolare la probabilità migliore; la tabella bp serve a ricostruire quale cammino l’ha realizzata.

L’algoritmo ha quattro fasi.

Inizializzazione, al tempo $t = 1$ . Non c’è un tempo precedente, quindi il cammino fino a uno stato $s$ è solo: cominciare in $s$ , ed emettere la prima osservazione.

$V[1][s] = \pi_s \cdot b_s(o_1)$

dove $o_1$ è la prima osservazione. La probabilità di iniziare in $s$ moltiplicata per la probabilità che $s$ emetta ciò che abbiamo visto. Il backpointer al tempo 1 non punta a nulla.

Ricorsione, per ogni tempo $t$ da 2 a $T$ e per ogni stato $s$ :

$V[t][s] = \left( \max_{r} \; V[t-1][r] \cdot a_{rs} \right) \cdot b_s(o_t)$

$bp[t][s] = \arg\max_{r} \; V[t-1][r] \cdot a_{rs}$

Leggiamo la prima formula da sinistra a destra. Per arrivare nello stato $s$ al tempo $t$ devo venire da qualche stato $r$ al tempo $t-1$ . Per ogni candidato $r$ considero il prodotto $V[t-1][r] \cdot a_{rs}$ : il meglio che potevo fare fino a $r$ , moltiplicato per la probabilità della transizione $r \to s$ . Prendo il massimo su tutti gli $r$ — il miglior modo di arrivare a $s$ ignorando per un attimo l’osservazione corrente. Infine moltiplico per $b_s(o_t)$ , la probabilità che $s$ emetta l’osservazione che vedo adesso. Quel prodotto è il valore della cella.

La seconda formula fa la stessa cosa ma tiene il arg max invece del max: registra quale stato $r$ ha vinto la competizione. È l’unica informazione che serve per la ricostruzione, ed è una sola cella per nodo: ecco perché Viterbi non deve conservare cammini interi.

Conviene soffermarsi su un dettaglio della ricorsione, perché è la fonte di un errore frequente. La probabilità di emissione $b_s(o_t)$ è fuori dal massimo, non dentro. La ragione è che $o_t$ è la stessa per tutti i candidati $r$ : lo stato $s$ emette l’osservazione corrente con la stessa probabilità indipendentemente da dove veniva. Un fattore costante rispetto alla variabile su cui si massimizza non cambia chi vince il massimo, quindi lo si può raccogliere fuori. Metterlo dentro non sarebbe sbagliato nel risultato — il valore della cella sarebbe identico — ma sarebbe lavoro ripetuto $N$ volte invece di una. La transizione $a_{rs}$ , invece, sta dentro il massimo, perché dipende da $r$ : è proprio la quantità che distingue un candidato dall’altro.

Un secondo dettaglio: la ricorsione non guarda mai più indietro della colonna t-1. Tutto il passato remoto è già condensato nei valori V[t-1][r]. Questo non è un compromesso, è una conseguenza diretta della proprietà di Markov: dato lo stato al tempo t-1, il futuro è indipendente da come ci si è arrivati. L’algoritmo eredita la memoria corta del modello e ne fa la sua forza.

Terminazione, dopo aver riempito la colonna $T$ . La probabilità del cammino di Viterbi è il massimo dell’ultima colonna; lo stato finale è il suo arg max:

$P^* = \max_s V[T][s] \qquad\qquad \text{stato}_T = \arg\max_s V[T][s]$

Backtracing. Si parte dallo stato finale appena trovato e si segue all’indietro la catena dei backpointer: bp[T][stato_T] dà lo stato al tempo T-1, da lì bp[T-1][...] dà quello a T-2, e così via fino al tempo 1. La sequenza viene fuori al contrario, dall’ultimo al primo: si inverte, e si ha il cammino di Viterbi completo.

Una nota sul perché il backtracing serve. Durante la ricorsione l’algoritmo non sa ancora quale sarà lo stato finale vincente, quindi non può sapere quale cammino sopravvivrà. Tiene allora aperte tutte le N possibilità, una per stato finale, ognuna con la sua catena di backpointer. Solo alla fine, quando la colonna T è completa e l’arg max indica il vincitore, si può risalire la catena giusta. Il backtracing non ricalcola nulla: legge soltanto i puntatori già scritti durante la ricorsione. È un’operazione $O(T)$ , trascurabile rispetto al riempimento della tabella. Tutto il costo di Viterbi sta nel riempimento in avanti; la ricostruzione è quasi gratis.

In pseudocodice:

funzione viterbi(osservazioni o[1..T], stati S, pi, A, B):
    # inizializzazione
    per ogni stato s in S:
        V[1][s] = pi[s] * B[s][o[1]]
        bp[1][s] = nessuno

    # ricorsione
    per t da 2 a T:
        per ogni stato s in S:
            miglior_r = argmax sui r di ( V[t-1][r] * A[r][s] )
            V[t][s]   = V[t-1][miglior_r] * A[miglior_r][s] * B[s][o[t]]
            bp[t][s]  = miglior_r

    # terminazione
    ultimo = argmax sui s di V[T][s]

    # backtracing
    cammino = [ ultimo ]
    per t da T fino a 2:
        ultimo = bp[t][ultimo]
        anteponi ultimo a cammino

    ritorna cammino, V[T][ argmax ]

Il costo, e perché non è esponenziale

Conta le operazioni. La tabella V ha $T \cdot N$ celle. Riempire una cella richiede di calcolare un massimo su $N$ predecessori, quindi $N$ operazioni. Totale: $O(T \cdot N^2)$ . Lineare nella lunghezza della sequenza, quadratico nel numero di stati.

Confronta con la forza bruta. Le sequenze di stati possibili sono $N^T$ : a ogni istante uno qualsiasi degli $N$ stati, per $T$ istanti. Enumerarle e valutarle costa $O(N^T \cdot T)$ . La crescita è esponenziale in $T$ . Con $N = 10$ stati e $T = 100$ osservazioni — una frase corta, una sequenza audio brevissima — la forza bruta affronta $10^{100}$ sequenze. È un numero più grande del numero di atomi nell’universo osservabile. Viterbi sullo stesso problema fa circa $100 \cdot 10^2 = 10\,000$ operazioni.

Da dove viene il salto da $10^{100}$ a $10^4$ ? Dal fatto che le $N^T$ sequenze non sono indipendenti: condividono prefissi a valanga. Innumerevoli sequenze passano per lo stato s al tempo t; tutte hanno bisogno di sapere “qual è il miglior modo di arrivare a s al tempo t”, e la forza bruta lo ricalcola da capo per ognuna. Viterbi lo calcola una volta sola e lo deposita in V[t][s]. Il numero di cose da calcolare non è il numero di cammini ( $N^T$ ) ma il numero di celle ( $T \cdot N$ ). Questo è precisamente il principio della programmazione dinamica: sottoproblemi che si sovrappongono, calcolati una volta e riusati. La sottostruttura ottima — vista nell’angolo 2 dell’intuizione — è la garanzia che comporre soluzioni ottime di sottoproblemi dà la soluzione ottima globale. Per questo Viterbi non è un’euristica veloce: è la soluzione esatta, semplicemente calcolata bene.

Vale la pena rendere concreto il guadagno con un conto intermedio. Pensa alla colonna t del trellis. Una ricerca esaustiva, per riempirla, dovrebbe enumerare tutti i cammini che la attraversano: a quel punto sono già $N^t$ . Viterbi invece tratta la colonna t come N sottoproblemi indipendenti — uno per stato — e ognuno guarda solo la colonna t-1, mai più indietro. Il “mai più indietro” è il punto: la colonna t-1 ha già condensato in N numeri tutto ciò che serve sapere del passato. Non è un’approssimazione che butta via informazione; è la sottostruttura ottima che garantisce che quei N numeri sono tutto ciò che serve. Il passato remoto non viene dimenticato per pigrizia, viene dimenticato perché è genuinamente irrilevante una volta fissato lo stato della colonna precedente. È la proprietà di Markov che lavora a favore dell’algoritmo: poiché il futuro dipende dal passato solo attraverso lo stato corrente, basta sapere il meglio per ogni stato corrente.

Decoding, evaluation, e la differenza di una sola operazione

Sul trellis di un HMM girano tre algoritmi diversi, e la cosa sorprendente è quanto poco li separi.

L’algoritmo di Viterbi è quello che abbiamo visto: ricorsione con il massimo sui predecessori. Risponde a “qual è la singola sequenza di stati più probabile?”. Il suo output è un cammino.

Il forward algorithm risolve il problema dell’evaluation: “qual è la probabilità totale di aver osservato questa sequenza, sotto il modello?”. La sua ricorsione è quasi identica a quella di Viterbi, ma con la somma al posto del massimo:

$\alpha[t][s] = \left( \sum_{r} \alpha[t-1][r] \cdot a_{rs} \right) \cdot b_s(o_t)$

Stesso trellis, stesse celle, stessa struttura. Cambia un operatore: max diventa somma. Il significato però cambia del tutto. Viterbi, prendendo il massimo, segue una singola sequenza — la migliore — e ignora tutte le altre. Il forward, sommando, accumula il contributo di tutte le sequenze possibili: il suo output non è un cammino, è un numero, la probabilità della sequenza osservata marginalizzata su ogni possibile sequenza di stati nascosti.

Detta in termini di distribuzioni: sulla totalità delle sequenze di stati esiste una distribuzione di probabilità. Viterbi ne trova la moda — il punto più alto, la sequenza singola più probabile. Il forward ne calcola la massa totale. Sono due domande genuinamente diverse, risolte dallo stesso scheletro algoritmico con un operatore scambiato.

Esiste un terzo algoritmo, il forward-backward, che combina la ricorsione forward con una ricorsione backward analoga per calcolare, per ogni istante e ogni stato, la probabilità a posteriori di trovarsi in quello stato in quell’istante. Da qui nasce il posterior decoding: invece di cercare la sequenza congiuntamente più probabile, si sceglie a ogni istante lo stato individualmente più probabile.

Attenzione, perché qui si annida una confusione frequente. Il posterior decoding e il cammino di Viterbi non sono la stessa cosa e in generale non coincidono. Il posterior decoding ottimizza ogni istante per conto suo; può quindi produrre una sequenza che, presa nel suo insieme, è illegale — contenere una transizione tra due stati che il modello dichiara impossibile (probabilità zero), perché quei due stati erano sì i più probabili ai loro rispettivi istanti, ma non potevano stare uno dopo l’altro. Viterbi non ha questo difetto: ottimizza la sequenza nel suo complesso e restituisce sempre un cammino legale. Quando i vincoli di transizione contano — e nei task di sequence labeling contano spesso — Viterbi è la scelta giusta proprio per questo.

Il sottoflusso numerico e il trucco del logaritmo

C’è un problema pratico che colpisce ogni implementazione ingenua di Viterbi, e che vale la pena affrontare in chiaro perché la soluzione è istruttiva.

Il valore di una cella V[t][s] è un prodotto di tanti fattori — una probabilità iniziale, t probabilità di emissione, t-1 probabilità di transizione — e ogni fattore è un numero compreso tra 0 e 1. Moltiplicare numeri minori di 1 li rende sempre più piccoli. Per una sequenza lunga il prodotto diventa minuscolo: per una sequenza di qualche centinaio di osservazioni si scende facilmente sotto $10^{-300}$ . A quel punto si scontra con il limite della rappresentazione in virgola mobile: un numero a 64 bit non riesce a rappresentare valori così piccoli e li arrotonda a zero. Questo si chiama underflow, sottoflusso. Quando succede, tutte le celle diventano zero, il arg max non sa più chi scegliere, e l’algoritmo restituisce spazzatura.

La soluzione standard è lavorare nello spazio dei logaritmi. Invece di memorizzare $V[t][s]$ , si memorizza $\log V[t][s]$ . Il trucco si appoggia a due proprietà del logaritmo. Primo: il logaritmo è una funzione monotona crescente, quindi lo stato che massimizza il prodotto è lo stesso che massimizza il logaritmo del prodotto — il arg max, e quindi il cammino di Viterbi, non cambia affatto. Secondo: il logaritmo trasforma i prodotti in somme, perché $\log(x \cdot y) = \log x + \log y$ . La ricorsione diventa:

$\log V[t][s] = \max_{r} \left( \log V[t-1][r] + \log a_{rs} \right) + \log b_s(o_t)$

Le moltiplicazioni sono diventate addizioni. E un log-probabilità è un numero negativo di magnitudine moderata: una probabilità di $e^{-700}$ , impossibile da rappresentare direttamente, diventa il logaritmo $-700$ , un numero che la virgola mobile gestisce senza battere ciglio. In più le somme sono più rapide e numericamente più stabili dei prodotti. Quasi tutte le implementazioni reali di Viterbi girano in spazio logaritmico.

Un’osservazione che chiude il cerchio con gli altri capitoli di questa Parte. In spazio logaritmico le probabilità di transizione ed emissione, essendo minori di 1, hanno logaritmo negativo. Massimizzare la somma dei log-probabilità (numeri negativi) equivale a minimizzare la somma dei loro opposti (numeri positivi). Se chiamiamo $-\log a_{rs}$ il “costo” dell’arco, allora Viterbi sta cercando il cammino di costo minimo nel trellis: è letteralmente un problema di shortest path su un grafo a strati, della stessa famiglia di quelli visti in search-bfs-dfs e A*. Il trucco del logaritmo non è solo un espediente numerico: è anche ciò che rivela la natura di Viterbi come algoritmo di cammino minimo.

Per inciso, il forward algorithm in spazio logaritmico è più delicato, perché lì bisogna sommare probabilità, non massimizzarle, e la somma non si trasforma altrettanto bene: serve la tecnica nota come log-sum-exp. Viterbi se la cava con il logaritmo puro proprio perché ha solo il massimo, e il massimo in spazio logaritmico resta un banale massimo.

Esempi

Esempio 1 — numerico: tre giorni di tempo

Riprendiamo l’HMM del tempo meteorologico, semplificato a due stati e tre osservazioni, e lo decodifichiamo a mano.

Stati nascosti: Sole (So) e Pioggia (Pi). Osservazioni possibili: ombrello e passeggiata. I parametri del modello:

Iniziali: $\pi(\text{So}) = 0.6$ , $\pi(\text{Pi}) = 0.4$ .
Transizioni: $a_{\text{So}\to\text{So}} = 0.7$ , $a_{\text{So}\to\text{Pi}} = 0.3$ , $a_{\text{Pi}\to\text{So}} = 0.4$ , $a_{\text{Pi}\to\text{Pi}} = 0.6$ .
Emissioni: dallo stato Sole, $b_{\text{So}}(\text{passeggiata}) = 0.8$ e $b_{\text{So}}(\text{ombrello}) = 0.2$ ; dallo stato Pioggia, $b_{\text{Pi}}(\text{passeggiata}) = 0.3$ e $b_{\text{Pi}}(\text{ombrello}) = 0.7$ .

Sequenza osservata su tre giorni: [passeggiata, ombrello, ombrello]. Qual è la sequenza di tempo più probabile?

Giorno 1 (inizializzazione), osservazione passeggiata:

$V[1][\text{So}] = \pi(\text{So}) \cdot b_{\text{So}}(\text{passeggiata}) = 0.6 \cdot 0.8 = 0.48$
$V[1][\text{Pi}] = \pi(\text{Pi}) \cdot b_{\text{Pi}}(\text{passeggiata}) = 0.4 \cdot 0.3 = 0.12$

Giorno 2 (ricorsione), osservazione ombrello. Per la cella So, confronto le due strade per arrivare a Sole:

da So: $V[1][\text{So}] \cdot a_{\text{So}\to\text{So}} = 0.48 \cdot 0.7 = 0.336$
da Pi: $V[1][\text{Pi}] \cdot a_{\text{Pi}\to\text{So}} = 0.12 \cdot 0.4 = 0.048$

Vince la provenienza da So (0.336). Quindi $V[2][\text{So}] = 0.336 \cdot b_{\text{So}}(\text{ombrello}) = 0.336 \cdot 0.2 = 0.0672$ , e bp[2][So] = So.

Per la cella Pi:

da So: $0.48 \cdot 0.3 = 0.144$
da Pi: $0.12 \cdot 0.6 = 0.072$

Vince da So (0.144). Quindi $V[2][\text{Pi}] = 0.144 \cdot b_{\text{Pi}}(\text{ombrello}) = 0.144 \cdot 0.7 = 0.1008$ , e bp[2][Pi] = So.

Giorno 3 (ricorsione), osservazione ombrello. Per la cella So:

da So: $V[2][\text{So}] \cdot a_{\text{So}\to\text{So}} = 0.0672 \cdot 0.7 = 0.04704$
da Pi: $V[2][\text{Pi}] \cdot a_{\text{Pi}\to\text{So}} = 0.1008 \cdot 0.4 = 0.04032$

Vince da So. $V[3][\text{So}] = 0.04704 \cdot 0.2 = 0.009408$ , bp[3][So] = So.

Per la cella Pi:

da So: $0.0672 \cdot 0.3 = 0.02016$
da Pi: $0.1008 \cdot 0.6 = 0.06048$

Vince da Pi. $V[3][\text{Pi}] = 0.06048 \cdot 0.7 = 0.042336$ , bp[3][Pi] = Pi.

Terminazione. L’ultima colonna: $V[3][\text{So}] = 0.0094$ , $V[3][\text{Pi}] = 0.0423$ . Il massimo è Pioggia. Backtracing: parto da Pi al giorno 3; bp[3][Pi] = Pi, quindi giorno 2 è Pioggia; bp[2][Pi] = So, quindi giorno 1 è Sole. Il cammino di Viterbi è [Sole, Pioggia, Pioggia].

Ha senso: il primo giorno una passeggiata punta al Sole, poi due ombrelli di fila spostano la stima verso la Pioggia, che per giunta tende a persistere. Si noti che la decisione sul giorno 1 — Sole — è emersa solo alla fine, dal backtracing: è il segno che Viterbi ottimizza la sequenza intera, non i singoli giorni in isolamento.

C’è un confronto istruttivo da fare con il posterior decoding. Se invece di seguire i backpointer avessimo scelto, giorno per giorno, lo stato con la cella di valore più alto, al giorno 2 avremmo guardato $V[2][\text{So}] = 0.0672$ contro $V[2][\text{Pi}] = 0.1008$ e scelto Pioggia, coerente con Viterbi qui. Ma in generale i due metodi divergono, e su modelli con transizioni rare il posterior decoding può incollare due stati che il modello vieta di mettere in fila. Viterbi, seguendo un cammino unico costruito coi backpointer, non può mai produrre una sequenza illegale: ogni transizione del cammino è una transizione che esisteva nel trellis.

Esempio 2 — in codice: Viterbi in spazio logaritmico

Un’implementazione compatta in Python che lavora con log-probabilità, come si fa nella pratica per evitare l’underflow.

import math

def viterbi_log(osservazioni, stati, log_pi, log_A, log_B):
    T = len(osservazioni)
    V  = [dict() for _ in range(T)]   # log-prob del miglior cammino
    bp = [dict() for _ in range(T)]   # backpointer

    # inizializzazione: t = 0
    o0 = osservazioni[0]
    for s in stati:
        V[0][s] = log_pi[s] + log_B[s][o0]
        bp[0][s] = None

    # ricorsione
    for t in range(1, T):
        ot = osservazioni[t]
        for s in stati:
            # miglior predecessore: somma di log, non prodotto
            miglior_r = max(stati, key=lambda r: V[t-1][r] + log_A[r][s])
            V[t][s]  = V[t-1][miglior_r] + log_A[miglior_r][s] + log_B[s][ot]
            bp[t][s] = miglior_r

    # terminazione
    ultimo = max(stati, key=lambda s: V[T-1][s])
    log_prob = V[T-1][ultimo]

    # backtracing
    cammino = [ultimo]
    for t in range(T-1, 0, -1):
        ultimo = bp[t][ultimo]
        cammino.append(ultimo)
    cammino.reverse()

    return cammino, log_prob

Le moltiplicazioni della formula sono diventate addizioni (+), perché lavoriamo in spazio logaritmico. I parametri vanno passati già in forma di logaritmo: chi chiama la funzione applica math.log a probabilità iniziali, transizioni ed emissioni una volta sola, all’inizio. La struttura ricalca riga per riga le quattro fasi della meccanica: inizializzazione, ricorsione con max su V[t-1][r] + log_A[r][s], terminazione con l’arg max sull’ultima colonna, backtracing che risale i backpointer e poi inverte. La complessità è quella prevista: i due cicli annidati su t e s, con il max interno su r, danno $O(T \cdot N^2)$ .

Esempio 3 — scenario reale: il POS tagging

L’etichettatura grammaticale, in inglese part-of-speech tagging o POS tagging, assegna a ogni parola di una frase la sua categoria grammaticale: nome, verbo, articolo, aggettivo. È stato per anni l’applicazione-bandiera di Viterbi nel linguaggio naturale.

L’inquadramento come HMM è diretto. Gli stati nascosti sono i tag grammaticali — ciò che vogliamo ricostruire e che il testo non rende esplicito. Le osservazioni sono le parole della frase, ciò che vediamo. La matrice di transizione cattura la sintassi: la probabilità che un tag segua un altro, stimata contando su un corpus annotato. Un articolo è quasi sempre seguito da un nome o un aggettivo, quasi mai da un verbo coniugato; questa regolarità finisce nei numeri di $A$ . La funzione di emissione cattura il lessico: la probabilità che un dato tag produca una data parola. Il tag “nome” emette “casa” con probabilità alta, “corre” con probabilità bassissima.

Prendi una frase ambigua. La parola inglese “book” può essere un nome (“a book”, un libro) o un verbo (“to book”, prenotare). Da sola è indecidibile. Ma nella frase “the book”, l’articolo “the” che precede ha una transizione fortissima verso il tag nome e debolissima verso il tag verbo. Viterbi, ottimizzando la sequenza intera di tag, sfrutta proprio questo: la transizione articolo-nome pesa più dell’eventuale leggera preferenza lessicale, e “book” viene etichettata correttamente come nome. È esattamente il motivo per cui serve Viterbi e non una decisione parola-per-parola: la categoria giusta di una parola dipende dal contesto delle parole vicine, e Viterbi è l’algoritmo che trova la sequenza di tag globalmente più coerente.

In termini di codice, l’inquadramento è una manciata di dizionari, e poi la stessa funzione viterbi_log dell’esempio 2. La funzione logify qui sotto converte un dizionario di probabilità in log-probabilità, mandando lo zero a meno infinito:

def logify(d):
    return {k: (math.log(p) if p > 0 else float("-inf"))
            for k, p in d.items()}

stati = ["ART", "NOME", "VERBO"]            # tag grammaticali
log_pi = logify({"ART": 0.5, "NOME": 0.4, "VERBO": 0.1})

# transizioni: dopo un articolo, quasi sempre un nome
log_A = { "ART":   logify({"ART": 0.01, "NOME": 0.94, "VERBO": 0.05}),
          "NOME":  logify({"ART": 0.05, "NOME": 0.30, "VERBO": 0.65}),
          "VERBO": logify({"ART": 0.55, "NOME": 0.40, "VERBO": 0.05}) }

# emissioni: "book" puo' essere nome o verbo
log_B = { "ART":   logify({"the": 0.9,  "book": 0.0}),
          "NOME":  logify({"the": 0.0,  "book": 0.6}),
          "VERBO": logify({"the": 0.0,  "book": 0.3}) }

cammino, _ = viterbi_log(["the", "book"], stati, log_pi, log_A, log_B)
# -> ['ART', 'NOME']: la transizione ART->NOME domina

Il decoding restituisce ['ART', 'NOME']: anche se la parola “book” da sola sarebbe stata leggermente più probabile come nome che come verbo, è la transizione fortissima ART -> NOME a fissare la scelta. È il contesto, codificato in log_A, a risolvere l’ambiguità — ed è precisamente ciò che una decisione parola-per-parola non potrebbe fare.

Lo stesso schema si applica al named-entity recognition (NER), il riconoscimento delle entità nominate — nomi di persone, luoghi, organizzazioni. Qui gli stati nascosti sono etichette in formato BIO: B-PER per l’inizio di un nome di persona, I-PER per la sua continuazione, O per le parole fuori da ogni entità, e così via. Una transizione da O a I-PER è illegale — non si può “continuare” un’entità che non è “cominciata” — e una matrice di transizione che le assegna probabilità zero, decodificata con Viterbi, garantisce che la sequenza di etichette prodotta sia sempre ben formata. Il posterior decoding, scegliendo le etichette in modo indipendente, potrebbe invece produrre una sequenza illegale: un altro modo di vedere perché, sotto vincoli di transizione, Viterbi è la scelta corretta.

Applicazioni pratiche

Oltre a POS tagging e NER, l’algoritmo di Viterbi compare in diversi punti del lavoro quotidiano di chi costruisce sistemi di linguaggio, audio e segnali.

Il riconoscimento del parlato classico — i sistemi che hanno dominato l’ASR per tre decenni prima dei modelli neurali end-to-end — è costruito su HMM. Gli stati nascosti sono unità fonetiche (fonemi o loro sotto-parti); le osservazioni sono vettori di feature acustiche estratti a finestre dal segnale audio. Viterbi decodifica la sequenza di unità fonetiche più probabile, da cui si ricostruisce la trascrizione. Ogni assistente vocale e ogni sistema di dettatura pre-2015 aveva un decoder Viterbi nel cuore. Vale la pena notare la scala: il trellis di un sistema di riconoscimento del parlato non ha pochi stati, ne ha molti, perché incorpora il modello acustico, il dizionario di pronunce e il modello di linguaggio compilati insieme. In quel regime il termine $N^2$ comincia a pesare, e i sistemi reali usano una variante potata di Viterbi — il beam search Viterbi — che a ogni colonna scarta gli stati con punteggio troppo distante dal migliore. È la prova, sul campo, della parentela tra Viterbi esatto e beam-search: lo stesso algoritmo, con o senza potatura, a seconda di quanti stati il problema mette in gioco.

In bioinformatica Viterbi gira nei profile HMM, modelli che descrivono una famiglia di sequenze biologiche correlate. Database come Pfam catalogano migliaia di famiglie proteiche tramite profile HMM; allineare una nuova proteina a una famiglia significa decodificare con Viterbi la sequenza di stati — corrispondenza, inserzione, delezione — più probabile. Nei gene finder la stessa idea separa, lungo una sequenza di DNA, le regioni che codificano geni da quelle che non lo fanno: gli stati nascosti sono “dentro un gene” e “fuori da un gene”, l’osservazione è la sequenza di nucleotidi.

E naturalmente il dominio originale: la decodifica dei segnali nelle telecomunicazioni. I codici convoluzionali negli standard di telefonia mobile, nei modem, nei link satellitari e nelle comunicazioni con le sonde spaziali si decodificano con Viterbi. Qui gli “stati” sono lo stato interno dell’encoder convoluzionale e le “osservazioni” sono i simboli ricevuti dal canale rumoroso. Ogni telefono cellulare contiene, in hardware o in software, un decodificatore di Viterbi.

Il ponte verso il machine learning moderno

Viterbi non si è ritirato con gli HMM: è migrato. Il passaggio chiave sono i conditional random field (CRF), introdotti da John Lafferty, Andrew McCallum e Fernando Pereira nel 2001. Un CRF a catena lineare è un modello per il sequence labeling che, a differenza dell’HMM, non modella la probabilità generativa di osservazioni e stati, ma direttamente la probabilità condizionata delle etichette date le osservazioni. Questo gli permette di usare feature ricche e sovrapposte — la parola, la sua forma, il prefisso, le parole vicine — che un HMM, con la sua funzione di emissione rigida, non può sfruttare.

Cosa c’entra Viterbi. Il decoding di un CRF a catena lineare — trovare la sequenza di etichette di punteggio totale massimo — è esattamente lo stesso algoritmo. Si costruisce un trellis, dove ogni arco ha un punteggio invece di una probabilità, e si riempie la tabella con la stessa ricorsione max e gli stessi backpointer. Cambia solo l’origine dei pesi degli archi: nell’HMM sono probabilità generative stimate per conteggio, nel CRF sono punteggi appresi in modo discriminativo. La macchina di decoding è identica. Per questo dire “il CRF si decodifica con Viterbi” non è un’analogia: è la stessa procedura applicata a un trellis con pesi di origine diversa.

Questa filiazione arriva fino al deep learning. I modelli BiLSTM-CRF, standard per NER e POS tagging intorno al 2016-2018, mettono una rete neurale ricorrente a produrre i punteggi di emissione token per token, e sopra un layer CRF con decoding di Viterbi a imporre la coerenza di sequenza. La rete impara cosa dice ogni token; Viterbi garantisce che la sequenza di etichette nel suo insieme sia legale e globalmente coerente.

Oggi il sequence labeling si fa spesso con un transformer: per ogni token produce una distribuzione sulle etichette, e si prende l’arg max token per token. È decoding greedy, indipendente per posizione — si rinuncia alla garanzia di coerenza globale che Viterbi dava. La scommessa è che il contesto bidirezionale del transformer renda le predizioni locali già abbastanza coerenti da non aver bisogno di un decoder strutturato. La scommessa spesso funziona, ma non sempre: diversi sistemi mantengono ancora un layer CRF con Viterbi sopra il transformer proprio quando i vincoli di transizione sono forti e una sequenza di etichette illegale è inaccettabile. Viterbi non è stato cancellato dai transformer; è diventato uno strato opzionale che si aggiunge quando la struttura della sequenza conta più della comodità del decoding greedy.

Dove si rompe

Viterbi è esatto e veloce, ma “esatto” e “veloce” hanno confini precisi. Vale la pena tracciarli, perché è in questi confini che vivono gli errori di chi lo usa.

Il quadrato negli stati. La complessità è $O(T \cdot N^2)$ : lineare nella lunghezza della sequenza, ma quadratica nel numero di stati. Per un HMM con qualche decina o centinaia di stati va benissimo. Ma il termine $N^2$ esplode quando lo spazio di stati è grande. Se gli “stati” fossero le parole di un vocabolario — decine di migliaia — o i token di un modello di linguaggio, $N^2$ diventa proibitivo. È esattamente il regime in cui Viterbi non si può più usare e si passa alla beam search, che rinuncia all’esattezza per restare trattabile. Viterbi è il lusso dell’esattezza che ci si può permettere solo quando gli stati sono pochi.

La proprietà di Markov è un’assunzione, non un fatto. L’HMM su cui Viterbi opera assume che il prossimo stato dipenda solo da quello corrente, e che l’osservazione dipenda solo dallo stato corrente. È un’assunzione di memoria corta. Per molti fenomeni reali è falsa: nel linguaggio la categoria grammaticale di una parola dipende da un contesto largo, non solo dal tag immediatamente precedente. Si può allargare la memoria — HMM di ordine superiore, dove lo stato incorpora gli ultimi due o tre stati — ma il prezzo è che $N$ cresce esponenzialmente con l’ordine, e il termine $N^2$ di Viterbi cresce con lui. C’è una tensione strutturale tra quanta memoria si vuole modellare e quanto l’algoritmo resta trattabile.

Viterbi è ottimo rispetto al modello, non rispetto al mondo. L’algoritmo trova il cammino di probabilità massima sotto i parametri $A$ , $B$ , $\pi$ che gli vengono dati. Se quei parametri sono stimati male — corpus di training piccolo, distorto, non rappresentativo — Viterbi restituirà fedelmente il cammino ottimo di un modello sbagliato. L’errore non è dell’algoritmo: è del modello. Questa è la stessa distinzione tra errore di ricerca ed errore di modello che beam-search tratta in dettaglio. Viterbi non commette mai errori di ricerca — trova sempre l’ottimo — ma è completamente alla mercé degli errori di modello.

Viterbi dà la sequenza congiunta, non le probabilità marginali. È una confusione ricorrente. Se la domanda è “qual è la sequenza di stati più probabile nel suo insieme”, la risposta è Viterbi. Se la domanda è “in questa posizione specifica, qual è lo stato più probabile, e con quanta confidenza”, la risposta non è Viterbi: è il posterior decoding, che richiede l’algoritmo forward-backward. Usare il cammino di Viterbi per leggere “la confidenza sullo stato al tempo t” è un errore: il valore V[t][s] non è la probabilità di trovarsi in s al tempo t, è la probabilità del miglior cammino che passa per s al tempo t — un oggetto diverso.

Il cammino di Viterbi e la sequenza degli stati marginalmente più probabili possono divergere. Conseguenza del punto precedente, ma vale isolarla perché è controintuitiva. Si potrebbe pensare che “la sequenza più probabile” sia uguale a “metti in fila, posizione per posizione, lo stato più probabile di quella posizione”. Falso. Le due sequenze sono in generale diverse, e la seconda può addirittura essere illegale sotto il modello — contenere una transizione a probabilità zero. Viterbi ottimizza l’oggetto giusto, la sequenza intera; la concatenazione di scelte locali ottime non lo fa.

Pareggi e instabilità. Quando due predecessori danno esattamente lo stesso valore nel max, l’arg max deve rompere il pareggio in modo arbitrario. Implementazioni diverse lo fanno in modo diverso, e su modelli quasi-degeneri questo può portare a cammini di Viterbi diversi a parità di probabilità. Non è un errore — entrambi i cammini sono ottimi — ma è una sorgente di non-determinismo che sorprende chi confronta due implementazioni.

Una sola risposta, nessuna misura di ambiguità. Viterbi restituisce il cammino migliore e basta. Non dice quanto il secondo cammino migliore gli stava vicino. Una sequenza di osservazioni può essere genuinamente ambigua — due interpretazioni quasi equiprobabili — e Viterbi sceglierà comunque, in modo secco, una delle due, senza segnalare che la decisione era sul filo. Se serve sapere quanto la risposta è robusta, Viterbi da solo non basta: occorre l’algoritmo forward per la probabilità totale, oppure varianti come l’N-best che producono le N sequenze migliori invece di una sola. La singola risposta è comoda finché non si confonde “il cammino più probabile” con “il cammino certo”.

Le emissioni a probabilità zero propagano il disastro. Se in un punto della sequenza l’osservazione corrente non è mai stata vista emessa da nessuno stato — una parola fuori vocabolario nel POS tagging, un simbolo mai osservato in training — tutte le probabilità di emissione $b_s(o_t)$ valgono zero per quell’istante. In spazio logaritmico questo è $-\infty$ . L’intera colonna del trellis collassa, e con essa il cammino. Le implementazioni serie aggiungono uno smoothing — una piccola probabilità di fondo a ogni emissione — proprio per evitare che un singolo simbolo sconosciuto azzeri la decodifica dell’intera sequenza. È un problema di modello più che di algoritmo, ma si manifesta come un fallimento di Viterbi, e va riconosciuto come tale.

Collegamenti

programmazione-dinamica — Viterbi è un caso esemplare di programmazione dinamica: sottostruttura ottima, sottoproblemi sovrapposti, tabella riempita una volta. Il capitolo sulla DP fornisce il quadro generale di cui Viterbi è un’istanza.
beam-search — la beam search è Viterbi che rinuncia all’esattezza per spazi di stati troppo grandi. Sul trellis di un HMM, Viterbi è la beam search con beam pari al numero di stati: nessuna potatura, decoding esatto. Analogia strutturale precisa, non filiazione storica.
catene-markov — lo strato nascosto di un HMM è una catena di Markov; la matrice di transizione e la proprietà di Markov del primo ordine vengono da lì.
processi-stocastici — l’HMM è un processo stocastico a due strati; il capitolo dà il contesto generale dei sistemi che evolvono nel tempo in modo casuale.
search-bfs-dfs — in spazio logaritmico Viterbi è la ricerca del cammino di costo minimo su un grafo a strati, della stessa famiglia degli algoritmi di ricerca su grafo.
A* — come Viterbi, A* cerca un cammino ottimo su grafo pesato; la differenza è che A* tiene una frontiera potata da un’euristica, Viterbi tiene tutta la colonna del trellis.
monte-carlo-tree-search — l’altra strategia per spazi troppo grandi per la ricerca esatta; utile come termine di paragone su quando l’esattezza è alla portata e quando no.
rinascita-statistica-90 (in preparazione) — gli HMM e Viterbi sono al centro della svolta statistica dell’AI negli anni ‘90, il passaggio dalla logica alle probabilità.
hmm (in preparazione) — il capitolo dedicato ai modelli di Markov nascosti completi, dove Viterbi è uno dei tre algoritmi accanto a forward e Baum-Welch.
entropia-cross-entropy (in preparazione) — il trucco del logaritmo che rende Viterbi numericamente stabile usa la stessa proprietà che trasforma prodotti di probabilità in somme di log alla base della cross-entropy.

Per andare oltre

A. J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, IEEE Transactions on Information Theory, vol. 13, pp. 260-269, 1967. Il paper originale: l’algoritmo nasce qui, come strumento per la decodifica dei codici convoluzionali.
G. D. Forney Jr., “The Viterbi Algorithm: A Personal History”, arXiv:cs/0504020, 2005. Resoconto storico di prima mano di chi battezzò l’algoritmo: il contesto del 1967, il riconoscimento come programmazione dinamica, le scoperte indipendenti multiple.
L. R. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Proceedings of the IEEE, vol. 77, n. 2, pp. 257-286, 1989. Il tutorial di riferimento sugli HMM: formalizza i tre problemi canonici e presenta Viterbi, forward e Baum-Welch in notazione standard.
D. Jurafsky, J. H. Martin, “Speech and Language Processing”, 3a edizione in bozza, appendice A “Hidden Markov Models”. Trattazione didattica di HMM e Viterbi in ambito linguaggio naturale, con la distinzione max-vs-somma e il POS tagging come esempio guida. Disponibile online sul sito di Jurafsky a Stanford.
J. Lafferty, A. McCallum, F. Pereira, “Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data”, ICML 2001. Introduce i conditional random field: il loro decoding è un Viterbi sul trellis dei punteggi appresi in modo discriminativo, il ponte verso il sequence labeling moderno.