Viterbi algorithm: Difference between revisions

Revision as of 16:38, 17 March 2016

Revision as of 09:09, 24 March 2016

Line 8:

"Viterbi (path, algorithm)" has become a standard term for the application of dynamic programming algorithms to maximization problems involving probabilities.<ref name="slp"/>

For example, in [[statistical parsing]] a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is commonly called the "Viterbi parse".<ref>{{Cite conference | doi = 10.3115/1220355.1220379| title = Efficient parsing of highly ambiguous context-free grammars with bit vectors| conference = Proc. 20th Int'l Conf. on Computational Linguistics (COLING)| pages = <!--162-->| year = 2004| last1 = Schmid | first1 = Helmut| url = http://www.aclweb.org/anthology/C/C04/C04-1024.pdf}}</ref><ref>{{Cite conference| doi = 10.3115/1073445.1073461| title = A* parsing: fast exact Viterbi parse selection| conference = Proc. 2003 Conf. of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (NAACL)| pages = 40–47| year = 2003| last1 = Klein | first1 = Dan| last2 = Manning | first2 = Christopher D.| url = http://ilpubs.stanford.edu:8090/532/1/2002-16.pdf}}</ref><ref>{{Cite journal | doi = 10.1093/nar/gkl200| title = AUGUSTUS: Ab initio prediction of alternative transcripts| journal = Nucleic Acids Research| volume = 34| pages = W435| year = 2006| last1 = Stanke | first1 = M.| last2 = Keller | first2 = O.| last3 = Gunduz | first3 = I.| last4 = Hayes | first4 = A.| last5 = Waack | first5 = S.| last6 = Morgenstern | first6 = B.}}</ref>

==Algorithm==

Suppose we are given a [[hidden Markov model]] (HMM) with state space <math>S</math>, initial probabilities <math>\pi_i</math> of being in state <math>i</math> and transition probabilities <math>a_{i,j}</math> of transitioning from state <math>i</math> to state <math>j</math>. Say we observe outputs <math>y_1,\dots, y_T</math>. The most likely state sequence <math>x_1,\dots,x_T</math> that produces the observations is given by the recurrence relations:<ref>Xing E, slide 11</ref>

:<math>

\begin{array}{rcl}

V_{1,k} &=& \mathrm{P}\big( y_1 \ | \ k \big) \cdot \pi_k \\

V_{t,k} &=& \max_{x \in S} \left( \mathrm{P}\big( y_t \ | \ k \big) \cdot a_{x,k} \cdot V_{t-1,x}\right)

\end{array}

</math>

Here <math>V_{t,k}</math> is the probability of the most probable state sequence <math>\mathrm{P}\big(x_1,\dots,x_T,y_1,\dots, y_T\big)</math> responsible for the first <math>t</math> observations that have <math>k</math> as its final state. The Viterbi path can be retrieved by saving back pointers that remember which state <math>x</math> was used in the second equation. Let <math>\mathrm{Ptr}(k,t)</math> be the function that returns the value of <math>x</math> used to compute <math>V_{t,k}</math> if <math>t > 1</math>, or <math>k</math> if <math>t=1</math>. Then:

:<math>

\begin{array}{rcl}

x_T &=& \arg\max_{x \in S} (V_{T,x}) \\

x_{t-1} &=& \mathrm{Ptr}(x_t,t)

\end{array}

</math>

Here we're using the standard definition of [[arg max]].<br>

The complexity of this algorithm is <math>O(T\times\left|{S}\right|^2)</math>.

==Example==