Search-space reduction for fast, optimal HMM decoding in speaker verification

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 a difficult problem in determining a beam width beforehand. To address this problem, we propose a novel approach on search space reduction. Following the definition of HMM, we first detect the possible change points between HMM states sequentially, then 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 algorithms 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 comparing to the full search approach is approximately S/3