Differentiable Segmentation of Sequences

Abstract

Segmented models are widely used to describe non-stationary sequential data with discrete change points. Their estimation usually requires solving a mixed discrete-continuous optimization problem, where the segmentation is the discrete part and all other model parameters are continuous. A number of estimation algorithms have been developed that are highly specialized for their specific model assumptions. The dependence on non-standard algorithms makes it hard to integrate segmented models in state-of-the-art deep learning architectures that critically depend on gradient-based optimization techniques. In this work, we formulate a relaxed variant of segmented models that enables joint estimation of all model parameters, including the segmentation, with gradient descent. We build on recent advances in learning continuous warping functions and propose a novel family of warping functions based on the two-sided power (TSP) distribution. TSP-based warping functions are differentiable, have simple closed-form expressions, and can represent segmentation functions exactly. Our formulation includes the important class of segmented generalized linear models as a special case, which makes it highly versatile. We use our approach to model the spread of COVID-19 with Poisson regression, apply it on a change point detection task, and learn classification models with concept drift. The experiments show that our approach effectively learns all these tasks with standard algorithms for gradient descent.

arXiv commentsource codes available at https://github.com/diozaka/diffseg

References in corpus (13)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Neural Discrete Representation Learning
• Optimal detection of changepoints with a linear computational cost
• Selective review of offline change point detection methods
• DARTS: Differentiable Architecture Search
• An Evaluation of Change Point Detection Algorithms
• Segmental Recurrent Neural Networks
• Large-Margin Metric Learning for Partitioning Problems
• Multiple Change Point Analysis: Fast Implementation And Strong Consistency
• Fast Algorithms for Segmented Regression
• The Segmented iHMM: A Simple, Efficient Hierarchical Infinite HMM
• Segmental Audio Word2Vec: Representing Utterances as Sequences of Vectors with Applications in Spoken Term Detection
• Temporal Transformer Networks: Joint Learning of Invariant and Discriminative Time Warping