Viterbi algorithm: Difference between revisions

Revision as of 14:00, 3 October 2022

Revision as of 14:03, 3 October 2022

Line 62:

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

'''function''' ''viterbi''<math>(O, S, \Pi, Tm, Em): best\_path </math> Tm: transition matrix Em: emission matrix

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

<math>pointers \leftarrow matrix(length(S), length(O))</math> To hold backpointer to best prior state

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

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

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

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

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

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

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

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

Line 77:

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

<math>k \leftarrow pointers[k, o]</math> Use backpointer to find best previous state

'''return''' ''best_path''<math>best\_path</math>

;Explanation: