Fast sequence segmentation using log-linear models

DOI10.1007/S10618-012-0301-YMaRDI QIDQ2435697zbMATH OpenOpenAlexFDO

Authors Nikolaj Tatti

Publication date 19 February 2014

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

Full work available at URL https://arxiv.org/abs/1902.03285, https://lirias.kuleuven.be/handle/123456789/374399

zbMATH Keywords

change-point detectionpruningsegmentationdynamic program

Mathematics Subject Classification ID

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

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.

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 DE number 6378100

Cites work

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

Cited in

(3)

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

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)