Title :
On efficient Viterbi decoding for hidden semi-Markov models
Author :
Datta, Ritendra ; Hu, Jianying ; Ray, Bonnie
Author_Institution :
Penn State Univ., University Park, PA
Abstract :
We present algorithms for improved Viterbi decoding for the case of hidden semi-Markov models. By carefully constructing directed acyclic graphs, we pose the decoding problem as that of finding the longest path between specific pairs of nodes. We consider fully connected models as well as restrictive topologies and state duration conditions, and show that performance improves by a significant factor in all cases. Detailed algorithms as well as theoretical results related to their run times are provided.
Keywords :
Viterbi decoding; computational complexity; directed graphs; hidden Markov models; optimisation; Viterbi decoding; computational complexity; directed acyclic graph; fully connected model; hidden semiMarkov model; optimisation; restrictive topology; state duration condition; Algorithm design and analysis; Decoding; Event detection; Hidden Markov models; Inference algorithms; Proteins; Speech analysis; Speech recognition; Topology; Viterbi algorithm;
Conference_Titel :
Pattern Recognition, 2008. ICPR 2008. 19th International Conference on
Conference_Location :
Tampa, FL
Print_ISBN :
978-1-4244-2174-9
Electronic_ISBN :
1051-4651
DOI :
10.1109/ICPR.2008.4761926
