Labeled Optimal Partitioning
From MaRDI portal
Publication:136548
DOI10.48550/ARXIV.2006.13967arXiv2006.13967OpenAlexW3037923944MaRDI QIDQ136548FDOQ136548
Authors: Toby Dylan Hocking, Anuraag Srivastava, Toby Hocking, Anuraag Srivastava 
Publication date: 24 June 2020
Published in: Computational Statistics (Search for Journal in Brave)
Abstract: In data sequences measured over space or time, an important problem is accurate detection of abrupt changes. In partially labeled data, it is important to correctly predict presence/absence of changes in positive/negative labeled regions, in both the train and test sets. One existing dynamic programming algorithm is designed for prediction in unlabeled test regions (and ignores the labels in the train set); another is for accurate fitting of train labels (but does not predict changepoints in unlabeled test regions). We resolve these issues by proposing a new optimal changepoint detection model that is guaranteed to fit the labels in the train data, and can also provide predictions of unlabeled changepoints in test data. We propose a new dynamic programming algorithm, Labeled Optimal Partitioning (LOPART), and we provide a formal proof that it solves the resulting non-convex optimization problem. We provide theoretical and empirical analysis of the time complexity of our algorithm, in terms of the number of labels and the size of the data sequence to segment. Finally, we provide empirical evidence that our algorithm is more accurate than the existing baselines, in terms of train and test label error.
Full work available at URL: https://arxiv.org/abs/2006.13967
Cites Work
- Constrained dynamic programming and supervised penalty learning algorithms for peak detection in genomic data
- On optimal multiple changepoint algorithms for large data
- Estimating the dimension of a model
- Title not available (Why is that?)
- A Cluster Analysis Method for Grouping Means in the Analysis of Variance
- Estimating the number of change-points via Schwarz' criterion
- Algorithms for the optimal identification of segment neighborhoods
- Optimal detection of changepoints with a linear computational cost
- Greedy Kernel Change-Point Detection
- A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data
- CONTINUOUS INSPECTION SCHEMES
- Title not available (Why is that?)
Cited In (1)
This page was built for publication: Labeled Optimal Partitioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q136548)
