Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Francesco Cutugno » 12.Riconoscimento del parlato - parte seconda


Riconoscimento del parlato


Riconoscimento del parlato


Riconoscimento del parlato


Riconoscimento del parlato


Elementi Fondamentali di un HMM

O=[O1..OM] vettori delle osservazioni
S= [s1 ...sN] insieme degli stati
A =[aij] matrice di probabilità di transizione fra gli stati
B=[bi(k)] matrice di probabilità di emissione dei vettori Oi
P = [Pi] 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 s1 …sT 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

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 Vt(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 V1(i) per ogni stato (uguali alle a1(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 Vt(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 aij si ottiene valutando \xi_t(i,j) per tutte le t

bj(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.

Fase di apprendimento in partica


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion