Iterative Viterbi decoding: Difference between revisions

Content deleted Content added
No edit summary
Gzornenplatz (talk | contribs)
names
Line 1:
Iterative Viterbi Decoding is an algorithm that spots the subsequence S of an observation O={o<sub>1</sub>,...,o<sub>n</sub>} having the highest average probability (i.e., probability scaled by the length of S) of being generated by a given Hidden Markov Model M with m states. The algorithm uses a modified [[Viterbi algorithm]] as an internal step.
 
The scaled probability measure was first proposed by [[John S. Bridle]]. An early algorithm to solve this problem, [[sliding window]], was proposed by [[Jay G. Wilpon]] et. al., 1989, with constant cost T=mn<sup>2</sup>/2.
 
A faster algorithm was developed by [[Marius C. Silaghi]] in 1998 (published 1999). It consists of an iteration of calls to the [[Viterbi algorithm]], reestimating a filler score until convergence.
 
== The Algorithmalgorithm ==
 
A basic (non-optimized) version looks like:
Line 48:
== References ==
 
* Silaghi,M.; Marius; "Optimizing normalized costs with Iterating Dynamic Programming", submitted to EJOR, 2000.
* Silaghi,M. Marius, and Bourlard,H. Hervé; "A new Keyword Spotting approach based on iterative dynamic programming", ICASSP 2000.
* Silaghi,M. Marius, and Berinde,V. Vasile; "A new optimization algorithm", in Journal of North University at Baia Mare, Romania, 1999.
* RosenknopRozenknop, Antoine,A and Silaghi,M. Marius; "Algorithme de decodage de treillis selon le critere de cout moyen pour la reconnaissance de la parole", TALN 2001.