Home

Federica EU

1/17

Francesco Cutugno » 12.Riconoscimento del parlato - parte seconda

Riconoscimento del parlato

Elementi Fondamentali di un HMM

O=[O₁..O_M] vettori delle osservazioni
S= [s₁ ...s_N] insieme degli stati
A =[a_ij] matrice di probabilità di transizione fra gli stati
B=[b_i(k)] matrice di probabilità di emissione dei vettori Oi
P = [P_i] vettore di probabilità iniziali
Vale inoltre:
$\sum_{j=1}^n a_{ij}=1~~~~~~ \sum_{i=1}^n \pi_i=1~~~~~~ \sum_{k=1}^M b_i(k)=1$

Vincolo al primo ordine dei sistemi Markoviani

$p(s_t) = p(s_t) = p(s_t|s_{t-1},s_{t-2}...s_1)= p(s_t|s_{t-1})$

Problemi Fondamentali di un HMM

-Problema di Valutazione (algoritmo Forward):
Dati H e una sequenza O come stimare la probabilità P(O|H)

-Problema di Decodifica (algoritmo di Viterbi):
Dati H e una sequenza O ottenere la sequenza di stati s₁ …s_T di H che ha la probabilità più alta di produrre la sequenza O

-Problema di Addestramento (algoritmo di Baum-Welch):
Dato un modello H e una sequenza O, come determinare i parametri di H in modo da massimizzare la probabilità che H generi O?

Il trellis

Un grafo multistadio che descrive gli algoritmi sulle HMM

Valutazione-Algoritmo Forward

Definiamo la probabilità forward come:

$\alpha_t(i)=p(O_1 ^t, s_t=i|H)$

$\alpha_t(i)$ è la probabilità che H si trovi nello stato I avendo generato la sequenza

$O_1^t = O_1O_2...O_t$

La probabilità forward, per ogni t si calcola in questo modo:
$\left[ \sum_{i=1}^N \alpha_{t-1}(i)a_{ij} \right] b_j(O_t)$

Valutazione-Algoritmo Forward (segue)

Inizializzazione: Valuta le α1 per ogni stato:

$\alpha_1(i)=\pi_ib_i(O_1) \hspace{20} con \hspace{4} 1\le i \le N$

Ricorsione: valuta le αt(i) per ogni stato i nei vari istanti di tempo:
$\alpha_t(i)=\left[ \sum_{t=1}^N\alpha{t-1}(i)a_{ij}\right]b_j(O_t) \hspace{3} con \hspace{3} 2\le t\le T, \hspace{3} 1\le j\le N$

Terminazione: calcola la probabilità complessiva di forward sommando tutte le probabilità parziali sull’ultimo stato.
$P(O|H)=\sum_1^N \alpha_t(i)$

Decodifica: Algoritmo di Viterbi

La decodifica procede prendendo spunto dall’algoritmo forward: al posto di TUTTE le α, si prendono in considerazione solo quelle massime.

Algoritmo di Viterbi (segue)

La variabile αt(i) del forward viene sostituita da V_t(i), probabilità che all’istante t l’HMM sia transitato per i migliori t-1 stati precedenti e si trovi in i avendo generato le osservazioni O1…Ot.

$V_t(j)= \displaystyle{\max_{1\le j \le N}\left (V_{t-1}(i)a_{ij}\right ) b_j(O_t)}$

Ad ogni passo computazionale viene memorizzata la coppia Vt(j) e j

Algoritmo di Viterbi (segue)

Inizializzazione : valuta le V₁(i) per ogni stato (uguali alle a₁(i))
Ricorsione:
a) $V_t(j)= \displaystyle{\max_{1\le i\le N}\left [V_{t-1}(i)a_{ij}\right ] b_j(O_t) \hspace{3} con \hspace{3} 2 \le t\le T , \hspace{3} 1 \le j \le N}$

b) Memorizza lo stato che massimizza V_t(j)

$B_t(j)= arg\displaystyle{\max_{1\le i\le N}\left [V_{t-1}(i)a_{ij}\right ]}$

Terminazione:

$stato\_finale\_migliore=arg \displaystyle{\max_{1\le i\le N}\left [V_T(i)\right ]}$

Backtracking:
recupera a ritroso i massimi registrati lungo il cammino

$s_t^*=B_{t+1}(s_{t+1}^*) \hspace{10} con \hspace{3}t= T-1, T-2,...1$

$S^* = (s_1^*,s_2^*,..., s_T^*)$

Apprendimento-Algoritmo di Baum-Welch

Dato un modello di Markov H e una sequenza di osservazioni O, vogliamo determinare i migliori valori per le transizioni di stato A e le probabilità di osservazione B

$a_{ij}=\frac {numero \hspace{3 pt}previsto \hspace{3 pt}di \hspace{3 pt} transizioni \hspace{3 pt} dallo \hspace{3 pt} stato \hspace{3 pt} i \hspace{3 pt}a \hspace{3 pt}quello \hspace{3 pt} j } {numero \hspace{3 pt} previsto \hspace{3 pt}di \hspace{3 pt} transizioni \hspace{3 pt}totali \hspace{3} dallo \hspace{3 pt}stato \hspace{3 pt} i }$

$b_i(k)=\frac {numero \hspace{3 pt}previsto \hspace{3 pt}di \hspace{3 pt} volte \hspace{3 pt} in \hspace{3 pt} cui \hspace{3 pt} nello \hspace{3 pt}stato \hspace{3 pt}i \hspace{3 pt} si\hspace{3 pt} osserva \hspace{3 pt}o_k} {numero \hspace{3 pt}previsto \hspace{3 pt}di \hspace{3 pt} volte \hspace{3 pt} in \hspace{3 pt} cui \hspace{3 pt} si \hspace{3 pt}passa \hspace{3 pt}per \hspace{3 pt} lo\hspace{3 pt}stato \hspace{3 pt}i}$

Algoritmo di Baum-Welch (segue)

Introduciamo una nuova probabilità denominata p. di backward
$\hat\sigma_i^2=\frac{\sum_{t=1}^T\xi_t(i)(o_t-\mu_i)^2}{\sum_{t=1}^T\xi_t(i)}$

La probabilità di trovarsi all’istante t nello stato i e nello stato j all’istante t+1 è:
$\xi_t(i,j)= \frac {\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)} {\alpha_T(N)}$
Il calcolo di a_ij si ottiene valutando $\xi_t(i,j)$ per tutte le t

b_j(k) sono determinati dalle μ eδ delle multigaussiane, si ha che*:

$\hat\mu_i=\frac{\sum_{t=1}^T\xi_t(i)o_t}{\sum_{t=1}^T\xi_t(i)}$

*per semplifcare è riportato il calcolo per singola gaussiana monodimensionale

Algoritmo di Expectation – Maximization

Dato un modello nascosto di Markov H(πi, O, B, A, S):

Step 1: Inizializzazione-> Definire una configurazione iniziale per A e B in H

Step 2: expectation -> calcolare $\xi_t(i,j)$ $\gamma_t(j)$ per ogni t, i e j

Step 3: massimizzazione -> calcolare nuovi valori per A e B

Step 4: iterazione -> ripetere l’algoritmo iterativamente dal passo 2 x volte

Lo scopo dell’algoritmo è quello di massimizzare la probabilità P(O|H) che il modello H produca la sequenza O. Ciò può essere ottenuto per via iterativa, scrivendo P(O|H) in funzione di aij e bi.
Dalla massimizzazione di questa funzione verranno calcolati dei nuovi parametri aij e bi, a partire dai quali verrà rivalutata la funzione f e si procederà con un’ulteriore massimizzazione.