# Fast Sequence Segmentation using Log-Linear Models

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2019.

## Built on by (most cited first, 2 of 2)

- [Fast likelihood-based change point detection](https://mlsanity.com/paper/2301.08892/) (2023)
- [Information Bottleneck Meets Quantization: Finite Rate Analysis and Optimal Designs](https://mlsanity.com/paper/2606.10869/) (2026)

## Abstract (arXiv)

Sequence segmentation is a well-studied problem, where given a sequence of elements, an integer K, and some measure of homogeneity, the task is to split the sequence into K contiguous segments that are maximally homogeneous. A classic approach to find the optimal solution is by using a dynamic program. Unfortunately, the execution time of this program is quadratic with respect to the length of the input sequence. This makes the algorithm slow for a sequence of non-trivial length. In this paper we study segmentations whose measure of goodness is based on log-linear models, a rich family that contains many of the standard distributions. We present a theoretical result allowing us to prune many suboptimal segmentations. Using this result, we modify the standard dynamic program for one-dimensional log-linear models, and by doing so reduce the computational time. We demonstrate empirically, that this approach can significantly reduce the computational burden of finding the optimal segmentation.