Change Point Detection via Multivariate Singular Spectrum Analysis
Authors: Arwa Alanqary
Abdullah Omar Alomar
Devavrat Shah
Venue: NeurIPS 2021 Poster (2021)
Keywords: Change point detection
time series
CUSUM

Abstract: The objective of change point detection (CPD) is to detect significant and abrupt changes in the dynamics of the underlying system of interest through multivariate time series observations. In this work, we develop and analyze an algorithm for CPD that is inspired by a variant of the classical singular spectrum analysis (SSA) approach for time series by combining it with the classical cumulative sum (CUSUM) statistic from sequential hypothesis testing. In particular, we model the underlying dynamics of multivariate time series observations through the spatio-temporal model introduced recently in the multivariate SSA (mSSA) literature. The change point in such a setting corresponds to a change in the underlying spatio-temporal model. As the primary contributions of this work, we develop an algorithm based on CUSUM-statistic to detect such change points in an online fashion. We extend the analysis of CUSUM statistics, traditionally done for the setting of independent observations, to the dependent setting of (multivariate) time series under the spatio-temporal model. Specifically, for a given parameter $h > 0$, our method achieves the following desirable trade-off: when a change happens, it detects it within $O(h)$ time delay on average, while in the absence of change, it does not declare false detection for at least $\exp(\Omega(h))$ time length on average. We conduct empirical experiments using benchmark and synthetic datasets. We find that the proposed method performs competitively or outperforms the state-of-the-art change point detection methods across datasets. 

Change Point Detection via Multivariate Singular Spectrum Analysis
Arwa Alanqary
Abdullah Alomar EECS MIT aalomar@mit.edu
Devavrat Shah EECS MIT devavrat@mit.edd
Computational Science and Engineering MIT alangaryGmit.edd edu
Abstract
The objective of change point detection (CPD) detect significant and abrupt changes in the dynamics of the underlying system of interest through multivariate time series observations. In this work, we develop and analyze algorithm for CPD that inspired by variant of the classical singular spectrum analysis (SSA) approach for time series by combining it with the classical cumulative sum (CUSUM) statistic from sequential hy- pothesis testing. In particular, we model the underlying dynamics of multivariate time se- ries observations through the spatio-tempora model introduced recently in the multivari- ate SSA (mSSA) literature. The change point in such setting corresponds to a change in the underlying spatio-temporal model. As the primary contributions of this work, we de- velop an algorithm based on CUSUM-statises to detect such change points in an online fashion. extend the analysis of CUSUM statistics, traditionally done for the setting independent observations, to the dependent setting of (multivariate) time series under the spatio-temporal model. Specifically, for a given parameter > O, our method achieves the following desirable trade-off:: when change happens, it detects it within O(h) time delay on average, while the absence change, it does not declare false detection for at least ex)) time length average. We conduct empirical experiments using benchmark and synthetic datasets. We find that the proposed method performs competi- tively outperforms the state-of-the-art change point detection methods across datasets.
Introduction
The task of change point detection (CPD) is concerned with detecting significant changes in the temporal evolution a system from noisy observations. This task has attracted considerable attention in the statistics and machine learning communities it has broad range of applications including quality control (5). climate research
[5] and speech recognition 36 This interest resulted many methods and algorithms-
we refer
3 for thorough review.
Despite the relatively simple setup of the CPD problem, different variations the problem have been studied and analyzed. We contrast two general settings characterized by the assumptions the data generating process. The first is the classical view that aims to detect distribution changes from independent and identically distributed (i.id.) observations, cf. [34] and more recently 23). The second deals with the more intricate time series dynamics by assuming the data to dependent and following specific temporal structure. Therein, the aim is to detect changes in this temporal structure of the observations. Some of the time series models considered include auto-regressive models
and state-space models (20]
An important model comes from the singular spectrum analysis (SSA) literature, where the data is assumed to follow an underlying function associated with a low-dimensional subspace. This time series model has inspired algorithms for different inference tasks in time series, including imputation, forecasting, and CPD B
The key idea behind using SSA for CPD is that the subspace spanned by the columns the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

Hankel matrix constructed from an initial subsequence of the time series is approximately equivalent to the one spanned by the later subsequences of the time series. The theoretical analysis of this algorithm focused primarily on the probability of error in the asymptotic setting where the signal and noise are assumed to be separable. However, previous work on SSA for CPD does not provide finite-sample analysis on any metric on interest in CPD. Further, its extension to the case of multivariate time series (multiple SSA or mSSA) lacks theoretical understanding, despite being empirically effective M. In this work, we consider variant of mSSA proposed and analyzed in M for the tasks of imputation and forecasting. We extend the use of this mSSA variant to devise an algorithm for CPD.
Another important distinction between CPD methods lies in whether the method is online versus offline. In the offline setting, the dataset is fixed and the detection is made retrospectively based on the knowledge of the entire dataset. In such settings, only the accuracy of the detection is of concern. In contrast, in the online setting, the data arrives sequentially and a decision must be made as quickly as possible. addition to the detection accuracy, the delay in making the detection (i.e. the number of data points observed after the change until is detected) is another important metric in the online setting.
A common overarching framework for the online CPD problem extends from sequential hypothesis testing, where the problem is formulated as binary hypothesis test that is applied sequentially as new data comes in 40. This framework provides a way to evaluate the performance of online CPD methods in terms of the trade-off between false alarm rate and detection delay. The classical setting of this framework uses parametric models and forms likelihood ratio-bases test statistics. In more recent work, this framework has been utilized with different test statistics. For example. tests using statistics based on the kernel Fisher discriminant ratio [61 maximum mean discrepancy [25], and subspace distance [19 were proposed. However, rigorously characterizing the trade-off between false alarm rate and detection delay for time
series is absent in the literature.
In this work, we are motivated to fill the gap in literature by providing an online method for CPD for the setting of multivariate time series data (not i.ddd) to detect change points with provable performance guarantees and desirable empirical performance.
Summary of contributions. Below, we summarize the main contributions of this work.
1. We introduce an expressive and posit the question of detection as a change in these dynamics.
model as described in Section 2.] to model the dynamics
2. We develop a variant of the SSA algorithm for online change point detection in multivariate time series. In particular, we propose an algorithm that utilizes the owwddimensional structure of the time series to construct cumulative sum (CUSUM) statistic (a la (34) based on subspace distance. We refer to Section for a full description of the proposed algorithm.
3. We analyze the performance of this algorithm in terms of the average running length (ARL), common metric used in CUSUM tests to measure both the delay in detection and the average running time until false alarm. Our main result shows that in the case of no change, the expected running length is exponential in the selected threshold (Theorem 4.1. While in the presence of change, the expected
detection delay is linear in the threshold (Theorem 4.2 The results are consistent with the behavior of the CUSUM tests in the i.i.d. case.
4. We conduct comparative empirical experiments against -fate-of-the--at change point detection methods we provide a summary that suggests that our method is at least
using benchmark datasets. In Table [
as good, if not better than, state-of-art methods (SOTA) across datasets.
Related work. Due to space constraints, we provide an overview of related topics in Appendix A
Table 1: The Fi-score improvement our algorithm achieves compared to SOTA methods. See section for details.
Benchmark Data Improvement over SOTA
Synthetic Data
Improvement over SOTA
Beedance 10.4%
Energy 8.2%
Hasc 7.6%
Mean 14.1%
Occupancy
65.2%
Mixed 51.4%
Yahoo
0.6%
Frequency
36.1%
2 Problem Setup
We consider the discrete time setting where for each time index 1 E (1...T) we observe a multivariate time series X(t) = (f(.))...xx((() RR.V. For each n [N], we denote the n-th latent time series by
2

---

fn:Zt RR, such that at each timestep E (T), the observations take the form fxx where (t) is the per-step noise modeled as mean zero ii.d. random variable. We define the latent multivariate time series as f: R.V such that ((1) = [Ai (()))((((())) That is, the observation X()) takes the form
(() = +(()+))))))
(1)
where e(()= fei (().....e,(()) We note that although the additive noise en (1) is i..dd, the latent time series (()) can have a complex dependence structure across both and n,, see Section 2.1
Our objective is to detect changes in the latent time series f(t) as quickly as possible. Precisely, our goal detect a change point r such that
(o(())((1) ifl<T ( = (0())) ift2T.
where fo.f: : - RR and fo(1) * fz (t). In this setting, treat the change point unknown deterministic quantity. We frame this CPD problem as sequential hypothesis test where at each time t one of two hypotheses is accepted
Ho: (()
H1: E (f)
Let H(t) - (0.1) be the indicator random variable that indicates whether not the null hypothesis rejected at time We then estimate the change point 7 as
= (1]
Ideally, we wish to have T2, r, but also f- T to be small.
2.1 Time Series Model
There are multiple settings for the CPD problem characterized by the probabilistic structure of the observations. In this work, we consider the spatio-temporal factor model for multivariate time series introduced in [.]. which captures wide variety of time series dynamics. Next, we describe the model in detail. The spatio-temporal factor model requires the underlying latent multivariate time series to satisfy two properties. The first property captures the "spatial" structure, i.c.. the structure across the N time series (Property 2.1 and the second property captures the "temporal" structure (Property 2.2
Property 2.1 (Spatial structure). There exist R E N, where 1 I R & min(N,T), W, 7+ - R. and Onr ER Vr R ne [N], such that for any n [N], tE fttt== Car (t),,, where (anrlST. [W) <Tw w for constants Ta,, Tw 00
Property 2.1 implies that there are R "fundamental" time series, and each latent time series (x(+) Vn [N] be obtained through weighted combination of these R times series. To capture the temporal structure, additional assumptions are imposed on these fundamental time series W,(-) Vr E [R]. To do so, we first introduce the Page matrix representation of time series.
Definition 2.1 (Page Matrix). Given time series f: zz - R. its Page matrix representation over T observations with parameter 1 < ILST is given by the matrix Z Lx//LL with Zij = ((i+(i-))x for iE [T), j [[T/L]]]
Property 2.2 (Temporal structure). For each r [R] and for any T> T>1,1<L<T, let Z/p be RT/L/
Page Matrix associated with time series W,((), LE [T]. Then, the rank of Z is at most G for any choice S.
Property 2.2 imposes particular temporal structure in the time series W. W-(-),rell [R)) While seemingly restrictive at first, has been shown in the SSA literature that many standard functions that model time series dynamics satisfy this property. In particular, the Page matrix representation of any finite sum of products of harmonics, low-degree polynomials, and exponential functions low-rank and satisfies Property 2.2 (refer to Proposition 2.1 in II). These functions can capture rich class of time series dynamics which are typi- cally modeled by three components: stationarity, periodicity, and trend. Periodicity is modeled as harmonies and trend as polynomials; the mixture of both are instances of this model. The inclusion of stationarity in this
3

---

(0)
4
40) 5(3) /16)
.07)
MD MC++
M1 Su +11
-37-1
M0 MC++
40) (20))) ((3) (,4)
g00
1(2) fil ... 1/7
(() RUL 1)
662)
BxT -1+
:
3,073
(11 (,02) (,3) 5,00 ... 400
Figure 1: A depiction the stacked Page matrix of the multivariate time series f(t).
model can be understood by considering the spectral representation of stationary processes (refer to Property 4.1 in (9), which states that any sample-path of a stationary process can he decomposed into a sum of har- monics. Therefore, finite sum of harmonics provides good model representation for stationary processes.
For a given 1 ISLST, let z) E E [T/1] denote the Page matrix induced by the n-th latent time series ft)()) Vn [M]. Further, consider the stacked Page matrix Zr e R (x((/L)) obtained by column-wis
concatenation of the Page matrices /
Z(N) (See Figure Specifically,
Zr /
(1)
2)
(4)
Proposition 2.1 (Proposition 2.2 (1) establishes that under the spatio-tempont factor model satisfying
Properties and 2.2 the stacked Page matrix is low-rank. We refer to [1 for the proof of this property.
Proposition 2.1 (Proposition 2.2 in (]) Let Properties 2.7 a222222 hold. Then for any S LST, the rank of of for n E [N] is at most RxG. Moreover, the rank of the stacked Page matrix Ze is also at most RxG.
2.2 Changes in the Spatio-Temporal Factor Model
In this section, we give characterization of the change points in view of the spatio-temporal model described in Section 2.1 Let us consider the following interpretation of Proposition 2. I for multivariate time series f() that satisfies Properties and 2.2] and for a sufficiently large L and number of observations T, the columns of its stacked Page matrix span the same linear subspace of R.L independently of T. To formalize the notion of sufficiently large I. and T, introduce the definition of the order of the time series. Definition 2.2 (Order of the time series). Given a multivariate time series Zz IRR we define its order as the integer k 0 such that for all LZk k and T such that N [T/L] 2 k, the stacked Page matrix representation of the time series with parameter L over T observations Ze E IR [X/LL has rank k.
Proposition 2.1 suggests that time series that follows Properties 2.1 and 2.2 has a finite order & R.x G. Further, any L, T that satisfy 22 k, N x [T/L] 2 k. are sufficient for this to hold. In licu of the above, we can characterize changes in the latent time series using the distance from the subspace spanned by the columns of the stacked Page matrix Ze. Before we do so, we introduce appropriate notations and definitions. Definition 2.3 (L-lagged vectors). Given time series ʃ Z+ + RR. and a lag parameter L 1, the L-lagged vector af time E (I.g...TT} is given by [(1-11 [()=)++ [[][[[++1]] 1)..... ([)) ERR
For a multivariate time series f(t), we define the L-lagged matrix at time E [L,.., as the column-wise concatenation of the L-lagged vectors (1-1++1:1) for n [N]. Specifically,
f(t-L+1: (1-
fN(t- [(1--++1:()
(5)
We analogously denote the L-lagged observation matrix at time by ((t-L+1:te Let (f(t-L+11:)) 1++:tt) be the largest singular values of the L-lagged matrix of f(.) at time EE [L....TT} We define the following quantities for the pre-change functions fo(:):
max,0 \
max (f((t-L+1:t) tCT
X
min.0
(6)
KCT
with X max.11 and X min,, analogously defined for (-) over the time range & 1 1 Now let
Lo == span (Zr,) C RL, where Zr, is the stacked Page matrix induced by fo(-) with parameter L over To observations (assuming no change occurs at any < To). If the latent time series continues follow the same function for 1.> To, then the columns of its T.-lagged matrix belong to the subspace I. The
'Since Proposition 2.1 is stated for the Page matrix representation, this is true for L-lagged vectors that are non-overlapping and spaced by L observations. However, an analogous result to Proposition 2.1 can be proven for the Hankel matrix representation making this valid for any segment of L observations. For simplicity, we omit discussion of the Hankel matrix but refer to ! for such results.

---

occurrence of the change point at t = forces some or all of the columns of the the L-lagged matrix leave the pre-change subspace Lø- Eventually, i... for t + 1, the columns of the L-lagged matrix will be in the post change subspace T,, which corresponds to the function fı (.()). Following this characterization of change points, we revisit our hypotheses in and reformulate them
Ho: span (E[[(((-L+::0))) CLo
H1 span (F
The occurrence of change point can be captured by test statistic that monitors the distance between the lagged vectors and the pre-change subspace. This motivates the CPD algorithm we propose next.
3 Algorithm
The core steps in the proposed CPD algorithm are to first estimate the pre-change subspace from the stacked Page matrix of noisy observations (t), then repeatedly estimate the distance between this subspace and future lagged vectors. If our estimation of the subspace accurate, the distance will remain small as long as the observations continue to follow the same latent time series. Once a change occurs, the lagged vectors are forced to leave the subspace causing the distance become larger. The algorithm uses the subspace distance as a detection score to construct a CUSUM statistic to perform the hypothesis test in 7 In what follows, we review the CUSUM procedure for sequential hypothesis testing then introduce the full CPD algorithm.
3.1 CUSUM Procedure
Definition 3.1 (CUSUM Statistic). Given an observation X(t) we assign detection score D(t), and as ((t)=mman max
define the CUSUM statistic of the observations
is easy to verify that the CUSUM statistic in Definition 5. can be, more conveniently, computed
recursively (also known Lindley's recursion in queueing theory 26
v() = (tt
y(0)
(8)
Using the CUSUM statistic, and for threshold h h= 0, we define the decision rule at each time as
H (ttt w022
and the estimated change point in (3) can be written as + ( The CUSUM procedure for change point detection, as introduced by Page 34 requires the assigned detection score D(I) to satisfy the following Property 3.1
Property 3.1. valid CUSUM detection score D(t) has a negative expectation when no change is present, and a positive expectation when change occurs, that is B(D(() Ho] <0 and (()) Hh) O.
3.2 Algorithm Description
Our mSSA algorithm for CPD has five parameters: (1) the number of initial observations To used to estimate the subspace TL., (2) the lag parameter
< To, (3) the estimated order of the time series k>0 0, (4) the CUSUM test threshold h> O, and (5) the shift-downwards constant e2 0. For simplicity and without loss of generality let To be an integer multiple of L. We introduce two additional integer quantities: M : To/ L and M = N x M. what follows, we detail the four main steps of the algorithm.
F
Step I: Base Matrix Construction. Transform the observations X,, (1 To) = [X,, (I, nE [N] into Page matrix (n) eI...> M as per Definition 2.1 Then, form the stacked Page matrix Zx R
as in 4h. We refer to Zx as the base matrix.
Step II: Subspace Estimation. Let u, for ie [4] be the left singular vectors of the base matrix Zx sorted as per associated singular values in the decreasing order. We group the singular vectors into two matrices U - - (u.....uull Up] and Ú, = = -fu.,..... Then, we estimate the pre-change subspace L. as:
=p=s (Ün).
Let iL = spanspaannu.aa (1) be the orthogonal complement of the subspace Lo in R.
If Pi is not integer multiple of can introduce new 1% Lx [Tb/L].
5

---

4,0-000
X,6
Kytt 1020
K07g- 13
Ky7 +
Xg0
Ke0 Xy(2
N b Ke0
K
Nuth
mossA S.txpasc Estimation
Rosurrhe Desection Score
X
Cannet on Scow
dar'
dise G
L dimc(a= F
+dw (
-darr
diat K. L.
QUSUM
Mol montyt--
montyir-
Change
Cummuattio Summ
Figure Visual illustration of the algorithm steps.
Step III: Detection Scores. For >>>>> To. construct the L-lagged matrix X(I-L+1: analogous to 5 We define the subspace detection score, which measure the Euclidean distance between the columns of the L-lagged matrix and the estimated subspace Lo. as
D(t)= = (t-
(10)
Step IV: CUSUM Test. For t To. compute the CUSUM statistic y(t) using 8 with y(To)
Steps III and IV repeated until change point is detected when v(t) >>>>>>>>>> h. That is,
== inf (11x(1)2)))
(11)
<>
To adapt this algorithm for multiple change point detection, when a change point is detected at f, the algorithm restarts with new base matrix being constructed using the segment X(f:f+To-D) Refer to Figure 2 for visual depiction of these steps, and Algorithm iin Appendix Cl summary of the algorithm.
3.3 Choice of Parameters
Below, we provide general guidelines for selecting the parameters To and L,, k. Further, we detail data-driven procedure for choosing the CUSUM parameters e and h in Appendix D.
A general recommendation is to choose To to be as large as possible and set L min XTo achieve a good estimation of the pre-change subspace (see Proposition 4.1. However, if To large we might potentially miss or smooth out change point. In practice, one heuristic used to choose To follows: given a starting To, construct the stacked Page matrix and compute its "effective rank" (e.g. top l singular values whose sum of squares is at least 90% of the squared Frobenius norm). Then keep increasing To till the "effective rank" of Zx stops changing. Once it does, this indicates that we have captured the principal subspace Lo. Additionally, the "effective rank" of matrix Zx can be used as k, the estimated order of time series. Indeed, it is well understood that the largest singular value of random Ax B matrix with independent zero mean sub-Gaube Gabo-Gassian entries scales O(VA+ /B). That is, the x M matrix Zx. which can be viewed as a summation of the 'signal' matrix (corresponding to the stacked time series f-)-)) and 'noise' matrix (corresponding to the stacked observation noise e(-)), )), is such that the top singular values scale as O(vL M) while other singular values scale as O( MM. Therefore, with large enough I. and M, clear separation is observed and is the reason for this heuristic to work. See g and 100 for use of such reasoning and heuristic the context of matrix estimation literature.
4 Theoretical Analysis
this section, we establish theoretical performance guarantees of the described algorithm. To that end, we formally introduce the performance objective. Recall that if a change point is present at time t= 7, then
(t) ifter
f(()
(t)
itt2,,

---

where (t) and f (t) each satisfying Properties 2.1 and 2.2 with parameters G, os and Tw; for iE {0,1}. The algorithm declares as the estimate T. Therefore, ideally < then we wish have f F2 and f-r as small as possible. Further, if oo, i.e. no change point is present, then we want 2 to be as large as possible. This is captured through average running length of type and type defined next.
Average running length. This metric is typically considered in the setting of sequential hypothesis testing Let = To+ ie.. one time-step after the time horizon used for the base matrix. Then, define
ARLo 1 Bli
Tolt - =o) ARL, -
The desired behavior is to have large ARLo and small ARL. In what follows, we provide bounds on these two quantities for the specific choice of the detection score (() as a function of the threshold h.
Subspaces distance and affinity. We introduce the definitions of two quantities that will be used in the main results. The first is e which describes how well our estimation of the pre-change subspace. The other is 8, which describes the similarity between the pre and post change subspaces. Recall the subsapces Lo. L1. Lo, and IL, and their corresponding basis matrices. Then define
c= dist(LLo,Lo) = |0 Uollops 8 == 10 U1llop
(12)
Operating assumptions. We make certain operating assumptions to establish our results stated next.
Asumption 4,1 (Parameter Selection). We assume that the parameters of the algorithm are chosen such that TT L- wwi/miinnn)No)../// Tol, LS M, and LZk.
Assumption 4.2 (Gaussian Noise). We shall assume i...d. Gaussian noise en NO)
Assumption 4.3 (Balanced spectra). that satisfies properties 2.7 and 2.2 and has order where under the setup of Proposition 2.7 k RxG.
Let Ze be the stacked Puge matrix associated with the time series f(.)
Then for L min N, ( x Tol k, the stacked page matrix such that A (Ze) 2 / V for
some absolute constant K > O, where )u(-)) is the k-th largest singular value of its argument.
Based on the these assumptions, we can quantify the bound on the estimation error c, as follows.
Proposition 4.1. Let assumptions 4.7 4.3 hold. Let be the estimation error defined in 12 Let
(=((sgh with q:= 40 Go
(13)
((min(Tb.N) xTo)
Then 21 1exppp 1exxp(22v/1)) N/7
Note that the choice of I,= I.=lymiine N x XTo] plays a key role in minimizing the subspace estimation error. Precisely, the bound on the estimation error (g) scales inversely with the square root of the minimum dimension of the Page matrix. Thus, to minimize the error, we construct a nearly square base matrix.
Main results. Now we state the main result providing a lower bound on ARLg and an upper bound on ARL, for a given parameter h O. particular, it shows that ARL scales exponentially in while ARL, scales linearly in h. Proofs of Proposition 4.1, Theorems
4.
4.2 and 4.3 can be found in Appendix B
Theorem 4.1 (Bound on ARLa). Let Assumptions 4. hold. Let be the estimate of T as per
Given h 0, k and a choice of e such that (recall notation in
<> N(L-k)o² +Ro max,0
(14)
Then, =0
= 2 Co exp(C),),
where Co,C1 are positive constants that depend on the parameters a RRo.Go,N,L and To-
Theorem 4.2 (Bound on ARL)). Let Assumptions 4.1 4.3 hold. Let be the estimate of T as per Conditioned on E and given > 0, k and choice of c such that (recall notation in
<< NL + () m2..
(15)
The analysis and guarantees obtained will extend easily for generic ulb-Gaussian distribution.
7

---

T then
ARL, GRL,sC++Ch++C exp( exp(-Oshh).
(16)
where Co C₁ C2 and C3s are positive constants that depend on the parameters L.
Next, we show that there exists feasible choice of с for both theorems to hold, provided that the pre and post change subspaces are sufficiently "different".
Theorem 4.3. Let the affinity between the pre and post change subspaces defined as per
12 Then
there exists feasible choice of e that satisfies both equations
14 and 15 if is such that
mmxx0
5<1-9 L+
(17)
minI
Interpretation. Recall that is measure of "similarity" between subspaces which takes value in [0,1]: it is 1 the two subspaces intersect, otherwise, it is < Theorem implies that as q gets smaller, which may be achieved more data points (NT,) become available, the feasibility c. Under perfect estimation (e.g. no noise in data or infinite data availability), i.e. q any 8 < 1 will guarantee the feasibility of c.
tolerate larger à without compromising
5 Evaluation on Benchmark Datasets
We present a comparative evaluation of two variants of the proposed mSSA algorithm and four other standard methods for CPD: BinSeg (21, KL-CPD 77. Microsoft SSA 29 and BOCPDMS [23]
Datasets, The evaluation conducted on four benchmark datasets (see Table 2 Details of these datasets, their sources, and physical interpretations of change points given in Appendix D.2
Evaluation metric. For evaluation we use the F1-score metric, which is defined as: F TP+ & FF)+
where TP, FP, and FN denote the number of true positives, false positives, and false negatives, respectively. Following standard practice cf. 42 27 16,, we use the following soft true positive (TP) rule: for a constant 17 7>00 0, if the algorithm detects change point i such that / where is labeled change point, TP is recorded, otherwise a FP is recorded. Here we report the results for 77= 10. To avoid double-counting. ensure that each labeled and detected change point is associated with at most one TP. Further, the convention of counting the first index of the time series (t =t=1] 1) as a TP.
Note that we choose the F1-score as our metric over the average running length (i.e. ARLa and ARL)) for two practical reasons: (i) it a more commonly used metric the change point detection literature; (ii) it can be used for both online and offline change point detection methods, both are used in our experiments.
Practical implementation (mSSA-MW). The Algorithm described in Section change point detection. In practice, there can be multiple change points in a time series and hence we use natural Moving Window variant. This is described in details Algorithm in Appendix C this section, we run the evaluations for both the original variant (mSSA) and the Moving Window variant (mSSA-MW),
meant for single
Table 2: Summary of datasets.
Dataset
Domain
No. time series
Length series
No. change points
Beedance
608-1124
117
Real-world data
HASC
18
11738 12000
196
Occupancy
R4
8143
12
Yahoo
R
99
1680
207
Energy
5000
Synthetic
Mean
5000
data
Frequency
R
20
5000
Mixed
R2 100
1000
Parameter Selection. When applying CPD algorithm as a statistical for the automatic detection of change points, common challenge that arises in practice is tuning the algorithm's 's parameters. This

---

is particularly challenging in the task of CPD as it is often applied in an unsupervised manner due to the scarcity of labels (change points are anomalous events). To overcome this, we follow the evaluation setup proposed in [22 where for each dataset we report (1) the Fl-score using default parameters, and (2) the best Fl-score over a grid search of parameter configurations. We provide details about the default parameters and the grid search for all algorithms in Appendix D.I
Results. We compare with retrospective change point detection methods (BinSeg and KL-CPD) and real-time methods (BOCPDMS and Microsoft SSA). Two of these algorithms (BinSeg and Microsoft SSA) only support univariate time series. For datasets of higher dimension, we report the results of these algorithms on univariate time series constructed from the L2 norm of the observation vector (in Appendix D.5 we explore other approaches of applying univariate algorithms to multivariate data).
In Table 3 the best and default performance of each algorithm are shown as the average and standard deviation of the F1-scores across time series in each datasef] mSSA-MW algorithm shows consistently superior performance over other methods, including the retrospective ones, across all datasets in the best parameters setting, and all but one dataset using the default parameters.
For all datasets, we notice a significant improvement of A-MW over the mSSA variant. We describe one possible explanation for this behavior. If the order of the time series is large compared to the dimensions of the base matrix, then the estimation of the subspace is inaccurate, leading to a large detection score even when no change occurs. While this is also true for the moving window approach, therein the base matrix estimates a new subspace in every time step, which captures the local structure of the time series at that time. While it doesn't 't necessarily capture the full signal, its estimated subspace has more proximity to the test lagged vectors. Another plausible explanation is the existence of gradual and small changes in the data that aren't labeled as change points. In such a case, constructing fixed base matrix makes the algorithm more sensitive to such changes, while having a moving window smooths out such changes.
Table 3: Mean (and standard deviations) of Fl-scores for each algorithm reported. mSSA outperforms other methods across all datasets with best parameters choice. The No Change rows correspond to an algorithm that detects no change point.
Real-world Datasets
Beedunce
HASC
Occupancy
Yahoo
Best
Default
Best
Default
Best
Default
Best
Default
BinSeg
0.597 (0.10) 0.097 (0.02) 0.304 (0.08) 0.161 (0.05) 0.308 (N/A) 0,308 (N/A) 0.715 (0.19) 0.372 (0. (0.10)
Microsoft SSA
0,583 (0.06) 0.279 (0.08) 0.265 (0.07) 0.049 (0.02) 0,462 (N/A) 0.375 (NIA) 0.684 (0.19) 0.283 (0.11)
KL-CPD
0.401 (0.05) 0.252 (0:07) 0.156 (0.01) 0.155 (0.01) 0.341 (N/A) 0.302 (N/A) 0.699 (0.18) 0.617 (0.20)
BOCPDMS
0.167 (0.07) 0.092 (0.02) 0.204 (0.06) 0.078 (0.04) 0.474 (N/A) 0.198 (N/A) 0.479 (0.19) 0.463 (0.19)
mSSA (ours)
0.404 (0.17) 0.124 (0.04) 0.190 (0.06) 0.142 (0.03) 0.526 (N/A) 0.222 (N/A) 0.667 (0.21) 0.422 (0.18)
mSSA MW (ours)
0.659 (0.12) 0.500 (0.13) 0.327 (0.10) 0.177 (0.1 0.783 (N/A) 0.480 (N/A) 0.719 (0.18) 0.384 (0.16)
No Change
0.097 (0.02)
0.155 (0.01)
0.143 (N/A)
0.556 (0.22)
Synthetic Datasets
Energy
Mcan
Mixed
Frequency Default
Best
Default
Best
Default
Best
Default
Best
BinSeg
0.663 (0.18) 0.209 (0.03) 0.714 (0.18) 0.600 (0.21) 0.634 (0.14) 0.240 (0.08) 0.350 (0.03) 0.200 (0.00)
Microsoft SSA
0.849 (0.07) 0.811 (0.09) 0.807 (0.10) 0.733 (0.17) 0,546 (0.07) 0.232 (0.03) 0.735 (0.11)
(0.26)
KL-CPD
0.475 (0.12) 0.399 (0.10) 0.499 (0.12) 0.407 (0.11) 0.333 (0.00) 0.333 (0.00) 0.345 (0.05) 0.333 (0.00)
ROCPDMS
0.449 (0.13) 0.280 (0.10) 0.328 (0.09) 0.213 (0.04) 0.152 (0.02) 0.131 (0.00) 0.443 (0.07) 0.209 (0.10)
mSSA (ours)
0.929 (0.09) 0.786 (0.21) 0.915 (0.06) 0.673 (0.28) 0.950 (0.10) 0.740 (0.17) 0.994 (0.02) 0.874 (0.19)
mSSA-MW (ours)
0.919 (0.09) 0.763 (0.17) 0.921 (0.07) 0.697 (0.31) 0.960 (0.05) 0.856 (0.10) 1.000 (0.00) 0.930 (0.11)
No Chunge
0.333 (0.00)
0.333 (0.00)
0.333 (0.00)
0.333 (0.00)
6 Evaluation on Synthetic Data
To further explore its performance, we evaluate mSSA on synthetic datasets, using the same setup of Section 5 We follow the practice of 77 and [2 and create synthetic datasets using our proposed time series model, each with a different representative mode of change. Specifically, we generate four sets
'For the occupancy, we only have time series, and hence the standard deviation is not reported.

---

of synthetic time series, each is a mixture of harmonics and a polynomial trend with the following modes of change: (i) jumping mean (Mean), a univariate time series where at each change point, constant offset is added; (ii) scaling signal energy (Energy), a univariate time series where at each change point, the amplitude of the harmonics is changed; (iii) changing frequency (Frequency), a univariate time series where at each change point, the frequencies of the harmonics are changed; (iv) mixed change (Mixed), a multivariate time series where at each change point, a mixture of the above changes is applied. Refer to Table 2 for more details and Appendix D.3 for details about the data generation process.
Results. In Table B] the best and default performance of each algorithm are shown as the average and standard deviation of the Fi-scores across time series in each synthetic dataset. Both mSSA and mSSA-MW implementations show consistently superior performance over other methods across all datasets in the best parameters setting, and they compete with Microsoft SSA in the default parameters setting. Notice that the results on the simulated data show similar performance of the two variants of the algorithm (mSSA and mSSA-MW). Here the data is constructed to follow the proposed model with a low-rank Page matrix, and enough time steps are available to construct a sufficiently large base matrix. As result, the subspaces of the fixed base matrix (in mSSA) and the moving window base matrices (in mSSA-MW) become almost identical with small variations due to the noise.
For the univariate datasets, another algorithm that performs well is the Microsoft SSA, which is proposed for a similar time series model. However, we notice significant degradation in the performance the case of the multivariate time series. This highlights the importance of extending SSA to accommodate multivariate time series. The BinSeg algorithm performs relatively well on the Energy and Mean datasets. However, the algorithm is not capable of detecting the Frequency mode of change, nor the Mixed mode. We note that BinSeg has designated methods for detecting mean and variance changes, which might be the reason for its good performance in the Energy and Mean datasets. KL-CPD and BPCPDMS algorithms are built with the assumption of i.i.d. samples, so the highly dependant structure and the viryiigyyig mean of our data might explain the bad performance of these algorithms on the simulated datasets.
Multivariate data helps. Here, we explore the benefits of utilizing information across time series in mSSA. Specif- ically, we study the trade-off between ARLo and ARL1 as NN (number of time series) increases. We start by gen- erating 25 synthetic time series as described in details in Appendix D.4 Then for each value of N E [5,10,1522) 20,25 we perform the following experiment. First, we assume that there is no change point (T oo) and run the algorithm for 10 trials. In each trial, we vary the threshold h and record & which represents the time of false alarm. Next, we introduce& a change point at To + 1, and run the algo- rithm for another 10 trials. Again vary the threshold h and record è which represents the detection delay.
2030
10
1500
ARL1
1030
530-
ARLo
Trade-off between ARLa and ARL: we increase the dimension of the time series.
Figure 3:
Figure 3 shows the average results of the 10 trials for each pair (N,)). Each line of connected dots corresponds to the same value of N with different values of h. As shown in the figure, as we fix the value of ARL. at certain acceptable rate, we can achieve better ARL, (i.e. detection delay) using a time series of larger dimension. This shows that mSSA effectively utilizing information across multiple time series to improve the detection performance over the univariate SSA.
7 Limitations
Our method achieves encouraging theoretical and empirical results for change point detection. However, like any such research program, there are various limitations suggesting exciting directions for future research. A prominent one being extending the theoretical analysis to the setting of multiple change points. In sense, this would be important step forward for the field of change point or anomaly detection.
Acknowledgements and Funding Disclosure
This work was supported in parts by the MIT-IBM project on time series anomaly detection, NSF TRIPODS Phase grant towards Foundations of Data Science Institute, KACST project on Towards Foundations of Reinforcement Leaming, and scholarship from KACST (for Arwa Alangary and Abdullah Alomar).
10

---

References
[1] A. Agarwal, A. Alomar, and D. Shah. On multivariate singular spectrum analysis. arXiv preprint arXiv:2006. 13448, 2020.
[2] A. Agarwal, M. Amjad, D. Shah, and D. Shen. Model agnostic time series analysis via matrix estimation. Proceedings of the ACM on Measurement and Analysis Computing Systems, 2(3):1-39, 2018.
[3] S. Aminikhanghahi and D. J. Cook. A survey of methods for time series change point detection. Knowledge and information systems, 51(2):339-667, 2017.
[4] D. Angelosante and G. B. Giannakis. Group lassoing change-points in piecewise-constant ar processes. EURASIP Journal on Advances in Signal Processing, 2012(1):1-16, 2012.
[5] S. Basu and M. Meckesheimer. Automatic outlier detection for time series: an application to sensor data. Knowledge and Information Systems, 11(2)137-1144, 2007.
[6] L. M. Candanedo and V. Feldheim. Accurate occupancy detection of an office room from light, temperature, humidity and co2 measurements using statistical learning models. Energy and Buildings, 1 12.28-39, 2016.
[7] W.-. Chang, C.-L. Li, Yang, and B. Póczos. Kemel thange-poin detection with auxiliary deep generative models. arXiv preprint WXXv:1901.06077, 2019.
[8] S. Chatterjee et al. Matrix estimation by universal singular value thresholding. Annals of Statistics, 43(1)1177-214, 2015.
[9] C. Davis and W. M. Kahan. The rotation of eigenvectors by perturbation. ili. SIAM Journal on Numerical Analysis, 7(1):1466, 1970.
[10] M. Gavish and D. L. Donoho. The optimal hard threshold for singular values is 4/v3. IEEE Transactions Information Theory, 6068):5440-5053 2014.
[11] M. Ghodsi, H. Hassani, and S. Sanei. Extracting fetal heart signal from noisy maternal ecg by singular spectrum analysis. Journal of Statistics and its Interface, Special Issue the Application of SSA, 3(3):399-411, 2010.
[12] M. A. Girshick, H. Rubin, et al. A bayes approach to a quality control model. Annals of Mathematical Statistics, 23(1):114-225, 1952.
[13] N. Golyandina, V. Nekrutkin, and A. A. Zhigljavsky. Analysis of time series structure: SSA and related techniques. CRC press, 2001.
[14] G. Grimmett and D. Stirzaker. Probability and random processes. Oxford university press, 2020.
[15] T. Hagemann and K. Katsarou. Reconstruction-basee anomaly detection for the cloud: comparison on the yahoo! webscope s5 dataset. In Proceedings of the 2020 4th International Conference on Cloud and Big Data Computing, pages 68-75, 2020.
[16] Z. Harchaoui, E. Moulines, and F. Bach. Kernel change- poinge- analysis. In D. Koller, D. Schuurmans, Y. Bengio, and I.. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2009.
[17] H. Hassani and R. Mahmoudvand. Multivariate singular spectrum analysis: A general view and new vector forecasting approach. International Journal of Energy and Statistics, 1(01):55-83) 83, 2013.
[18] T. Idé and K. Inoue. Knowledge discovery from heterogeneous dynamic systems using change-point correlations. In Proceedings of the 2005 SIAM International Conference on Data Mining, pages 571-575. SIAM, 2005.
[19] Jiao, Chen, and Gu. Subspace change-point detection: new model and solution. IEEE Journal of Selected Topics in Signal Processing, 1266):1224-1239 2018.

---

[20] Y. Kawahara, T. Yairi, and K. Machida. Change-point detection in time-series data based on subspace identification. In Seventh IEEE Interational Conference on Data Mining (ICDM 2007), pages 559-564. IEFR, 2007.
[21] Killick and I. Eckley. changepoint: An package for changepoint analysis. Journal of statistical software, 58(3):1-99, 2014.
[22] J. F. Kingman. A martingale inequality in the theory of queues. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 60, pages 359-361, Cambridge University Press, 1964.
[23] J. Knoblauch and T. Damoulas. Spatio-temporie bayesian on-line changepoint detection with model selection. In International Conference on Machine Learning, pages 27 18-2777. PMLR, 2018.
[24] S. Lee. S. Lee, and M. Moon. Hybrid change point detection for time series via support vector regression and cusum method. Applied Soft Computinng 89:106101, 2020.
[25] S. Li, Y. Xie, H. Dai, and L. Song. M-statistic for kernel change-point detection. In C. Cortes, Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[26] D. Lindley. The theory of queues with single server. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 48, pages 277-289, Cambridge University Press, 1952.
[27] S. Liu, M. Yamada, N. Collier, and M. Sugiyama. Change-poin detection in time-series data by relative density-ratio estimation. Neural Networks, 43:72 83, 2013.
[28] A. M. Mathai and S. B. Provost. Quadratic forms in random variables: theory and applications. Dekker, 1992.
[29] Microsoft.
nimbusml package, class, 2020.
https://bessmmicrooff.ccmmee
[30] Y. Mohammad and T. Nishida. Robust singular spectrum transform. In International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, pages 123-132. Springer, 2009.
detection. Communications in Statistics Simulation and Computation, 32(2):319 352, 2003. [31] V. Moskvina and A. Zhigljavsky. An algorithm based on singular spectrum analysis for change-point
Staristics-Simllttion
[32] G. V. Moustakides et al. Optimal stopping times for detecting changes in distributions. Annals of Statistics, 14(4):1379-138) 1986.
[33] Oh, J. M. Rehg. T. Balch, and Dellaert Learning and inferring motion patterns using parametric segmental switching linear dynamic systems. International Journal of Computer Vision, 77(1)1003-124 2008
[34] E. S. Page. Continuous inspection schemes. Biometrika, 41(112):100-11 -15,, 1954.
[35] J. Reeves, J. Chen, X. L. Wang, Lund, and Q Lu. A review and comparison of changepoint detection techniques for climate data, Journal of applied meteorology and climatology, 46(6):900-155, 2007.
[36] D. Rybach, C. Gollan, R. Schluter, and H. Ney. Audio segmentation for speech recognition using segment features. In 2009 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 4197-4200. IEEE, 2009.
[37] Y. Saatçi, R. D. Tumer, and C. E. Rasmussen. Gaussian process change point models. In ICML, 2010.
[38] W. A. Shewhart. Economic control of quality of manufactured product. Macmillan And Co Ltd, London, 1931.
[39] H. Shumway, D. Stoffer, and D. Stoffer. Time series analysis and applications, volume Springer, 2000.
12

---

[40] A. Tartakovsky, L. Nikiforov, and M. Basseville. Sequential analysis: Hypothesis testing and changepoint detection. CRC Press, 2014.
[41] L. Vaisman, J. Zariffa, and M. R. Popovic. Application of singular spectrum-based change-point analysis to emg-onset detection. Journal of Electromyography and Kinesiology, 20(4):750-760, 2010.
[42] G. van den Burg and C. K. Williams. An evaluation of change point detection algorithms. arXiv preprint 2rX1::2003.06222, 2020.
[43] Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 2010.
[44] R. Vershynin. High-dimensiona. probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[45] P.-.. Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics, 12(1):99-111, 1972.
[46] Yamanishi and J.-i. Takeuchi. A unifying framework detecting outliers and change points from non-stationary time series data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 676 606, 2002.
13


Reviews:
[{"review_id": "mxdkub4wYYC", "reviewer": "Reviewer_TMbJ", "summary": "This paper studies the online change-point detection for multivariate time series and proposes a new cusum-like detection statistic based on singular spectrum analysis. Theoretical approximations for the ARL and EDD are provided. This paper also validates the performance of the proposed method using a variety of synthetic and real data sets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The main contribution of this paper is the proposed detection statistic for online change detection, together with theoretical analysis on two major performance metrics: the average run length when there is no change, and the average detection delay. \nThe basic idea in this paper is to first use historical data to estimate the nominal subspace of the Page matrix, then under the assumption that the change will affect the corresponding subspace, the change can be detected by monitoring the deviation of the sequential observations with respect to the nominal subspace. \n\nThe construction of the detection statistic is only of incremental contribution since the deviation of the observation with a referenced subspace has been used in previous literature for change detection, and the construction and properties of the Page matrix are also known. However, this paper also provides a complete theoretical analysis on ARL_0 and ARL_1 which matches with classical results for iid data, and these theoretical results seem to be relatively new.\n\nThis paper may still be improved in the following directions. \nFirst, it would be interesting to list some key constants (those C's) in Theorem 4.2 and Theorem 4.1 -- then we may obtain a more clear relationship between ARL_1 and ARL_0 and compare with the theoretical lower bound (the optimal detection performance).\nSecond, in the numerical results, the author spent a lot of space comparing the F1 score for different algorithms. Since this is an online algorithm, maybe the detection delay (and the trade-off between ARL_0 and ARL_1 as shown in Figure 3) would be more interesting to present. For example, instead of showing the trade-off curves for different N values, it would be more interesting to compare the trade-off curves for different algorithms.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "YTbhtOTRloH", "reviewer": "Reviewer_iaBb", "summary": "The article presents a change point detection (CPD) method for multivariate data. The proposed methodology operates by monitoring the space generated by segments of the data and then assesses how this space varies. A sound theoretical treatment and convincing experiments are reported as well. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The paper is dense in notation and definitions that are needed to present the contribution, however, the authors present them in a very clear manner. Among the positive points of this work I would like to mention the fact that the proposed method is nonparametric, meaning that no model is imposed to the data, and also online, meaning that CPD is performed as observations arrive by evaluating the CUSUM statistic. The proposed method is multivariate and exploits across-channel relationships, a necessary feature for real-world applications. The ideas presented in the paper are also supported on a theoretical analysis, a discussion on the optimal hyperparameters and two sets of experiments. \n\nI have the following criticisms\n\n- The proposed method is for discrete-time observations, in the spirit of classical digital-signal processing techniques. This is undesirable for real-world scenarios for which the observations are asynchronous or there are (regions of) missing data. I know this paper targets another particular setting, but I suggest the authors refer to that case. \n\n- The noise model, and the randomness, associated to the approach may be overly simple. Recently, there has been Gaussian process based CPD methods, which despite having several drawbacks are very capable in modelling complex trajectories. This proposed method, however, only considers a fixed structure with iid noise, which might be unable to detect changes in the form of, e.g., the distribution of the noise or the covariance of successive values of f_0(t). \n\n- As the proposed method focuses on monitoring the distance of new points wrt the span of the previous data, how would the method behave for a nonstationary signal which changes very gradually and there is no changepoint per se but rather a continuous model evolution.\n\n\nparticular comments: \n\nl111: denotes -> denote\nl191: why is that choice for L recommended? Please elaborate\nTable2:Summery -> Summary\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "TWIRFI6Qde1", "reviewer": "Reviewer_e36y", "summary": "This paper presents a multivariate singular spectrum analysis to perform change point detection. A spatio-temporal model is introduced to model the dynamics and CUSUM statistic was used to perform online change point detection. The experiment results showed the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Strengths:\n* This paper is well organized.\n* Change point detection is an interesting problem to investigate.\n* Both theoretical and empirical justifications are provided for the proposed technique.\n\nWeaknesses:\n* It is not clear how the derived upper bounds are helpful for practical CPD.\n* More discussions about the results are necessary.\n\nOverall, the proposed multivariate singular spectrum analysis is innovative and technically sound. The following are a few questions:\n\nIt is not clear how the derived theoretical performance guarantee is related to performance improvement. Further explanations and discussions are necessary.\n\nIn Table 1, it is not clear why performance improvement is limited on Yahoo but very significant on Occupancy, Mixed, and Frequency.\n\nWhy is the variance of the proposed mSSA relatively large on several datasets in Table 2 and Table 3?\n\nWhat’s the length of those time series datasets?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "EMyMsT7CI53", "reviewer": "Reviewer_xiRb", "summary": "The paper studies change-point detection in time-series using a combination multi-variate singular spectrum analysis (SSA) and CUSUM.   While multi-variate SSA and CUSUM are established techniques, the contribution of the paper is to (a) analyze the online CPD setting with a dependent (non-iid) timeseries. (b) Conduct rigorous analysis of the tradeoff of detection delay vs. false-alarm within the MSSA model.  (c) The exact version of MSSA is a bit different from the classical one. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The papers takes a fresh look at applying classical techniques MSSA and CUSUM to change-point detection.   While the combination of SSA and CUSUM has already been proposed for CPD (as cited in ref [30], Moskvina and Zhigljavsky, 2003),  and MSSA itself has been proposed a decade ago (e.g. 2013 -- also Zhigljavsky et al) -- the main contribution of this paper is a formal theoretical analysis, and a detailed numerical evaluation. \n\nThe paper is mostly clearly written (some caveats below), and I believe the style of analysis (using concentration inequalities, and the distribution of subspace angles and matrix singular values) is a contribution to the SSA / CPD literature.  I would prefer the paper to be more upfront about what's new and what has been done before, and novelty:  in the appendix there's a good description of the existing literature, and the contribution that this paper makes.  I'd suggest moving a few sentences into the main paper.  The main paper itself is a bit cryptic and lacks references (e.g.  ref for early MSSA would be good). \n\nI'm not clear that the evaluation is as strong as it could be -- how were the baselines chosen?  Is using the norm of multivariate time-series and furnishing to univariate CPD a good baseline?  Can you maybe run univariate CPD on each time-series  and do some sort of a voting -- that may have more of a chance at detecting richer classes of changes? Other than that, experiments seem to have been done thoughtfully. \n\nThe setting in the introduction could be made clearer (it's clear by the end of the paper -- but confusing at the start):  \n1) You mention f0 and f1 on page 2.   Are you detecting a change from f0 to f1 when both are known,  or do you only know f0, and declare a change when you're sufficiently far from f0?  \n2) Page 3 -- let H(t) -- be the random variable equal to the accepted hypothesis at time t.   This is too informal -- you're not 'accepting' a hypothesis H0 vs H1 -- but trying to reject H0?   \n3) The description of detecting slow-moving changes vs.  abrupt changes can be made clearer as well.  It seems that the shift-downward constant is related to the baseline slow-moving rate of change. Can you make this clear. \n4) What is a 'valid' CUSUM detection score?  Is it bad to have an 'invalid' score? What does it mean?\n5) I was happy to see that in addition to bounds on ARL0 and ARL1, the paper analyzes when these are not vacuous. Also happy to see various suggested heuristics choices for various parameters. Sign of practical mindset. \n6) Why did you chose the particular 4 methods?  Are these representative of state-of-the-art?   Picking the norm of multivariate time-series and using univariate CPD methods seems like a rather suboptimal approach. \n7) The tradeoff of ARL0 vs ARL1 changes dramatically w.r.t number of time-series.  Is the subspace distance as a function of N somhow normalized?  It sounds like higher dimensional problems are simply much easier \n(subspace angle after the change is much larger in higher dimensions). \n\nAdditional comments: \n[1] Minor:  notation Gamma^alpha -- this is just a constant, but suggests some power law w.r.t. alpha.  same for Gamma^w. \n[2] You use [1] as the ref for MSSA -- how is it different from earlier MSSAs that you describe in appendix? (add a comment + ref in main paper)  . \n[3] Property 2.2. The language makes it confusing as to whether it's an assumption or implication. \n[4] For finite sums of harmonics, low-degree polys, and exp-functions Page matrix is low-rank.  Comment on rank vs. num terms?  In general for your data-sets in the experimental section, what rank did you end up choosing (for default / best params)? \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I'm not aware of societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A.  ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
The paper studies sequential change-point detection using a combination multi-variate singular spectrum analysis (SSA) and CUSUM.  The paper presents a novel analysis of the online CPD setting with a dependent (non-i.i.d.) sequence and characterizing the tradeoff of detection delay vs. false-alarm. Extensive numerical results validate the performance of the algorithm. 
Decision: Accept (Poster)