Viterbi Lattice Decoding Algorithm

A Viterbi Lattice Decoding Algorithm is a dynamic programming-based beam-search optimal lattice-path algorithm that can locate a Viterbi lattice optimal path.

• Context:
  • Input: Viterbi Lattice.
  • It can range from being a 1-best Viterbi Algorithm to being a k-best Viterbi Algorithm.
  • It can be used for inferencing on a Discrete-Outcome Discrete-Time Stochastic Model (such as a Hidden Markov Model)
  • It can be applied by a Viterbi-based Decoding System (possibly within a CRF testing system).
  • …
• Counter-Example(s):
  • an A* Algorithm, or Dijkstra Algorithm.
  • a Mixed Integer Programming Algorithm.
• See: Hidden Markov Modeling Algorithm, Shortest-Path Search Algorithm.

---

---

References

2012

• http://en.wikipedia.org/wiki/Viterbi_algorithm
  • QUOTE: The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources and hidden Markov models.

    The terms "Viterbi path" and "Viterbi algorithm" are also applied to related dynamic programming algorithms that discover the single most likely explanation for an observation. 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 sometimes called the "Viterbi parse".

    The Viterbi algorithm was proposed by Andrew Viterbi in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links. The algorithm has found universal application in decoding the convolutional codes used in both CDMA and GSM digital cellular, dial-up modems, satellite, deep-space communications, and 802.11 wireless LANs. It is now also commonly used in speech recognition, keyword spotting, computational linguistics, and bioinformatics. For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.

2011

• (Sammut & Webb, 2011) ⇒ Claude Sammut, and Geoffrey I. Webb. (2011). “Viterbi Algorithm.” In: (Sammut & Webb, 2011) p.1025

1989

• (Rabiner, 1989) ⇒ Lawrence R. Rabiner. (1989). “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” In: Proceedings of the IEEE, 77(2).
• (Chow et al., 1989) ⇒ Yen-Lu Chow, and Richard Schwartz. (1989). “The N-Best Algorithm: An Efficient Procedure for Finding Top N Sentence Hypotheses.” In: Proceedings of the workshop on Speech and Natural Language. doi:10.3115/1075434.1075467

1967

• (Viterbi, 1967) ⇒ A. J. Viterbi. (1967). “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm". IEEE Transactions on Information Theory 13 (2): 260–269. DOI:10.1109/TIT.1967.1054010. (note: the Viterbi decoding algorithm is described in section IV.) Subscription required.

---