Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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