Fast sequence segmentation using log-linear models

DOI10.1007/S10618-012-0301-YzbMATH Open1281.68195arXiv1902.03285OpenAlexW2043149556MaRDI QIDQ2435697FDOQ2435697

Authors: Nikolaj Tatti 

Publication date: 19 February 2014

Published in: Data Mining and Knowledge Discovery (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1902.03285

Recommendations

• A conditional random field-based model for joint sequence segmentation and classification
• A model selection approach for multiple sequence segmentation and dimensionality reduction
• Sequence classification via large margin hidden Markov models
• Learning mixture models with support vector machines for sequence classification and segmentation
• Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data
• Time-series segmentation: A model and a method
• scientific article

zbMATH Keywords

change-point detectionpruningsegmentationdynamic program

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Dynamic programming (90C39)

Cites Work

• Estimating the dimension of a model
• On the approximation of curves by line segments using dynamic programming
• Inductive Databases and Constraint-Based Data Mining

Cited In (3)

• Strongly polynomial efficient approximation scheme for segmentation
• A dynamic programming algorithm for linear text segmentation
• Text segmentation by product partition models and dynamic programming

This page was built for publication: Fast sequence segmentation using log-linear models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2435697)