Differentiable Segmentation of Sequences
Authors: Erik Scharwächter
Jonathan Lennartz
Emmanuel Müller
Venue: ICLR 2021 Poster (2021)
Keywords: segmented models
segmentation
change point detection
concept drift
warping functions
gradient descent

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.

Published as a conference paper at ICLR 2021
DIFFERENTIABLE SEGMENTATION OF SEQUENCES
Erik Scharwächter"
Jonathan Lennartz University of Bonn, Germany
TU Dortmund University, Germany
Emmanuel Müller
TU Dortmund University, Germany
ABSTRACT
Segmented models are widely used to descrihe 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-ther tfetthe-rt deep learning architectures that critically depend on gradient-based optimization techniques. In this work, we formulate relaxed variant of segmented models that enables joint estimation of all model parameters, including the segmentation, with gradient descent. We build recent ad vdvccc 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-fore 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 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 solves all these tasks with a standard algorithm for gradient descent.
INTRODUCTION
Non-stationarity is classical challenge in the analysis of sequential data. A common source of non-stationarity is the presence of change points, where the data-generating process switches its dynamics from one regime another regime. In some applications, the detection of change points is of primary interest, since they may indicate important events in the data (Page) 1954 Box & Tiao
1965 Basseville & Nikiforov 1986 [Mtteson & James 2014 Li al. 2015 Arlot et al. [2019]
Scharwächter & Müller 2020). Other applications require models for the dynamics within each segment, which may yield more insights into the phenomenon under study and enable predictions. A
plethora of segmented models for regression analysis (McGee & Carleton, 1970; Hawkins 1976
Lerman 1980; Bai & Perron 2003) Muggeo 2003 Acharya et al. (2016) and time series analysis (Hamilton) 1990: Davis et al. 2006 Aue & Horváth 2013) Ding et al. (016)) have been proposed in
the literature, where the segmentation materializes either the data dimensions or the index set.
We adhere to the latter approach and consider models of the following form. Let x = (#1..., IT) be a sequence of T observations, and let (2,,.., ..., 2r) be an additional sequence of covariates used to predict these observations. Observations and covariates may be scalars or vector-valued. We refer to the index = 1, ..., T as the time of observation. The data-generating process (DGP) of given is time-varying and follows segmented model with K << T segments on the time axis. Let Tk denote the beginning segment We assume that
Ft foor (21, 0x) if Th S Tkt1:
(1)
"corresponding author, e-mail: erik wrrkk.scharraechterre.cc www.::a:c..ddddodroeoeoo

---

Published as a conference paper at ICLR 2021
where the DGP in segment k is parametrized by 0g. This scenario is typically studied for change
point detection (Truong et al. 22220 van den Burg & Dalliamss(22000 and modeling of non- stattoatt
time series (Guralmik & Srivastava 1999: 1994 Kohlmorgen & Lemm 2001; Davis et al. [0066]
Robinson & Hartemink] 2008 Saeedi et al. 2016). but also captures classification models with
concept drift (Gama al. 2013). and segmented generalized linear models (Muggeo) (003))
We express the segmentation of the time axis by a segmentation function Ç {1...., T) - {I,... K.....)) K} that maps each time point to a segment identifier k. The segmentation function monotonically increasing with boundary constraints ((1) = 1 and ((T)) = K. We denote all segment-wise find a segmentation Ç as well as segment-wise parameters A that minimize loss function Z(5. 0), for example, the negative log-lik log-likelihood of the observations æ. Existing approaches exploit the fact that model estimation within a segment is often straightforward when the segmentation is known. These approaches decouple the search for an optimal segmentation Ç algorithmicaly from the estimation of the segment- parameters A::
parameters by 0 (01, ..... 0x). ). The ultimate goal
min L(s, 0) min min L(S.
C,0
<
Various algorithmic search strategies have been explored for the outer minimization of (, including grid search (Lerman 1980), dynamic programming (Hawkins) 1976 Bai & Perron (200). hierarchical clustering (McGiee & Carleton 1970) and other greedy algorithms (Acharya et al., 2016), some of which come with provable optimality guarantees. These algorithms often tailored to specific class of models like piecewise linear regression, and do not generalize beyond. Moreover, the use of non-standard optimization techniques in the outer minimization hinders the integration of such models with deep learning architectures, which usually perform joint optimization of all model parameters with gradient descent.
In this work, we provide continuous and differentiable relaxation of the segmented model from Equation[]thaa allows joint optimization of all model parameters, including the segmentation function, using saate-of-hhe-rt gradient descent algorithms. Our formulation is inspired by the learnable warping functions proposed recently for sequence alignment (Lohit et al.] [019]] Weher et al. 2019). In nutshell, we replace the hard segmentation function with soft warping function y. An optimal segmentation can be found by optimizing the parameters of the warping function. We propose a novel class of piecewise-constree warping functions based on the two-sided power (TSP) distribution Van Dorp & Kotz 2202; Kotz & van Dorp, 2004) that can represent segmentation functions exactly. -Sp-based warping functions are differentiable, have simple closed-form expressions that allow fast evaluation, and their parameters have a one-to-one correspondence with segment boundaries. Source codes for the model and all experiments can be found in the online supplementary material at
2 RELAXED SEGMENTED MODELS
We relax the model definition from Equation
T the following way. We assume that
Ft
24
iid foor (24,6,) 6.)
(3)
where we substitute the actual parameter 0g of the DGP at time step t in segment k by the predictor 0,. The predictor 0g is a weighted sum over the individual segment parameters
0, : Σ OR:0k
(4)
with weights रेxz E [0, 1] such that Σx vikt = 1 for all f. The weights can be viewed as the entries of a (soft) alignment matrix that aligns every time step t to segment identifier k. Given a (hard) segmentation function Ç, we can construct (hard) alignment matrix by setting wkz = 1 if and only if ((1) = k. In our relaxed model, we employ a continuous predictor Č. E [1,, K] for the value of the segmentation function (t)) and let the weight the depend on the difference between Č and k:
ukz = max (o. -
xl) -
(5)
The smaller the difference, the closer the alignment weight uhke will be to 1. If < 4 this choice of weights leads to a linear interpolation of the parameters 9₂ and 0x+1 in Equation 4 Hidher-order interpolations can be achieved by adapting the weight function accordingly.
2

---

Published as a conference paper at ICLR 2021
71
73
2
5
6
7
8
10
11
Figure 1: Example segmentation function ((t) and warping functions (u). The shaded regions piecewise constant in 7/ and 72, respectively; "a is strictly increasing.
The key question is how to effectively parametrize the continuous predictors Č for the segmentation function. For this purpose, we observe that the continuous analogue of a monotonically increasing segmentation function is a warping function (Ramsay & Li. 1998). Warping functions describe monotonic alignments between closed continuous intervals. Formally, the function y [o, 1] - [0, 1] is warping function if it is monotonically increasing and satisfies the boundary constraints ((0) and 7(1) 1. Any warping function y can be transformed into continuous predictor Č by evaluating at T evenly-spaced grid points on the unit interval [0, 1] and rescaling the result to the domain [1, K]. Let u, (t 1)/(7 (T 1) for i,.... T be unit grid. We define
& = ((4)) (K 1).
(6)
Similar transformations of warping functions have recently been applied for time series alignment with neural networks (Weber et al. 2019). An example segmentation function and predictors based on several warping functions are visualized in Figure With the transformation from Equation [
relaxed segmented model is parametrized by the segment parameters 0 and the parameters of the warping function y that approximates the segmentation. The discrete-continuous optimization problem from Equation 2 has changed to continuous optimization problem that is amenable to gradient-bar badie learning:
min L(>, 7.0
Figure | Illlutraaee that the ideal warping function for segmentation piecewise constant formal argument is provided in Appendix A Several families of warping functions have been proposed in
literature and can employed within our model (Aikawal 1991 Ramsay Li 1998, Gervini
& Gasser 2004 Gaffney & Smyth 2004| Claeskens et al.) 2010 Freifeld et al. 2015 Detlefsen jet al.) 2018 Weber et al.) 2019, Kurtek et al.) [01 Lohit et al. 2019). However, none them
contains piecewise-come constant functions, and many of them more expressive than necessary for the segmentation task. Below, we define a novel family of piecewise-constar warping functions that is tailored specifically for the segmentation task, with only one parameter per change point.
TSP-BASED WARPING FUNCTIONS
Warping functions are similar to cumulative distribution functions (cdfs) for random variables (Lohit al. 2019). Cdfs are monotonically increasing, right-continuous, and normalized over their domain (Wasserman 2004). If their support is bounded to j0, 1]. they satisfy the same boundary constraints as warping functions. Therefore, we can exploit the vast literature on statistical distributions define and characterize families of warping functions. Our family of warping functions is based on the
two-sided power (TSP) distribution Van Dorp & Kotz, 2002
Kotz van Dorp 2004).
3.1 BACKGROUND: TWO-SIDED POWER DISTRIBUTION
The TSP distribution has been proposed recently to model continuous random variables with bounded support Ja, b) C R. It generalizes the triangular distribution and can be viewed a peaked alternative to the beta distribution (Johnson et al., 1994). In its most illustrative form, its probability density function (pdf) is unimodal with power-law decay both sides, but it yield U-shaped and J-shaped
3

---

Published as a conference paper at ICLR 2021
TS,( 1,
(S.(, 1,4)
(S.( 0.5, 4)
(0.700.,0.5.44
(S.9 0.5,
mode
Width
Figure 2: Three-par prrem-arreette variant of the two-sided power distribution TSP w, n) on the interval
[0. 1]. Dashed lines denote the modes m. arrows the widths w; shaded regions have probability zero. Top row: probability density function. Bottom row: cumulative distribution function.
pdf's as well, depending on the parametrization. Formally, the pdf is given by
M-ma for a < u S m
b-a
fTSP(GG o, m. b,)
b-
n-1
for elsewhere,
b
(8)
with a S m S b. and define the boundaries of the support, m is the mode (anti-mode) of the distribution, and > 0 is the power parameter that tapers the distribution. The triangular distribution the special case with n 2. In the following, we restrict our attention to the unimodal regime with < y b and n > 1. In this case, the cdf is given by
0,
for u S a
m--
a
M--a
for a S u S m
Fisp (u; a. m, b)
b-a
mi-a
for m S a S b
b-a
m
for S u.
For convenience, we introduce a three prree-parreete variant of the TSP distribution with support support restricted to subintervals of j0, 1] located around the mode. It is fully specified by the mode m (0, 1). the width w E (0, 1] of the subinterval, and the power n >> 1. Depending on the mode and the width, the distribution is symmetric asymmetric. Illustrations of the pdf and edf of the three-parameter TSP distribution for various parametrizations can be found in Figure 2 We denote the three-parameter TSP distribution as (m, w, n) and write fisP(te (t; m, w, nı) and FisP (u; m, w, n) for its pdf and edf, respectively. The original parameters and are obtained from m and w via
max 00 min (1 w.
2 ))
(10)
= min (1, a + w),
(11)
and yield a unimodal regime. Intuitively, the three-parameter TSP distribution describes symmetric two-sided power kernel of window size that is located a symmetric window would exceed the domain [0, 1]. An advantage of the TSP distribution over the beta distribution is that its pdf and edf have closed form expressions that are easy evaluate computationally. Moreover, they are differentiable almost everywhere with respect to all parameters.
and becomes asymmetric only if
3.2 WARPING WITH MIXTURES OF TSP DISTRIBUTIONS
We define the TSP-based warping function YTSP [0, 1] - [o, 1] for a fixed number of segments as mixture distribution of K three-parameter TSP distributions. Mixtures of unimodal distributions
4

---

Published as a conference paper at ICLR 2021
Table 1: The relaxed segmented model with TSP-based warping functions.
data generating process
Jt.
it ~ SDGP
0z
1,...? T
parameter predictors
0. Σ PE max (0, - -h-
1,...
segmentation predictors
& ; + TTSP
T m
(K - 1)
En'e exp((xx)
TSP mode predictors
mg
k 1, ,, K
W= exp(ux)
segment parameters TSP parameters
,... K 1 K
f4
have step-like cdfs that approximate segmentation functions. We use uniform mixture weights, and treat the width and power n of the TSP component distributions as fixed hyperparameters. The components differ only in their modes (m1,.... "a.l,..,...ll with my E (0, 1):
(usp(u; u1 m)
= K
E Fisp mg, n)..
(12)
We constrain the modes to be strictly increasing, so that "risp is identifiable. the windows around two consecutive modes m4-1 and my non-overlapping, then "Tsp((; m) x between these windows. Furthermore, TTSP (u; m) 0 before the first window and YISP u; m) after the last window. Therefore, the family of TSP-basee warping functions contains piecewise-constan functions. The functions ?/ and "/2 Figure are examples of bSp-based warping functions. We show in Appendix that any segmentation function can be represented by a TSP-based warping function.
k-1
4 MODEL ARCHITECTURE
We have described all components of the relaxed segmented model architecture. It can use any family of warping functions to approximate segmentation function. An overview of the complete model architecture with 7SP-based warping functions is provided in Table [ To simplify the estimation problem, we rewrite the TSP modes as a normalized cumulative sum,
EvSA exp(px) ΣK exp(ux)
mi
for k: = 1,..., 1
(13)
with unconstrained real parameters (11, (k)) The transformation of the parameters guaran- tees that the modes m (m=,,... ..., 11) are strictly increasing and come from the interval (0, 1). The warping function is now overparametrized, since the transformation is invariant to additive terms in the parameters μa. This issue can be resolved by enforeing #l :=
The learnable parameters of this architecture are 0 = (f.. 0x) for the DGP and == (M1, Pk) ........,
for the warping function. The hyperparameters are the number of segments window size w E (0, 1] and power n > 1 of the TSP distributions. This architecture is concatenation of simple functions that are either fully differentiable or differentiable almost everywhere. Therefore, all parameters can be learned jointly using gradient descent. A hard segmentation Ç of the input sequence can be obtained at any time during after training by rounding Ç. the nearest integers.
K < T, and the
EXPERIMENTS
Our relaxed segmented model is highly versatile and can be employed for many different tasks. In Section we study the performance of our approach in estimating a segmented generalized linear model (GLM) (Muggeo) 2003 on COVID-19 data. In Section 5.2 evaluate approach

---

Published as a conference paper at ICLR 2021
8000
7000
reported production an average
-200
6000
-300
ROW CIVES
-400
5000
-000
saturated model
Maggeo (2003)
-7000
CPAb
2000
-0000
TSPb
1000
110000
0
64
Feb 24
Mar Mar 0u
02
Mar 16
Mar
Mar 30
Apr vs
App
App
Apr
May Di
May II
May
number of segments K
Figure 3: Segmented Poisson regression results on COVID-19 case numbers in Germany.
a change point detection benchmark against various competitors. In Section 5.3 we apply it on a streaming classification benchmark with concept drift. At last, Section [544 illustrates potential future applications of our model for discrete representation learning. We implemented our model in Pythor using PyTorch and optimize the parameters with ADAM (Kingma & Ba 2015). We employ three different families of warping functions in our relaxed model: nonparametric (NP) (oohit et al., 2019), CPA-based (CPAb) (Weber al.) 2019), and our TSP-based functions (TSPb). Source codes be found in the supplementary material.
5.1 POISSON REGRESSION
Recent work has applied segmented Poisson regression to model COVID-19 case numbers (Küchen hoff et al.) 2020 Muggeo et al. 2020). We follow Küchenhoff et al. (2020) and model daily time series of newly reported COVID- cases during the first wave of the pandemic. We obtained official data for Germany from Robert Koch Institute [ A visualization of the reported data in Figure (right plot, bars) reveals non-stationary growth rates and weekly periodicity. Therefore, we use time and a day-of-week indicator as covariates in the model. We tie the coefficients for the day-of-week indicators across all segments, while the daily growth rates and the bias terms differ in every segment. We estimate a standard segmented Poisson regression model with the baseline algorithm by Muggeo (2003), and our relaxed models (TSPb, CPAb, NP) with gradient descent. We estimate the baseline model and the relaxed models with K = 2, 4, 8, 16, 32, and 64 segments. The true number of segments is unknown in this task. More details can be found in Appendix B.1
Figure 3 (left plot) shows the goodness-of-fn (log-likelihood) of all models. TSPb consistently reaches the performance of the baseline algorithm. Moreover, TSPb consistently outperforms the other families of warping functions in this experiment. The improvement over NP is particularly large, which indicates that the "nonparametrie" warping functions Lohit al. (2019) are harder to train than the parametric families. CPAb achieves a performance similar to TSPb, but the training time is much longer due the more complex mathematical operations involved.
We observe that the goodness-of-fe offfit generally grows with the number of segments K and approaches the performance of saturated model (one Poisson distribution per data point). For K 8, the baseline of Muggeo (2003) terminates without a model estimate. Figure 3 (right plot) visualizes the best TSPb model for K (blue line). We also provide smoothed predictions where the average day of week (dow) effect is incorporated into the bias term to highlight the change of the growth rate from segment to segment (purple line). The three change points are located 2020-03- 16, 2020-03-31. 1. and 2020-05-05. The baseline algorithm of Muggeo 2003) detects consistent change points at 2020-03-16 (=00 days), 2020-03-30 (-1 day), and 2020-05 01 (-4 days). Since the reported data is not iid within segment (it is only conditionally iid given the covariates), other algorithms for change point detection cannot be applied as competitors on this task. Overall, the experiment shows that our model architecture allows effective training of segmented generalized linear models using gradient descent, in particular, when employed with TSPb warping functions.
https://pythen.org
https://pvtorch.cc
https://ww.rrii.

---

Published as a conference paper at ICLR 2021
rundom sequence
TSPb frequencies sequences
20
0
1000
200
300
400
5000
600
700
800
900
1000
1001
200
300
400
500
600
700
800
900
1000
Figure 4: Change point detection task of Arlot et al. (2019) with detection results from our model.
Table Empirical change point detection results.
algorithm
sonsitivity
#CPs (de
tuer (mean::std)
den (mean::std)
reference
random
10
127.8 1 45.5
3.3 d 0.2
baseline
DP21
10
753.3 + 120.8
4.1 + 0.3
Truong al.
2020
DP210
123.6 170.7
2.1 + 0.7
Truong ar
2020
BinSeg
10.0 + 3.1
122.0 97.7
2.5 + 0.4
Scoll Knol 197
PELT
86.2
26.7
100.0 1 26.9
8.7 1.5
Killikk el al. 2012
NP
88.4 +: 35.7
2.3
CPAb
10
88.4 1. 32.3
2.7 0.3
thär work
82.5
2.3 0.3
this
E- Diviisive
5.9 1.9
162.0 1: 108.2
2.2 0.4
0.4
Matteson & James
2014
KCP
8.6 1.4
67.3 55.1
1.4
KCpE
10
33.8 +: 37.6
1.2 + 0.6
Tarchaou
uppe
2007
sensitivity; menn/arrance = full distribution.
ICPs; number of change points; it equai to 10, 8CPs is parameter, otherwise, it inferred antomatically.
5.2 CHANGE POINT DETECTION
In the next experiment, evaluate relaxed segmented model change point detection task with simulated data. Our experimental design exactly follows Arlot et al. (2019). All details are given in Appendix B.2 We sample random sequences of length 7'= 1000 with 10 change points at predefined locations. For every segment in every sequence, distribution is chosen randomly from a set of predefined distributions, and observations within that segment are sampled independently from that distribution. We follow scenario I of Arlot et al. (2019), where all predefined distributions have different means and/or variances. An example is shown in Figure (left). (left). We sample N 500 such sequences, with change points at the same locations across all samples.
We apply our relaxed segmented model to estimate the change points. We model the data generating process by normal distribution with different means and variances in every segment. This design choice makes our approach sensitive only to changes in the means and variances of the observed data, and other distributional characteristics. We fit our model individually to all N sequences to obtain individual estimates for the change points. Figure 4 (right) shows how many times a specific time step detected change point by our approach (with TSPb warping functions). We observe clear peaks at the correct change point locations, which indicates that our model successfully recovers the original segmentations in many runs.
Table 2 summarizes the empirical detection performance of our approach (TSPb, CPAb and NP) and various competitors, including baseline where change points drawn randomly without replacement. It shows the Hausdorff distance diar and Frobenius distance dyo between the true segmentations and the detected segmentations (the lower the better). Among the approaches that detect changes in the mean and variance, our model performs best in terms of dhar and second best in terms of dmn regardless of the choice of warping function. Note that all approaches in this group optimize the same objective function (the likelihood of the data under normal distribution). The dynamic programming approaches (DP>() (Truong et al. (020) exactly find the optimal solution for a predefined number of change points, with minimum segment length of t. PELT (Killick et al. (0122) finds the optimal solution with an arbitrary number of change points, while BinSeg (Scott & Knott 1974) approximates that solution. Although our gradient- based method finds suboptimal solutions in terms of the normal likelihood, produces results with the lowest segmentation costs. This indicates regularizing effect of the relaxed segmented model that avoids degenerate segmentations. Our
7

---

Published as a conference paper at ICLR 2021
incremental
abrupt
inc gradual
inc aaaraabbreeeeee
inc rence
1.8 ARE
accuracy
0.8
TSPb
0.8
0.7
0.6
0.6
0.5
0.5
16
32
128
32 61
128
2
16
64
128
4
8
16
32
128
16 32 64
128
K
K
K
K
K-
Figure 5: Classification performance on the insect stream benchmark of Souza et al.
2020
approach is only outperformed by algorithms for kernel-based change point detection (Harchaoui
Cappé 2007 Arlot et al. 2019) that are sensitive towards all distributional characteristics.
5.3 CONCEPT DRIFT
A key novelty of our segmented model architecture is that it allows joint training of the segmentation and any other model component using gradient descent. As proof of concept, we apply our model on a classification problem with concept drift (Gama et al. 2013). The model has to learn the points in time when the target concepts change, and useful feature transformation for the task. We use the insect stream benchmark of (oozaa et al. (2020) for this purpose. The task is to classify insects into 6 different species using 33 features collected from an optical sensor. The challenge that these species behave differently when the air temperature (which is not included as feature) changes. The benchmark contains multiple data streams, where the air temperature is controlled in different ways (incremental, abrupt, incremental -gradual, incremenntalaaruup--oooo abrupt-reoccurrngg The classifier must adapt the learned concepts depending on the current air temperature.
pecremental-reoccuminn
We employ our relaxed segmented model for softmax regression with the cross entropy loss to obtain segmentations of the data streams. We focus on the five data streams with balanced classes from the benchmark, and measure performance by the classification accuracy. We fit models with K = 2, 4, 8, ..., 128 segments using TSPb warping functions. We transform the input instances with fully connected layer followed by a ReLU nonlinearity before passing them to the segmented model. The feature transformation is shared across all segments. We jointly learn the parameters of the segmented model and the feature transformation with gradient descent. Details can be found in Appendix B.33 Results are visualized in Figure [ In addition to our own results, we include the prequential accuracies of the strongest competitors reported by [Souza et al. (2020): Leveraging Bagging (LB) (Bifet et al. 2010)) and Adaptive Random Forests (ARF) (Gomes et al. 2017).
Our relaxed segmented model reaches and outperforms the strongest competitors on all streams from the benchmark, if the number of segments K is large enough to accommodate the concept drift present the stream. Note that only the data stream with abrupt concept drift satisfies our modeling assumption of piecewise stationary data generating process. It consists of six segments with constant air temperatures within each segment. The pireemental-graddie stream has three segments, with mildly varying temperatures in the outer segments and mixed temperatures in the inner segment. The black boxes in their plots show the performances achieved with our approach for K = and K = 3 segments, respectively. The results indicate that these in fact the minimum numbers of segments required to obtain competitive performance on these data streams.
5.4 DISCRETE REPRESENTATION LEARNING
At last, we apply our model on a speech signal to showcase its potential for discrete representation learning the level of phonemes. We assume that the speech 12-dimensional MFCC vectors piecewise constant within a phoneme. We model it by a minimal B.4 for
by sequence of
DGP with covariates that simply copies the parameter vectors to the output. See Appendix B.4
a complete model description. We fit the model to a single utterance ("choreographer" 10 phonemes) from the TIMIT corpus (Garofolo et al. 1993) by minimizing the mean squared error loss, and obtain:
Although the simple DGP does not capture all dynamics of the speech signal, out of 9 phoneme boundaries were correctly identified, with time tolerance of 20 ms. This minimal experiment
8

---

Published as a conference paper at ICLR 2021
observed sequesce, with true phoneme boundaries
preducted sequence, with true phoneme boundarics
suggests that relaxed segmented models, when combined with more powerful DGPs, may be useful for discrete representation learning (Rolfe 2017 van den Oord et al. 2017 Fortuin al. (019). in particular for learning segmental embeddings (Kong et al. 2016 Wang et al. 2018 Chorowski
et al. 2019) Kreuk al.) 2020). In fact, our relaxed segmented model may be part of larger model architecture, where the covariates 2₁ and the parameters 02 come from some upstream computational layer, and the outputs 2i are passed on the next computational layer with an arbitrary downstream loss function. The interpretation of 2, as covariates and 8g as parameters is merely for consistency with prior work on segmented models. It is more accurate interpret 2 as temporal variables that differ for every time step I, and 0g as segmental variables that differ for every segment k. The DGP combines the information from both types of variables to produce an output for every time step.
6 CONCLUSION
We have described a novel approach to learn segmented models for non-stationary sequential data with discrete change points. Our relaxed segmented model formulation is highly versatile and can use any family of warping functions to approximate hard segmentation function. If the family of warping functions is differentiable, our model can be trained with gradient descent. A key advantage of a differentiable model formulation is that it enables the integration of state-of-the-art learning architectures within segmented models. We have introduced the novel family of TSP-based warping functions designed specifically for the segmentation task: it is differentiable, contains piecewise- constant functions that exactly represent segmentation functions, its parameters directly correspond to segment boundaries, and it is simple evaluate computationally. The experiments on diverse tasks demonstrate the modeling capacities of our approach.
Limitations and future work. The most immediate limitation of our relaxed segmented model
that it shares with classical segmented models (Bai & Perron 2003 Muggeo 2003) is that the number of segments K is a hyperparameter and needs to be chosen prior to model fitting. This issue can be resolved externally with any model selection criterion (Davis et al. 2006). However, due to differentiable model formulation, future work may be able to solve the model selection task internally within a single objective function that optimized with gradient descent, e.g., using the differentiable architecture search approach of Liu et al. (2019).
Another limitation that we inherit from classical segmented models that all K segments are treated as distinct regimes with their own parameter vectors 0₂. For example, if the data data-generating process switches back and forth multiple times between only two distinct regimes, a segmented model has to learn the same parameter vector every time the regime switches. During training, we can favor solutions with reused segment parameters by adding regularization term to the loss function that penalizes high rank of the segment parameter matrix 0 = (0,,..., 0x). If we wanted to control the number of distinct regimes separately, we could learn a codebook of << K distinct segment parameters and mapping from segment identifiers to codebook entries f (1., K) + {1...., C}, e.g., using the vector quantization approach of van den Oord et al. (2017). 7. This is possible only because model is fully differentiable and can easily be augmented with such components.
At last, we consider the application of our approach for discrete representation learning under powerful deep data- generatnnn processes sketched in Section 5.4 a fruitful direction for future work.
REFERENCES
Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt. Fast algorithms for segmented regression. In ICML, 2016.
Kiyoaki Aikawa. Speech recognition using tinewwarping neural networks. In /EEE Workshop on Neural Networks for Signal Processing, 1991.

---

Published as a conference paper at ICLR 2021
Sylvain Arlot, Alain Celisse, and Zaïd Harchaoui. A Kernel Multiple Change- poigee--oonttooo Algorithm via Model Selection. Journal of Machine Learning Research, 20:1-56, 2019.
Alexander Aue and Lajos Horváth. Structural breaks in time series, Journal of Time Series Analysis, 34(1):1-16, 2013.
Jushan Bai and Pierre Perron. Computation and analysis of multiple structural change models. Journal of Applied Econometrics, 18(1):1-22, 2003.
M Basseville and Igor V Nikiforov. Detection of Abrupt Changes: Theory and Application. 1986.
Albert Bifet, Geoff Holmes, and Bernhard Pfahringer. Leveraging bagging for evolving data streams. In ECML PKDD, 2010.
George Box and George Tiao. Change in Level of Non-Stationary Time Series. Biometrika, 52 (1/2):181-192, 1965.
Jun Cai. A Markov Model of Switching-Regime ARCH. Journal of Business and Economic Statistics, 12(3):309-311 1994.
Jan Chorowski, Ricard Marxer, Guillaume Sanchez, and Antoine Laurent. Unsupervised Neural Segmentation and Clustering for Unit Discovery in Sequential Data. In NeurIPS Workshop on Perception Generative Reasoning, 2019.
Gerda Claeskens, Bernard W. Silverman, and Leen Slacts. A multiresolution approach to time warping achieved by a Bayesian prior-posterior transfer fitting strategy. Journal of the Royal Statistical Society. Series B: Statistical Methodology, 72(5):6736644 2010.
Richard A Davis, Thomas C M Lee, and Gabriel A. Rodriguez-Yam Structural Break Estimation for Nonstationary Time Series Models. Journal of the American Statistical Association, 101(473): 223-239 2006.
Nicki Skafte Detlefsen, Oren Freifeld, and Soren Hauberg. Deep Diffcomorphic Transformer Networks. In CVPR, 2018.
Jie Ding, Yu Xiang, Lu Shen, and Vahid Tarokh. Multiple Change Point Analysis: Fast Implementa- tion And Strong Consistency. In ICML Anomaly Detection Workshop, 2016.
Vincent Fortuin, Matthias Hüser, Francesco Locatello, Heiko Strathmann, and Gunnar Rätsch. SOM- VAE: Interpretable discrete representation learning time series. In ICLR, 2019.
Oren Freifeld, Soren Hauberg, Kayhan Batmanghelich, and John W. Fisher. Highly-expressee exxresssie spaces of well-behaved transformations: Keeping it simple. In ICCV, 2015.
Scott Gaffney and Padhraic Smyth. Joint probabilistic curve clustering and alignment. In NIPS, 2004.
João Gama, Indré Žliobaité, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. A survey on concept drift adaptation. ACM Computing Surveys, 1(1), 2013.
John S. Garofolo, Lori F. Lamel, William M. Fisher, Jonathan G. Fiscus, David S. Pallett, Nancy I.. Dahlgren, and Victor Zue. TIMIT Acoustic-Phonetic Continuous Speech Corpus LDC93S1, 1993.
Daniel Gervini and Theo Gasser, Self-modelling warping functions. Journal of the Royal Statistical Society B, 66(4):959-9)) 971, 2004.
Heitor M. Gomes, Albert Bifet. Jesse Read, Jean Paul Barddal, Fabrício Enembreck, Bernhard Pfharinger, Geoff Holmes, and Talel Abdessalem. Adaptive random forests for evolving data stream classification. Machine Learning, 1699--1)):469-1144 2017.
Valery Guralnik and Jaideep Srivastava. Event detection from time series data. In KDD, 1999.
James D. Hamilton. Analysis of time series subject to changes in regime. Journal of Econometrics, 45(1-2)339-70, 1990.
10

---

Published as a conference paper at ICLR 2021
Zaid Harchaoui and Olivier Cappé. Retrospective Multiple Change-Point Estimation With Kernlss In IEEE Workshop on Statistical Signal Processing (SSP), 2007.
Douglas M. Hawkins. Point Estimation of the Parameters of Piecewise Regression Models. Journal of the Royal Statistical Society C, 25(1), 1976.
Norman L. Johnson, Samuel Kotz, and N. Balakrishnan. Continuous univariate distributions, vol. 2.
John Wiley & Sons, Inc., New York, USA, 1994.
Corinne Jones and Zaid Harchaoui. End-to-end Learning for Retrospective Change-poing Estimation. In IEEE International Workshop on Machine Learning for Signal Processing, 2020.
R. Killick, P. Fearnhead, and I. a. Eckley. Optimal detection of changepoints with a linear computa- tional cost, Journal of the American Stutistical Association, (0955 2012.
Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Jens Kohlmorgen and Steven Lemm. A dynamic HMM for on-line segmentation of sequential data. In NIPS, 2001.
Lingpeng Kong, Chris Dyer, and Noah A. Smith. Segmental recurrent neural networks. In ICLR, 2016.
Samuel Kotz and Johan René van Dorp. Beyond Beta: Other Continuous Families of Distributions with Bounded Support and Applications. World Scientific Publishing Co. Pte. Ltd., Singapore, 2004.
Felix Kreuk, Yaniv Sheena, Joseph Keshet, and Yossi Adi. Phoneme Boundary Detection using Learnable Segmental Features. In ICASSP, 2020.
Helmut Küchenhoff, Felix Günther, Andreas Bender, and Michael Höhle. Analyse der Epidemis- chen Covid-19 Kurve in Bayern durch Regressionsmodelle mit Bruchpunkten. Technical re- München, Germany, Munich, Germany, 2020. URL
port, Buddiigs-axximlllan--Unvveeees https: sta.toorrooaaa.t....ooo... stat. uni -wwncchen.dee.
Sebastian Kurtek, Anuj Srivastava, and Wei Wu. Signal estimation under random time-warpings and nonlinear signal alignment. In NIPS, 2011.
Rémi Lajugie, Sylvain Arlot, and Francis Bach. Large-margin metric learning for constrained partitioning problems. In JCML, 2014.
P. M. Lerman. Fitting Segmented Regression Models by Grid Search. Journal of the Royal Statistical Society. Series C (Applied Statistics), 2911)777-84, 1980.
Shuang Li, Yao Xie, Hanjun Dai, and Le Song. M-Statistic for Kernel Change-Point Detection. In NIPS, 2015.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In ICLR, 2019.
Suhas Lohit, Qiao Wang, and Pavan Turaga. Temporal Transformer Networks: Joint Learning of Invariant and Diseriminative Time Warping. In CVPR, 2019.
David S. Matteson and Nicholas A. James. A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data. Journal of the American Statistical Association, 109(505):334 345, 2014.
McCullagh and A. Nelder. Generalized Linear Models. Chapman and Hall/CRC, Boca Raton, Florida, USA, 2nd edition, 1989.
Victor E. McGee and Willard Т. Carleton. Piecewise regression. Journal of the American Statistical Association, (00331):1109-113 1970.
Vito M.R. Muggeo, Estimating regression models with unknown break treak-points. Statistics in Medicine, 2211533055-3071, 2003.
11

---

Published as a conference paper at ICLR 2021
Vito M.R. Muggeo, Gianluca Sottile, and Mariano Poreu. Modelling COVID-19 out-
break: Segmented Regression to Assess Lockdown Effectiveness. Technical re-
port, ResearchGate, 2020. URL Btpp:///w..ressarccaaaeee http://wwaaacaaaaaaeeeeeeeeoeeee
App1 ons of seef-segeenedd mode dreereeettteeemmeeeeleiiinnnnnnr
instimatioo
E. S. Page.
Continuous Inspection Schemes. Biometrika, 41(1/2), 1954.
James O. Ramsay and Xiaochun Li. Curve registration. Journal of the Royal Statistical Society B, 60 (2):551-363, 1998.
Joshua W. Robinson and Alexander J. Hartemink. Non-stationary dynamic bayesian networks. NIPS, 2008.
Jason Tyler Rolfe. Discrete variational autoencoders. In ICLR, 2017.
Ardavan Saeedi, Matthew Hoffman, Matthew Johnson, and Ryan Adams. The Segmented iHMM: simple, efficient hierarchical infinite HMM. In ICML, 2016.
Erik Scharwächter and Emmanuel Müller. Two-Sample Testing for Event Impacts in Time Series, In Proceedings of the SIAM International Conference on Data Mining (SIAM SDM), 2020.
J Scott and M Knott. A Cluster Analysis Method for Grouping Means in the Analysis of Variance. Biometrics, 30(3):007--12, 1974.
Vinicius M.A. Souza, Denis M. dos Reis, André G. Maletzke, and Gustavo E.A.P.A. Batista. Chal- lenges in benchmarking stream learning algorithms with real-world data. Data Mining and Knowledge Discovery, 34(6):1805-1855 2020.
Charles Truong, Laurent Oudre, and Nicolas Vayatis. Selective review of offline change point detection methods. Signal Processing, 167, 2020.
Genrit J. J. van den Burg and Christopher K. I. Williams. An Evaluation of Change Point Detection Algorithms, arXiv:20033.6622222 2020.
Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learning. In NIPS, 2017.
René Van Dorp and Samuel Kotz. The standard two-sided power distribution and properties: With applications in financial engineering, American Statistician, 56(2):90-99, 2002.
Yu-Hsuan Wang, Hung-yi Lee, and Lee Lin-shan. Segmental Audio Word2Vec: Representing Utterances as Sequences of Vectors with Applications Spoken Term Detection. In ICASSP, 2018.
Larry Wasserman. All of Statistics: A Concise Course Statistical Inference. Springer Sci- ence+Business Media, LLC, New York, USA, 2004.
Ron Shapira Weber, Matan Eyal, Nicki Skafte Detlefsen, Oren Shriki, and Oren Freifeld. Diffeomor- phic Temporal Alignment Nets. In NeurIPS, 2019.
Nancy R. Zhang and David O. Siegmund. A modified Bayes information criterion with applications to the analysis of comparative genomic hybridization data. Biometrics, 63(1):22-33) 22,22,2242 2007.
12

---

Published as a conference paper at ICLR 2021
A WARPING FUNCTIONS FOR SEGMENTATION
In this section, we provide a technical notion of representation of segmentation functions and show that TSP-based warping functions can represent segmentation functions in this sense.
Definition The warping function y [0. 1] - [0. 1] exactly represents the segmentation function S {1,.... 7 (1,... K} with respect to the unit grid (we) if
1
7(2) = K-1 + c(t) = k for t.
(14)
Exact representation entails that the predictors ? defined in Equation 6 satisfy & ((t) for all t. Clearly, exact representation can only be achieved with piecewise-constant warping functions. We have the following result:
Lemma 1. For every segmentation function S, there is TSP-based warping function "Yrsp that exactly represents Ç.
Proof. We place the K --1 modes me of TISP the change points т.e (projected to the unit grid)
and choose a window size w not larger than the resolution of the grid. The power n > 1 can be chosen frrelly Formally, let Tы {2, TJ be the k-th change point, such that <(TH - 1) k and ((Tk) = l: + 1. We set my == (U+, + "T, /) for all 1,..,, K 1, and w == 1/( 1).
In practice, the segmentation function Ç unknown and the modes estimated in an unsupervised way. For effective training with gradient descent, the window size should initially be larger than the sampling resolution of the unit grid, w 1/(T 1). to allow the loss to backpropagate across segment boundaries. The window size can be interpreted as the receptive field of the individual TSP components. The width can be tapered down w S 1/(T- over the training epochs to obtain warping function that exactly represents segmentation function. For simplicity, we do not follow this strategy in experiments, but instead round the predictors Ç to the nearest integers, whenever we need hard segmentations.
(m11,... mk- 1) must be
B DETAILS ON THE EXPERIMENTS
B. POISSON REGRESSION
Data. We obtained official data on COVID-19 cases in Germany from Robert Koch Institute (RKI), the German public health institute. The data is publicly available under an open data license We provide copy used for the experiments in this work in the supplementary material. For every day in the study period, we aggregate all new cases reported on that day. Due to the delays between the actual infection of patient and the time the infection is reported to the health authorities, the new cases reported on a specific day contain new infections from several days before.
Segmented Poisson regression model. Poisson regression is a GLM for count data, where the data generating process modeled by a Poisson distribution and the linear predictor is transformed with the logarithmic link function (McCullagh & Nelder 1989).
Let 2, denote the number of newly reported cases at time t. Furthermore, let zt 2t and 2 denote binary day-of-week indicators. If the time step is Monday, all indicators are O. For all other days, exactly one indicator set to I. We use the following vector of covariates, including a bogus covariate for the bias terms:
Th Fr Saa
zt
2 [1,4, Tu We Th Sn Su
(15)
In our segmented Poisson regression model, the bias terms and the daily growth rates (the parameters associated with the covariates and t) differ in every segment, while the parameters for the day-of- week indicators are tied across all segments (they are independent of segment k):
0g [0x. 02.2, TTh We Th thr OSy
(16)
''Fllzahlenn in Deutschland" by Robert Koch Institut (RKI), open data license "Data licence Germany attribution Version 2.0" (dl-de/by-2-0), link: https: / www. regi com/home i item html 2
F10774F1c63440168o2
13

---

Published as a conference paper at ICLR 2021
-300
log- log-likellbood
-1000
-2000
saturated model
saturated model Maggoo (2003) TSP6
saturated model Murgeo (2003)
-2500
Maggeo (2000)
TSPb
TSPb
-2000
2048
TSPh integer epochs
TSPb width 10
TSPb power n2
Figure 6: Ablation study for TSPb hyperparameters (segmented Poisson regression); default values for the fixed hyperparameters are: 2048 integer epochs, = .5, and = 16, respectively.
In this model, the bias terms 1 control the base rates of newly reported cases Monday within every segment k, while the parameters for the day-of of-w indicators are global scaling factors that control the relative increase decrease of the base Monday. Overall, we have the following segmented Poisson regression model:
the other days-of-week with respect to
E[2,
2.] == exp 0R.1 + 0k,2 +++
Σ
gday day 2t
if ift
(17)
dayE (Tu, Su.
The training objective is to minimize the negative ligeliiel under Poisson distribution:
[(S. =
Σ log Poisson(2ç iz))
(18)
In our TSP-based warping functions (TSPb), we set the window size to w .5 and the power to 16. In the CPA-based warping functions (CPAb) of Weber et (2019), set the dimensionality of the underlying velocity fields to K, the number of segments to learn. This choice makes the function family flexible enough to approximate warping functions with K 1 discrete steps, using the minimum number of parameters necessary. Note that the "nonparametric" warping functions (NP) Lohit et al. (2019) have
parameters, where the sequence length. We perform training with ADAM with learning rate of 1 0.01 for a total of 10000 training epochs. In the last 2048 epochs, round the predictors & to the nearest integers obtain a hard segmentation function ((t). We perform 10 restarts of the training procedure with random initialization and keep the model with the best fit for evaluation (highest log-likelihood).
Competitor. We the reference implementation of Muggeo 2003) from the R segment ed package. As pointed out in Section [ our segmented model architecture learns a segmentation of the index set 1, ...,, T. The segmented models Muggeo (2003) learn segmentation in the domain of one (or more) of the covariates. Since we use the index as a covariate, we can configure the algorithm of Muggeo 2003) to segment the covariate which makes the two models equivalent.
Ablation study. Figure G shows the goodness-of-fit (log-likelihood, the higher the better) obtained with our relaxed segmented model (TSPb) using different settings of the hyperparameters. The performance is quite robust with respect the width and power of the TSP components. The number of integer epochs (with hard segmentations) has impact on the estimation performance. We hypothesize that the learning problem is simpler with soft segmentations, so that gradient descent moves towards better region of the loss function. During integer epochs, the parameters within segment are fine-tuned within region found during the soft epochs.
B.2 CHANGE POINT DETECTION
Data generating process. We follow scenario of Arlot et al. (019) to sample N 500 random sequences of length T 1000 with total of 10 change points (k 11 segments). The change points are located at time steps 100, 130, 220, 320, 370, 520, 620, 740. 790, and 870. We define change point the beginning of new segment. The data generating process is described in
14

---

Published as a conference paper at ICLR 2021
Algorithm Data generating process Arlot et al. (2019).
for all sequences n I, ...,, .N do
for all segments k = 1, 1,.., K do sample a distribution Puk uniformly from P (Pn,k-1)
Hd sample Txa Pnk for all time steps in segment lt end for end for
Algorithm where P is set of predefined probability distributions. For scenario 1, we have
: (n 10, = 0.2), NegBinom(n = 3.p = - 0.7),
Hypergeom - 10, n 5, N N1 2.5, - 0.25), M(a 0.5, 5), Weibullla 2, 5), Parcto(a 3, 1.5)),
(19)
where a is the shape parameter and à is the scale parameter in the case of Т, Weibull, and Pareto. For every algorithm in the evaluation, we create new sample 500 sequences.
Segmented normal model. We employ our relaxed segmented model with the assumption that the data generating process within each segment a normal distribution with its own mean and variance,
Hd N o if ((t) = k.
(20)
With this design choice, we can detect changes in the mean and variance between the segments, but no other distributional characteristics. The training objective is to minimize the negative liliikeeihhod:
((C,0) = Σ log (wx Me(a), 2Q())
(21)
We ensure positive variance throughout training by estimating the logarithm of the variance, i.e., the parameter vector within segment is given by 0₂ = [1x, log (d2)
For TSPb, we set the window size to .125 and the power dimensionality of the velocity field to K. NP has no hyperparameters. We perform training with ADAM with learning rate of 0.1 for total of 300 epochs with 100 integer epochs. We perform 10 restarts with random initialization and keep the model with the best fit for evaluation.
16. For CPAb, we set the
Competitors. For the experiments with the dynamic programming approaches (DP > f), use the implementation of Truong et al. (020) from the Python ruptures module, using the normal cost function with a minimum segment size of f, 10 change points, and no subsampling. For the binary segmentation approach (BinSeg) by |Scott& & Knott (974)) and the Pruned Exact Linear Time (PELT) method of Killick et al. (2012). we use the R changepoint package (cpt meanvar, normal test statistic, MBIC penalty (Zhang & Siegmund (007). minimum segment size 2, maximum number of change points 100). The experiments with the E-divisive approach (Matteson & James 2014) were conducted with the R eep package (e di visive. significance level .05, 199 random permutations, minimum, minimum segment size 2, moment index 1). For the experiments with the kernel-based approaches KCP (Allt et al. 2019) and KCpE (Harchaoui & Cappé 2007). the implementation from the Python chapydet package kindly provided by Jones & Harchaoul (2020), with the default Gaussian-Euclidenn kernel, bandwidth 0.1, and minimum segment size 2.
Performance measures. We use the same evaluation measures as Arlot et al. (2019) and follow their definitions. Let ( and ç' be two segmentations of sequence of length T. Let and 7 be the corresponding sets of change points. The Hausdorff distance is the largest distance between any change point from one segmentation and its nearest neighbor from the other segmentation:
dnar(S, (S, 5²) max
max Isisir
min I - 1515|11
min |T, Tih |T/hhb
(22)
15

---

Published as a conference paper at ICLR 2021
Table 3: Ablation study for TSPb hyperparameters (change detection).
width
dua (mean (idd
dn (mean.istu)
31.9
16 0.25
83.3
35.1
2.3
0.3
0.125
82.3
32.3
2.3 0.3
16 0.0625
85.0
36.1
2.4 1.41000
0.3
0.125
83.0 34.4
244
8 0,125
79.5 31.3
2.3 1 0.4
0,125
82.5 32.3
2.3 = 0.3
32
0,125
80.4
30.1
2.3
0.3
The Frobenius distance between two segmentations (Lajugie al,, 2014) defined as the Frobenius distance between the rescaled equivalence matrix representations of the segmentations:
din (¹) || M
(23)
c(())
where M
(24)
En' (((0=((()))
It penalizes ver-segmentation more strongly than the Hausdorff distance.
Ablation study. We experimented with different values for the TSPb hyperparameters; Table shows the results. The detection performance is robust towards the choice of hyperparameters.
B.3 CONCEPT DRIFT
Benchmark data. The insect stream benchmark is described in detail in Souza et al. (020). The five data streams with balanced class distributions that consider here have the following lengths. incremental: 57,018; abrupt: 52,848; incremental-graduee 24,150; incrementallabrugee inceemendd-bbrrugrroowrrrrg 79,986; incremental-reocccrring 79,986 (sic).
Softmax regression model. Softmax regression is standard multi-class classification model, where the data generating process modeled by categorical distribution with probabilities computed from the softmax function. Let (Iz; yt) denote a training instance from the insect stream benchmark, where It E (1, C} is the target class label and y/s the raw observation. We learn a more informative representation 2, of the observation y, by passing it through linear layer with output dimension
8, followed by ReLU nonlinearity. We denote this feature transformation by : (Vr). where á are the learnable parameters of the transformation. The covariates used within a segmented softmax regression model to predict the targets Zt.
2/ Categgrica(Softmaxx((aa.)) if ((t) =
(25)
In this model, 0g RCx is matrix, that 2 RC contains unnormalized classification scores for every class e in segment k. The softmax function transforms the scores into normalized class probabilities. The feature transformation f is shared across all segments, while the parameters of the linear predictor change from segment to segment. With this design, we learn feature transformation that useful for the classification task in general, while taking concept drift in the label associations into account. The training objective is to minimize the negative likeelioooood under the categorical distribution, more commonly known as the cross-entropy loss
L(C, 0,) = Σ log Categorical(1z (oftmaxx((<()
(26)
= = [[cc))=]] -log Σ exp [0cco)=]])
(27)
We employ TSPb warping functions with window size .25 and power 16. We perform training with ADAM with a learning rate of r .1 for total of 300 epochs, with 100 integer epochs. We perform 10 restarts with random initialization and keep the model with the best fit for evaluation.
16

---

Published as a conference paper at ICLR 2021
B.4 DISCRETE REPRESENTATION LEARNING
Piecewise constant model.
We assume the piecewise constant, deterministic DGP
Jt. = 0p:
if ((t)
(28)
and minimize the mean squared error of the output
[(S, 8) - Σ 11, - 1x11
(29)
We fit our relaxed segmented model with TSPb warping functions (K = 10 segments) with window size .125 and power 71 16. We perform training with ADAM with learning rate of 1) = for a total of 300 epochs with 100 integer epochs. We perform 10 restarts with random initialization and keep the model with the best fit for evaluation.
17


Reviews:
[{"review_id": "dYdf4kqyFfQ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[summary]\nThe paper proposes a relaxed way to solve the segmentation of sequence that can directly leverage the deep learning architectures. The relaxed model allows each segmentation parameter to be a linear interpolations between two consecutive parameters depends on a continuous warping function. The paper then proposes to use mixture of TSP distribution to simulate a step-like warping function and perform a thorough empirical comparison results with different methods and different warping functions. It turns out that TSP-based methods consistently achieve good performance.\n\n[novelty]\nTo be honest I am not familiar with this area. It seems that this is a very novel method and may have impact across the area.\n\n[significance]\nThe algorithm is very easy to understand and simple to implement, which may be very easy to reproduce by the community. The segmentation problem itself, especially the COVID19 case, show the importance of this area and may attract further attention from even outside the community.\n\n[clarity]\nI enjoy reading the paper and find it very easy to follow. The experimental results are clear and detailed.\n\n[some further questions]\nI'm curious for the relaxed models in equation (4). I didn't see why (4) should be very general form of relaxation. Why is it important to only interpolate consecutive two parameters? Is is possible to rewrite (4) into a weighted average $\\sum_k w_{k,t} \\theta_k$ and we hope so that $w_{k,t}$ depend on a continuous function, similar to $\\zeta_t$, and index $k$?", "extra_scores": {}, "extra_text": {}}, {"review_id": "QUlWFynAhof", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper describes the use of two-sided power functions for differentiable approximation of segmentation in discrete sequences with monotonic segmentation (each event in the sequence is defined by one continuous interval). The authors show that their particular parametrization allows to control exactly the length, starting, and ending point of the interval, and the slope of change (Fig. 2). \nThe main result of the paper is the ability to pose segmentation and segment estimation problem jointly and differentiably without assumptions on the model that produced the segment data, which is an improvement over several recent works with could also pose the problem jointly, but made such assumptions, such as van den Burg & Williams, 2020, and Arlot et al., 2019. \n\nThe authors show results on several tasks: modelling of COVID-19, change point detection on synthetic dataset from Arlot et al, 2019, and concept drift dataset. The results on change point detection and concept drift dataset are convincing, showing better quality of segmentation than previous approaches. The results on COVID-19 are, though, rather qualitative and serve more as an ablation study as there aren't many different results on this datasets.\n\nMy biggest issue is the absence of proper evaluation on harder tasks, where the estimation problem is solved with the help of a neural network, as opposed to something else, as in the previous 3 datasets.\nAuthors show results on speech segmentation without any comparison to other approaches except for random segmentation (with a comment that \"random segmentation is worse in 9932 out of 10000 trials (99.32%)\") in the \"eval-timit colab\", which is hardly a fair comparison). There is a number of baseline techniques and datasets for segmentation that the authors could compare to. For example, one way of extracting segmentation in OCR / Speech is by looking at logits for \"empty class\" coming from the decoder and it would be interesting to compare such segmentation with a task of segmentation + character recognition formulated in this framework. Another group of approaches, identified by the authors themselves, uses discrete latent space representation for segmentation, in the domain of Speech. Finally, in the domain of action segmentation  there are similar in nature approaches also predicting a differentiable segmentation, but without explicit parametrization, such as in this work (eg. [Fast Weakly Supervised Action Segmentation Using Mutual Consistency])\n\nOne other question is regarding section 5.3 and Fig. 6. It seems that increasing the number of segments up to 32 still produces improvements in accuracy, so I would be interested in seeing how the model behaves with even larger K. (I expect that starting at some value of K overfitting to small segments should start reducing the accuracy?)\n\nI believe paper could be strengthened by evaluation on harder tasks and comparison with other types of methods. That being said, I find the described approach valuable in and of itself, hence the rating.", "extra_scores": {}, "extra_text": {}}, {"review_id": "3A4vmY6958-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The proposed paper introduces a novel approach for the segmentation of sequences. The proposed method is based on two-sided power distributions (TSP) that are mathematically well-define and enable differentiability. The main goal of the method is to jointly optimize model parameters, including the segmentation function. The method is validated through experiments on modeling the spread of COVID-19 based on Poisson regression, change point detection, a classification model with concept drift (insect stream benchmark), and discrete representation learning (speech signal). \n\nOverall, I have the impression that this is in interesting paper that has most things going for it. Replacing a hard segmentation function with a soft differentiable warping function (two-sided power distributions) seems technically-sound and is an interesting novel solution to a difficult problem. The paper is mostly well-written and easy to follow. Furthermore, the experiments are well-defined and novel datasets (COVID, insect stream benchmark) were used to validate the effectiveness of the model. Therefore, I am leaning toward accepting this work to ICLR 2021. \n\nAdditional comments: \n\n- The abstract is somewhat difficult to comprehend and appears more cryptic than necessary. \n- In Section 3.2. it is not clear what is meant by levels 0 and 1. \n- Section 4: It is not clear what 'bogus mode' refers to.\n- To better understand the model in Figure 3 (and given the white space around the equations) it would be helpful to provide  labels for the introduced variables. \n- Please add details on whether the RKI data is publicly available. \n- Currently the paper does not discuss any limitations. To further understand the introduced model it would be helpful to highlight corner cases across the experiments in which the model does not perform well. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, a method to solve the segmentation problem by continuous optimization is proposed by using a soft differentiable warping function. The proposed method is theoretically sound, and interesting experiments such as the data analysis of covid19 are also presented. This is a good paper in terms of both theory and application.
Decision: Accept (Poster)