Efficient Decoding of High-order Hidden Markov Models

[摘要] Most speech recognition and language identification engines are based on hidden Markovmodels (HMMs). Higher-order HMMs are known to be more powerful than first-orderHMMs, but have not been widely used because of their complexity and computationaldemands. The main objective of this dissertation was to develop a more time-efficientmethod of decoding high-order HMMs than the standard Viterbi decoding algorithmcurrently in use.We proposed, implemented and evaluated two decoders based on the Forward-BackwardSearch (FBS) paradigm, which incorporate information obtained from low-order HMMs.The first decoder is based on time-synchronous Viterbi-beam decoding where we wishto base our state pruning on the complete observation sequence. The second decoder isbased on time-asynchronous A* search. The choice of heuristic is critical to the A* searchalgorithms and a novel, task-independent heuristic function is presented. The experimentalresults show that both these proposed decoders result in more time-efficient decodingof the fully-connected, high-order HMMs that were investigated.Three significant facts have been uncovered. The first is that conventional forwardViterbi-beam decoding of high-order HMMs is not as computationally expensive as iscommonly thought.The second (and somewhat surprising) fact is that backward decoding of conventional,high-order left-context HMMs is significantly more expensive than the conventional forwarddecoding. By developing the right-context HMM, we showed that the backwarddecoding of a mathematically equivalent right-context HMM is as expensive as the forwarddecoding of the left-context HMM.The third fact is that the use of information obtained from low-order HMMs significantlyreduces the computational expense of decoding high-order HMMs. The comparisonof the two new decoders indicate that the FBS-Viterbi-beam decoder is more time-efficientthan the A* decoder. The FBS-Viterbi-beam decoder is not only simpler to implement,it also requires less memory than the A* decoder.We suspect that the broader research community regards the Viterbi-beam algorithmas the most efficient method of decoding HMMs. We hope that the research presentedin this dissertation will result in renewed investigation into decoding algorithms that areapplicable to high-order HMMs.

[发布机构] Stellenbosch University