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 [21], as well as to the forward-backward and Baum-Welch [4] 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) [19], run length encoding (RLE) and Lempel-Ziv (LZ78) parsing [12]. Compared to Viterbi’s algorithm, we achieve a speedup of

Ω

(

r

) using BPE, a speedup of

$\Omega(\frac{r}{\log r})$

using RLE, and a speedup of

$\Omega(\frac{\log n}{k})$

using LZ78, where

k

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.