Detecting Change in Seasonal Pattern via Autoencoder and Temporal Regularization
Authors: Raphael Fettaya
Dor Bank
Rachel Lemberg
Linoy Barel
Venue:  (2020)
Keywords: Autoencoder
Change Point Detection
Timeseries

Abstract: Change-point detection problem consists of discovering abrupt property changes in the generation process of time-series. Most state-of-the-art models are optimizing the power of a kernel two-sample test, with only a few assumptions on the distribution of the data. Unfortunately, because they presume the samples are distributed i.i.d, they are not able to use information about the seasonality of a time-series. In this paper, we present a novel approach - ATR-CSPD allowing the detection of changes in the seasonal pattern of a time-series. Our method uses an autoencoder together with a temporal regularization, to learn the pattern of each seasonal cycle. Using low dimensional representation of the seasonal patterns, it is possible to accurately and efficiently estimate the existence of a change point using a clustering algorithm. Through experiments on artificial and real-world data sets, we demonstrate the usefulness of the proposed method for several applications.

Under review as a conference paper at ICLR 2020
DETECTING CHANGE IN SEASONAL PATTERN VIA AU- TOENCODER AND TEMPORAL REGULARIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Slange-point detection problem consists of discovering abrupt property changes in the generation process of time-series. Most otate-of-the-art models are opti- mizing the power of kernel two-sample test, with only a few assumptions on the distribution of the data. Unfortunately, because they presume the samples are distributed i.i.d., they are not able to use information about the scasonality of a time-series. In this paper, we present a novel approach - ATR-CSPD allowing the detection of changes in the seasonal pattern of time-series. Our method uses autoencoder together with a temporal regularization, to learn the pattern of each seasonal cycle. Using low dimensional representation of the seasonal patterns, it is possible to accurately and efficiently estimate the existence of a change point using a clustering algorithm. Through experiments on artificial and real-world data sets, we demonstrate the usefulness of the proposed method for several ap- plications.
INTRODUCTION
Time series data sequences of measurements time describing the behavior of systems. Time series analysis has become increasingly important in monitoring systems health and performance. As the system behavior changes over time due to external events and/or internal modifications, the problem of identifying the locations of these changes, referred to as Change Point Detection (CPD) has quickly drawn researchers attention. The CPD problem has been widely researched during the last three decades 44
and it has been applied to several fields such as financial market analysis, medicine, climate science as well as system monitoring. The first methods found in the literature for CPD compared probability distributions between two consecutive intervals in time-series, and alarmed if the difference became significant. Among them we find the cumulative sum algorithm (4) or the change finder for auto-regressive processes (18) Another line of research focuses on subspace identification (12), where the time series is modeled using linear state-space and change is identified using the model parameters.
18 13
6
9 16
Since all these methods make strong assumptions on the distributions, a need arises for more generic solutions and non parametric algorithms, such as direct density estimation methods. Unfortunately, these methods suffer from the curse of dimensionality (17) and are not applicable to real life prob- lems. To overcome this challenge, one possible solution is estimate the ratio of densities between two successive window without computing the densities themselves. This is achieved by going through the estimation of probability divergence metric such as Kullback-Leibler in (16) or the Person divergence (13). Such methods proved to be quite successful. Another line of research fo- cuses on Kernel two sample test (8), where the kernel trick is used evaluate mean discrepancy of two samples in Reproducing Kernel Hilbert Space. For example, Harchaoui et al. (10) introduced a test statistic using the maximum kernel fisher discriminant ratio. More recently, Chang et al. (G) proposed a way to learn an optimal kernel representation for CPD by using auxiliary generative model.
Nonetheless, although more general, these models still assume that the process is time independent. However, very often, a time-series follows a seasonal behavior. Seasonality is defined as the ten- dency of time-series to exhibit behavior that repeats itself every fixed period of time. The term season is used to represent the period of time before behavior begins to repeat itself. Detecting change in the seasonal pattern of time-series is critical for many applications such service mon-

---

Under review as a conference paper at ICLR 2020
itoring climate change detection 15) In cases, it requires totally different approach than regular CPD solutions. For example, Figure shows Fiswss the CPU utilization metric values recorded over period of six days for some server machine. An event occurs every day at 10AM, representing some background process that is important for the system. A forecasting system should adapt its predictions to take into consideration this event. If for some reason, this process
moved 4PM, the forecasting system is expected to detect this change and adjust the forecast values accordingly. Some information about the location of the peak in each period has be taken into account order to detect this kind of change.
Figure I: Example of change in process execution. On the first four days (blue section), the process running 10AM. During the two last days (orange section), it ran 4PM.
The regular algorithms presented in this section would fail detect such kind of change points. Indeed: (a) Existing parametric models for CPD compare the distribution between two windows by looking some statistics. Here, will not observe persistent statistical change, as the spike still occurs. (b) Kernel based methods assume that the samples are generated i.i.d (10, [3] 6). Hence, they will consider every seasonal spike anomaly instead of including them the model.
In this paper, we introduce a CPD variation for seasonal time series. The issue of seasonal CPD has also been addressed by Lund al. (14) where they developed test for periodic and auto correlated time series. However, this test is based on predefined statistics and focuses on median (level) change of the metric.
We present ATR-CSPD, a method which uses an Autencoder with Temporal Regularization for detecting Changes in Seasonal Pattern. Our contributions are the following:
In section introduce variation of the Change Point Detection (CPD) problem called Change in Seasonal Pattern Detection (CSPD) for seasonal time series, and explain why current solutions CPD are inefficient detecting them.
In section 3 we describe ATR-CSPD, an unsupervised approach that is designed to capture essential information of each period in a seasonal time series. This is achieved by applying a time dependant regularization to the model's loss. We explain then how to use this model for CPD.
Sections and present an extensive evaluation both generated and real-life data. This benchmark exhibits how ATR-CSPD manages to detect new types of change points, unde- tected by regular algorithms.
2 PROBLEM FORMULATION
In this section, we start by presenting the simplified formulation of the Change Point Detection problem. Then we will introduce a more elaborated formulation for the detection of change points seasonal metrics, and illustrate the difference with an example. The simplified formulation assumes a single generative function behind the time-series values, and independence between the obser- vations. Many common methods for detecting change points applied based on this simplified version. For example, kemel density methods are based on the analysis of the single underlying function that generates the observations before and after the change (13 6)
2

---

Under review as a conference paper at ICLR 2020
Definition 1. Change Point Detection (CPD):
Given a sequence of I I-dimensional observations {21. ..., T.....NN } for which Vi, 24 R. A change point to is point such that {z). - } are sampled i.i.d from a distribu- tion Fi, and
IN) are sampled i.i.d from the distribution F2 where F1 # F2.
However, for seasonal time-series the assumption that up to the change-point all samples are i.i.d does not hold, since seasonality creates dependencies between the samples and their index in the period (i.e their phase). In the extreme, it might be that each observation within period is drawn from an entirely different distribution. However, as we are targeting metrics that are generated by one origin system, a more plausible assumption would be that each data point x; generated by combination of generative function of the time series and another generative function of its phase. For seasonal time series with period size p. define each point x; as 2y where ý is its period number, & is its phase number, and i = j.p k. We denote single seasonal window of observations of size p by w, where wi 2/1 Lip. We can represent the original time series by grouping all its seasonal windows: {wi,... Wr,...,, wy E IRP.
Denote F as the generative function of the time series, {St} J as the phase-wise generative functions, and Jjkk Gj, where Gj S, F and @ can be an additive or multiplicative factor (7). In additive seasonal models, the metric is explained by a weighted sum of the seasonal components {Sk] / and the generating function F. In multiplicative model, the sum is replaced by multiplication. In our analysis and results we don't 't differentiate the two.
Definition 2. Change in Seasonal Pattern Detection (CSPD): change point in a seasonal pattern a period number jo such that V(k. < jo), Izh ~ Gg. and 3k, Ijok ~ Gz where G& + G.
The difference between the formulations can be demonstrated by the example displayed in Figure It is clear that the time-series displayed in the chart represents a system that has altered its behavior. However, when considering the classical CPD problem formulation, the chart does not fall under the definition of a time series containing a change point as the overall distribution did not change. Considering the CSPD formulation, the change of the seasonal distribution component of both S10AM and SaPM distribution functions are identified as a change point in the time series. This observation suggests the CSPD a generalization of the CPD problem. While CPD is centered around the cumulative values distribution parameters such as median and variance of the time series values, CSPD also focuses on the shape and proportions between the values observed each period eycle.
Remark: Both problems can be extended to multi-dimennional time series and are only presenting it in 1-dimension for simplicity.
AUTOENCODER WITH TEMPORAL REGULARIZATION
We introduce an algorithm that is able detect changes in the seasonal pattern of a time-series. We start by using an autoencoder to capture the main pattern of each period in the time-series. The aim to have close encoding (in terms of euclidean distance) for two periods that behaves similar, and different ones if there is an abrupt change between them. By having such representation we can detect if there has been change point by examining the euclidean distance between two adjacent encoded periods in the time series.
3.1 THE AUTOENCODER MODEL
Autoencoders are neural networks that attempt to copy its input to its output. It consists of an encoder function, that maps the input an encoded version, and decoder that performs the reconstruction. Here we are training an autoencoder to reconstruct fix-size windows of time-series. Let Φ; E Rd<P,, be the 7th window of size p in a ddddimensional time series, fo, Rdxp + Rdxy our encoder function, gog: Rdxq - dx the decoder function and n the total number of windows. In general autoencoder model, want minimize:
min 9
I2; - 9o, (fo, (2:)) + A(10111a + +162112)
(1)
3

---

Under review as a conference paper at ICLR 2020
81 and Bg are set of parameters that can be learn by gradient descent using back- prok--papaattion and E allows us to control the L2-norm of 01 and 02.
In ATR-CSPD regularization term is added to this loss function, which will contribute to the detection change points.
3.2 TEMPORAL REGULARIIZTIION
In order encourage the network generate similar low- ciw-dimensional representations, introduce a new term in equation (T)
The idea is to penalize the network for difference between the encoding of two consecutive periods. The resulting loss function is given in
2 (fo (2:)) X(I1 1a 1102112)
1 hella
01.02
We refer to the last term temporal regularization as it applies neighbours period in the time- series. Here E R allows us to control the strength of this regularization and h; So, (a:).
To understand its effect take the following examples. Figure saows one-dimensional, weekly seasonal, time-series. On we run two autoencoder models, the first one optimizing equation (T)
and the second one equation (2). We p = 288 meaning that we consider the period as daily (the metric is recorded every 5 minutes), and expect to observe changes in the weekends. The additional parameters are set to
0.00005, y 0.001 and = 18. We observe that, although the regular autoencoder doesn't it get rid of the major anomalies in the data (Figure 2b), the temporal regularized model creates a generic pattern for the weekdays and for the weekends (Figure 2cp. According to
this result, we can infer that the low dimensional representations are similar within the weekdays and
within the days of the weekends, and we can use clustering identify breakpoints. In Appendix C
show the results of a Principal Components Analysis (PCA) applied to the encodings generated by both algorithms, which confirms this hypothesis.
W
(a) Raw time-series
(b) Regular autoencoder (Eq)
(c) With regularization (Eq
a regular autoencoder model 2b and a temporal regularized version (2c). Even if it drops some anomalies, the regular autoencoder does not rid of the minor differences between different days. However, using temporal regularization, the patterns for the week days (blue and green sections) are very similar, as well as the one for the weekends (orange and red).
Figure 2: Given the time-series Zap.
3.3 LOCATING THE CHANGE POINTS
Once every window is mapped to an embedding in a reduced space, finding change points becomes much easier. We aim to find groups of similar windows, based on their location in the space. A change points will be detected if two consecutive points do not end up in the same partition.
To do that we choose use the well known k-means clustering algorithm (TI). In order to find the best number of clusters, and thus the number of change points, we use the silhouette score. It compares the mean pairwise distance of points the same cluster (a) with the mean distance of b-a
each points to the nearest cluster (b): max[a.b]
We k-means iteratively candidates number of change points, and select the one with the best silhouette score. the received score is larger than a specified threshold (which is a hyperparameter of the model), select the resulting partition, otherwise consider that there were changes.
4

---

Under review as a conference paper at ICLR 2020
4 EXPERIMENTS
In order to illustrate the difference between regular CPD algorithms and ATR-CSPD, we start by generating data containing different types of seasonal or non seasonal change points. Then we run some experiments on several real-life seasonal data sets. We present the results in the Smart meters London (3) data set, the NYC taxi data set (2) and on time-series taken from Azure monitoring. In the experiments,
assume that for seasonal time-series the length of the period is known (the inference of the season is outside the scope of this article).
4.1 NETWORK ARCHITECTURE
In all the experiments we use a similar network architecture. The encoder function fo, is a 3-layer feed-forward neural network. Each layer consists of linear function and a hyperbolic tangent function. Equation 33 shows how the layer output 2 is computed from its input æ. The decoder is 2-layer neural network, with similar activation function.
y = Wx+b 2
e +e
The shape of W in the layers determines whether it increases, decreases leaves unchanged the dimension of the output. In ATR-CSPD, we reduce the dimension during the encoding phase and increase it back when decoding. This way, only the main information for the reconstruction will be stored in the encoding.
The initial window is always of the size of one period. For example if we have a daily seasonality and the data recorded every 30 minutes, we will have window size of 48. Then divided successively by 4, 2 and again 2 in the encoding phase, and multiplied by 2 and 8 in the decoding layers. The architecture is displayed in Appendix
Depending on the experiment, we use learning rate that ranges from 0.005 to 0.05. The value of the parameter À in the loss function 0.00001.
set to 0.00005 or 0.000001 and y varies from 0.001 and
Note that the time-series are first scaled to range between and using min-max scaling.
4.2
EVALUATION ON GENERATED SET
4.2.1
SIMULATED SET WITH CHANGE POINT
For each category of change point, we generate 20 random time-series and keep track of the location of the change point inserted the data. For all the seasonal time-series we the period length to 288. The first type is regular change points from non seasonal time-series. They can be change the mean, the variance or both on white Gaussian noise without (category A), and with random anomalies (category B).
Then we generate time-series with seasonal spikes and white Gaussian noise and search for two different types of change points: change in the height of the spike (category C), and change in the position of the spike. (category D)
Finally, we consider seasonal time-series that alternate between a quiet state and active state, with higher values and higher noise. On them we insert the following kind of change: : A change in the active period height (category E), change in the quiet period height (category and change in the active period length (category G). We also generate 120 samples from those categories without changes in order to evaluate the false detection.
Samples for each category are drawn in Appendix A along with more details about the implemen- tation of the generating process.
4.2.2 RESULTS
We compare the results for ATR-CSPD with two non-parametric change point algorithm: KCpE introduced by Harchaoui and Capp 99, and RDR presented by Liu et al. (3). We choose use
5

---

Under review as a conference paper at ICLR 2020
regular gaussian kernel: (xxxx') ezp(-><la =1.)) The bandwidth parameters which required for KCpE were set according to the "median trick" (8. For the RDR model, we follow Li et al. by adjusting the bandwidth and the regularization parameter at each time step. Finally, KCpE on deseasonalized data. Thus means, that for the seasonal samples, we compute the mean for each period and remove it from their original values. This is common procedure for obtaining stationarity in seasonal time-series. We refer to this model as DS-KCpE.
Each model F; runs on a time-series z and returns of candidate change points 8 A change point to in 2, is detected by Fj if
A and 1t- t < 288.
(4)
Note that even if every model is able to detect multiple change points on time-series, our generated samples all have at most one.
The detection for each category is equal to the number of change points detected divided by the category size. The false positive rate for F; is the ratio in time-series without change on which F, found at least one CP.
The results are summarized in Table
Category
KCpF
ATR-CSPD
RDR
DS-KCpE
A
90%
40%
50%
90%
B
80%
0%
15%
80%
C
0%
100%
20%
0%
D
0%
90%
5%
25%
E
55%
75%
50%
55%
F
100%
95%
80%
100%
G
55%
80%
60%
55%
False positives
0.8%
0%
2.5%
0.8%
Table 1: Results on generated set
The results clearly show that regular CPD approaches fail to detect most changes in the seasonal pattern when it comes to seasonal spike. They also demonstrate that ATR-CSPD performs at least as well as classical algorithms on detecting change points in seasonal time-series. Indeed, in cate- gories C and D, the impact of the changes on the kernel mean estimate of the windows is minimal or nonexistent, which explains why KCpE and RDR hardly detect them. We can notice that using decomposition of the seasonal component helped DS-KCpE for category D, still the detection is far from ATR-CSPD A similar explanation can be derived for the next categories. Except for category F, the changes made only on minor section of the periods and the statistical impact is smaller.
It worth noticing that ATR-CSPD performs badly on categories and B. For very noisy gaussian data, since getting a minor decrease the MSE requires a high increase of the temporal regulariza- tion term, the autoencoder will create a change in the encodings and the detection will be bad. In other cases, where there are too much anomalies on one period, it decides to learn the anomalies decrease the MSE which might create a wrong detection of change point.
4.3 LONDON ELECTRICITY DATA SET
The data records the energy consumption of 5567 households in London between November 2011 and February 2014. For each time-series the consumption kWh/hh saved every 30 minutes. We assume that, in general, we will observe weekly scasonal pattern, with similar weekdays and different weekends. Of course this assumption is not always true, for example retired people will probably exhibit more monotonic week but the results will support this assumption.
First we preprocess each entry in the dataset by aggregating every 30 minutes of the week within the timeseries. Meaning that for specific timeseries, we retrieve all the Mondays 8:30 AM and take the mean. Doing for every recorded timestamp, gives us a new timeseries representing the average week for household.

---

Under review as a conference paper at ICLR 2020
Then run KCpE and ATR-CSPD this new set. As RDR is quite slow, and could not on this set. We say a model correctly detected a change detected changes only after Friday 00:00. Any other change is considered as false positive. In Table we present the precision and recall of the two models using the previous definitions. At that algorithm outperforms the baseline model. Figure 3 displays a few examples of unique detection of ATR-CSPD.
pretty similar precision level, we
Model
Precision
Recall
kCpE
68%
47%
ATR-CSPD
67%
54%
Table 2: ATR-CSPD and KCpE on the London electricity set
(a)
(b)
(c)
Figure 3: Electricity consumption of three households which ATR-CSPD alone found differ- ence on the weekend. In all of them, is not reflected by a drastic change in the mean. Top charts: electricity consumption. Bottom charts: the mean consumption of each day. In orange: periods recognized by ATR-CSPD as different
We can observe that the weekends, in those cases, is characterized by different shape whether the level (mean) changes seem to occur at different places in the time-series. In Figure 33 we can easily distinguish the working hours of the weekdays, whether on the weekend no drop is observed. Looking at B. we notice that peak of activity occurs every day. On Sundays, however, it happens 12:00 PM instead of 4:00 PM days and ATR-CSPD spotted the change. Finally in [3p. we can observe that our model detected change in the pattern on Sundays that did not drastically impact the mean.
4.4 NYC TAXI DATASET
The city of New York provides every month dataset containing lot of information about taxi trips (2). Taken from the kaggle Numenta Anomaly Benchmark repository (I), the current dataset consists of aggregation of the total number of taxi passengers into 30 minutes buckets between July 2014 4 and February 2015.
The results of ATR-CSPD, compared with the two baseline models introduced in section 4, exhibit well the differences between regular Change Points and Changes in Seasonal Patterns. Looking at Figure 4 we, fact, observe that although KCpE and RDR detects many level change, whether STR-CSPD identifies only seasons in which the regular weekly pattern is broken. Looking at the dates of Figure 4p, one can notice that the weeks match respectively: the 4th of July, Thanksgiving and Christmas holidays. Being able to identify non-regular seasons and to treat them separately could drastically benefit a forecasting algorithm.
4.5 AZURE MONITOR DATA
Azure Dynamic Threshold (DT) Monitor is service provided in the Azure cloud for monitoring vast range of services and usage metrics. For this purpose, DT analyzes the past observable history of metric values and creates baseline that describes the normal behavior expected for this metric. later uses this baseline as a forecasting method. We used the training stage (analysis of past data) and run, before, KCpE, ATR-CSPD and RDR try detect change point that happened in

---

Under review as a conference paper at ICLR 2020
(a) KCpF
(b) RDR
(c) ATR-CSPD
Figure 4: KCpE. RDR and ATR-CSPD on NYC taxi dataset. Although KCpE (a) and RDR (b) are looking for level change, ATR-CSPD (c) finds only changes the pattern. They correspond to the weeks of the 4th of July, Thanksgiving and Christmas holidays respectively.
those time series. We selected random 958 daily seasonal time series for this purpose. The values recorded either every 5-15-30 60 minutes, and we total record of 10 days.
As there is not any label for this data, we will focus on the differences the change points detected. We tune the three model to find change points in 25% of the time-series. Among the changes found by ATR-CSPD, 40% are not reported by the others. We present in Figure 5 few examples of changes only detected by our model.
(a) Change in spike time
(b) Appearance of seasonal pattern
(c) Change in seasonal pattern
Figure 5: Three types of seasonal changes only detected by ATR-CSPD
In 5 blue spikes occurs between 2:40 and 2:45, in the green section, for some reasons it occurs
1:35, an hour before usually. Finally in the orange section the spikes all occurs between 0:55 and
1:05. While monitoring the production system detecting such kind of update in process could save
false alarms while still allowing quick detection of anomalies.
In 5p. seasonal pattern appears the end of the time-series and ATR-CSPD managed find the change points.
Finally 5t. we can notice that even a slight change in complex seasonal pattern can be detected as long it is repeated enough time.
5 CONCLUSION
We propose ATR-CSPD, new deep learning baasing-based algorithm that detects changes in seasonal pat- tern of timeseries. The model combines an autoencoder network with a clustering algorithm, and able to identify changes from different real- world applications. Evaluations on multiple benchmark datasets illustrate the difference between our new approach and existing CPD methods. They also demonstrate that ATR-CSPP outperforms other models in detecting specific types of change points and could used to improve the efficiency time-series forecasting in many applications.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
[1] Numenta httph//wwwnn///ooo/////////////d oaaaeiaiiaaaaaaaaaaaaaaaaieeeeen (NAB,
des dec.gpacesscpb...eeeeeeeeeeeeeer 2019, Accessed: 2019-09-
23.
[2] Nyc open data.
2018- Yellow Taxi wwip-Data/t23m 2019 20, 2000s 2019-09923.
2019.
[3] Smart smart-meters-in--oooe
meters in
london.
htttps:/www... www. www.kkaggg.......aaaeeee
2019. Accessed: 2019-09-23.
[4] Michèle Basseville, Igor V Nikiforov, et al. Detection of abrupt changes: theory and applica- tion, volume 104. Prentice Hall Englewood Cliffs, 1993.
[5] Claudie Beaulieu, Jie Chen, and Jorge L Sarmiento. Change-point analysis as a tool to detect abrupt climate variations. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 370(1962):1228-133 1249, 2012.
[6] Wei- Wei-Cheng Chang, Chun-Liang Li, Yiming Yang, and Barnabás Póczos. Kernel change-pon -oinntt detection with auxiliary deep generative models. arXiv preprint arXiv:1901.06077, 2019.
[7] Eric Ghysels. Denise Osborn, and Thomas Sargent. The econometrie analysis of seasonal time series. Cambridge University Press, 2001.
[8] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(M27):723-773, 2012.
[9] Zaid Harchaoui and Olivier Cappé. Retrospective mutiple change-point estimation with ker- nels. In 2007 IEEE/SP 14th Workshop on Statistical Signal Processing, pages 768-772. IEEE, 2007.
[10] Zaïd Harchaoui, Eric Moulines, and Francis R Bach. Kernll change-point analysis. In Ad- vances in neural information processing systems, pages 609-616, 2009.
[11] John Hartigan and Manchek Wong. Algorithm as 136: k-means clustering algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1): 100-108, 1979.
[12] Yoshinobu Kawahara, Takehisa Yairi, and Kazuo Machida. Change-poin detection in time- series data based on subspace identification. Seventh IEEE International Conference on Data Mining (ICDM 2007), pages 559-564. IEEE, 2007.
[13] Song Liu, Makoto Yamada, Nigel Collier, and Masashi Sugiyama. Change-point detection in time-series data by relative density-ratio estimation. Neural Networks, 43:72-83, 2013.
[14] Robert Lund, Xiaolan L Wang, Qi Qi Lu, Jaxk Reeves, Colin Gallagher, and Yang Feng- Changepoint detection in periodic and autocorrelated time series. Journal of Climate, 10720):518--5190, 2007.
[15] Vasundhara Puttagunta and Konstantinos Kalpakis. Adaptive methods for activity monitoring of streaming data. In ICMLA, volume 2, pages 197-203, 2002.
[16] Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul V Buenau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application to covariate shift adaptation. In Advances in neural information processing systems, pages 1433-1440, 2008.
[17] Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
[18] Kenji Yamanishi, Jun-Ichi Takeuchi, Graham Williams, and Peter Milne. On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms. Data Mining and Knowledge Discovery, 833):755300, 2004.

---

Under review as a conference paper at ICLR 2020
A GENERATED DATA SAMPLES
A.1 PLOTS
(a) Category B
(b) Category C
(c) Category D
(d) Category E
(c) Category F
(f) Category
Figure 6: Samples from the generated dataset
A.2 IMPLEMENTATION DETAILS
In this section, we explain, category by category, how samples in section 4.2 are generated. Category A: Samples are following gaussian distribution with a mean between and 10 and standard deviation between and 10. Then we randomly choose whether a change will occur in the mean, the standard deviation or both. Finally, again at random, we define the parameters of after the change.
Category We use the same process as category A but we add some random spikes (anomalies). The spikes generated with at random frequency, there will be between I 60 spikes in the time- series. Their height is also generated randomly, from 2 to 10 times the max value of the gaussian samples. Same for their length, between 5 and 15 points. At the end, add some gaussian centered noise with a standard deviation that depends on its height.
Category C: We generate some regular gaussian samples with random mean and variance. Then we add the spikes as previously but make them repeat every 288 points. For the last 4 spikes, we increase the height by a random factor (between 1.5 and 2).
Category D: The process is similar to the generation of samples of category C, but we create random change in the periodic spike time and not in the height.
Category E: First we split randomly the period into three parts: quiet part, an active part and quiet part again. Then we generate some gaussian samples for the quiet part, with a random mean and standard deviation that determined by this mean. We do the same for the active part but make sure the mean is bigger. Finally, at a specific point in time, we randomly increase the mean of the active part.
Category We do the same as category E, but we randomly increase the mean of the quiet part and make sure it still stays lower than the active Category G: Again, the same process as category E, but we do not modify the mean, we randomly change the split to make the active part longer.
10

---

Under review as a conference paper at ICLR 2020
B NETWORK ARCHITECTURE
300x1
INITIAL WINDOW
75x1
ENCODING
37x1
18x1
CODE
36x1
DECODING
300x1
RECONSTRUCTED WINDOW
Figure Network architecture for a window size of 300
C PCA ON THE ENCODINGS
000
600-
434
600
600
(a) Regular autoencoder (Eq
(b) With regularization (Eq
Figure 8: Results of a PCA applied to the encoding of Figure 2b and Figure 2c
11


Reviews:
[{"review_id": "Skgh0uOCKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "This paper proposed a new model for change point detection, using autoencoders with temporal regularization, in order to impose temporal smoothness in the latent codes. To motivate this new model, the authors also provided a toy example to show how the abnormality in a time series is removed in the reconstructed signal using this additional regularization term. Experimental results were provided to support the proposed new model.\n\nI have a few concerns about some technical details of the paper, as explained below:\n1) The paper motivated the new model with difficulty in detecting change points in seasonal time series. However, the proposed model with the temporal regularization is not directly related to the seasonality or periodicity of the input data. It is more related to the smoothness of the latent code. Hence it seems to me that there is a slight disconnection between the motivation and the actually proposed model. It would be nice if the authors can provide more intuitive explanation on why the temporal regularization can handle well change point detection in seasonal temporal series.\n\n2) The temporal regularization proposed in this paper is very similar to the total variation penalty used extensively in statistics and image processing. It would be nice if the authors can make a connection between the two. For example:\nHarchaoui, Z., & Lévy-Leduc, C. (2010). Multiple change-point estimation with a total variation penalty. Journal of the American Statistical Association, 105(492), 1480-1493.\nBeck, A., & Teboulle, M. (2009). Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE transactions on image processing, 18(11), 2419-2434.\n\n3) In the experimental section 4.3, the authors mentioned that \"In Table 2, ... we can see that our algorithm outperforms the baseline model\". However, in Table 2 the precision of the proposed model (67%) is lower than the baseline model (68%). Hence it is not obvious to the reader that the proposed model outperforms the baseline. \n\n4) In the appendix B, the authors explained the architecture of the autoencoder used in the paper. I wonder why the authors chose an asymmetric structure between the encoder and decoder, as most autoencoders have a symmetric structure.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkeXgdrT9S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 investigates the important problem of detecting changes in seasonal patterns, and proposes ATR-CSPD to learn a low-dimensional representation of the seasonal pattern and then detects changes with clustering-based approaches.  ATR-CSPD achieves improved results on part of synthetic and real-world datasets.\n\nThe paper may not have enough contribution to be accepted due to the following key concerns:\n  - The proposed model is not quite novel, and the design needs more justification.\n  - The empirical results are not strong enough to show the effectiveness of ATR-CSPD. \n\n# Model design\n\nThe idea of using auto-encoder with temporal smoothing to learn a low-dimensional representation of time-series need more justification.\n- What are the main intuitions of using an auto-encoder? e.g., removing anomaly or denoising. Why will it be easier for the model to detect the changes on the reconstructed time-series?\n- The temporal smoothing makes adjacent periods similar to each other. However, this may have side effects like low recall.  For example, in Figure 2(a), the pattern in Aug 17th (Sat) and that in Aug 18th(Sun) can possibly be different (i.e., a change in seasonal pattern), while the difference is smoothed out by the temporal regularization.  Is the model sensitive to the regularization, e.g., $\\lambda$? Why L1 regularization instead of L2 is used?  It will be helpful to provide more justification/intuition of the model design.\n- Why only the smoothness regularization between adjacent seasons is used? Other potential regularization includes penalizing the difference between the same phase in different seasons. \n\n# Assumption and limitation\nThe proposed method requires the seasonal period being provided, and also requires a large number of hyperparameters being specified, e.g., 1) the threshold of silhouette score, 2) the hidden representation dimension $q$, 3) the regularization coefficient, 4) $\\gamma, \\lambda$,  5) hyperparameters for constructing the encoder/decoder and 6) training the models.  \n\nRegarding the threshold of the silhouette score in the clustering step, is setting this hyperparameter easier than the number of clusters, i.e., the number of changing points?  Is ATR-CSPD sensitive to this parameter?  How this hyperparameter is tuned? Having too many hyperparameters (that are potentially non-trivial to set/tune) may make the proposed method less robust. \n\n# Experimental results: \nAccording to the results in Table 1, ATR-CSPD is mainly better at detecting Category C/D/E change points, which are mainly caused by changes of height/position of the spike.  However, it performs either similarly or worse than the other baselines on other tasks.  Besides, the lack of ground-truth data on NYC Taxi dataset and the Azure monitor dataset makes it hard to evaluate the effectiveness of the proposed algorithm. Moreover, only uni-variate time series tasks are investigated.  These issues may limit the application domain of the proposed algorithm. \n\n# Minor notation and presentation issues\n- In Definition 2, does CSPD assume F is the same in $G_k$ and $G'_k$? If not, CPD might be a subset of CSPD. \n\n- In Equation 1 and 2, $n$ is used to represent the number of observations, while in Definition 1, capital $N$ is used to represent the same concept.\n\n- In Figure 2, it might be easier to understand if all the weekdays are drawn using the same color (blue or green) and all the weekends are also drawn in the same color (yellow or red).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyerFBLVtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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: The paper raises an alarm that state-of-the art change-point detection methods in the ML literature do not handle important practical aspects arising in time-series modeling, namely seasonality. Indeed, methods designed to detect changing distribution under an i.i.d. setting can fail dramatically when the assumption is violated, when the change happens in the seasonal component.  The paper proposes to use an auto-encoder to find the \"main pattern\" within each seasonal window, and to use total variation penalty (l1-norm on the change) of the hidden state in the auto-encoder to encourage a smooth state-sequence which allow breaks.  They use k-means clustering to partition data-points, and detect a change-point if two consequent hidden states don't end up in the same cluster. \n\nWhile the proposal is sensible and the paper is reasonably readable, I find the paper lacking in several respects, and recommend to reject it. My main concerns are \n(a) novelty: despite the claims in the paper -- the importance of seasonality is well known and appreciated in time-series literature, and the proposal to look for changes in seasonality is fairly obvious when dealing with practical time-series. I would suggest to do a comprehensive literature search and re-evaluate the novelty of the paper. \nI believe that recent ML papers e.g. kernel two-sample tests and such, focus on the i.i.d. setting and ignore seasonality (and other messy aspects of practical TS) -- as it is the more challenging statistical problem.\n(b) The paper considers a setting where the time-series consists of a seasonal component and an i.i.d. component (combined additively or multiplicatively). It doesn't attempt to model any kind of stochastic dynamics -- e.g. at least a simple auto-regressive model instead of iid, and non-stationarity (trends) in the time-series. So despite aiming to look at practical time-series, the paper still considers a simplified model.\n(c) The paper's presentation is often sloppy in language use, assumptions, mathematical details, and simulations and needs to be significantly improved to be considered for ICLR (or related ML conferences). \n\nDetailed comments: \na) The references are severely lacking. There is an extensive literature in modeling time-series with seasonality and classical methods such as SARIMA (seasonal ARIMA), or exponential smoothing can track the evolution and changes in seasonal components. Various nonlinear DL-approaches to TS with seasonality have also started to appear. Once time-series is decomposed into trend, seasonal and stochastic part (using any linear or nonlinear or deep model), it is straightforward to apply anomaly detection algorithms to each component separately. Please take a look at e.g. https://anomaly.io/blog/index.html (from salesforce.com), to see practical change-point or anomaly detection in time-series in practice which does pay attention to seasonality. Also papers by Rob Hyndman pay close attention to seasonality, see e.g. https://otexts.com/fpp2/. \n\"Changepoint Detection in Periodic and Autocorrelated Time Series\", https://journals.ametsoc.org/doi/full/10.1175/JCLI4291.1\nhttps://cran.r-project.org/web/packages/trend/vignettes/trend.pdf  (which has a section on seasonal change-point detection)\nHarvey, Koopman, Penzer, \"Messy Time Series: A Unified approach\", Adv. in Econometrics, Vol. 13, pp. 103-143., https://www.stat.berkeley.edu/~brill/Stat248/messyts.pdf\nPerhaps there's relatively less focus on these practical details of change-point detection in recent ML literature and the focus is on the stochastic component, as it is the most challenging for prediction. The use of l1-norm of differences in time-series to detect changes is a natural idea, and has been suggested many papers e.g.in: http://eeweb.poly.edu/iselesni/lecture_notes/TV_filtering.pdf, \n\"Time Series Clustering using the Total Variation Distance\", \nStephen Boyd's trend filtering, https://web.stanford.edu/~boyd/papers/pdf/l1_trend_filter.pdf .\n\nWhile I am not aware of a specific prior work on auto-encoder with temporal smoothness for CPD, most of the main ideas are well known, and in my view the contribution is very limited in novelty.\n\nb) You're ignoring any memory or dynamics in the stochastic component of the time-series -- e.g. allowing something like a simple AR model rather than iid would be a good step. Detecting changes in the dynamics or correlation structure (temporal or cross-sectional) would make the paper more interesting.  Something closer to switching linear dynamical systems, see for example https://arxiv.org/abs/1610.08466. \n\nc) The presentation has many issues in language / math / simulations and needs to be improved:\n\n1. The setting is not described clearly / formally -- are you trying to detect change-points online or offline, what assumptions are you making on the segments after removing seasonality -- are these just iid / stationary, can they include trends, outliers, e.t.c.\n2. Baseline methods for detecting seasonal patterns are naive -- clearly applying methods that are not aware of seasonality will fail when there is strong seasonal components. There is one basic attempt at removing the seasonal component by averaging, and applying iid kernel CPD methods -- where it does help.  I believe doing something a bit more realistic (like doing a seasonal decomposition) will make the baselines much stronger. \n3. Citation format is inconsistent with ICLR.  \n4. ATR-CSPD is undefined in the abstract. \n5. Intro:  i, j, k notation inconsistent -- you seem to use i both for i = j*p + k, and also to refer to window id. \n6. What is a \"generative function\" of time-series? Do you mean the pdf / cdf? What do you mean by a product of generative functions (which is additive or multiplicative), do you mean adding / taking products of random variables coming from independent distributions? What do you mean that you do not differentiate between additive / multiplicative? Do you claim to handle both within the same model?\n7. Definition 2 -- do you look for x_jo,k ~ Gk',  or x_j for j> j0 ~ Gk'? \n8. You claim a multi-variate extension is easy -- but is it? How would you tackle e.g. changes in correlation structure?\n9. \"Autoencoders attempt to copy input to output\" - isn't this trivial by using an identity function? You should mention some compression / bottleneck as well. \n10. How do you optimize the total-variation (l1-norm) penalty in your formulation? Just throw it into SGD in keras?\n11.  The discussion in 3.2. is confusing -- you talk about weekly series, but use daily-seasonality, however you then describe detecting weekdays vs. weekends? How can you associate separate weekends without a weakly seasonal model? \n12. London electricity data-set -- why do you average all weeks within the time-series to find average customer week? This was very surprising. Don't you loose most of the interesting anomaly data this way?\n13. Figures are not explained well. While there's nice use of color -- it's often hard to understand what is the description pointing at. \n\ntypos: Person -> Pearson,  Autencoder -> Autoencoder, and many others. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1lt_1QroB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "I am quite disappointed with the presentation and technical quality of the paper. \n\nThere are numerous grammatical errors that make the reading unpleasant. The mathematical notations are also inconsistent throughout different places in the paper.\n\nThe extensive literature of modelling time series with seasonality trends, both in the statistics and the machine learning community, is severely under-represented in the motivations and related works. Models like SARIMA have no mention in the paper. \n\nThe temporal regularization imposed in section 3.2, coupled with an autoencoder, does not seem very different from the state-space models and their more complex and recent variants that use multi-layered networks (a google search will provide plenty references).  \n\nThe experiments, with many of the useful baselines missing, are equally unimpressive. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes ATR-CSPD, which learns a low-dimensional representation of seasonal pattern, for detecting changes with clustering-based approaches. 

While ATR-CSPD is simple and intuitive, it lacks novel contribution in methodology. It is unclear how it is different from existing approaches. The evaluation and the writing could be improved significantly. 

In short, the paper is not ready for publication. We hope the reviews can help improve the paper for a strong submission in the future. 
Decision: Reject