Change Point Detection by Cross-Entropy Maximization

Abstract

Many offline unsupervised change point detection algorithms rely on minimizing a penalized sum of segment-wise costs. We extend this framework by proposing to minimize a sum of discrepancies between segments. In particular, we propose to select the change points so as to maximize the cross-entropy between successive segments, balanced by a penalty for introducing new change points. We propose a dynamic programming algorithm to solve this problem and analyze its complexity. Experiments on two challenging datasets demonstrate the advantages of our method compared to three state-of-the-art approaches.

Preprint

References in corpus (7)

• Natural Scales in Geographical Patterns
• Optimal detection of changepoints with a linear computational cost
• Selective review of offline change point detection methods
• Nonparametric maximum likelihood approach to multiple change-point problems
• Dirichlet Process Hidden Markov Multiple Change-point Model
• ruptures: change point detection in Python
• A robust approach for estimating change-points in the mean of an AR(1) process