Skip to main content

Search-Space Reduction for Fast, Optimal HMM Decoding with Application to Speaker Verification

New Image

Currently, the most popular algorithm for hidden Markov model (HMM) decoding is the Viterbi algorithm with beam search to reduce search space; however, it is difficult to determine a suitable beam width beforehand. A smaller beam width may miss the optimal path while a large one may slow down the decoding speed. To address this problem, we propose a novel approach on search space reduction without using any beam width or threshold. Following the definition of HMM, we first detect the possible change points between HMM states sequentially, than use the change points to locate a subspace for searching. Using a combined forward and backward scheme, we can detect two boundaries consisting of change points to enclose the subspace. The Viterbi algorithm or any other search algorithm can then be applied in the subspace. The experiments on a speaker verification task show that the proposed algorithm is about 4 times faster than a full search algorithm while the accuracy is almost the same. On the same decoding speed, the proposed algorithm provides a better accuracy than a beam-search approach. For an HMM with S states, the upper bound of speedup of the proposed algorithm is approximately S/3, compared to the full search approach.