Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:311321, 2017.
Abstract
The classic algorithm of Viterbi computes the most likely path in a Hidden Markov Model (HMM) that results in a given sequence of observations. It runs in time $O(Tn^2)$ given a sequence of T observations from a HMM with n states. Despite significant interest in the problem and prolonged effort by different communities, no known algorithm achieves more than a polylogarithmic speedup. In this paper, we explain this difficulty by providing matching conditional lower bounds. Our lower bounds are based on assumptions that the best known algorithms for the AllPairs Shortest Paths problem (APSP) and for the MaxWeight kClique problem in edgeweighted graphs are essentially tight. Finally, using a recent algorithm by Green Larsen and Williams for online Boolean matrixvector multiplication, we get a $2^{\Omega(\sqrt{\log n})}$ speedup for the Viterbi algorithm when there are few distinct transition probabilities in the HMM.
Related Material


