Algoritmo di Baum-Welch

L'algoritmo di Baum-Welch viene usato in elettrotecnica, informatica, informatica statistica e bioinformatica per trovare i parametri incogniti di un modello di Markov nascosto (HMM). Si avvale di un algoritmo forward-backward che prende il nome di Leonard Esau Baum e Lloyd Richard Welch.

Descrizione

Dato un HMM (Hidden Model Markov) e una sequenza di simboli osservabili o un insieme di tali sequenze, l'algoritmo di Baum-Welch permette di trovare l'insieme più probabile per il quale si possano dichiarare le probabilità di uscita e di transizione (ovvero le matrici ${\displaystyle b}$ ed ${\displaystyle a}$). L'algoritmo segue il modello di Expectation-Maximization, nel quale inizializziamo una stima grezza delle matrici ${\displaystyle a}$ e ${\displaystyle b}$.

Nella prima fase generiamo la matrice ${\displaystyle \alpha }$ e ${\displaystyle \beta }$, e la matrice ${\displaystyle \gamma }$ così definita ${\displaystyle \gamma (i,j,t)=\alpha (i,t-1)a_{ij}b_{jk}\beta (j,t)}$.

Nella seconda fase calcoliamo le matrici ${\displaystyle a'}$ e ${\displaystyle b'}$ nel seguente modo: ${\displaystyle a'}$ è data dal rapporto del numero di volte in cui passiamo dallo stato ${\displaystyle i}$-esimo allo stato ${\displaystyle j}$-esimo e il numero di volte che passiamo dallo stato ${\displaystyle i}$-esimo a qualunque altro stato; ${\displaystyle b'}$ è data dal rapporto del numero di volte in cui dallo stato i-esimo emetto il simbolo ${\displaystyle k}$ e il numero di volte in cui da uno stato ${\displaystyle i}$-esimo passa ad un simbolo qualunque. Tali matrici verranno sostituite ad ${\displaystyle a}$ e ${\displaystyle b}$, reiterando finché i miglioramenti saranno significativi e le matrici saranno stabilizzate.