#  Data-Adaptive Symmetric CUSUM for
Sequential Change Detection

Nauman Ahad, Mark A. Davenport, and Yao Xie

###### Abstract

Detecting change points sequentially in a streaming setting, especially when
both the mean and the variance of the signal can change, is often a
challenging task. A key difficulty in this context often involves setting an
appropriate detection threshold, which for many standard change statistics may
need to be tuned depending on the pre-change and post-change distributions.
This presents a challenge in a sequential change detection setting when a
signal switches between multiple distributions. For example, consider a signal
where change points are indicated by increases/decreases in the mean and
variance of the signal. In this context, we would like to be able to compare
our change statistic to a fixed threshold that will be symmetric to either
increases or decreases in the mean and variance. Unfortunately, change point
detection schemes that use the log-likelihood ratio, such as CUSUM and GLR,
are quick to react to changes but are not symmetric when both the mean and the
variance of the signal change. This makes it difficult to set a single
threshold to detect multiple change points sequentially in a streaming
setting. We propose a modified version of CUSUM that we call Data-Adaptive
Symmetric CUSUM (DAS-CUSUM). The DAS-CUSUM change point detection procedure is
symmetric for changes between distributions, making it suitable to set a
single threshold to detect multiple change points sequentially in a streaming
setting. We provide results that relate to the expected detection delay and
average run length for our proposed procedure. Extensive simulations are used
to validate these results. Experiments on real-world data further show the
utility of using DAS-CUSUM over both CUSUM and GLR.

††N.Ahad and M.A.Davenport are with the School of Electrical and Computer
Engineering, Georgia Tech, Atlanta, GA, 30302, USA. Y.Xie is with the School
of Industrial and Systems Engineering, Georgia Tech, Atlanta, GA, 30302, USA.
The work of N. Ahad and M. Davenport was supported, in part, by NSF grants
CCF-2107455 and DMS-2134037, NIH grant R01AG056255, and gifts from the Alfred
P. Sloan Foundation and Coulter Foundation. The work of Y. Xie was supported,
in part, by an NSF CAREER grant CCF-1650913, and NSF grants DMS-2134037,
CMMI-2015787, DMS-1938106, and DMS-1830210.
E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1 Introduction

For a sequence of observations $x_{1},\ldots,x_{t}$, the goal of change point
detection is to detect whether there exists an instance $n_{c}$ such that
$x_{1},\ldots,x_{n_{c}-1}$ are generated according to a different distribution
than $x_{n_{c}},\ldots,x_{t}$, and if so, estimating $n_{c}$. This is
typically accomplished by computing a simple change statistic based on the
log-likelihood ratio, which can be compared to a threshold to detect changes
or optimized to estimate $n_{c}$. Sequential change point detection involves
sequentially detecting multiple changes in streaming data. Many real-world
world applications require sequential detection of change points within
streaming signals. Healthcare, communication, and finance are just a few areas
where sequential change detection is widely used [27, 16, 1]. An extended
discussion of applications of change point detection can be found in [3].

Despite being devised more than half a century ago, the CUSUM statistic is
still one of the most popular methods for detecting change points [20]. This
is chiefly due to two reasons. First, it has a simple recursive implementation
which makes it computationally efficient to apply. Second, it has been shown
to be optimal in minimizing the detection delay for a given false alarm rate
[18]. However, computing the CUSUM statistic requires complete knowledge of
both the pre-change and post-change distributions. This is not feasible in
many real-world scenarios where the post-change distribution can be unknown.
In such settings, a more common approach is to use the GLR statistic, which
involves estimating the post-change distribution for all possible change
points [21]. Both the CUSUM and GLR statistics leverage the log-likelihood
ratio for the known/estimated pre- and post-change distributions.

Most work on change point detection has focused on identifying a _single_
change point in the quickest possible manner. Though this has been useful for
some applications, especially those that monitor a process for abnormal
behavior such as machine fault detection and network intrusion detection, many
modern applications require the detection of _multiple_ change points
sequentially in streaming data. In sequential change point detection, the
detection procedure must be restarted and continued after each change point is
detected, resulting in multiple change points being detected. Examples of such
settings include segmentation of signals for activity recognition where change
points are used to identify transitions from one activity to another in a
streaming setting [4]. In such settings, the pre-change and post-change
distributions themselves change after each change point and cannot be assumed
to be known _a priori_. This presents a significant challenge to most standard
change detection approaches because the detection threshold must be set
without any knowledge of these distributions (with the threshold typically
being fixed in advance and held constant throughout the procedure).

The machine learning community has been addressing this problem of identifying
multiple change points in data streams [17]. Such works show that procedures
employed to detect change points should be _symmetric._ This means the
magnitude of a change from a distribution $\theta_{0}$ to a distribution
$\theta_{1}$ should be the same for a change from $\theta_{1}$ to
$\theta_{0}$. Using a procedure that has a similar power in detecting such
changes makes it easy to select a threshold for detecting multiple changes
sequentially. Statistics such as the GLR and CUSUM are not symmetric when
distribution changes involve a change in variance. This makes it difficult to
use these in detecting multiple changes.

In this work, we present an adaptive symmetric version of CUSUM that we call
Data-Adaptive Symmetric CUSUM (DAS-CUSUM). DAS-CUSUM uses a window to estimate
the post-change distribution and employs a symmetric change statistic to make
it easier to select a fixed threshold to detect multiple change points in
streaming data. We provide theoretical results for our proposed method that
relate the expected detection delay (EDD) (average delay in detecting true
changes) to the average run length (ARL) (average time until a false alarm
occurs).

The rest of the paper is organized as follows. After reviewing related
literature in Section 2, we formalize the change detection problem in Section
3 and further motivate the need to have a symmetric change statistic for
detecting multiple changes. Section 4 provides a description of the proposed
procedure. Theoretical results that relate EDD versus ARL are described in
Section 5, where a sketch of the related proofs is also given. Section 6
contains simulations that empirically validate the theoretical results in a
practical setting. Experiments on real-world data are summarized in Section 7.

##  2 Related work

The CUSUM statistic is known for being asymptotically optimal in minimizing
the maximum average detection delay as the average time to false alarm reaches
infinity [18]. CUSUM was later shown to be optimal in minimizing the expected
detection delay for a provided (non-asymptotic) expected time to false alarm
[19]. There has been extensive work done to further investigate and generalize
the optimality property of CUSUM. These results, however hold when both pre-
change and post-change distribution are completely known. A summary of such
work can be found in [23]. A two-sided CUSUM test can be used to detect either
an increase or decrease in mean [12], but this approach still assumes a fixed
and known variance. When the post-change distribution is unknown, the
generalized log-likelihood ratio test (GLR) can be used by estimating both the
change location and the post-change distribution through maximum likelihood
estimation. However, CUSUM, GLR, and their variants are often used to detect
only a _single_ change point [22]. The few works that do use these methods to
detect multiple changes do so by only detecting changes in the mean of
normally distributed data [8, 11]. It is more challenging to detect multiple
changes when both the mean and the variance of a signal change. There is
limited prior work that detects joint changes in both the mean and the
variance of the signal [14], however, this has not been considered in the
context of detecting multiple changes.

Recently, there has been increasing interest in the machine learning community
to detect multiple change points sequentially within streaming data [15, 17,
2, 10]. Most of these methods use non-parametric change statistics, which are
symmetrical. This means that the magnitude of the change statistic for a
change from $\theta_{0}$ to $\theta_{1}$ is equivalent in magnitude for a
change from $\theta_{1}$ to $\theta_{0}$. The need for this symmetrical
statistic was noted by [17], who use a symmetric KL-divergence to detect
multiple changes within streaming data where both the mean and variance of the
normally distributed signal are changing. The symmetric statistic makes it
easy to set a single detection threshold before the procedure is started to
detect multiple changes within streaming data. At each time instance, a pre-
change distribution is estimated using a “past window,” and the post-change
distribution is estimated using a “future window.” These methods, however, do
not incorporate data samples directly. These samples are incorporated through
estimates of the distribution, which makes these methods slow to react to
changes. None of these methods characterize the relationship between detection
delay and false alarm rate.

The need to use symmetric statistics for change detection was also earlier
noticed in [6, 5, 13], where the authors noted the asymmetry in change
statistics when there are changes in both mean and variance. These works used
a log-likelihood ratio with a drift term to make the expected value of the
change statistic symmetric under the post-change distribution. However, this
drift term meant that the expected value of the statistic is zero under the
pre-change distribution, which can lead to more false positives. A slightly
modified version of this technique was mentioned in [7], where false alarm
rates were reduced by adding a fixed drift term which made the expected value
of the statistic negative under the pre-change distribution. However, no
details were provided about setting this drift term. These methods also
provided no characterization of the relationship between detection delay and
false alarm rate.

In this work, we investigate a suitable choice for this fixed drift to make
the statistic symmetric under the post-change distribution while also ensuring
the expectation is negative under the pre-change distribution. Our proposed
change detection procedure provides a symmetric change statistic for different
families of probability distributions, however, the theoretical results
relating detection delay and false alarm rate consider the more restricted
setting of i.i.d. univariate normally distributed data.

##  3 Problem statement

Change points are instances in a signal where the underlying distribution of
data changes, e.g., the parameters of the signal generating distribution
change from $\theta_{0}$ to $\theta_{1}$. Most change point detection methods
rely on hypothesis tests based on the log-likelihood ratio. Specifically,
suppose we are given observations $x_{0},\ldots,x_{t}$ of a time series $X$.
We will assume that each element $x_{i}$ is drawn independently from a
distribution $f_{\theta}$ where $\theta$ represents some (possibly changing)
parameters. To detect a change we compare the null hypothesis
($\mathcal{H}_{0}$) that all $x_{i}$ are drawn according to $f_{\theta_{0}}$
for some (known) $\theta_{0}$ to the alternate hypothesis ($\mathcal{H}_{1}$)
that the time series distribution changes from $f_{\theta_{0}}$ to
$f_{\theta_{1}}$, at time $n_{c}$, for some $\theta_{1}\neq\theta_{0}$.

The likelihood of $X$ under these two hypotheses is given by:

$\displaystyle\mathcal{L}(\mathcal{H}_{0}|X)$
$\displaystyle=\prod_{i=1}^{t}f_{\theta_{0}}(x_{i})$
$\displaystyle\mathcal{L}(\mathcal{H}_{1}|X)$
$\displaystyle=\prod_{i=1}^{{n_{c}}-1}f_{\theta_{0}}(x_{i})\prod_{i=n_{c}}^{t}f_{\theta_{1}}(x_{i}).$

By computing the likelihood ratio and taking the logarithm, we obtain the
likelihood-ratio statistic at instance $t$ for a change at $n_{c}$:

$\ell^{t}_{n_{c}}=\sum_{{i=n_{c}}}^{t}\log\frac{f_{\theta_{1}}(x_{i})}{f_{\theta_{0}}(x_{i})}.$

Since the location of the change point $n_{c}$ is unknown, the maximum over
all possible change point locations is taken to compute the change statistic
at instance $t$:

$\ell^{t}=\mathop{\max}_{1<n_{c}<t}\ell_{n_{c}}^{t}.$ (1)

A change point is detected the first time the change statistic $\ell^{t}$ is
greater than a specified threshold $b$. For a sequence of i.i.d. random
variables, the sum of the log-likelihood probability ratio between
distributions $\theta_{1}$ and $\theta_{0}$ satisfies an intuitive property:
if a sequence is generated through a post-change distribution, the expected
value of this sum should be positive. If the sequence is generated through the
pre-change distribution, this sum should be negative. Concretely speaking, if
we represent his log-likelihood ratio as

$\ell^{t}_{1}=\sum_{{i=1}}^{t}\log\frac{f_{\theta_{1}}(x_{i})}{f_{\theta_{0}}(x_{i})},$

then $\mathbb{E}_{\theta_{1}}(\ell^{t}_{1})>0$ and
$\mathbb{E}_{\theta_{0}}(\ell^{t}_{1})<0$. In (1), we are maximizing over
$n_{c}$ to find the maximum log-likelihood ratio. Instead of maximizing (1)
with respect to $n_{c}$, we can also maximize the log-likelihood ratio by
minimizing, over $n_{c}$, the expression:

$\ell^{t}=\sum_{{i=1}}^{t}\log\frac{f_{\theta_{1}}(x_{i})}{f_{\theta_{0}}(x_{i})}-\mathop{\min}_{1<n_{c}<t}\sum_{{i=1}}^{n_{c}}\log\frac{f_{\theta_{1}}(x_{i})}{f_{\theta_{0}}(x_{i})}.$
(2)

The CUSUM statistic [20] provides a computationally attractive recursive
implementation of the test in (2). It assumes both pre-change parameters
$\theta_{0}$ and post-change $\theta_{1}$ distribution parameters are known.
In such a setting, a recursive implementation of (2) can be obtained as shown
below in (3) :

$\displaystyle S_{t}$
$\displaystyle=\left(S_{t-1}+\log\frac{f_{\theta_{1}}(x_{t})}{f_{\theta_{0}}(x_{t})}\right)^{+},$
(3)

where $(S_{t-1})^{+}=\max(0,S_{t-1})$ and $S_{0}=0$. A change is detected at
the first instance, $n_{c}$, where the corresponding change statistic $S_{t}$
is greater than a set threshold $b$. This is made concrete in the equation
below:

$n_{c}=\inf(t>0:S_{t}>b).$

The post-change distribution is often unknown in real-world settings. In such
cases, the GLR [21] can be used to obtain the change statistic $\ell_{t}$. GLR
maximizes the change statistic in (4) over both the post-change distribution,
$\theta_{t}$ at instance $t$, as well as the change instance $n_{c}$. Let

$\ell^{t}_{n_{c}}:=\max_{\theta_{t}}\sum_{{i={n_{c}}}}^{t}\log\frac{f_{\theta_{t}}(x_{i})}{f_{\theta_{0}}(x_{i})}.$

Define

$\ell^{t}=\max_{1<n_{c}<t}\ell_{t}^{n_{c}}.$ (4)

This is done by first choosing a possible change instance, $n_{c}$, and
finding the maximum likelihood estimate (MLE) $\hat{\theta}_{t}^{n_{c}}$ for
(4). This MLE estimate is used to obtain a possible change statistic,
$\ell_{n_{c}}^{t}$, corresponding to a change at $n_{c}$. This is repeated for
all possible change instances before $t$, and the maximum of these is taken as
the change statistic $\ell^{t}$ at time $t$.

Once the change statistic, $\ell_{t}$, crosses the threshold $b$, a change is
detected, and the corresponding post-change estimate
$\hat{\theta}_{t}^{n_{c}}$ is used as the new pre-change estimate $\theta_{0}$
and the sequential change point detection procedure is repeated to detect the
next change. This way _multiple_ change points are detected. It is important
to point out that the GLR procedure is non-recursive and can be
computationally expensive to run.

###  3.1 Asymmetry of log-likelihood ratio

The log-likelihood ratio statistic, employed by both GLR and CUSUM, is quick
to react to changes but is an asymmetric statistic for detecting joint changes
in mean and variance. Figure 1 illustrates this asymmetry. This difference
gets more pronounced when one of the two distributions has a much smaller
variance.

(a) $\mathcal{N}(1,1)\rightarrow\mathcal{N}(10,3)$

(b) $\mathcal{N}(10,3)\rightarrow\mathcal{N}(1,1)$

Figure 1: Joint changes in mean variance lead to asymmetric Likelihood Ratios.
In Figure 1(a), the pre-change likelihood is in the tail, leading to a large
likelihood ratio. In Figure 1(b), the post-change likelihood is higher than it
is in Figure 1(a), leading to a relatively smaller likelihood ratio

Figure 2 shows a real-world example where this asymmetry makes it difficult
for GLR to detect multiple change points. The log-likelihood ratio for the
first change point is much larger than the log-likelihood ratio for the second
change point. This makes it difficult to set a detection threshold _a priori_
to detect multiple change points in a streaming data setting. In the first
figure, the fixed detection threshold results in missing the second change
point, which has a much smaller statistic. A reduction in the detection
threshold leads to many false change point detections, which can be seen in
the second figure.

(a) Missed change point

(b) False change point

Figure 2: Joint changes in mean variance lead to asymmetric likelihood ratio.
In Figure 2(a), the likelihood ratio (in GLR) for the second change is much
smaller than the likelihood for the first change. This can lead to a missed
change point when the detection threshold is set to be large. When the
detection threshold is lowered to detect this missed change point, many false
change points are detected, which can be seen in Figure 2(b).

##  4 Data-adaptive symmetric CUSUM (DAS-CUSUM)

###  4.1 Adaptive post-change estimation

When the post-change distribution is not known, another way to estimate the
post-change distribution is to use a window of size $w$ to estimate the post-
change parameters $\hat{\theta}_{t}$ at time $t$ for the CUSUM statistic
$S_{t}$. The same approach is used in [24] where a window is used to estimate
post-change distribution change distribution for subspace change detection.
Figure 3 shows how this update is done.

For normally distributed i.i.d. data, the post-change distribution estimate
$\hat{\theta}_{t}=(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})$ at time $t$ is
calculated via:

$\hat{\mu}_{t}=\sum_{i=t+1}^{t+w}x_{i},\quad\hat{\sigma}_{t}^{2}=\sum_{i=t+1}^{t+w}\frac{1}{w}(x_{i}-\hat{\mu}_{t})^{2}.$

Figure 3: Adaptive version of CUSUM. Using a “future” window to estimate post-
change parameters $\hat{\theta}_{t}$, which could be used in place of post-
change distribution $\theta_{1}$ for CUSUM update.

Using “future” samples to calculate post-change estimates $\hat{\theta}_{t}$
may seem unreasonable at first, but detection decisions can be delayed by $w$
samples so that data is available for calculating these estimates (provided,
of course, that $w$ is not excessively large). These estimates can be
substituted for $\theta_{1}$ in (3) to obtain an adaptive form of CUSUM where
the post-change distribution is estimated. Such estimates are also independent
of the change statistic $S_{t}$. In comparison to GLR, adaptive CUSUM leads to
a more computationally efficient method for detecting change points when the
post-change distribution is unknown. CUSUM has been extensively studied to
develop tools that characterize the detection average run length (ARL), which
is the average time till false detection under the pre-change distribution,
and the expected detection delay (EDD), which is the expected time till true
detection under the post-change distribution. Adaptive CUSUM can utilize the
same tools to characterize the ARL and EDD performance.

###  4.2 Proposed procedure

As discussed in Section 3.1, the log-likelihood ratio test is asymmetric for
changes between two distributions having different variances. This makes it
difficult to select a single threshold for adaptive CUSUM to detect multiple
changes.

To solve this problem, we introduce a symmetric version of adaptive CUSUM that
we call DAS-CUSUM. The DAS-CUSUM based change detection procedure is given
below:

$\displaystyle S_{t}$ $\displaystyle=(S_{t-1})^{+}+s_{t}$
$\displaystyle=(S_{t-1})^{+}+\log{\frac{f_{\hat{\theta}_{t}}(x_{i})}{f_{\theta_{0}}(x_{i})}}-\mathbb{E}_{\theta_{0}}\big{(}\log\frac{f_{\hat{\theta}_{t}}(x_{i})}{f_{\theta_{0}}(x_{i})}\big{)}-v$
$\displaystyle=(S_{t-1})^{+}+\log{\frac{f_{\hat{\theta}_{t}}(x_{i})}{f_{\theta_{0}}(x_{i})}}+D_{\rm
KL}(f_{\theta_{0}}(x),f_{\hat{\theta}_{t}}(x))-v.$ (5)

Here, the incremental update statistic is given by:

$s_{t}=\log{\frac{f_{\hat{\theta}_{t}}(x_{i})}{f_{\theta_{0}}(x_{i})}}+D_{KL}(f_{\theta_{0}}(x),f_{\hat{\theta}_{t}}(x))-v,$
(6)

where $D_{\rm KL}(f_{\theta_{0}}(x),f_{\hat{\theta}_{t}}(x)))$ represents the
term to ensure symmetry of the statistic (for either “direction” of change),
and $v>0$ is the drift term.

Compared to the incremental update for CUSUM, which only contains the log-
likelihood ratio, the DAS-CUSUM update statistic contains two additional
terms, which can be seen in (6). The first of these terms is a KL divergence
which makes the incremental statistic almost symmetric under the post-change
distribution. When $v$ is much smaller than the sum of two divergences, the
expected value is almost the same for changes from distribution $\theta_{0}$
to $\theta_{1}$ and vice versa:

$\mathbb{E}_{\theta_{1}}[s_{t}]=D_{\rm KL}(\theta_{1},\theta_{0})+D_{\rm
KL}(\theta_{0},\theta_{1})-v.$ (7)

The second of these additional terms, $v$, is a drift term that makes the
expectation of the incremental statistic negative under the pre-change
distribution. This allows our proposed statistic to match the property of
CUSUM, which requires that the incremental statistic should be negative under
the pre-change distribution to avoid detecting false change points, i.e.,

$\mathbb{E}_{\theta_{0}}[s_{t}]=-v.$

###  4.3 Practical implementation

Algorithm 1 shows how to implement DAS-CUSUM for detecting multiple change
points. This algorithm uses values for the window size $w^{*}$ and drift term
$v^{*}$, which are based on theoretical results presented in Section 5. These
results, however, require complete knowledge of the post-change distribution
$\theta_{1}$ to compute the symmetric KL divergence $s$ which is needed to
compute the desired values for $w^{*}$ and $v^{*}$. Since this post-change
distribution is unknown, we can set a minimum symmetric KL divergence
$s^{\prime}$, which corresponds to the minimum change in distribution that is
to be detected in a streaming data setting. This minimum symmetric KL
divergence can be used to set values of window size $w^{*}$ and drift term
$v^{*}$. The optimal window size $w^{*}$ can be found by minimizing an
expression. This expression is discussed in more detail in Remark 5.2. Despite
this expression being convex with respect to $w$, a closed-form expression of
$w^{*}$ is difficult to obtain. This optimal window size $w^{*}$ can be solved
numerically. When a change point is detected, the previous post-change
estimate $\hat{\theta}_{t}$ is used as the pre-change distribution
$\theta_{0}$ for detecting the subsequent change point.

Algorithm 1 DAS-CUSUM for multiple change point detection

Inputs: Sequence: $X$, Threshold $b$, Target ARL: $\gamma$, Min sym div:
$s^{\prime}$, Pre-change dist :$\theta_{0}{(\mu_{0},\sigma_{0}^{2})}$

Output CpList : List containing change points

Choose window size  $\displaystyle w^{*}$
$\displaystyle=\mathop{\text{arg\,min}}_{w}\frac{\log\gamma}{-1+(1+ws^{\prime
2})^{\frac{1}{2}}+\log\left(1-\frac{\left(-1+(1+ws^{\prime
2})^{\frac{1}{2}}\right)^{2}}{ws^{\prime 2}}\right)}+w$
$\displaystyle\delta_{0}^{*}$
$\displaystyle=-\frac{1}{s^{\prime}}+\left(\frac{1}{s^{\prime
2}}+w^{*}\right)^{1/2},\quad
v*=\frac{-\log(1-\frac{{\delta_{0}^{*}}^{2}}{w})}{\delta_{0}^{*}}$

for $t=1\text{ to length}(X)]$ do

$\hat{\mu}_{t}=\sum_{i=t+1}^{t+w}x_{i},\quad\hat{\sigma}_{t}^{2}=\sum_{i=t+1}^{t+w}\frac{1}{w}(x_{i}-\hat{\mu}_{t})^{2},\quad\hat{\theta}_{t}=\\{\hat{\mu}_{t},\hat{\sigma}^{2}_{t}\\}$

Compute CUSUM recursion
$S_{t}=(S_{t-1})^{+}+\log{\frac{f_{\hat{\theta}_{t}}(x_{i})}{f_{\theta_{0}}(x_{i})}}+D_{\rm
KL}(f_{\theta_{0}}(x),f_{\hat{\theta}_{t}}(x))-v^{*}$

if $S_{t}>b$ then

Add $t$ to CpList

$\mu_{0}=\hat{\mu}_{t},\quad\sigma_{0}^{2}=\hat{\sigma}^{2}_{t}$

end if

end for

##  5 Theoretical results: EDD versus ARL

When our detection delay takes $T$ samples to detect a change, the average run
length (ARL) is the expected value of $T$ under the pre-change distribution
$\theta_{0}$ such that a false change is detected. Expected detection delay
(EDD) is the expected value of $T$ under the post-change distribution
$\theta_{1}$ such that a true change point is detected. Our first result
relates DAS-CUSUM’s average run length with its expected detection delay.
Similar analysis techniques have been done in [26, 25].

######  Theorem 5.1.

Let $f_{\theta_{0}}(x)$ and $f_{\theta_{1}}(x)$ be the Gaussian probability
density functions of $x$ under the pre-change distribution $\theta_{0}$ and
post-change distribution $\theta_{1}$ which is unknown and estimated using a
window of size $w$. $D_{\rm KL}(f_{\theta_{1}}(x),f_{\theta_{0}}(x))$ is the
Kullback-Leibler divergence between these distributions and $\delta_{0}>0$ .
For the proposed statistic, the asymptotic(as $w$ becomes large) expected
detection delay (EDD) for a change from $x\sim\mathcal{N}(\theta_{0})$ to
$x\sim\mathcal{N}(\theta_{1})$ at an average run length (ARL) $\gamma$, with
$\gamma\rightarrow\infty$ is given by:

$\displaystyle\mathbb{E}_{\theta_{1}}[T]$
$\displaystyle=\frac{\log\gamma+o(1)}{\delta_{0}\left(D_{\rm
KL}(\theta_{1},\theta_{0})+D_{\rm
KL}(\theta_{0},\theta_{1})\right)+\log(1-\frac{{\delta_{0}}^{2}}{w})}+w.$

######  Corollary 5.1.

The value of $\delta_{0}$ that minimizes the expected detection delay for a
given average run length in Theorem 5.1 is given by:

$\displaystyle{\delta_{0}^{*}=-\frac{1}{(D_{KL}(\theta_{0},\theta_{1})+D_{\rm
KL}(\theta_{1},\theta_{0})}+\left(\frac{1}{\left((D_{\rm
KL}(\theta_{0},\theta_{1})+D_{\rm
KL}(\theta_{1},\theta_{0})\right)^{2}}+w\right)^{1/2}.}$

######  Remark 5.1.

The value of $\delta_{0}^{*}$ from Corollary 5.1 can be used in the result of
Theorem 5.1 to obtain the minimum EDD for a given ARL.

######  Corollary 5.2.

The optimal drift term $v^{*}$ which minimizes the expected detection delay
for any ARL is given by

$v^{*}=\frac{-\log(1-\frac{\delta_{0}^{*}{{}^{2}}}{w})}{\delta_{0}^{*}}.$

######  Remark 5.2.

The expression in Theorem 5.1 can be minimized with respect to $w$ (at a
provided value of average run length and symmetric KL divergence) to find the
optimal window size $w^{*}$. A closed-form expression for $w^{*}$ cannot be
obtained, but $w^{*}$ can be solved numerically. Figure 4 shows how EDD
relates to window size $w$. The curve has a minimum point which corresponds to
a window size of $w=11$. When this solution is too small, the results in
Theorem 5.1 do not hold, which assume $w$ to be large (so that post-change
estimates converge to true post-change distribution). More details on this can
be found in Section 6.2. Additionally, the window size should be large enough
such that $\delta_{0}^{*}<w$ for the logarithmic term in Theorem 5.1 to be
real.

Figure 4: Expected detection delay (EDD) versus window size for a change with
symmetric KL divergence of 0.5 at an ARL value of 5,000. This figure shows
that the EDD is a convex function of $w$ which can be minimized to obtain the
optimal window $w^{*}$.

###  5.1 Comparison to CUSUM results

The relationship between ARL ($\gamma$) and EDD ($\mathbb{E}_{\theta_{1}}(T)$
for CUSUM [18] is shown below:

$\mathbb{E}_{\theta_{1}}(T)=\frac{\log\gamma(1+o(1))}{\mathbb{E}_{\theta_{1}}\left[\log\frac{f_{\theta_{1}}(x)}{f_{\theta_{0}}(x)}\right]}.$

For the proposed statistic, it can be seen in Theorem 5.1 that the expected
detection delay at a set ARL value would be similar for a change from
$\theta_{0}$ to $\theta_{1}$ and a change from $\theta_{1}$ to $\theta_{0}$.
This is not true for CUSUM, where the detection delay for a change from
$\theta_{0}$ to $\theta_{1}$ will not be equal to a change from $\theta_{1}$
to $\theta_{0}$.

The expression in Theorem 1 also has an additional $w$ term, which takes into
account the time delay for obtaining the window to estimate post-change
parameters, but this is a consequence of the post-change distribution is
unknown.

###  5.2 Sketch of the Proof

The increment of the CUSUM statistic in (3) consists of a log-likelihood ratio
which has a negative expectation under the pre-change distribution
$\theta_{0}$. The proposed increment statistic for DAS-CUSUM in (6) has a
negative drift under the post-change distribution but is not a log-likelihood
ratio. One way to find the optimal value $v$ in our proposed update statistic
is to convert it into a valid log-likelihood ratio. Once this is done, ARL and
EDD results from CUSUM can be used for our proposed statistic. This expression
would consist of the negative drift term $v$, which could be minimized to find
the optimal value for $v$. It can been seen in [18] that for a detection
threshold $b$ , the CUSUM procedure has the following average run length:

$\mathbb{E}_{0}[T]=\frac{e^{b}(1+o(1))}{K},$ (8)

where $K$ is a constant. For CUSUM, the expected detection delay is related to
the detection threshold $b$ by

$\mathbb{E}_{\theta_{1}}(T)=\frac{b+o(1)}{\mathbb{E}_{\theta_{1}}\left[\log\frac{f_{\theta_{1}}(x)}{f_{\theta_{0}}(x)}\right]}.$
(9)

Using the tools proposed in [24], an equivalence term $\delta_{0}$ can be
introduced to our incremental statistic, which satisfies the equation

$\mathbb{E}_{\theta_{0}}[\exp({\delta_{0}{s}_{t}})]=1.$ (10)

When (10) is satisfied, $\delta_{0}s_{t}$ is a martingale and can be
considered to be the log-likelihood ratio between distributions
$\tilde{f}_{\theta_{1}}=\exp[{\delta_{0}s_{t}}]f_{\theta_{0}}$ and
$f_{\theta_{0}}$ which then allows us to use (8) to obtain the ARL performance
for DAS-CUSUM. The threshold $b$ can be expressed in terms of the average run
length ($\gamma$)

$b=\frac{\log\gamma+o(1)}{\delta_{0}}.$ (11)

This expression is obtained through (8) where the constant $K$ is absorbed
within $o(1)$ and the introduced scaling factor $\delta_{0}$ for the
incremental statistic is appropriately scaled. Similarly, $\delta_{1}$ can be
introduced such that $\delta_{1}s_{t}$ is the log-likelihood ratio between
$f_{\theta_{1}}$ and
$\tilde{f}_{\theta_{0}}=\exp[-{\delta_{1}s_{t}}]f_{\theta_{1}}$. Thus (9) can
be used to relate change between $f_{\theta_{1}}$, where the $\delta_{1}$ term
is observed in $o(1)$ as shown below:

$\mathbb{E}_{\theta_{1}}(T)=\frac{b+o(1)}{\mathbb{E}_{\theta_{1}}\left[s_{t}\right]}.$
(12)

Substituting (11) in the above equation, we obtain

$\mathbb{E}_{\theta_{1}}(T)=\frac{\log\gamma+o(1)}{\delta_{0}\mathbb{E}_{\theta_{1}}\left[s_{t}\right]}.$
(13)

Substituting (7) yields

$\mathbb{E}_{\theta_{1}}(T)=\frac{\log\gamma+o(1)}{\delta_{0}\left(D_{\rm
KL}(\theta_{0},\theta_{1})+D_{\rm KL}(\theta_{1},\theta_{0})-v\right)}.$ (14)

Our expression above assumes that our statistic is converted to a log-
likelihood ratio by satisfying the martingale property in (10). Lemma 15
satisfies this requirement by finding an expression that relates the drift
value $v$ with the equivalence factor $\delta_{0}$

######  Lemma 5.1.

As
$w\xrightarrow{}\infty,\mathbb{E}_{\theta_{0}}[\exp({\delta_{0}{s}_{t}})]=1$
when

$v=\frac{-\log(1-\frac{\delta_{0}{{}^{2}}}{w})}{\delta_{0}}.$ (15)

The value for $v$, for which (10) is satisfied, can be substituted. As $w$
samples are needed to estimate the post-change distribution
$\hat{\theta_{t}}$, the detection delay would be

$\mathbb{E}_{\theta_{1}}(T)=\frac{\log\gamma+o(1)}{\delta_{0}\left(D_{KL}(\theta_{0},\theta_{1})+D_{KL}(\theta_{1},\theta_{0})\right)+\log(1-\frac{\delta_{0}{{}^{2}}}{w})}+w.$
(16)

This expression can be minimized with respect to $\delta_{0}$ by taking the
derivative and equating to 0. The resulting optimal value of $\delta_{0}^{*}$.
is given below:

$\delta_{0}^{*}=-\frac{1}{(D_{KL}(\theta_{0},\theta_{1})+D_{KL}(\theta_{1},\theta_{0})}+\left(\frac{1}{\left((D_{KL}(\theta_{0},\theta_{1})+D_{KL}(\theta_{1},\theta_{0})\right)^{2}}+n\right)^{1/2}.$
(17)

Using this optimal value of $\delta_{0}$ in (16) and (15) leads to the results
of Theorem 5.1 and Corollary 5.2.

####  5.2.1 Sketch of Proof for Lemma 1

The left side of (10) can be written as shown below by substituting the
proposed update statistic from (6):

$\mathbb{E}_{\theta_{0}}\left[\exp({\delta_{0}\tilde{s}_{t}})\right]=\mathbb{E}_{\theta_{0}}\left[\exp\left(\delta_{0}\left(-\frac{(x_{t}-\hat{\mu}_{t})^{2}}{2\hat{\sigma}_{t}^{2}}+\frac{(x_{t}-\mu_{0})^{2}}{2\sigma_{0}^{2}}+\frac{\sigma_{0}^{2}+(\mu_{0}-\hat{\mu}_{t})^{2}}{2\hat{\sigma}_{t}^{2}}-\frac{1}{2}-v\right)\right)\right].$

Since a future window ($x_{t+1}....x_{t+w}$) is used to estimate
$\hat{\mu}_{t}$ and $\hat{\sigma}_{t}$, these estimates are independent from
$x_{t}$. These estimates can be treated as constants while introducing a
conditional expectation through the tower rule. The equation above can be
written as

$\displaystyle\mathbb{E}_{x_{t+1,...,t+w}\sim\theta_{0}}\left[\exp\left(\delta_{0}\left(\frac{\sigma_{0}^{2}+(\mu_{0}-\hat{\mu}_{t})^{2}}{2\hat{\sigma}_{t}^{2}}-\frac{1}{2}-v\right)\right)\mathbb{E}_{x_{t}\sim\theta_{0}}\left[r(x_{t})\Big{|}\hat{\mu}_{t},\hat{\sigma}_{t}\right]\right]$
$\displaystyle=\exp(\delta_{0}(-\frac{1}{2}-v))\mathbb{E}_{\mathop{x}_{t+1,..,t+w}\sim\theta_{0}}\left[\exp\left(\delta_{0}\left(\frac{\sigma_{0}^{2}+(\mu_{0}-\hat{\mu})^{2}}{2\hat{\sigma}_{t}^{2}}\right)\right)\mathbb{E}_{x_{t}\sim\theta_{0}}\left[r\left(x_{t}\right)\Big{|}\hat{\mu}_{t},\hat{\sigma}_{t}\right]\right],$
(18)

where

$r\left(x_{t}\right)=\exp\left(\delta_{0}\left(-\frac{(x_{t}-\hat{\mu}_{t})^{2}}{2\hat{\sigma}_{t}^{2}}+\frac{(x_{t}-\mu_{0})^{2}}{2\sigma_{0}^{2}}\right)\right).$

Further details for these calculations can be found in the Appendix.

##  6 Simulations

###  6.1 ARL and EDD

As discussed in Section 4.2, the DAS-CUSUM change point detection procedure is
designed to have a symmetric change statistic. Due to this symmetric property,
DAS-CUSUM should have similar ARL versus EDD performance for changes from the
distribution $\theta_{0}$ to $\theta_{1}$ and from $\theta_{1}$ to
$\theta_{0}$. This symmetry is studied in ARL versus EDD plots in Figure 5.
This figure also contains plots for CUSUM and an adaptive version of CUSUM
where a future window of size $w$ is used to estimate the post-change
parameters. CUSUM curves for changes from
$\theta_{0}(\mu_{0}=1,\sigma_{0}^{2}=1)$ to
$\theta_{1}(\mu_{1}=2,\sigma_{1}^{2}=2)$ and $\theta_{1}$ to $\theta_{0}$ are
far away from one another, while DAS-CUSUM curves are closer to each other.
These DAS-CUSUM curves become closer when the post-change estimates become
more accurate with an increasing window size, as shown in Figure 5(b). These
results are is in line with Section 5.1, which compares the results of DAS-
CUSUM in Theorem 5.1 with corresponding results for CUSUM. Specifically, EDD
at a given ARL is the same for a change from $\theta_{0}$ to $\theta_{1}$ and
vice versa when the window length $w$ becomes asymptotically large.

(a)

(b)

Figure 5: EDD versus ARL performance comparison for DAS-CUSUM and CUSUM for
changes between $\theta_{0}(\mu_{0}=1,\sigma_{0}^{2}=1)$ and
$\theta_{1}(\mu_{1}=2,\sigma_{1}^{2}=2)$ which corresponds to a symmetric KL
divergence of 1. Figure 5(a) shows the relationship when a window size of 10
is used for the post-change estimate. while Figure 5(b) shows the case when
the window size is 40. Notice the similar performance for DAS-CUSUM for
changes from $\theta_{0}$ to $\theta_{1}$ and $\theta_{1}$ to $\theta_{0}$.
This similarity increases with window size $w$.

Now we validate the accuracy of theoretical approximation by comparing it
against simulation results. Figure 6 shows DAS-CUSUM plots for EDD versus ARL
at different window lengths ($w$ to estimate post-change distribution). For
each window length, plots for the theoretical relationship (from Theorem 5.1)
are compared to simulated plots. For a small window size ($w=10$), the
theoretical and simulated results grow apart as ARL increases. The difference
between the theoretical and simulated plots decreases as the window size
increases. This is expected as the results in Theorem 5.1 hold when $w$ grows
asymptotically. When $w=120$, the difference between theoretical and simulated
EDD is approximately 1 sample for the shown ARL range.

Figure 6: Comparison between theoretical and simulated DAS-CUSUM results for
different post-change estimation window sizes $w$. The change in this example
has a symmetric KL divergence of 1.

###  6.2 Optimal window length

DAS-CUSUM results that relate EDD with ARL in Theorem 5.1 depend on the
estimation window size $w$ (at provided values of ARL and symmetric KL
divergence). This equation can be minimized for $w$ to find the optimal window
length ($w^{*}$). Unfortunately, there is no closed-form expression for this
optimal value. Nevertheless, this equation can be minimized numerically to
obtain $w^{*}$. Figure 7(a) shows this relationship at an ARL of 5,000 for
changes with two different symmetric KL divergence values.

Figure 7(a) shows this relationship for a smaller change in distribution (a
symmetric diverge of 0.11), while Figure 7(a) shows this relationship for a
larger change (a symmetric KL divergence of 2). Intuitively, a larger change
(with a larger symmetric KL divergence) would be easier to detect, requiring a
shorter window length as compared to a smaller change (with a smaller
symmetric KL divergence). However, for larger changes, the window size
corresponding to the minimum EDD value could be too small, as seen in Figure
7(a) where this window is of size 4. The theoretical results start to match
simulated results at a window size of about 30 while results at a window size
of 10 divergences. For this reason, when the optimal window size ($w^{*})$ is
below 20, a rule should be in place for a minimum window size.

(a)

Figure 7:  Relation between EDD and window size for changes with different
symmetric KL divergence. The ARL has been set to 5,000 in both figures. The
optimal window size corresponds to the minimum EDD values. Figure 7 shows the
relationship for a change with symmetric KL divergence of 1 while 7(a) shows
the relationship for a symmetric KL divergence of 2

.

Results that relate the optimal window length for different ARL values can be
seen in Figure 7(a). The changes in this figure have small divergence values,
which lead to $w^{*}$ that is greater than a size of 20. The curves for
$w^{*}$ are in yellow and seem to provide better EDD versus ARL performance
than most other window sizes. As the optimal window size, $w^{*}$ increases in
Figure 8(a), the corresponding ARL versus EDD curve often performs best (or
close to best) when compared with other window sizes.

(a)

Figure 8:  ARL versus EDD performance for different window length ($w$) sizes.
Figures 8 shows plots for a change from
$\theta_{0}(\mu_{0}=1,\sigma_{0}^{2}=1)$ to
$\theta_{1}(\mu_{1}=1.3,\sigma_{1}^{2}=1.3)$ and 8(a) shows plots for changes
from $\theta_{0}(\mu_{0}=1,\sigma_{0}^{2}=1)$ to
$\theta_{1}(\mu_{1}=1.2,\sigma_{1}^{2}=1.2)$. Optimal window size ($w^{*}$)
provides optimal performance as $w^{*}$ increases.

###  6.3 Setting the detection threshold

The table below compares the simulated and theoretical detection threshold
($b$) to achieve different ARL values. The theoretical relationship between
ARL and the detection threshold is provided in (11). These experiments were
done on a distribution change from $\theta_{0}(\mu_{0}=1,\sigma_{0}^{2}=1)$ to
$\theta_{1}(\mu_{1}=2,\sigma_{1}^{2}=2)$ which corresponds to a symmetric KL
divergence of 1. For ARL, false alarms occur when data points generated from
pre-change distribution ($\theta_{0}$) is falsely detected as change points.
Intuitively ARL values should depend only on the pre-change $\theta_{0}$ but
the post-change distribution ($\theta_{1}$) is used to set the
$\delta_{0}^{*}$ value, which is used within the theoretical (11) as well as
for setting the drift term $v$ for the simulations. The difference between
theoretical and simulated results is large for small values of post-change
estimate window $w$, but these results become closer as this window size
increases. This is expected as the relationship between the detection
threshold, and average run length is obtained using (10), which is satisfied
asymptotically.

Table 1: Comparison between theoretical and simulated detection thresholds at different ARL values for a change with symmetric KL -divergence of 1 |  | $w=10$ | $w=20$ | $w=30$ | $w=40$ | $w=50$ | $w=100$ | $w=150$
---|---|---|---|---|---|---|---|---
ARL = 5,000 | Thr. | 3.68 | 2.38 | 1.86 | 1.57 | 1.37 | 0.94 | 0.75
| Sim. | 14.77 | 6.10 | 3.16 | 2.13 | 1.69 | 1.01 | 0.77
ARL = 10,000 | Thr. | 3.98 | 2.57 | 2.02 | 1.70 | 1.50 | 1.02 | 0.82
| Sim. | 18.16 | 7.91 | 4.13 | 2.70 | 2.11 | 1.26 | 0.96

(a)

Figure 9: Plots for results in table 1. Figure 9 shows the relationship for an
ARL value of 5,000 while Figure 9(a) shows the relationship for an ARL of
10,000.. The gap between simulation and theoretical results gets small at a
window value of about 30.

##  7 Real data

Due to its symmetric statistic for detecting changes between two
distributions, DAS-CUSUM is more useful for detecting multiple changes as
compared to GLR and Adaptive CUSUM. This is favorable for detecting multiple
changes in real-world problems, as seen in Figure 11. which shows readings
from a pressure mat that can be seen in Figure 10. The mat is inserted beneath
a wheelchair cushion and is used to characterize in-seat movement for
wheelchair users. When the wheelchair is occupied, the sensor signal has a
high mean and variance, whereas when the chair is unoccupied, the signal has a
low mean and variance. Detecting changes in occupancy can be treated as a
change detection problem. As discussed previously, the asymmetric log-
likelihood ratio makes it difficult for both GLR and adaptive CUSUM to detect
these changes.

Figure 10: Sensor mat used for characterizing in-seat behaviour for wheelchair
users. Sequential change point detection can be used to identify changes in
wheelchair occupancy.

For both Figure 11 and Figure 2, the statistic for getting into the chair (low
variance to high variance) is not equal to the statistic for getting out of
the chair. For this reason, it is difficult to select a threshold that detects
both changes. It can be seen that there is a larger delay in detecting the
change while still detecting a false positive change point. Because of the
asymmetric statistics, the change for the first statistic is extremely large
as compared to the second change. To detect both changes, a lower threshold is
set, which causes the first change to be detected really quickly (where the
signal is in the middle of the transition). This causes incorrect signal
estimates to be used as pre-change estimates causing false change points to be
detected. Figure 11(a) shows the performance of DAS-CUSUM on this signal. The
symmetric change statistic provides similar power for detecting both changes
without detecting any false positive changes. The symmetric statistic makes it
easy to select a threshold to detect multiple changes. This is attractive for
real-world scenarios where numerous changes need to be detected when signal
changes to unforeseen distributions.

(a)

Figure 11: Figures 11 shows performance and 11(a) show the advantages of using
DAS-CUSUM for multiple changes over adaptive CUSUM

Figure 12 provides an extended example of the occupancy problem. The signal
sensors develop drift, and the post-change distribution can change to
different unknown distributions at different times. This makes it difficult to
use 2-sided CUSUM or other variants as the post-change distribution is not
known. In such an example, it can be seen that with symmetric statistics, DAS-
CUSUM performs much better than GLR and adaptive CUSUM. The in-chair
distribution is not static. The mean and the variance of the signal changes
within the chair, however, these changes are much smaller than the changes in
distribution when there is a change in wheelchair occupancy. Symmetric DAS-
CUSUM’s change statistic is much larger for these occupancy change events,
which makes it easy to detect these events without detecting any false alarms.
For all methods, a window size of 300 was to estimate the post-change
distribution.

(a) Adaptive CUSUM misses true change points

(b) GLR misses true change points

(c) Adaptive CUSUM detects false change points

(d) GLR detects false change points

(e) DAS-CUSUM correctly detects true change points

Figure 12: Comparison of GLR, Adaptive CUSUM, and DAS-CUSUM for detecting
multiple change points. The asymmetric log-likelihood ratio makes it difficult
for CUSUM and GLR to detect all changes correctly without any false alarms. In
Figures 12(a) and 12(b), a large detection threshold to avoid false change
points results in many change missed change points while still detecting a few
false change points. Figures 12(c) 12(d) show how a lower threshold results in
many false change points. The symmetric DAS-CUSUM is able to correctly detect
all true change points without detecting any false change points

##  8 Conclusion

In this work, we have presented DAS-CUSUM, which is a symmetric change point
detection procedure. Due to DAS-CUSUM’s symmetric incremental statistic, the
EDD versus ARL relationship is the same for changes from a distribution
$\theta_{0}$ to $\theta_{1}$ and from $\theta_{1}$ to $\theta_{0}$. This
symmetric change statistic is helpful when identifying multiple changes in
both the mean and variance of a signal. A single threshold can be easily set
to detect multiple change points. This is extremely helpful for identifying
change points in real-world settings where log-likelihood ratio-based
approaches such as GLR and adaptive CUSUM struggle. We have derived results
that characterize DAS-CUSUM’s expected detection delay (EDD) and average run
length (ARL). Extensive simulations are used to validate these results.

## References

  * [1] Yousef Al-Assaf.  Surface myoelectric signal analysis: dynamic approaches for change detection and classification.  IEEE. Trans. Biomed. Eng., 53(11):2248–2256, 2006.
  * [2] Cesare Alippi, Giacomo Boracchi, Diego Carrera, and Manuel Roveri.  Change detection in multivariate datastreams: likelihood and detectability loss.  In Proc. Int. Joint Conf. on Artif. Intelligence (IJCAI), 2016.
  * [3] Samaneh Aminikhanghahi and Diane Cook.  A survey of methods for time series change point detection.  Knowl. Inf. Syst., 51(2):339–367, 2017.
  * [4] Samaneh Aminikhanghahi and Diane Cook.  Using change point detection to automate daily activity segmentation.  In Proc. IEEE Int. Conf. on Perv. Comp. and Comm. Workshops (PerCom Workshops), 2017.
  * [5] Regine Andre-Obrecht.  A new statistical approach for the automatic segmentation of continuous speech signals.  IEEE Trans. Accous. Speech. Signal Process., 36(1):29–40, 1988\.
  * [6] Michele Basseville and Albert Benveniste.  Sequential detection of abrupt changes in spectral characteristics of digital signals.  IEEE Trans. Inf. Theory, 29(5):709–724, 1983.
  * [7] Michele Basseville, Igor Nikiforov, et al.  Detection of abrupt changes: Theory and Application, volume 104\.  Prentice Hall, 1993.
  * [8] Dean Bodenham and Niall Adams.  Continuous monitoring for changepoints in data streams using adaptive estimation.  Stat. Comput., 27(5):1257–1270, 2017.
  * [9] George Casella and Roger Berger.  Statistical inference, volume 2.  Duxbury, 2002.
  * [10] Wei-Cheng Chang, Chun-Liang Li, Yiming Yang, and Barnabás Póczos.  Kernel change-point detection with auxiliary deep generative models.  In Proc. Int. Conf. on Learning Representations (ICLR), 2019.
  * [11] Yasmin Fathy, Payam Barnaghi, and Rahim Tafazolli.  An online adaptive algorithm for change detection in streaming sensory data.  IEEE Syst. J., 13(3):2688–2699, 2018.
  * [12] Pierre Granjon.  The CUSUM algorithm - a small review.  Technical report, hal-00914697, June 2013.
  * [13] Fredrik Gustafsson.  Adaptive filtering and change detection, volume 1.  Citeseer, 2000.
  * [14] Douglas Hawkins and KD Zamba.  Statistical process control for shifts in mean or variance using a changepoint formulation.  Technometrics, 47(2):164–173, 2005.
  * [15] Daniel Kifer, Shai Ben-David, and Johannes Gehrke.  Detecting change in data streams.  In Proc. V. Large Datab. (VLDB), 2004.
  * [16] Lifeng Lai, Yijia Fan, and Vincent Poor.  Quickest detection in cognitive radio: A sequential change detection framework.  In Proc. IEEE Glob. Telecom. Conf. (GLOBECOM), 2008., 2004.
  * [17] Song Liu, Makoto Yamada, Nigel Collier, and Masashi Sugiyama.  Change-point detection in time-series data by relative density-ratio estimation.  Neural Netw., 43:72–83, 2013.
  * [18] Gary Lorden.  Procedures for reacting to a change in distribution.  Ann. Math. Stat., 42(6):1897–1908, 1971.
  * [19] George Moustakides.  Optimal stopping times for detecting changes in distributions.  Ann. Stat., 14(4):1379–1387, 1986.
  * [20] Ewan Page.  Continuous inspection schemes.  Biometrika, 41(1):100–115, 1954.
  * [21] David Siegmund and ES Venkatraman.  Using the generalized likelihood ratio statistic for sequential detection of a change-point.  Ann. Stat., pages 255–271, 1995.
  * [22] Alexander G Tartakovsky, Boris L Rozovskii, Rudolf B Blazek, and Hongjoong Kim.  A novel approach to detection of intrusions in computer networks via adaptive sequential and batch-sequential change-point detection methods.  IEEE Trans. Signal Process., 54(9):3372–3382, 2006.
  * [23] Venugopal Veeravalli and Taposh Banerjee.  Quickest change detection.  In Academic Press Library in Signal Processing, volume 3, pages 209–255. Elsevier, 2014.
  * [24] Liyan Xie, George Moustakides, and Yao Xie.  First-order optimal sequential subspace change-point detection.  In Proc. IEEE Glob. Conf. on Sig. and Inf. Process.(GlobalSIP), 2018\.
  * [25] Liyan Xie, George V Moustakides, and Yao Xie.  Window-limited cusum for sequential change detection.  arXiv preprint arXiv:2206.06777, 2022.
  * [26] Liyan Xie, Yao Xie, and George V Moustakides.  Sequential subspace change point detection.  Sequential Analysis, 39(3):307–335, 2020.
  * [27] Ping Yang, Guy Dumont, and John Ansermino.  Adaptive change detection in heart rate trend monitoring in anesthetized children.  IEEE. Trans. Biomed. Eng., 53(11):2211–2219, 2006.

## Appendix

### A: Proof of Lemma 15

#### Computing the inner expectation

For the expression in (18), the inner expectation will be first simplified by
completing the square to form another normal distribution and then integrating

$\displaystyle\mathbb{E}_{x_{t}\sim\theta_{0}}\left[r\left(x_{t}\right)\Big{|}\hat{\mu}_{t},\hat{\sigma}_{t}\right]$
$\displaystyle=\mathbb{E}_{x_{t}\sim\theta_{0}}\left[\exp\left(\delta_{0}\left(-\frac{(x_{t}-\hat{\mu})^{2}}{2\hat{\sigma}^{2}}+\frac{(x_{t}-\mu_{0})^{2}}{2\sigma_{0}^{2}}\right)\right)\Big{|}\hat{\mu}_{t},\hat{\sigma}_{t}\right]$
$\displaystyle=\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi\sigma_{0}^{2}}}\exp\left(-\frac{\delta_{0}(x_{t}-\hat{\mu})^{2}}{2\hat{\sigma}^{2}}+\frac{\delta_{0}(x_{t}-\mu_{0})^{2}}{2\sigma_{0}^{2}}\right)\exp\frac{-(x_{t}-\mu_{0})^{2}}{2\sigma_{0}^{2}}d(x_{t})$
$\displaystyle=\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi\sigma_{0}^{2}}}\exp\left(-\frac{\delta_{0}(x_{t}-\hat{\mu})^{2}}{2\hat{\sigma}^{2}}-\frac{(1-\delta_{0})(x_{t}-\mu_{0})^{2}}{2\sigma_{0}^{2}}\right)d(x_{t})$
$\displaystyle=\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi\sigma_{0}^{2}}}\exp\left(-\frac{\delta_{0}\sigma_{0}^{2}(x_{t}-\hat{\mu})^{2}-(1-\delta_{0})\hat{\sigma}_{t}^{2}(x_{t}-\mu_{0})^{2}}{2\hat{\sigma}_{t}^{2}\sigma_{0}^{2}}\right)d(x_{t})$
$\displaystyle=\frac{1}{\sqrt{2\pi\sigma_{0}^{2}}}\int_{-\infty}^{\infty}\exp\left(\frac{-(z)\left(x_{t}^{2}-2x_{t}\frac{2y}{z}+\frac{y}{z}\right)}{2\hat{\sigma}_{t}^{2}\sigma_{0}^{2}}\right)d(x_{t})$
$\displaystyle\left(\text{ where:
}z=\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2}\text{ and
}y=\hat{\mu}_{t}\sigma_{0}^{2}\delta_{0}+\mu_{0}\hat{\sigma}_{t}^{2}(1-\delta_{0})\right)$
$\displaystyle=\frac{1}{\sqrt{2\pi\sigma_{0}^{2}}}\int_{-\infty}^{\infty}\exp\left(\frac{-\left(x^{2}-2x_{t}\frac{y}{z}+\right(\frac{y}{z}\left){}^{2}-\right(\frac{y}{z}\left){}^{2}+\frac{y}{z}\right)}{2\frac{\hat{\sigma}_{t}^{2}\sigma_{0}^{2}}{z}}\right)d(x_{t})$
$\displaystyle=\frac{1}{\sqrt{2\pi\sigma_{0}^{2}}}\exp\left(-\frac{\left(\frac{y}{z}\right)^{2}+\frac{y}{z}}{2\frac{\hat{\sigma}_{t}^{2}\sigma_{0}^{2}}{z}}\right)\int_{-\infty}^{\infty}\exp\left(\frac{-\left(x_{t}-\left(\frac{y}{z}\right)\right)^{2}}{2\underbrace{\frac{\hat{\sigma}_{t}^{2}\sigma_{0}^{2}}{z}}_{\sigma_{12}^{2}}}\right)d(x_{t})$
$\displaystyle=\frac{1}{\sqrt{2\pi\sigma_{0}^{2}}}\exp\left(\frac{-y^{2}+yz}{2z\hat{\sigma}_{t}^{2}\sigma_{0}^{2}}\right)\sqrt{2\pi\sigma_{12}^{2}}$
$\displaystyle=\frac{\sigma_{12}}{\sigma_{0}}\exp\left(\frac{-\left(\hat{\sigma}_{t}^{2}\sigma_{0}^{2}\delta_{0}(1-\delta_{0})\right)\left(\mu_{0}^{2}-2\mu_{0}\hat{\mu}_{t}+\mu_{t}^{2}\right)}{2\hat{\sigma}_{t}^{2}\sigma_{0}^{2}(\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2})}\right)\text{
(After substituting $y$ and $z$)}$
$\displaystyle=\frac{\sigma_{12}}{\sigma_{0}}\exp\left(\frac{-(\mu_{0}-\mu_{t})^{2}}{\frac{2\hat{\sigma}_{t}^{2}\sigma_{0}^{2}(\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2})}{\hat{\sigma}_{t}^{2}\sigma_{0}^{2}\delta_{0}(1-\delta_{0})}}\right)$
$\displaystyle=\frac{\sigma_{12}}{\sigma_{0}}\exp\left(\frac{-(\mu_{0}-\hat{\mu}_{t})^{2}}{2\frac{\sigma_{0}^{2}}{1-\delta_{0}}+2\frac{\hat{\sigma}_{t}^{2}}{\delta_{0}}}\right),$

where

$\sigma_{12}^{2}=\frac{\hat{\sigma}_{t}^{2}\sigma_{0}^{2}}{\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2}}.$
(19)

(Note: $\delta_{0}$ should be such that $\sigma_{12}^{2}>0$ in (19)).

Thus

$\displaystyle\mathbb{E}_{x_{t}\sim\theta_{0}}\left[\exp\left(\delta_{0}\left(-\frac{(x_{t}-\hat{\mu}_{t})^{2}}{2\hat{\sigma}_{t}^{2}}+\frac{(x_{t}-\mu_{0})^{2}}{2\sigma_{0}^{2}}\right)\right)\Big{|}\hat{\mu}_{t},\hat{\sigma}_{t}\right]$
$\displaystyle=\frac{\sigma_{12}}{\sigma_{0}}\exp\left(\frac{-(\mu_{0}-\hat{\mu}_{t})^{2}}{2\frac{\hat{\sigma}_{t}^{2}}{\delta_{0}}+2\frac{\sigma_{0}^{2}}{1-\delta_{0}}}\right).$
(20)

#### Computing the outer expectation

Plugging in the results of the inner expectation from (20) in (18):

$\mathbb{E}_{\theta_{0}}\left[\exp({\delta_{0}\tilde{s}_{t}})\right]=\exp(\delta_{0}(-\frac{1}{2}-v))\mathbb{E}_{\mathop{x}_{t+1..w}\sim\theta_{0}}\left[\exp\left(\delta_{0}\left(\frac{\sigma_{0}^{2}+(\mu_{0}-\hat{\mu}_{t})^{2}}{2\hat{\sigma}_{t}^{2}}\right)\right)\frac{\sigma_{12}}{\sigma_{0}}\exp\left(\frac{-(\mu_{0}-\hat{\mu}_{t})^{2}}{2\frac{\hat{\sigma}_{t}^{2}}{\delta_{0}}+2\frac{\sigma_{0}^{2}}{1-\delta_{0}}}\right)\right].$

Expressing and simplifying the above equation yields:

$\displaystyle\mathbb{E}_{\theta_{0}}\left[\exp({\delta_{0}\tilde{s}_{t}})\right]=\exp(\delta_{0}(-\frac{1}{2}-v))\mathbb{E}_{\mathop{x}_{t+1..w}\sim\theta_{0}}\left[\exp\left(\delta_{0}\left(\frac{\sigma_{0}^{2}+(\mu_{0}-\hat{\mu}_{t})^{2}}{2\hat{\sigma}_{t}^{2}}\right)\right)\frac{\sigma_{12}}{\sigma_{0}}\exp\left(\frac{-(\mu_{0}-\hat{\mu}_{t})^{2}}{2\frac{\hat{\sigma}_{t}^{2}}{\delta_{0}}+2\frac{\sigma_{0}^{2}}{1-\delta_{0}}}\right)\right]$
$\displaystyle=\exp(\delta_{0}(-\frac{1}{2}-v))\mathbb{E}_{\mathop{x}_{t+1..w}\sim\theta_{0}}\left[\exp\left(\frac{1}{2}\log\frac{\sigma_{12}^{2}}{\sigma_{0}^{2}}+\delta_{0}\left(\frac{\sigma_{0}^{2}+(\mu_{0}-\hat{\mu}_{t})^{2}}{2\hat{\sigma}_{t}^{2}}\right)-\frac{(1-\delta_{0})(\delta_{0})(\mu_{0}-\hat{\mu}_{t})^{2}}{2(1-\delta_{0})\hat{\sigma}_{t}^{2}+2\delta_{0}\sigma_{0}^{2}}\right)\right]$
$\displaystyle=\exp(\delta_{0}(-\frac{1}{2}-v))\mathbb{E}_{\mathop{x}_{t+1..w}\sim\theta_{0}}\left[\exp\left(g(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})\right)\right].$
(21)

#### Asymptotic distribution of $g(\hat{\mu}_{t},\hat{\sigma}_{t})$

Now the asymptotic distribution for the argument of the exponent
($g(\hat{\mu}_{t},\hat{\sigma}_{t})$) within the expectation would be found
(when sample mean and sample variance are estimated under the pre-change
distribution). This argument is defined as:

$g(\hat{\mu}_{t},\hat{\sigma}_{t})=\underbrace{\frac{1}{2}\log\left(\frac{\hat{\sigma}_{t}^{2}}{\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2}}\right)+\frac{\delta_{0}\sigma_{0}^{2}}{2\hat{\sigma}_{t}^{2}}}_{a(\hat{\sigma}_{t}^{2})}+\underbrace{\frac{(\mu_{0}-\hat{\mu}_{t})^{2}}{2}\left(\frac{\delta_{0}}{\hat{\sigma}_{t}^{2}}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\hat{\sigma}_{t}^{2}+\delta_{0}\sigma_{0}^{2}}\right)}_{b(\hat{\mu}_{t},\hat{\sigma}_{t})}.$
(22)

We now find the distribution of $g(\hat{\mu}_{t},\hat{\sigma}_{t})$ when
samples samples $x_{t}..x_{t+w}$ used to calculate $\hat{\mu}_{t}$ and
$\hat{\sigma}_{t}$ are distributed by $\theta_{0}$. Decomposing
$g(\hat{\mu}_{t},\hat{\sigma}_{t})$ into two terms:

$a(\hat{\sigma}_{t}^{2})=\frac{1}{2}\log\left(\frac{\hat{\sigma}_{t}^{2}}{\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2}}\right)+\frac{\delta_{0}\sigma_{0}^{2}}{2\hat{\sigma}_{t}^{2}},$
$b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})=\frac{(\mu_{0}-\hat{\mu}_{t})^{2}}{2}\left(\frac{\delta_{0}}{\hat{\sigma}_{t}^{2}}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\hat{\sigma}_{t}^{2}+\delta_{0}\sigma_{0}^{2}}\right).$

#### Asymptotic distribution of first term $a(\hat{\sigma}_{t}^{2})$

To find the asymptotic distribution of $a(\hat{\sigma}_{t}^{2})$, we first
recall some results. The asymptotic distribution of sample variance is
$\hat{\sigma}_{t}^{2}$:

$\displaystyle\hat{\sigma}_{t}^{2}$
$\displaystyle=\frac{1}{N}\sum_{1=1}^{N}(x_{i}-\hat{\mu}_{t})^{2},$
$\displaystyle\frac{\hat{\sigma}_{t}^{2}}{\sigma_{0}^{2}}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\underbrace{\frac{(x_{i}-\hat{\mu}_{t})^{2}}{\sigma_{0}^{2}}}_{\text{$\chi_{1}^{2}$
variables}}.$

(Note sample variance is divided by $(N-1)$ instead of $N$. Though as
$N\xrightarrow{}\infty$, the the sample variance is similar when divided by
$N$ or $N-1$. I divide by $N$ to use the tools of central limit theorem which
can be found below.) By the central limit theorem, as
$\frac{\hat{\sigma}_{t}^{2}}{\sigma_{0}^{2}}$ is a mean of sum of
$\chi_{1}^{2}$ variables. These variables have a mean 1 and variance 2:

$\displaystyle\sqrt{N}(\frac{\hat{\sigma}_{t}^{2}}{\sigma_{0}^{2}}-1)\xrightarrow{d}z\sim\mathcal{N}(0,2).$

Or equivalently

$\sqrt{N}(\hat{\sigma}_{t}^{2}-\sigma_{0}^{2})\xrightarrow{d}z\sim\mathcal{N}(0,2\sigma_{0}^{4}).$
(23)

An asymptotically normal estimator $\hat{\theta}$, for the parameter $\theta$,
is distributed through:

$\sqrt{n}(\hat{\theta}-\theta)\xrightarrow{d}W\sim\mathcal{N}(0,\sigma^{2})$

For a function $g(\hat{\theta})$, of an asymptotically normal estimator
$\hat{\theta}$ of $\theta$, the delta method states that:

$\sqrt{n}(g(\hat{\theta})-g(\theta))\xrightarrow{d}W^{*}\sim\mathcal{N}(0,g^{\prime}(\theta)^{2}\sigma^{2})$

This result is however true only when $g^{\prime}(\theta)$ exists and is not
0. Since the sample variance, $\hat{\sigma}_{t}^{2}$, is asymptotically normal
(as shown in (23)), we can try applying the delta method with
$a(\hat{\sigma}_{t}^{2})$ in place of $g(\theta)$:

$\sqrt{n}(a(\hat{\sigma}_{t}^{2})-a(\sigma_{0}^{2}))\xrightarrow{d}W^{*}\sim\mathcal{N}(0,2(a^{\prime}(\hat{\sigma}_{t}^{2}))^{2}\sigma_{0}^{4})$
$a^{\prime}(\hat{\sigma}_{t}^{2})=\frac{\delta_{0}\sigma_{0}^{2}}{-2\hat{\sigma}_{t}^{4}}+\frac{\delta_{0}\sigma_{0}^{2}}{2\hat{\sigma}_{t}^{2}(\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2})}$
$\displaystyle a^{\prime}(\sigma_{0}^{2})$
$\displaystyle=\frac{\delta_{0}\sigma_{0}^{2}}{-2\sigma_{0}^{4}}+\frac{\delta_{0}}{2\sigma_{0}^{2}}$
$\displaystyle=0.$

As $a^{\prime}(\sigma_{0}^{2})=0$, the delta method cannot be used. In such a
case, the second order delta method can be used if
$a^{\prime\prime}(\sigma_{0}^{2})\neq 0$ .

#### Second order delta method

For an asymptotically normal estimator $\hat{\theta}$ for the parameter
$\theta$, i.e.,

$\sqrt{n}(\hat{\theta}-\theta)\xrightarrow{d}W\sim\mathcal{N}(0,\sigma^{2}),$

the second order delta method [9] states that if there is a function $g$ on
these estimates $\hat{\theta}$, and both $g(\hat{\theta})$ and
$g^{\prime\prime}(\theta_{0})$ exist and are non 0, then

$n(g(\hat{\theta})-g(\theta_{0}))\xrightarrow{d}W\sim\sigma_{0}^{2}\frac{g^{\prime\prime}(\sigma_{0}^{2})}{2}\chi_{1}^{2}.$

Since the sample variance, $\hat{\sigma}_{t}^{2}$, is asymptotically normal
(as shown in (23)), we can try applying the second order delta method with
$a(\hat{\sigma}_{t}^{2})$ in place of $g(\theta)$

$n(a(\hat{\sigma}_{t}^{2})-a(\sigma_{0}^{2}))\xrightarrow{d}W\sim\sigma_{0}^{4}a^{\prime\prime}(\sigma_{0}^{2})\chi_{1}^{2}.$
(24)

Finding the double derivative of $a(\hat{\sigma}_{t}^{2})$ with respect to
$\hat{\sigma}_{t}^{2}$

$a^{\prime\prime}(\hat{\sigma}_{t}^{2})=\frac{\delta_{0}\sigma_{0}^{2}}{\hat{\sigma}_{t}^{6}}-\frac{\delta_{0}\sigma_{0}^{2}\hat{\sigma}_{t}^{-2}(1-\delta_{0})+\delta_{0}\sigma_{0}^{2}\hat{\sigma}_{t}^{-4}(\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2})}{2(\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2})^{2}}.$

Plugging in $\hat{\sigma}_{t}$ = $\sigma_{0}$

$\displaystyle a^{\prime\prime}(\sigma_{0}^{2})$
$\displaystyle=\frac{\delta_{0}}{\sigma_{0}^{4}}-\frac{\delta_{0}(1-\delta_{0})+\delta_{0}}{2\sigma_{0}^{4}}$
$\displaystyle=\frac{\delta_{0}^{2}}{2\sigma_{0}^{4}}.$

Plugging this result in (24), we have

$\displaystyle
n(a(\hat{\sigma}_{t}^{2})-a(\sigma_{0}^{2}))\xrightarrow{d}W\sim\frac{\delta_{0}^{2}}{2}\chi_{1}^{2},$
$\displaystyle
a(\hat{\sigma}_{t}^{2})\xrightarrow{d}W^{*}\sim\frac{\delta_{0}^{2}}{2n}\chi_{1}^{2}+a(\sigma_{0}^{2}).$

As $a(\sigma_{0}^{2})=\frac{\delta_{0}}{2}$,

$a(\hat{\sigma}_{t}^{2})\xrightarrow{d}W^{*}\sim\frac{\delta_{0}^{2}}{2n}\chi_{1}^{2}+\frac{\delta_{0}}{2},$
(25)
$a(\hat{\sigma}_{t}^{2})\xrightarrow{d}\frac{\delta_{0}^{2}}{2n}z+\frac{\delta_{0}}{2}\text{
( where }z\sim\chi_{1}^{2}).$

#### Looking at the 2nd term $b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})$

The second term is defined as:

$b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})=\frac{(\mu_{0}-\hat{\mu}_{t})^{2}}{2}\left(\frac{\delta_{0}}{\hat{\sigma}_{t}^{2}}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\hat{\sigma}_{t}^{2}+\delta_{0}\sigma_{0}^{2}}\right).$

Manipulating the second term:

$\displaystyle b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})$
$\displaystyle=\frac{(\mu_{0}-\hat{\mu}_{t})^{2}}{2}\left(\frac{\delta_{0}}{\hat{\sigma}_{t}^{2}}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\hat{\sigma}_{t}^{2}+\delta_{0}\sigma_{0}^{2}}\right)$
$\displaystyle=\frac{\frac{\sigma_{0}^{2}}{N}\frac{(\mu_{0}-\hat{\mu}_{t})^{2}}{\frac{\sigma_{0}^{2}}{N}}}{2}\left(\frac{\delta_{0}}{\hat{\sigma}_{t}^{2}}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\hat{\sigma}_{t}^{2}+\delta_{0}\sigma_{0}^{2}}\right)$
$\displaystyle=\frac{\frac{\sigma_{0}^{2}}{N}\frac{(\mu_{0}-\hat{\mu}_{t})^{2}}{\frac{\sigma_{0}^{2}}{N}}}{2}\left(\frac{\delta_{0}}{\frac{\sigma_{0}^{2}}{N-1}\frac{N-1}{\sigma_{0}^{2}}\hat{\sigma}_{t}^{2}}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\frac{\sigma_{0}^{2}}{N-1}\frac{N-1}{\sigma_{0}^{2}}\hat{\sigma}_{t}^{2}+\delta_{0}\sigma_{0}^{2}}\right).$
(26)

Recall that the distribution of the sample mean and the sample variance are
given by:

$\displaystyle\hat{\mu}_{t}$
$\displaystyle\sim\mathcal{N}(\mu_{0},\frac{\sigma_{0}^{2}}{n}),$
$\displaystyle\frac{(n-1)}{\sigma_{0}^{2}}\hat{\sigma}_{t}^{2}$
$\displaystyle=z\sim\chi_{n-1}^{2}.$ (27)

Also,

$\frac{(\mu_{0}-\hat{\mu}_{t})^{2}}{\frac{\sigma_{0}^{2}}{n}}=z\sim\chi_{n-1}^{2}.$

Using these results in (26) yields

$b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})=\frac{\frac{\sigma_{0}^{2}}{n}z}{2}\left(\frac{\delta_{0}}{\frac{\sigma_{0}^{2}}{n-1}z}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\frac{\sigma_{0}^{2}}{n-1}z+\delta_{0}\sigma_{0}^{2}}\right).$

As $n\xrightarrow{}\infty$, by law of large numbers
$\frac{\chi_{n-1}^{2}}{n-1}\xrightarrow{}1$. Thus as $n\xrightarrow{}\infty$,
$\frac{z}{n-1}\xrightarrow{}1$ leading to:

$\displaystyle b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})$
$\displaystyle\xrightarrow{}\frac{\frac{\sigma_{0}^{2}}{n}z}{2}\left(\frac{\delta_{0}}{\sigma_{0}^{2}}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\sigma_{0}^{2}+\delta_{0}\sigma_{0}^{2}}\right)$
$\displaystyle=\frac{\delta_{0}^{2}z}{2n}.$

As $z\sim\chi_{1}^{2}$, then when $n\xrightarrow{}\infty$,

$b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})\xrightarrow{d}\frac{\delta_{0}^{2}z}{2n}\sim\frac{\delta_{0}^{2}\chi_{1}^{2}}{2n}.$
(28)

#### Combining the two terms

Note that

$\displaystyle g(\hat{\mu}_{t},\hat{\sigma}_{t})$
$\displaystyle=\underbrace{\frac{1}{2}\log\left(\frac{\hat{\sigma}_{t}^{2}}{\delta_{0}\sigma_{0}^{2}+(1-\delta_{0})\hat{\sigma}_{t}^{2}}\right)+\frac{\delta_{0}\sigma_{0}^{2}}{2\hat{\sigma}_{t}^{2}}}_{a(\hat{\sigma}_{t}^{2})}+\underbrace{\frac{(\mu_{0}-\hat{\mu}_{t})^{2}}{2}\left(\frac{\delta_{0}}{\hat{\sigma}_{t}^{2}}-\frac{(1-\delta_{0})\delta_{0}}{(1-\delta_{0})\hat{\sigma}_{t}^{2}+\delta_{0}\sigma_{0}^{2}}\right)}_{b(\hat{\mu}_{t},\hat{\sigma}_{t})}$
$\displaystyle=a(\hat{\sigma}_{t}^{2})+b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2}).$

Since

$\displaystyle a(\hat{\sigma}_{t}^{2})$
$\displaystyle\xrightarrow{d}\frac{\delta_{0}^{2}}{2n}z+\frac{\delta_{0}}{2},$
$\displaystyle b(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})$
$\displaystyle\xrightarrow{d}\frac{\delta_{0}^{2}z}{2N}.$

we have,

$\displaystyle g(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})$
$\displaystyle\xrightarrow{d}\frac{\delta_{0}^{2}}{2n}z+\frac{\delta_{0}}{2}+\frac{\delta_{0}^{2}}{2n}z\text{
(where }z\sim\chi_{1}^{2})$
$\displaystyle=\frac{\delta_{0}^{2}}{2n}y+\frac{\delta_{0}}{2}\text{ (where
}y\sim\chi_{2}^{2}).$ (29)

A chi square variable of $v$ degrees of freedom can be written as a gamma
variable, with shape parameter $v/2$, and scale parameter 2. Also if
$x\sim\text{Gamma}(a,b)$, then $k.x\sim\text{Gamma}(a,k.b)$. Thus the
asymptotic distribution of $g(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})$ can be
written as:

$g(\hat{\mu}_{t},\hat{\sigma}_{t}^{2})\xrightarrow{d}x+\frac{\delta_{0}}{2}\text{
(where
}x\sim\text{Gamma}(a(\text{shape})=1,b(\text{scale})=\frac{\delta_{0}^{2}}{n})).$
(30)

#### Finding the equivalence factor $\delta_{0}$

The results from (30) can be used within (21) which can be written as:

$\mathbb{E}_{\theta_{0}}\left[\exp({\delta_{0}\tilde{s}_{t}})\right]=\exp(\delta_{0}(-\frac{1}{2}-v))\mathbb{E}_{\mathop{x\sim\text{Gamma}(1/2,2\delta_{0}^{2}/n)}}\left[\exp\left(x+\frac{\delta_{0}}{2}\right)\right].$

Using this result to solve for $\delta_{0}$ in the statement of Lemma 15

$\displaystyle\exp(\delta_{0}(-\frac{1}{2}-v))\mathbb{E}_{\mathop{x\sim\text{Gamma}(1/2,2\delta_{0}^{2}/n)}}\left[\exp\left(x+\frac{\delta_{0}}{2}\right)\right]$
$\displaystyle=1$
$\displaystyle\exp\left(-\delta_{0}v\right)\mathbb{E}_{\mathop{x\sim\text{Gamma}(1/2,2\delta_{0}^{2}/n)}}\underbrace{\left[\exp\left(x\right)\right]}_{\text{MGFunc
}}$ $\displaystyle=1.$ (31)

The moment generating function of the gamma distribution is:

$\mathbb{E}_{\mathop{x\sim\text{Gamma}(a,b)}}\left[\exp\left(tx\right)\right]=(1-tb)^{-a}.$

Using the moment generating function results in

$\displaystyle\exp\left(-\delta_{0}v\right)\left(1-\frac{\delta_{0}^{2}}{n}\right)^{-1}$
$\displaystyle=1$ $\displaystyle\delta_{0}v+\log(1-\frac{\delta_{0}^{2}}{n})$
$\displaystyle=0$ $\displaystyle v$
$\displaystyle=\frac{-\log(1-\frac{\delta_{0}^{2}}{n})}{\delta_{0}}\qed$


# End-to-End Cross-Domain Text-to-SQL
Semantic Parsing with Auxiliary Task

Peng Shi1 , Tao Yu2, Patrick Ng3, and Zhiguo Wang3
1 David R. Cheriton School of Computer Science, University of Waterloo
2 Department of Computer Science, The University of Hong Kong
3 AWS AI Labs
<EMAIL_ADDRESS><EMAIL_ADDRESS>Work done while at AWS AI
Labs.

###### Abstract

In this work, we focus on two crucial components in the cross-domain text-to-
SQL semantic parsing task: schema linking and value filling. To encourage the
model to learn better encoding ability, we propose a column selection
auxiliary task to empower the encoder with the relevance matching capability
by using explicit learning targets. Furthermore, we propose two value filling
methods to build the bridge from the existing zero-shot semantic parsers to
real-world applications, considering most of the existing parsers ignore the
values filling in the synthesized SQL. With experiments on Spider, our
proposed framework improves over the baselines on the execution accuracy and
exact set match accuracy when database contents are unavailable, and detailed
analysis sheds light on future work.

##  1 Introduction

Text-to-SQL semantic parsing is to translate natural language questions into
SQL queries Warren and Pereira (1982); Popescu et al. (2003); Li and Jagadish
(2014); Iyer et al. (2017); Yu et al. (2018a); Dong and Lapata (2018a), which
can be further executed against large scale databases to obtain query results.
These semantic parsers not only offer the chance of communicating with
databases to the users who are unknown of the underlying database query
language, but are handy toolkits for experts to synthesize complex SQL queries
by providing high-quality samples.

More recently, there has been significant interest in cross-domain text-to-SQL
modeling innovation Yu et al. (2018c); Guo et al. (2019); Bogin et al.
(2019a); Wang et al. (2019); Shi et al. (2020); Yu et al. (2020), and
different benchmarks are proposed, such as WikiSQL Zhong et al. (2017) and
Spider Yu et al. (2018d). Especially for the Spider dataset, some of the SQL
queries are nested which are more complicated than those in WikiSQL.
Furthermore, the attribute that training and test set do not have overlap
databases makes the task zero-shot. Therefore, linking entities in the
question to the correct schema (columns and tables) from the unseen databases
becomes a major problem in the cross-domain text-to-SQL parsing task. Another
tricky problem is that some questions contain database-dependent values in
different domains, which requires the model to extract them and fill in the
corresponding positions for composing an executable SQL query. However, this
value filling problem is ignored by a lot of previous work in the cross-domain
text-to-SQL parsing, making those parsers impractical.

Figure 1: The overall architecture of our framework. The question is “List of
countries where Spanish is an official language." The encoder-decoder model
firstly interprets the question into a SQL query with value placeholder
<mask>. A value filler then chooses the best value for each placeholder to
generate an executable SQL. The encoder-decoder model and the auxiliary task
column selection is trained jointly.

Considering the importance of the schema linking and value filling for a real-
world text-to-SQL parser in the cross-domain setting, we propose a framework
with enhanced schema encoding ability and value filling ability. In this
framework, based on sequence-to-sequence architecture, we design an auxiliary
task column classification for multitask training. The classifier determines
whether a specific column is used in the gold SQL query, as shown in Figure 1.
With this auxiliary task, the encoder has better relevance matching capability
(between the question and schema), supervised by explicit learning signals. In
this way, the decoder can distinguish relevant and irrelevant schema more
easily, leading to better schema linking performance. Furthermore, in our
framework, we propose two value filling methods, including a heuristic method
and a neural baseline, to make the zero-shot parsers usable in real-world
applications. With further analysis based on these two simple baselines, we
provide more insights on the value filling subtask, paving ways for future
work.

##  2 Framework

Given a question $X$ = $\\{x_{1},x_{2},...,x_{n}\\}$ and schema $S$ consists
of tables $T=\\{t_{1},t_{2},...,t_{|T|}\\}$ and columns
$C=\\{c_{1},c_{2},...,c_{|C|}\\}$, our goal is to map the question-schema pair
$(X,S)$ into the correct SQL query $Y$, which can be represented as a sequence
of tokens of SQL, or other intermediate representations. In this work, we
adopt the intermediate representation as our learning target.

###  2.1 Input, Encoding and Decoding

For a question, following Yu et al. (2018b) and Guo et al. (2019), we firstly
group tokens into a segment if that subsequence matches any column name or
table name, and add a special indicator [column] or [table] to it, as shown in
Figure 1. For the schema, we combine the column names with the corresponding
table names. For example, table country has a column population, we then
concatenate them into country population as an enhanced column name. In this
way, the model can obtain better representation for distinguishing those
columns that share the same column name but belong to different tables. Though
Graph Neural Network Bogin et al. (2019c) or Relational Transformer Wang et
al. (2019) can achieve similar purpose using schema graph structure, we argue
that this technique is simple to apply without introducing extra model
complexity.

To encode the processed question and schema, we use the pretrained transformer
BART Lewis et al. (2019)111We only leverage the encoder part of BART for the
encoding, to save computational resources. as the backbone. The input sequence
is the concatenation of processed question tokens and processed columns, as
shown in Figure 1. After feeding the input sequence into the encoder, we then
obtain the question representation $\\{h_{x_{1}},h_{x_{2}},...,h_{x_{m}}\\}$
and column representation $\\{h_{c_{1}}\\}$, $\\{h_{c_{2}}\\}$, …,
$\\{h_{c_{|C|}}\\}$, where $\\{h_{c_{j}}\\}$ denotes a sequence of hidden
vectors of $j-$th column, because each column contains several tokens. We
further apply two aggregation functions $f_{avg}$ and $f_{lstm}$ on the
question and column representation, respectively. Concretely, the aggregation
function $f_{avg}$ is an averaging function
$\frac{1}{r-l+1}\sum_{i=l}^{r}h_{x_{i}}$ applying on each question segment
which is determined in the pre-processing step. The obtained question segment
representation is denoted with $q_{i}$, which is further used for the decoding
process. The aggregation function $f_{lstm}$ is parameterized with a
bidirectional LSTM and the last hidden states from both directions are
concatenated to obtain the aggregated representation of each column.

For the decoder, we adopt the coarse-to-fine decoder from Dong and Lapata
(2018b) and Guo et al. (2019). The decoder firstly generates the overall
structure of the target SQL such as SELECT __ WHERE __ ORDER BY __, and then
conducts schema grounding in the fine-grained decoding process, including the
column linking and table linking. For more details about the coarse-to-fine
deocder, please refer to Dong and Lapata (2018b) and Guo et al. (2019).

###  2.2 Multitask Learning

To improve the schema encoding quality, an auxiliary column classification
task is designed for the model. This auxiliary task exploits the direct
supervision signals to enhance the encoder’s relevance matching capability.
Specifically, we apply the aggregation function $f_{avg}$ on the
representations of token sequence $\\{h_{c_{i}}\\}$ for each column, obtaining
$s_{i}$. An dot-product based attention mechanism is further applied on
$s_{i}$ and question segment representations $\\{q_{j}\\}$, to obtain
question-aware column representation $\hat{s}_{i}$ with equation
$\hat{s}_{i}=\text{MLP}([s_{i};r_{i}])$, where
$r_{i}=\sum_{j=1}^{m}\alpha_{j}q_{j}$ and
$\alpha_{j}\propto\text{exp}(s_{i}^{\top}q_{j})$. Finally, a binary classifier
is applied on $\hat{s}_{i}$: If the column is used in the target SQL sequence,
then a positive label is assigned; Otherwise, it is classified with a negative
label.

###  2.3 Value Filler

To bridge the gap between existing zero-shot semantic parsers Guo et al.
(2019); Bogin et al. (2019b); Wang et al. (2019) and real-world applications,
we propose two value fillers.

Heuristic Method. Our heuristic method is based on the database search and
string matching. For each question token $x_{i}$, we search for its candidate
cell values by executing the following SQL query

SELECT {column} FROM {table} WHERE {column} LIKE ‘{token} %’ OR {column} LIKE
‘% {token}’ OR {column} LIKE ‘% {token} %’ OR {column} LIKE ‘{token}’

for each column and the corresponding table. If there is a cell value string
$v$ from the database is retrieved, and string $v$ has high similarity with a
substring of the question (measured by the Levenshtein distance), then we
build a projection $P$ from {table, column} $\rightarrow$ {$v$}. We also
collect all numbers mentioned in the question as number candidate list $N$,
where the rule-based method is applied. With the projection $P$ and number
candidates $N$, we fill in the blank222We refer those positions in SQL that
require values as blanks. with value $P${table, column}, where the value is
used in the specific table and column. If multiple candidates are available,
we choose the unused one in the queue, whose ordering is based on the
collection sequence. If the column type is number, then a number will be
assigned from the number candidate list $N$ based on the collection sequence.
If all numbers are used, the default value 1 is used. If there is no
projection for {table, column}, a placeholder is assigned.

Neural Baseline. Based on the value candidates including retrieved cell values
in $P$ and the numbers in $N$, instead of filling the blanks with heuristic
rules, we leverage the neural model for composing the executable SQL. To
achieve this, we firstly use a placeholder <mask>, as shown in Figure 1, to
denote the value to be filled in the incomplete SQL. The input sequence for
the model is the concatenation of the question, the incomplete SQL and value
candidates, which is further fed into roberta-base Liu et al. (2019) encoder,
obtaining the <mask> token hidden states $u_{mask_{i}}$. For the value
candidates, averaging aggregation function $g_{avg}$ is applied to produce the
value candidate representation $u_{v_{j}}$. By querying the value candidates
with $u_{mask_{i}}$, best value candidate can be obtained based on
$p(u_{v_{j}}|u_{mask_{i}})\propto\text{exp}(u_{mask_{i}}^{\top}u_{v_{j}})$.

##  3 Experimental Setup

We conduct our experiments on the Spider Yu et al. (2018d) dataset333Test set
is not publicly available and model submission is required for obtaining test
performance.. For the Spider dataset, there are two methods of evaluation: One
is exact set match accuracy, requiring an exact set match between the
predicted SQL and the oracle SQL, except for the values in the SQL; the other
one is execution accuracy, requiring an exact match on the execution outputs.
In our work, we provide results on both evaluation metrics to provide a
complete baseline system for the benchmark. Considering some privacy issues in
real world cases, database contents might be unavailable in the model
development phase. So in this work, for exact set match accuracy metric, we
further evaluate our models under two different settings: without using cell
value and using cell value with one model without retraining. To achieve this,
our model is trained without leveraging cell values from the database and can
be evaluated directly when database contents are unavailable. When the model
can access the database contents, if a question token $x_{i}$ matches the cell
values in column $c$, column name of $c$ is inserted before $x_{i}$, as a
signal for the model. More training details are provided in Appendix.

##  4 Results and Analysis

Model | Dev | Test
---|---|---
GAZP (Zhong et al. (2020)) | - | 53.5
BRIDGE (Lin et al. (2020)) | - | 59.9
Ours (heuristic method) | 67.6 | 62.6
Table 1: Results on execution accuracy in test set. Model | Dev | Test
---|---|---
without using cell value
EditSQL Zhang et al. (2019) v1 | 57.6 | 53.4
IRNet v2 Guo et al. (2019) | 63.9 | 55.0
RASQL (anonymous) | 60.8 | 55.7
RYANSQL v2 Choi et al. (2020) | 70.6 | 60.6
Ours | 68.0 | 61.3
using cell value
BRIDGE (Lin et al. (2020)) | 65.5 | 59.2
RATSQL v2 Wang et al. (2019) | 65.8 | 61.9
RATSQL v3 Wang et al. (2019) | 69.7 | 65.6
Ours | 70.0 | 61.9
Table 2: Results on exact set match accuracy in test set (we are comparing
with leaderboard results on the submission date – May 31, 2020).

For the end-to-end evaluation with execution accuracy, Table 1 shows the main
results. We report the results based on the heuristic value filler because we
find that there is no significant difference between heuristic method and
neural baseline model while the heuristic method is more efficient. On the
development set, our model achieves 67.6% execution accuracy and 62.6% on the
test set.

We further show the results of exact set match accuracy in Table 2, under two
evaluation settings. When the cell values are not available, our model
achieves 68.0% and 61.3% accuracy on the development set and the hidden test
set, respectively. Note that RATSQL v2/v3 has significant performance drop
($>$7%) when database contents are unavailable. In comparison, our model is
more robust under this setting. When the database contents are available, with
the simple method, our model obtains 61.9% exact set match accuracy on the
hidden test set, which is comparable with RATSQL v2 with smaller model size
(RATSQL v2 leverages 24-layer pretrained transformer and 8-layer relational
transformer with hidden size 1024 vs. Ours leverages 12-layer pretrained
transformer with hidden size 1024).

Model | Dev
---|---
exact set match accuracy
Full Model | 70.0
\- w/o Auxiliary Task | 68.0
execution accuracy
No Value Filler | 41.4
Heuristic Method | 67.6
Neural Baseline | 67.4
Table 3: Ablation study on dev set. Split | Easy | Medium | Hard | Extra Hard | All
---|---|---|---|---|---
exact set match accuracy without using cell value
Dev | 87.4 | 72.6 | 54.0 | 42.7 | 68.0
Test | 81.9 | 67.7 | 52.5 | 30.3 | 61.3
exact set match accuracy with using cell value
Dev | 87.8 | 74.7 | 58.0 | 44.5 | 70.0
Test | 83.0 | 68.8 | 51.8 | 30.8 | 61.9
execution accuracy
Dev | 85.0 | 70.2 | 60.9 | 43.3 | 67.9
Test | 83.6 | 64.2 | 55.1 | 40.9 | 62.6
Table 4: Accuracy breakdown for different hardness.

Effects of Auxiliary Task: As shown in first part of Table 3, removing the
auxiliary task leads to 2.0% drop in exact set match accuracy. Further
analysis shows that our full model has better effectiveness on easy and medium
level queries, by improving easy-level query accuracy from 80.0% to 87.8%, and
from 72.6% to 74.7% for medium-level query.

Performance of Value Fillers: Here, we are comparing the performance of the
two value fillers, based on the predicted SQL by our full model. The results
are shown in second part of Table 3. Here, we also provide no value filler
results as a baseline, where the predicted SQL from the parser is directly
used for evaluation, which obtains 41.4% execution accuracy. With the
heuristic method, the model achieves 67.6% on the execution accuracy, which is
comparable with the neural baseline model (67.4%), showing that our heuristic
method is effective as a baseline model in the value filling sub-task, and
much simpler. Based on error analysis, the model can be further improved if
the model has the ability to link the values mentioned in question to actual
values in database which have different surface forms, for example, female and
United States in question should be linked to F (denotes female) and USA in
database.

Generalization As we can see from Table 1 and Table 2, there is a large
performance gap between the development set and hidden test set. To
investigate more on this issue, a breakdown of the accuracy by the query
hardness level is provided in Table 4, in all three settings.

From the results, we observe that for the exact set match accuracy, the gap
between the development set and the test set on extra hard questions is large
(12.4% and 13.7%), which is aligned with the finding of Wang et al. (2019).
However, another interesting finding is that the gap is much smaller on the
execution accuracy, which is only 2.4% drop. The reason for this remains
unknown because the test set is not available. However, one possible reason is
that our model provides semantically equivalent predictions as the oracle SQL,
leading to the same execution outputs, while the SQL predictions fail in the
exact set match testing which requires syntactical equivalence. For example,
the keywords EXCEPT and NOT IN can be used to express same meaning, and
similar for INTERSECT and AND in WHERE conditions. Based on this observation,
we suggest reporting both the exact set match accuracy and execution accuracy
in the future work, to gain better understanding of the proposed methods.

##  5 Conclusions

In this work, we leverage an auxiliary task to enhance the schema encoding
ability of encoder. We also propose two value filling baseline models to
bridge the gap between the existing models and a usable text-to-SQL parser.
With experiments on Spider dataset, we show improved performance over the
baselines, with the execution accuracy and exact set match accuracy when
database contents are unavailable.

## References

  * Bogin et al. (2019a) Ben Bogin, Jonathan Berant, and Matt Gardner. 2019a.  Representing schema structure with graph neural networks for text-to-sql parsing.  In _ACL_.
  * Bogin et al. (2019b) Ben Bogin, Matt Gardner, and Jonathan Berant. 2019b.  Global reasoning over database structures for text-to-sql parsing.  _arXiv preprint arXiv:1908.11214_.
  * Bogin et al. (2019c) Ben Bogin, Matt Gardner, and Jonathan Berant. 2019c.  Representing schema structure with graph neural networks for text-to-sql parsing.  _arXiv preprint arXiv:1905.06241_.
  * Choi et al. (2020) Donghyun Choi, Myeong Cheol Shin, Eunggyun Kim, and Dong Ryeol Shin. 2020.  Ryansql: Recursively applying sketch-based slot fillings for complex text-to-sql in cross-domain databases.  _ArXiv_ , abs/2004.03125.
  * Dong and Lapata (2018a) Li Dong and Mirella Lapata. 2018a.  Coarse-to-fine decoding for neural semantic parsing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 731–742. Association for Computational Linguistics.
  * Dong and Lapata (2018b) Li Dong and Mirella Lapata. 2018b.  Coarse-to-fine decoding for neural semantic parsing.  _arXiv preprint arXiv:1805.04793_.
  * Guo et al. (2019) Jiaqi Guo, Zecheng Zhan, Yan Gao, Yan Xiao, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. 2019.  Towards complex text-to-sql in cross-domain database with intermediate representation.  _arXiv preprint arXiv:1905.08205_.
  * Iyer et al. (2017) Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, Jayant Krishnamurthy, and Luke Zettlemoyer. 2017.  Learning a neural semantic parser from user feedback.  _CoRR_ , abs/1704.08760.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_.
  * Li and Jagadish (2014) Fei Li and HV Jagadish. 2014.  Constructing an interactive natural language interface for relational databases.  _VLDB_.
  * Lin et al. (2020) Xi Victoria Lin, Richard Socher, and Caiming Xiong. 2020.  Bridging textual and tabular data for cross-domain text-to-sql semantic parsing.  _arXiv preprint arXiv:2012.12627_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Popescu et al. (2003) Ana-Maria Popescu, Oren Etzioni, and Henry Kautz. 2003.  Towards a theory of natural language interfaces to databases.  In _Proceedings of the 8th international conference on Intelligent user interfaces_ , pages 149–157. ACM.
  * Shi et al. (2020) Peng Shi, Patrick Ng, Zhiguo Wang, Henghui Zhu, Alexander Hanbo Li, Jun Wang, Cicero Nogueira dos Santos, and Bing Xiang. 2020.  Learning contextual representations for semantic parsing with generation-augmented pre-training.  _arXiv preprint arXiv:2012.10309_.
  * Wang et al. (2019) Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. 2019.  Rat-sql: Relation-aware schema encoding and linking for text-to-sql parsers.  _arXiv preprint arXiv:1911.04942_.
  * Warren and Pereira (1982) David HD Warren and Fernando CN Pereira. 1982.  An efficient easily adaptable system for interpreting natural language queries.  _Computational Linguistics_ , 8(3-4):110–122.
  * Yu et al. (2018a) Tao Yu, Zifan Li, Zilin Zhang, Rui Zhang, and Dragomir Radev. 2018a.  Typesql: Knowledge-based type-aware neural text-to-sql generation.  In _Proceedings of NAACL_. Association for Computational Linguistics.
  * Yu et al. (2018b) Tao Yu, Zifan Li, Zilin Zhang, Rui Zhang, and Dragomir Radev. 2018b.  Typesql: Knowledge-based type-aware neural text-to-sql generation.  _arXiv preprint arXiv:1804.09769_.
  * Yu et al. (2020) Tao Yu, Chien-Sheng Wu, Xi Victoria Lin, Bailin Wang, Yi Chern Tan, Xinyi Yang, Dragomir Radev, Richard Socher, and Caiming Xiong. 2020.  Grappa: Grammar-augmented pre-training for table semantic parsing.  _arXiv preprint arXiv:2009.13845_.
  * Yu et al. (2018c) Tao Yu, Michihiro Yasunaga, Kai Yang, Rui Zhang, Dongxu Wang, Zifan Li, and Dragomir Radev. 2018c.  Syntaxsqlnet: Syntax tree networks for complex and cross-domain text-to-sql task.  In _Proceedings of EMNLP_. Association for Computational Linguistics.
  * Yu et al. (2018d) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, et al. 2018d.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.  _arXiv preprint arXiv:1809.08887_.
  * Zhang et al. (2019) Rui Zhang, Tao Yu, He Yang Er, Sungrok Shim, Eric Xue, Xi Victoria Lin, Tianze Shi, Caiming Xiong, Richard Socher, and Dragomir Radev. 2019.  Editing-based sql query generation for cross-domain context-dependent questions.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing_. Association for Computational Linguistics.
  * Zhong et al. (2020) Victor Zhong, Mike Lewis, Sida I Wang, and Luke Zettlemoyer. 2020.  Grounded adaptation for zero-shot executable semantic parsing.  _arXiv preprint arXiv:2009.07396_.
  * Zhong et al. (2017) Victor Zhong, Caiming Xiong, and Richard Socher. 2017.  Seq2sql: Generating structured queries from natural language using reinforcement learning.  _arXiv preprint arXiv:1709.00103_.

##  Appendix A Appendices

###  A.1 Experimental Setup

Within the encoder, the hidden size is 1024 for the pretrained transformer.
For the LSTM in the aggregation function $f_{lstm}$, the hidden size is 512.
The hidden size of parameters in the decoder LSTM and the binary classifier of
auxiliary task is 300. The overall model size is 822M in disk. Adam optimizer
with default hyper-parameters is used. Batch size is 32 and accumulating
gradient is applied. The learning rate is set to 5e-4 for the non-pretrained
parameters and 2.5e-5 for pretrained parameters. The weight between the main
parsing task and the auxiliary task is 1:0.5. The experiment is conducted with
Tesla V100 16GB and PyTorch version 1.3.0. The Levenshtein distance is
calculated by the FuzzyWuzzy 444https://github.com/seatgeek/fuzzywuzzy
library. The exact set match accuracy and execution accuracy is calculated by
the official evaluation script
555https://github.com/taoyds/spider/blob/master/evaluation.py.

The model is trained up to 20K steps for 10 hours on single GPU. The best
parsing model is selected based on the exact set match accuracy on development
set. For the neural value filler, query level accuracy is used for selecting
best model.