HMM

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Sequence Matching Episode Mining

Una catena di Markov è una tripla (Q, {p(p=S)}, A) dove:

1. Q = {1, 2, ..., k} è una catena finita di stati (eventi). Ogni stato è un simbolo ottenuto da un alfabeto .
2. p = rappresenta l'insieme delle probabilità iniziali.
3. A è l'insieme delle probabilità di transizione denotato con per ogni s, t in Q tale che
   

1. Probabilità di Transizione tra due stati qualsiasi:
   
2. Probabilità iniziali:
   
   tali che
   
3. Probabilità di emissione di un simbolo dato uno stato:
   
   ed è tale che:
   bi(o1) + bi(o2) + ... + bi(ok) = 1.

1. Evaluation:
   dato un modello M e una sequenza di osservazione X, trovare la probabilità che la sequenza X sia stata prodotta dal modello M, cioè P(X|M).
2. Decoding:
   dato un HMM M e una sequenza di osservazione X, trovare la sequenza PI di stati nascosti che massimizzi la P(X, P | M).
3. Learning:
   dato un HMM M con probabilità di emissione/transizione non note, e una sequenza X, trovare i parametri di M, cioè bi(o) e aij che massimizzino la P(X|M).

1. Soluzione al problema 1:
   Una soluzione rozza consiste nel calcolare tutti i possibili cammini, cioè fare una somma su ogni sequenza di stati delle probabilità di ottenere una determinata sequenza, cioè
   
   Per evitare la somma che coinvolge un numero di cammini esponenziale, introduciamo una variabile forward
   
   la cui definizione ricorsiva è la seguente:
   1. Caso Base:
      
   2. Passo Induttivo:
      
   La complessità dell'algoritmo è O(k2n), e l'algoritmo è il seguente:
   INPUT: M, X
OUTPUT: p
for i = 1 ...k do
;
endfor;
for t = 1 ... n-1 do
for j = 1 ... k do
sum = 0;
for i =1 ... k do
;
endfor;
;
endfor;
endfor;
p = 0;
for i = 1 ... k do
;
endfor;
2. Il problema del decoding si risolve in maniera analoga definendo la variabile:
   
   La definizione ricorsiva di V è:
   
   L'algoritmo di Viterbi ha complessità temporale O(k2n), complessità spaziale O(kn) e il suo pseudo-codice è il seguente:
   INPUT: M, X
OUTPUT: p
for i = 1 ...k do
;
endfor;
for t = 1 ... n-1 do
for j = 1 ... k do
max = 0;
for i =1 ... k do
if( Vt(i)*a(i,j) > max ) do
max = Vt(i) * a(i,j);
phit(j) = i;
endif;
endfor;
Vt+1(j) = max * bj(xt+1);
endfor;
endfor;
p = 0;
for i = 1 ... k do
if( Vt+1(i) > p ) do
p = Vt+1(i);
phit(n) = i;
endif;
endfor;
P = retrievePath(phi);
   
3. Prima di risolvere il terzo problema introduciamo la variabile che indica la probabilità backward definita come:
   
   cioè la sequenza di osservazioni parziali dallo stato t+1 allo stato T. La derivazione della probabilità backward è la seguente:
   1. Caso Base:
      
      
   2. Passo Induttivo:
      
      
   Il passo d'inizializzazione arbitrariamente pone a 1 per ogni i. Il passo 2) mostra che per essere nello stato Sj al tempo t e per rappresentare la sequenza di osservazione dal tempo t+1 in avanti, si devono considerare tutti i possibili stati al tempo t+1 che rappresentano la transizione dallo stato Si allo stato Sj (il termine aij), così come l'osservazione Ot+1 nello stato j (il termine bj(Ot+1) ), e quindi rappresentare la rimanente sequenza di osservazione parziale dallo stato j ( il termine bt+1(j) ).
   L'algoritmo per calcolare la variabile backward è il seguente:
   INPUT: M, X
OUTPUT: p
for i = 1 ...k do
;
endfor;
for t = n-1 ... 1 do
for i = 1 ... k do
sum = 0;
for j =1 ... k do
;
endfor;
;
endfor;
endfor;
p = 0;
for i = 1 ... k do
;
endfor;
   L'algoritmo per il calcolo di backward ha complessità O(k2n), dove k è il numero di stati e n è la lunghezza della stringa.Trovare una soluzione al terzo problema è opera quanto mai complessa, perchè si tratta di trovare i parametri del modello tali che la probabilità che una particolare sequenza X sia stata generata da esso.
   Quindi si tratta di addestrare un HMM a riconoscere un particolare pattern. Non esiste però un modo ottimale per stimare i parametri
   .
   Prima di introdurre l'algoritmo di Baum-Welch, che è un metodo E-M, diamo alcune definizioni di variabili che questo metodo usa.
   Sia
   
   la variabile che indica la probabilità di essere nello stato i al tempo t e nello stato j al tempo t+1, data la sequenza di osservazione X, cioè:
   
   Definiamo, ora, la variabile gt(i) come la probabilità di essere nello stato i al tempo t, data la sequenza X, cioè:
   
   Quindi le nuove matrici di transizione ed emissione saranno date da:
   
   I passi della procedura di Baum-Welch sono:
   1. Inizializza le matrici di transizione ed emissione in maniera random.
   2. Calcola , forward.
   3. Calcola , backward.
   4. Calcola A, E usando .
   5. Calcola i nuovi parametri
   6. Calcola il nuovo log-likelihood , che è il logaritmo della probabilità. Infatti
      
      che è computazionalmente più agevole da calcolare rispetto ai prodotti.
   7. Itera fino a quando il log(P) non cambia molto rispetto al passo precedente.
   Questa procedura porta a trovare massimi locali, che non sempre sono il valore corretto, perchè la superfice di ottimizzazione potrebbe essere molto complessa. La complessità dell'algoritmo di Baum-Welch è O(k2n)*#iterazioni.

Home Sequence Matching Episode Mining