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 $b$ ed $a$). L'algoritmo segue il modello di Expectation-Maximization, nel quale inizializziamo una stima grezza delle matrici $a$ e $b$.

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

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