Modelli nascosti di Markov spiegati con un esempio della vita reale e codice Python

I modelli nascosti di Markov spiegati con un esempio reale e codice Python

I Modelli Markoviani Nascosti sono modelli probabilistici utilizzati per risolvere problemi della vita reale che vanno dal qualcosa a cui tutti pensano almeno una volta alla settimana — com’è il tempo domani?[1] — a problemi di biologia molecolare complessi, come la previsione dei leganti peptidici alla molecola di classe II MHC umana[2].

I Modelli Markoviani Nascosti sono parenti stretti delle Catene di Markov, ma i loro stati nascosti li rendono uno strumento unico da utilizzare quando si è interessati a determinare la probabilità di una sequenza di variabili casuali.

In questo articolo analizzeremo i Modelli Markoviani Nascosti in tutti i suoi diversi componenti e vedremo, passo dopo passo con il codice matematico e Python, quali stati emotivi hanno portato ai risultati del tuo cane in un esame di addestramento. Utilizzeremo l’Algoritmo di Viterbi per determinare la probabilità di osservare una specifica sequenza di osservazioni e come utilizzare l’Algoritmo di Forward per determinare la verosimiglianza di una sequenza osservata, quando si dispone di una sequenza di stati nascosti.

Il mondo reale è pieno di fenomeni per i quali possiamo vedere l’esito finale, ma non possiamo osservare effettivamente i fattori sottostanti che hanno generato quegli esiti. Un esempio è prevedere il tempo, determinando se domani sarà piovoso o soleggiato, in base alle osservazioni meteorologiche passate e alle probabilità osservate di diversi esiti meteorologici.

• Together AI rilascia RedPajama v2 un dataset aperto con 30 trilioni di token per addestrare grandi modelli di linguaggio.
• Il team dell’Imperial College London sviluppa un metodo di intelligenza artificiale per l’apprendimento per imitazione con pochi esempi padronanza di nuovi compiti del mondo reale con poche dimostrazioni
• Come la tecnologia Acoustic Touch offre una visione attraverso il suono

Anche se guidati da fattori che non possiamo osservare, con un Modello Markoviano Nascosto è possibile modellare questi fenomeni come sistemi probabilistici.

Modelli Markoviani con Stati Nascosti

I Modelli Markoviani Nascosti, noti come HMM in breve, sono modelli statistici che funzionano come una sequenza di problemi di etichettatura. Questi sono tipi di problemi che descrivono l’evoluzione di eventi osservabili che dipendono, a loro volta, da fattori interni che non possono essere direttamente osservati — sono nascosti[3].

Un Modello Markoviano Nascosto è composto da due distinti processi stocastici, che sono sequenze di variabili casuali — variabili che dipendono da eventi casuali.

C’è un processo invisibile e un processo osservabile.

Il processo invisibile è una Catena di Markov, come concatenare più stati nascosti che vengono attraversati nel tempo per raggiungere un risultato. Questo è un processo probabilistico perché tutti i parametri della Catena di Markov, così come il punteggio di ogni sequenza, sono in realtà probabilità[4].

I Modelli Markoviani Nascosti descrivono l’evoluzione di eventi osservabili che dipendono, a loro volta, da fattori interni che non possono essere direttamente osservati — sono nascosti[3]

Come qualsiasi altra Catena di Markov, per sapere quale stato seguirà devi avere informazioni solo sullo stato attuale — in quale stato della Catena di Markov ti trovi attualmente. La cronologia degli stati precedenti in cui sei stato in passato non conta per capire dove andrai a seguire.

Questo tipo di memoria a breve termine è una delle caratteristiche chiave degli HMM ed è chiamata l’Assunzione di Markov, che indica che la probabilità di raggiungere lo stato successivo dipende solo dalla probabilità dello stato corrente.

L’altra caratteristica chiave di un HMM è che assume anche che ogni osservazione dipenda solo dallo stato che l’ha prodotta, quindi sia completamente indipendente da qualsiasi altro stato nella catena[5].

La Assunzione di Markov afferma che la probabilità di raggiungere lo stato successivo dipende solo dalla probabilità dello stato corrente.

Tutte queste informazioni di base sono ottime per comprendere le HMM, ma in quali categorie di problemi vengono effettivamente utilizzate?

Le HMM aiutano a modellare il comportamento dei fenomeni. Oltre a modellare e consentire l’esecuzione di simulazioni, è possibile anche porre diverse tipologie di domande riguardanti tali fenomeni:

• Probabilità o Punteggio, determinando la probabilità di osservare una sequenza
• Decodifica della migliore sequenza di stati che ha generato una specifica osservazione
• Apprendimento dei parametri della HMM che ha portato all’osservazione di una determinata sequenza, che ha attraversato uno specifico set di stati.

Vediamolo in pratica!

Prestazioni dell’addestramento del cane come HMM

Oggi non ti preoccupi tanto delle previsioni del tempo, ma è possibile che il tuo cane stia diplomandosi dal corso di addestramento. Dopo tutto il tempo, lo sforzo e le leccornie per cani coinvolti, tutto ciò che vuoi è che lui o lei riesca.

Durante le sessioni di addestramento del cane, si chiede al tuo amico a quattro zampe di eseguire alcune azioni o trucchi, in modo che l’addestratore possa osservare e valutare le sue prestazioni. Dopo aver combinato i punteggi di tre prove, si deciderà se il tuo cane si diplomerà o avrà bisogno di ulteriori allenamenti.

L’addestratore vede solo il risultato, ma ci sono diversi fattori che non possono essere osservati direttamente, come ad esempio se il tuo cane è stanco, felice, se non piace affatto all’addestratore o se non gli piacciono gli altri cani intorno.

Nessuno di questi fattori viene osservato direttamente, a meno che non ci sia indubbiamente una specifica azione che il tuo cane compie solo quando si sente in un certo modo. Sarebbe fantastico se potesse esprimere come si sente a parole, magari in futuro!

Con le Hidden Markov Models fresche nella tua mente, questa sembra essere l’opportunità perfetta per cercare di prevedere come il tuo cane si sentiva durante l’esame. Potrebbe ottenere un certo punteggio perché era stanco, forse aveva fame o era infastidito dall’addestratore.

Il tuo cane ha frequentato lezioni per un po’ di tempo e, sulla base dei dati raccolti durante quell’addestramento, hai tutti i blocchi di base necessari per costruire una Hidden Markov Model.

Per costruire una HMM che modella le prestazioni del tuo cane nella valutazione dell’addestramento, hai bisogno di:

• Stati Nascosti
• Matrice di Transizione
• Sequenza di Osservazioni
• Matrice di Probabilità delle Osservazioni
• Distribuzione di Probabilità Iniziale

Gli Stati Nascosti sono quei fattori non osservabili che influenzano la sequenza di osservazioni. Considererai solo se il tuo cane è Stanco o Felice.

Conoscendo molto bene il tuo cane, i fattori non osservabili che possono influenzare le sue prestazioni in un esame sono semplicemente essere stanco o felice.

Successivamente è necessario conoscere la probabilità di passare da uno stato all’altro, che è catturata in una Matrice di Transizione. Questa matrice deve essere anche stocastica per righe, il che significa che le probabilità da uno stato a qualsiasi altro stato nella catena, cioè ciascuna riga nella matrice, devono sommare ad uno.

Indipendentemente dal tipo di problema che stai risolvendo, hai sempre bisogno di una Sequenza di Osservazioni. Ogni osservazione rappresenta il risultato del percorso nella Catena di Markov. Ogni osservazione proviene da un vocabolario specifico.

Nel caso dell’esame del tuo cane, osservi il punteggio che ottengono dopo ogni prova, che può essere Sbagliato, OK o Perfetto. Questi sono tutti i possibili termini nel vocabolario di osservazione.

Hai anche bisogno della Matrice delle Probabilità di Osservazione, che è la probabilità che un’osservazione venga generata da uno stato specifico.

Infine, c’è la Distribuzione di Probabilità Iniziale. Questa è la probabilità che la Catena di Markov inizi in ogni specifico stato nascosto.

Può anche essere che alcuni stati non saranno mai lo stato iniziale nella Catena di Markov. In queste situazioni, la loro probabilità iniziale è zero. E proprio come le probabilità nella Matrice di Transizione, la somma di tutte le probabilità iniziali deve essere uguale a uno.

La Distribuzione di Probabilità Iniziale, insieme alla Matrice di Transizione e alla Probabilità di Osservazione, costituiscono i parametri di un Modello di Markov Nascosto. Queste sono le probabilità che stai cercando di determinare se hai una sequenza di osservazioni e stati nascosti, e cerchi di capire quale specifico Modello di Markov Nascosto potrebbe averle generate.

Mettendo insieme tutti questi pezzi, ecco come appare il modello di Markov Nascosto che rappresenta le prestazioni del tuo cane all’esame di allenamento.

Durante l’esame, il tuo cane effettuerà tre prove e si laureerà solo se non fallirà in due di quelle prove.

Alla fine della giornata, se il tuo cane ha bisogno di ulteriori allenamenti, ti prenderai comunque cura di lui allo stesso modo. La grande domanda che ti frulla nella mente è Come si sentono durante l’esame.

Immaginando uno scenario in cui si laureano con un punteggio di OK – Sbagliato – Perfetto esattamente in quest’ordine, in quale sequenza di stati emotivi si troveranno? Saranno principalmente stanchi o affamati durante tutto il tempo, o forse una combinazione di entrambi?

Questo tipo di problema rientra nella categoria dei problemi di Decodifica a cui possono essere applicati i Modelli di Markov Nascosti. In questo caso, sei interessato a capire qual è la miglior sequenza di stati che ha generato una specifica sequenza di osservazioni, OK – Sbagliato – Perfetto.

Il problema di decodificare la sequenza di stati che ha generato una data sequenza di osservazioni fa leva sull’uso dell’Algoritmo di Viterbi. Tuttavia, vale la pena fare una breve deviazione e dare un’occhiata a come potresti calcolare la probabilità di una data sequenza di osservazioni – un compito di Probabilità – utilizzando il Algoritmo Forward. Questo preparerà il terreno per una migliore comprensione di come funziona l’Algoritmo di Viterbi.

L’Algoritmo Forward

Se stessi modellando questo problema come una normale Catena di Markov e volessi calcolare la probabilità di osservare la sequenza di esiti OK, Sbagliato, Perfetto, attraverseresti la catena atterrando in ogni stato specifico che genera l’esito desiderato. Ad ogni passo, prendi la probabilità condizionata di osservare l’esito corrente dato che hai osservato l’esito precedente e moltiplica quella probabilità per la probabilità di transizione di passare da uno stato all’altro.

La grande differenza è che, in una normale Catena di Markov, tutti gli stati sono ben noti e osservabili. Non in un Modello di Markov Nascosto! In un Modello di Markov Nascosto, osservi una sequenza di esiti, senza sapere quale sequenza specifica di stati nascosti doveva essere attraversata per osservarli.

La grande differenza è che, in una normale Catena di Markov, tutti gli stati sono ben noti e osservabili. Non in un Modello di Markov Nascosto!

A questo punto potresti pensare: Beh, posso semplicemente percorrere tutti i possibili percorsi e alla fine avere una regola per selezionare tra percorsi equivalenti. La definizione matematica di questo approccio assomiglia a qualcosa del genere

Questa è sicuramente una strategia! Dovresti calcolare la probabilità di osservare la sequenza OK, Fail, Perfect per ogni singola combinazione di stati nascosti che potrebbe generare quella sequenza.

Quando hai un numero sufficientemente piccolo di stati nascosti e una sequenza di risultati osservati, è possibile effettuare questo calcolo in un tempo ragionevole.

Fortunatamente, il modello Hidden Markov che hai appena definito è relativamente semplice, con 3 risultati osservati e 2 stati nascosti.

Per una sequenza osservata di lunghezza L, su un HMM con M stati nascosti, hai “M alla potenza L” stati possibili che nel tuo caso significa 2 alla potenza di 3, cioè 8 percorsi possibili per la sequenza OK — Fail — Perfect, comportando una complessità computazionale esponenziale di O(M^L L), descritta nella Notazione O Grande. Man mano che la complessità del modello aumenta, il numero di percorsi da prendere in considerazione cresce in modo esponenziale.

Man mano che la complessità del modello aumenta, il numero di percorsi da prendere in considerazione cresce in modo esponenziale.

Ecco dove brilla l’Algoritmo Forward.

L’Algoritmo Forward calcola la probabilità di un nuovo simbolo nella sequenza osservata, senza la necessità di calcolare le probabilità di tutti i percorsi possibili che formano quella sequenza [3].

Invece di calcolare le probabilità di tutti i percorsi possibili che formano quella sequenza, l’algoritmo definisce la variabile forward e ne calcola il valore ricorsivamente.

Il fatto che utilizzi la ricorsione è la ragione chiave per cui questo algoritmo è più veloce del calcolo di tutte le probabilità dei percorsi possibili. Infatti, può calcolare la probabilità di osservare la sequenza x in soli “L volte M alla potenza 2” calcoli, invece di “M alla potenza L volte L”.

Nel tuo caso, con 2 stati nascosti e una sequenza di 3 risultati osservati, questa è la differenza tra calcolare le probabilità O(MˆL L) = 2³x3 = 8×3 = 24 volte, rispetto a O(L Mˆ2)=3*2²=3×4 = 12 volte.

Questa riduzione del numero di calcoli viene ottenuta attraverso la Programmazione Dinamica, una tecnica di programmazione che utilizza una struttura dati ausiliaria per memorizzare le informazioni intermedie, garantendo così che i calcoli non vengano eseguiti più volte.

Ogni volta che l’algoritmo sta per calcolare una nuova probabilità, controlla se l’ha già calcolata e, in caso affermativo, può accedere facilmente a quel valore nella struttura dati intermedia. Altrimenti, viene calcolata la probabilità e il valore viene memorizzato.

Torniamo al tuo problema di decodifica, utilizzando l’Algoritmo di Viterbi.

L’Algoritmo di Viterbi

Pensando in pseudocodice, se volessi forzare la decodifica della sequenza di stati nascosti che generano una specifica sequenza di osservazioni, dovresti fare semplicemente:

• generare tutte le possibili permutazioni dei percorsi che portano alla sequenza di osservazione desiderata
• utilizzare l’Algoritmo di Forward per calcolare la probabilità di ciascuna sequenza di osservazione, per ciascuna possibile sequenza di stati nascosti
• scegliere la sequenza di stati nascosti con la probabilità più alta

Per il tuo specifico HMM, ci sono 8 possibili percorsi che portano a un risultato di OK — Fail — Perfect. Aggiungi solo un’altra osservazione, e avrai il doppio del numero di sequenze possibili di stati nascosti! Come descritto per l’Algoritmo di Forward, si finisce facilmente con un algoritmo complessivamente complesso ed è difficile ottenere performance elevate.

L’Algoritmo di Viterbi ti darà una mano.

Quando la sequenza di stati nascosti nell’HMM viene attraversata, ad ogni passaggio, la probabilità vt(j) è la probabilità che l’HMM si trovi nello stato nascosto j dopo aver visto l’osservazione ed essersi spostato attraverso lo stato più probabile che porta a j.

La chiave per decodificare la sequenza di stati nascosti che genera una specifica sequenza di osservazioni, è concetto di percorso più probabile. Chiamato anche percorso di Viterbi, il percorso più probabile è il percorso con la probabilità più alta, tra tutti i percorsi che possono portare a uno stato nascosto specifico.

La chiave per decodificare la sequenza di stati nascosti che genera una specifica sequenza di osservazioni, è utilizzare il percorso di Viterbi. Il percorso più probabile che porta a uno stato nascosto specifico.

Puoi fare un parallelismo tra l’Algoritmo di Forward e l’Algoritmo di Viterbi. Mentre l’Algoritmo di Forward somma tutte le probabilità per ottenere la probabilità di raggiungere uno stato specifico tenendo conto di tutti i percorsi che lo conducono, l’algoritmo di Viterbi non vuole esplorare tutte le possibilità. Si concentra sul percorso più probabile che porta a uno stato specifico.

Tornando al compito di decodificare la sequenza di stati nascosti che porta ai punteggi OK — Fail — Perfect nel loro esame, l’esecuzione dell’Algoritmo di Viterbi a mano sarebbe simile a questo

Un’altra caratteristica unica dell’algoritmo di Viterbi è che deve avere un modo per tenere traccia di tutti i percorsi che hanno portato a uno stato nascosto specifico, al fine di confrontare le loro probabilità. Per fare ciò tiene traccia dei backpointer di ciascuno stato nascosto, utilizzando una struttura dati ausiliaria tipica degli algoritmi di programmazione dinamica. In questo modo può accedere facilmente alla probabilità di qualsiasi percorso di Viterbi attraversato in passato.

I backpointer sono la chiave per capire il percorso più probabile che porta a una sequenza di osservazioni.

Nell’esempio dell’esame dei tuoi cani, quando calcoli i percorsi di Viterbi v3(Felice) e v3(Stanco), scegli il percorso con la probabilità più alta e inizi a tornare indietro, cioè a seguire a ritroso, attraverso tutti i percorsi che hanno portato a dove ti trovi.

L’algoritmo di Viterbi in Python

Far tutto questo a mano richiede tempo e può portare a errori. Se si sbaglia una cifra significativa, potrebbe essere necessario ricominciare da capo e rivedere tutte le probabilità!

La buona notizia è che puoi sfruttare librerie software come hmmlearn, e con poche righe di codice puoi decodificare la sequenza di stati nascosti che porta al superamento dell’esame del tuo cane con OK — Fail — Perfect, nella giusta sequenza.

da hmmlearn import hmmimport numpy as np## Parte 1. Generazione di un HMM con parametri specifici e simulazione dell'esameprint("Imposta il modello HMM con i parametri")# init_params sono i parametri utilizzati per inizializzare il modello per l'addestramento# s -> probabilità di inizio# t -> probabilità di transizione# e -> probabilità di emissionemodel = hmm.CategoricalHMM(n_components=2, random_state=425, init_params='ste')# probabilità iniziali# probabilità di iniziare nello stato Tired = 0# probabilità di iniziare nello stato Happy = 1initial_distribution = np.array([0.1, 0.9])model.startprob_ = initial_distributionprint("Passo 1. Completato - Distribuzione iniziale definita")# probabilità di transizione#        tired    happy# tired   0.4      0.6# happy   0.2      0.8transition_distribution = np.array([[0.4, 0.6], [0.2, 0.8]])model.transmat_ = transition_distributionprint("Passo 2. Completato - Matrice di transizione definita")# probabilità di osservazione#        Fail    OK      Perfect# tired   0.3    0.5       0.2# happy   0.1    0.5       0.4observation_probability_matrix = np.array([[0.3, 0.5, 0.2], [0.1, 0.5, 0.4]])model.emissionprob_ = observation_probability_matrixprint("Passo 3. Completato - Matrice di probabilità di osservazione definita")# simulazione di 100.000 tentativi, ovvero test di idoneitàtrials, simulated_states = model.sample(100000)# Output di un campione delle simulazioni dei test di idoneità# 0 -> Fail# 1 -> OK# 2 -> Perfectprint("\nEsempio di prove simulate - Basato sui parametri del modello")print(trials[:10])## Parte 2 - Decodifica della sequenza di stati nascosti che porta## a una sequenza di osservazioni OK - Fail - Perfect# divide i dati in set di addestramento e test (diviso a metà)X_train = trials[:trials.shape[0] // 2]X_test = trials[trials.shape[0] // 2:]model.fit(X_train)# l'esame aveva 3 prove e il tuo cane ha ottenuto i seguenti punteggi: OK, Fail, Perfect (1, 0, 2)exam_observations = [[1, 0, 2]]predicted_states = model.predict(X=[[1, 0, 2]])print("Prevedi le transizioni di stato nascosto che determinano i punteggi dell'esame OK, Fail, Perfect: \n 0 -> Tired , "      "1 -> Happy")print(predicted_states)

In pochi secondi ottieni un output che corrisponde ai risultati dei calcoli effettuati a mano, molto più veloce e con molto meno margine di errore.

Conclusioni

Ciò che affascina dei Modelli di Markov Nascosti è quanto questo strumento statistico creato nella metà degli anni ’60 [6] sia potente e applicabile a problemi del mondo reale in aree così diverse, dalla previsione del tempo alla ricerca della parola successiva in una frase.

In questo articolo, hai avuto la possibilità di conoscere i diversi componenti di un HMM, come possono essere applicati a diversi tipi di compiti e di individuare le somiglianze tra l’Algoritmo Forward e l’Algoritmo di Viterbi. Due algoritmi molto simili che utilizzano la programmazione dinamica per gestire il numero esponenziale di calcoli coinvolti.

Sia eseguendo i calcoli manualmente che inserendo i parametri nel codice TensorFlow, spero ti sia divertito ad immergerti nel mondo degli HMM.

Grazie per aver letto!

Riferimenti

1. D. Khiatani e U. Ghose, “Weather forecasting using Hidden Markov Model,” 2017 International Conference on Computing and Communication Technologies for Smart Nation (IC3TSN), Gurgaon, India, 2017, pp. 220–225, doi: 10.1109/IC3TSN.2017.8284480.
2. Noguchi H, Kato R, Hanai T, Matsubara Y, Honda H, Brusic V, Kobayashi T. Hidden Markov model-based prediction of antigenic peptides that interact with MHC class II molecules. J Biosci Bioeng. 2002;94(3):264–70. doi: 10.1263/jbb.94.264. PMID: 16233301.
3. Yoon BJ. Hidden Markov Models and their Applications in Biological Sequence Analysis. Curr Genomics. 2009 Sep;10(6):402–15. doi: 10.2174/138920209789177575. PMID: 20190955; PMCID: PMC2766791.
4. Eddy, S. What is a hidden Markov model?. Nat Biotechnol 22, 1315–1316 (2004). https://doi.org/10.1038/nbt1004-1315
5. Jurafsky, Dan and Martin, James H.. Speech and language processing : an introduction to natural language processing, computational linguistics, and speech recognition. Upper Saddle River, N.J.: Pearson Prentice Hall, 2009.
6. Baum, Leonard E., and Ted Petrie. “Statistical Inference for Probabilistic Functions of Finite State Markov Chains.” The Annals of Mathematical Statistics 37, no. 6 (1966): 1554–63.

In pochi secondi ottieni un output che corrisponde ai risultati dei calcoli effettuati a mano, molto più veloce e con molto meno margine di errore.

Conclusioni

Ciò che affascina dei Modelli di Markov Nascosti è quanto questo strumento statistico creato nella metà degli anni ’60 [6] sia potente e applicabile a problemi del mondo reale in aree così diverse, dalla previsione del tempo alla ricerca della parola successiva in una frase.

In questo articolo, hai avuto la possibilità di conoscere i diversi componenti di un HMM, come possono essere applicati a diversi tipi di compiti e di individuare le somiglianze tra l’Algoritmo Forward e l’Algoritmo di Viterbi. Due algoritmi molto simili che utilizzano la programmazione dinamica per gestire il numero esponenziale di calcoli coinvolti.

Sia eseguendo i calcoli manualmente che inserendo i parametri nel codice TensorFlow, spero ti sia divertito ad immergerti nel mondo degli HMM.

Grazie per aver letto!

Riferimenti

1. D. Khiatani e U. Ghose, “Weather forecasting using Hidden Markov Model,” 2017 International Conference on Computing and Communication Technologies for Smart Nation (IC3TSN), Gurgaon, India, 2017, pp. 220–225, doi: 10.1109/IC3TSN.2017.8284480.
2. Noguchi H, Kato R, Hanai T, Matsubara Y, Honda H, Brusic V, Kobayashi T. Hidden Markov model-based prediction of antigenic peptides that interact with MHC class II molecules. J Biosci Bioeng. 2002;94(3):264–70. doi: 10.1263/jbb.94.264. PMID: 16233301.
3. Yoon BJ. Hidden Markov Models and their Applications in Biological Sequence Analysis. Curr Genomics. 2009 Sep;10(6):402–15. doi: 10.2174/138920209789177575. PMID: 20190955; PMCID: PMC2766791.
4. Eddy, S. What is a hidden Markov model?. Nat Biotechnol 22, 1315–1316 (2004). https://doi.org/10.1038/nbt1004-1315
5. Jurafsky, Dan and Martin, James H.. Speech and language processing : an introduction to natural language processing, computational linguistics, and speech recognition. Upper Saddle River, N.J.: Pearson Prentice Hall, 2009.
6. Baum, Leonard E., and Ted Petrie. “Statistical Inference for Probabilistic Functions of Finite State Markov Chains.” The Annals of Mathematical Statistics 37, no. 6 (1966): 1554–63.