Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions

摘要

We present a method to speed up the dynamic program algorithms used for solving the HMM decoding and training problems for discrete time-independent HMMs. We discuss the application of our method to Viterbi's decoding and training algorithms, as well as to the forward-backward and Baum-Welch algorithms. Our approach is based on identifying repeated substrings in the observed input sequence. We describe three algorithms based alternatively on byte pair encoding (BPE), run length encoding (RLE) and Lempel-Ziv (LZ78) parsing. Compared to Viterbi's algorithm, we achieve a speedup of Ω(r) using BPE, a speedup of Ω(r/(log r)) using RLE, and a speedup of Ω((log n)/κ) using LZ78, where κ is the number of hidden states, n is the length of the observed sequence and r is its compression ratio (under each compression scheme). Our experimental results demonstrate that our new algorithms are indeed faster in practice. Furthermore, unlike Viterbi's algorithm, our algorithms are highly parallelizable.