Trovare la cima - k percorsi viterbi in HMM

Question

Ho bisogno di scrivere un algoritmo che trovi i percorsi viterbi top-k in un HMM (usando l'algoritmo viterbi regolare per trovare il percorso migliore).

Penso che probabilmente devo salvare una lista V_t, N di dimensione k per ogni stato N che contiene i percorsi K superiori che terminano nello stato N, ma non sono sicuro di come tenere traccia di quella lista. qualche idea? Grazie

Answer 1

Possiamo risolvere questo con un po 'di attenzione. E 'più semplice per vedere, cercando in struttura a traliccio di hmm:

In questo esempio gli stati nascosti sono 00, 01, 10, 11, indicare l'insieme di questi quattro come S. Le osservazioni sono non mostrato, ma si assume che siano 0,1.

Supponiamo di avere la giusta matrice di transizione:

transition[4][4] 

probabilità di emissione:

emissions[4][2] 

e le probabilità iniziali:

p[2] 

Così ogni colonna rappresenta gli stati nascosti, e l'obiettivo di Viterbi è calcolare la sequenza di stati nascosti più probabile data t lui osservazioni. Ora lasciamo alpha (i, t) = la più grande probabilità che la sequenza dello stato nascosto sia nello stato i (i è uno di 00, 01, 10, 11), al tempo t dove l'osservazione al tempo t è o_t (o_t è uno di 0, 1). Lascia che la prima osservazione sia denotata o_1. Essa può essere calcolata in modo efficiente come:

alpha(i, 1) = p[i] * emissions[i][o_1] 
alpha(i, t) = emissions[i][o_t] * max_{k in states} (alpha(k, t-1) * transition[k][i]) 

Al fine di trovare il miglior percorso, continuiamo puntatori ritroso nel alfa (i, t) passo, allo stato che massimizzata la funzione max in precedenza. Infine, esaminiamo tutti gli alfa (i, T) e i in stati, e troviamo quale è il più grande, quindi seguitelo per ottenere la sequenza di stati più probabile.

Ora dobbiamo estendere questo per memorizzare i migliori percorsi k. Attualmente ad ogni alpha (i, t) memorizziamo solo un genitore. Tuttavia supponiamo di aver archiviato i primi k predecessori. Quindi ogni alfa (i, t) corrisponde non solo a un valore molto probabile e al nodo da cui è transitato, ma a un elenco dei principali nodi k da cui avrebbe potuto effettuare la transizione e i loro valori nell'ordine ordinato.

Questo è facile da fare, in quanto invece di fare il massimo, e prendere solo un nodo precedente, prendiamo il primo k dei nodi precedenti e li memorizziamo. Ora per il caso base non esiste un nodo precedente, quindi alfa (i, 1), è ancora solo un singolo valore. Quando arriviamo a una colonna arbitraria (diciamo t) e vogliamo trovare i cammini top-k che terminano su un nodo (i) in quella colonna, dobbiamo trovare i primi k predecessori da cui provengono ei percorsi migliori da cui prelevare.

Questo è come se avessimo il seguente problema, una matrice, m, di dimensione 4 per k, in cui una riga rappresenta uno stato precedente e m [stato] rappresenta le probabilità in alto k per i percorsi che terminano lì Così ogni fila di m è ordinato dal più grande al più piccolo, il problema diventa ora trovare:

Best_K_Values(t, i) = Top K over all i,preceding_state,k (emissions[i][o_t] * m[preceding_state][k] * transition[preceding_state][i]) 

Ora, questo sembra scoraggiante, ma prendere un po 'di tempo per capirlo, siamo in grado di risolvere il k superiore dal problema matrice ordinata utilizzando un mucchio in O (4 log k) o O (numStates log k) in generale.

Vedere questa leggera variazione Kth smallest element in sorted matrix, basta notare che nel nostro caso le colonne non sono ordinate, ma l'idea esiste ancora.

Se si sta ancora leggendo, si noti che la complessità complessiva di questo metodo è O ((numStates log k) * numStates * t) = O (numStates^2 * t * log k) (Credo che sia la complessità corretta).

Questo può essere difficile da seguire, ma per favore fatemi sapere se avete domande, o ho fatto qualcosa in modo errato.

Answer 2

C'è davvero molta letteratura su questo. Ci sono voluti degli scavi, ma ho trovato questo.

Elenco Viterbi decodifica algoritmi con le applicazioni

http://www.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/42comm02-seshadri.pdf