Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For
  Hidden Markov Models
Alexandre Mösching Housen Li Axel Munk
Hidden Markov models (HMMs) are characterized by an unobservable (hidden)
Markov chain and an observable process, which is a noisy version of the hidden
chain. Decoding the original signal (i.e., hidden chain) from the noisy
observations is one of the main goals in nearly all HMM based data analyses.
Existing decoding algorithms such as the Viterbi algorithm have computational
complexity at best linear in the length of the observed sequence, and
sub-quadratic in the size of the state space of the Markov chain. We present
Quick Adaptive Ternary Segmentation (QATS), a divide-and-conquer procedure
which decodes the hidden sequence in polylogarithmic computational complexity
in the length of the sequence, and cubic in the size of the state space, hence
particularly suited for large scale HMMs with relatively few states. The
procedure also suggests an effective way of data storage as specific cumulative
sums. In essence, the estimated sequence of states sequentially maximizes local
likelihood scores among all local paths with at most three segments. The
maximization is performed only approximately using an adaptive search
procedure. The resulting sequence is admissible in the sense that all
transitions occur with positive probability. To complement formal results
justifying our approach, we present Monte-Carlo simulations which demonstrate
the speedups provided by QATS in comparison to Viterbi, along with a precision
analysis of the returned sequences. An implementation of QATS in C++ is
provided in the R-package QATS and is available from GitHub.