Viterbi algorithm: Difference between revisions

Revision as of 20:26, 12 March 2022

Revision as of 04:24, 3 October 2022

Line 62:

Restated in a succinct near-[[Python (programming language)|Python]]:

#'''function''' probability''viterbi''<math>(O, ==S, p.\Pi, Tm, Em): thebest\_path </math> Tm: transition matrix. Em: the emission matrix.

<math>trellis \leftarrow matrix(length(S), length(O))</math> To hold probability of each state given each observation

'''function''' viterbi(O, S, Π, Tm, Em): best_path

trellis<math>pointers ←\leftarrow matrix(length(S), length(O))</math> # To hold p.backpointer ofto eachbest prior state given each observation.

'''for''' s '''in''' <math>range(length(S))</math>: Determine each hidden state's probability at time 0…

pointers ← matrix(length(S), length(O)) # To hold backpointer to best prior state

<math>trellis[s, 0] ←\leftarrow Π\Pi[s] * Em[s, O[0]]</math>

# Determine each hidden state's p. at time 0...

'''for''' so '''in''' <math>range(1, length(SO))</math>: …and after, tracking each state's most likely prior state, k

'''for''' s '''in''' <math>range(length(S))</math>:

trellis[s, 0] ← Π[s] * Em[s, O[0]]

''<math>k'' ←\leftarrow argmax\arg\max(''k''\ \mathsf{in}\ trellis[''k'', o-1] * Tm[''k'', s] * Em[s, o])</math>

# ...and afterwards, tracking each state's most likely prior state, k.

<math>trellis[s, o] \leftarrow trellis[k, o-1] * Tm[k, s] * Em[s, o]</math>

'''for''' o in range(1, length(O)):

<math>pointers[s, o] ←\leftarrow ''k''</math>

'''for''' s in range(length(S)):

<math>best\_path \leftarrow list()</math>

''k'' ← argmax(''k'' in trellis[''k'', o-1] * Tm[''k'', s] * Em[s, o])

<math>k \leftarrow \arg\max(k\ \mathsf{in}\ trellis[s, o] ← trellis[''k'', olength(O)-1] *)</math> Find Tm[''k'', s]of *best Em[s,final o]state

'''for''' o '''in''' <math>range(length(O)-1, -1, -1)</math>: # Backtrack from last observation.

pointers[s, o] ← ''k''

best_path<math>best\_path.insert(0, S[''k''])</math> # Insert previous state on most likely path

best_path ← list()

''k'' ← argmax( '' <math>k'' in\leftarrow trellispointers[''k'', length(O)-1o]</math> ) # Find k of Use backpointer to find best finalprevious state

'''return''' ''best_path''

'''for''' o in range(length(O)-1, -1, -1): # Backtrack from last observation.

best_path.insert(0, S[''k'']) # Insert previous state on most likely path

''k'' ← pointers[''k'', o] # Use backpointer to find best previous state

'''return''' best_path

;Explanation: