# Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models

arXiv: https://arxiv.org/abs/2305.18578 · HTML: https://mlsanity.com/paper/2305.18578/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 62 references that are in the map.
- First posted on arXiv 29 May 2023.

## Builds on (most cited first, 10 of 10)

- [Multiple Change-point Detection: a Selective Overview](https://mlsanity.com/paper/1512.04093/) (2015)
- [Localizing Changes in High-Dimensional Regression Models](https://mlsanity.com/paper/2010.10410/) (2020)
- [Inferring serial correlation with dynamic backgrounds](https://mlsanity.com/paper/2101.10962/) (2021)
- [Temporal Parallelization of Inference in Hidden Markov Models](https://mlsanity.com/paper/2102.05743/) (2021)
- [Optimistic search: Change point estimation for large-scale data via adaptive logarithmic queries](https://mlsanity.com/paper/2010.10194/) (2020)
- [Statistical Inference in Hidden Markov Models using k-segment Constraints](https://mlsanity.com/paper/1311.1189/) (2013)
- [Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms](https://mlsanity.com/paper/1607.04229/) (2016)
- [Localizing Changes in High-Dimensional Vector Autoregressive Processes](https://mlsanity.com/paper/1909.06359/) (2019)
- [Decoding Hidden Markov Models Faster Than Viterbi Via Online Matrix-Vector (max, +)-Multiplication](https://mlsanity.com/paper/1512.00077/) (2015)
- [Heterogeneous Idealization of Ion Channel Recordings -- Open Channel Noise](https://mlsanity.com/paper/2008.02658/) (2020)

## Abstract (arXiv)

Hidden Markov models (HMMs) are characterized by an unobservable Markov chain and an observable process -- a noisy version of the hidden chain. Decoding the original signal from the noisy observations is one of the main goals in nearly all HMM based data analyses. Existing decoding algorithms such as Viterbi and the pointwise maximum a posteriori (PMAP) 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 hidden chain. We present Quick Adaptive Ternary Segmentation (QATS), a divide-and-conquer procedure with computational complexity polylogarithmic 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. It 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, and is meanwhile admissible. The maximization is performed only approximately using an adaptive search procedure. Our simulations demonstrate the speedups offered by QATS in comparison to Viterbi and PMAP, along with a precision analysis. An implementation of QATS is in the R-package QATS on GitHub.