Asymptotically Optimal Search for a Change Point Anomaly under a Composite Hypothesis Model

The problem of searching for a change point anomaly, as considered in this paper, is closely related to both the sequential design of experiments and change point detection. Within the sequential design of experiments, search problems involving a finite set of processes require critical decisions about which processes to sample sequentially at each time step. This process continues until testing concludes, and the anomaly’s location is reliably identified. This class of problems has been referred to in recent years as controlled sensing for hypothesis testing [2] or active hypothesis testing [3]. These frameworks trace their origins to Chernoff’s seminal work on sequential design of experiments [4]. Chernoff primarily addressed binary hypothesis testing, introducing a randomized test strategy, the Chernoff test, which is asymptotically optimal as the error probability approaches zero. Variations and extensions of this framework are discussed in Section I-B. However, these approaches typically assume a fixed distribution setting, where the anomalous state is present from the outset.

In contrast, the problem addressed in this paper involves a target process that transitions from a benign to an anomalous state at an unknown change point. This aspect aligns the problem with change point detection, where the objective is to identify a change in the distribution as quickly as possible after it occurs, while maintaining a low false alarm rate to avoid premature declarations. The CUSUM algorithm, introduced in [5], serves as a foundational method in change point detection for single processes, achieving optimality under certain performance criteria. Variants of this problem are also discussed in Section I-B. Despite these connections, the specific problem of searching for a change point anomaly across multiple processes under a composite hypothesis model considered here has not been analyzed before. Below, we summarize the main contributions of this work.

First, in terms of algorithm development, We propose a novel algorithm, Searching for Change Point Anomaly (SCPA), to address the problem at hand. The algorithm is deterministic with low-complexity implementations and operates through three distinct phases: Exploration, exploitation, and sequential testing. In the exploration phase, all cells are probed in a round-robin fashion to estimate the unknown parameter. During the exploitation phase, probing focuses on the cell where the change point is most likely to occur. Finally, in the sequential testing phase, this cell is sampled until sufficient confidence is reached to declare it as anomalous. A notable challenge arises from early observations in the pre-change regime, which could delay detection. This is mitigated by strategically resetting the statistic measure. Detailed descriptions of the algorithm are provided in Section III.

In terms of theoretical performance analysis, we establish the asymptotic optimality of SCPA as the error probability approaches zero. Traditional change point analysis often restricts the change point $\tau_{c}$ by assuming prior distributions on $\tau_{c}$ or adopting weaker performance metrics, such as fixed, non-vanishing error rates. Here, we introduce a novel approach to tackle the problem by setting $\tau_{c}$ in a manner that ensures robust guarantees for vanishing error probabilities. Specifically, we impose an asymptotic constraint on $\tau_{c}$, enabling it to be arbitrarily large while ensuring it occurs within a timeframe that does not excessively delay detection. This approach enables strong guarantees on the vanishing of error probabilities, aligning with the classical Chernoff’s sequential experimental design [4], and addresses gaps in existing approaches where globally optimal solutions are unavailable under general settings [6, 7]. Current modifications often use techniques like increasing curved boundaries [8] or constraining local false alarm probabilities [7]. In contrast, our analysis provides explicit conditions under which SCPA achieves asymptotic optimality. This setting is particularly applicable to real-world scenarios, such as cyber anomaly detection, where algorithms operate during intervals where anomalies are likely to manifest (e.g., before corrective actions like patch installations are implemented). More generally, it applies to systems operating within time intervals where the focus is on ensuring vanishing error probabilities within periods after the change point. This robust framework contrasts with approaches accepting fixed error rates across the entire time horizon.

We demonstrate the asymptotic optimality of SCPA in two scenarios: (i) When the distributions of normal and anomalous processes are unknown, and (ii) when the parameter value under the null hypothesis is known and identical across all non-anomalous processes. In both cases, our algorithm matches the performance of the active hypothesis testing setting in [9], which is a special case of our problem where the anomaly is present from the start without temporal change. Finally, we present simulation results that validate our theoretical findings and demonstrate the practical effectiveness of the SCPA algorithm.

As highlighted earlier, our problem is closely related to both sequential experimental design and change point detection. Sequential experimental design, originally introduced by Chernoff [4], has been extensively studied and expanded upon in works such as [3, 2, 10, 11, 12, 13, 14, 15, 16, 9, 17, 18, 19, 20, 21, 22, 23, 24]. The specific challenge of anomaly detection across multiple processes has been addressed in [25, 20, 14, 16, 21, 22, 23, 10, 12, 9, 13, 15]. The detection of abnormal processes over densities with an unknown parameter was explored in [10], focusing on independent process states across cells. In [25], anomaly detection among $M$ processes was studied, where $K$ processes could be observed at each time step. Observations followed one of two known distributions, depending on whether the process was normal or abnormal. A deterministic search policy was proven asymptotically optimal in minimizing detection time under an error probability constraint. An extension of [25] was considered in [9], where observations followed a common distribution with an unknown parameter, varying based on the process state. A sequential search strategy achieving asymptotic optimality was developed. For Poisson point processes with unknown rates, [13] established an asymptotically optimal policy for single-location probing, requiring a randomized selection rule and linear exploration time. Non-parametric detection over finite observation spaces was studied in [26], showing asymptotic optimality with logarithmic exploration time when the null distribution is known. Extensions to M-ary and composite hypothesis testing for single processes were investigated in [27, 28]. In contrast to these anomaly detection frameworks with fixed distribution settings, our setting addresses a dynamic scenario involving a change point where the anomalous process transitions between states. Additional works on sequential detection across independent processes include [29, 30, 31, 10, 32, 33].

This work also relates to the field of change point detection. Page [34] introduced CUSUM charts, which leverage cumulative data for enhanced detection efficiency. Shiryaev [35] developed a Bayesian framework minimizing average detection delay with known geometric priors. Lorden [36] proposed a minimax framework optimizing worst-case detection delay, with CUSUM achieving asymptotic optimality. Subsequent improvements to Lorden’s criterion were presented in [37, 38]. Pollak [39] introduced a single-maximization criterion, showing the asymptotic optimality of Shiryaev-Roberts and CUSUM algorithms [28]. Non-Bayesian quickest detection was explored in [40], demonstrating CUSUM’s optimality. In [41], the problem of detecting distribution changes in random vector sequences was considered, addressing unknown post-change parameters influenced by control actions, requiring both a stopping rule and a sequential control policy. [42] addressed streaming data changing from a known to an unknown parametric distribution, combining CUSUM with post-change parameter estimation. Shiryaev [43] examined change detection in a single process under a Bayesian loss framework, while Lorden [44] and Pollak [45] proposed minimax criteria for i.i.d. observations with known pre- and post-change distributions but unknown deterministic change points. Asymptotic performance of Shiryaev’s procedures was studied in [46]. Extensions and variations appear in [6, 47, 48, 49]. Multi-stream settings were addressed in [50], where streams share a known distribution pre-change, and one stream diverges to a different known distribution post-change. [51] generalized to exponential distributions with a common pre-change parameter, where one stream shifts to an unknown parameter. However, these studies focused on declaring a change without pinpointing the affected stream.

We consider the problem of detecting a change point in an anomalous process within a finite set of $M$ processes, where $M$ is large yet finite. Initially, before the change point, all processes—including the anomalous one—are in a normal state. After the change point, the anomalous process transitions to an abnormal state. Specifically, the system consists of $M$ discrete time stochastic processes $\{X_{n}^{m}\}_{n\geq 1},1\leq m\leq M$, with $X_{n}^{m}$ taking real values at times $n=1,2,...$. The distribution of the anomalous process changes at an unknown deterministic change point $\tau_{c}$. If process $m$ is the anomalous one, we denote this as hypothesis $H_{m}$ being true. Drawing an analogy from target search, we often refer to the anomalous process as the target, which can be located in any of the $M$ cells.

We focus on a composite hypothesis setting, where the observation distribution depends on an unknown parameter (vector). Let $\theta_{m}$ denote the unknown parameter specifying the observation distribution for cell $m$. When cell $m$ is observed at time $n$, an observation $y_{m}(n)$ is drawn independently from a common density $f(y|\theta_{m})$, where $\theta_{m}\in\Theta$ and $\Theta\subseteq\mathbb{R}$ represents the parameter space for all cells. We define two disjoint open subsets of $\Theta$: $\Theta^{(0)}$ and $\Theta^{(1)}$, representing the parameter spaces for the non-anomalous distribution and the anomalous distribution, respectively. Specifically, under the non-anomalous distribution, $\theta_{m}\in\Theta^{(0)}$, while under the anomalous distribution, $\theta_{m}\in\Theta^{(1)}$. Under hypothesis $H_{m}$, the observations $\{y_{j}(n)\}_{n\geq 1},\forall j\neq m$, are drawn independently from $f(y|\theta_{j})$ with $\theta_{j}\in\Theta^{(0)}$. For cell $m$, the observations $y_{m}(1),y_{m}(2),\ldots,y_{m}(\tau_{c}-1)$ are drawn independently from $f(y|\theta_{m})$ with $\theta_{m}\in\Theta^{(0)}$, and the observations $y_{m}(\tau_{c}),y_{m}(\tau_{c}+1),\ldots$ are drawn independently from $f(y|\theta_{m})$ with $\theta_{m}\in\Theta^{(1)}$. The prior probability that $H_{m}$ is true is denoted by $\pi_{m}$, where $\sum_{m=1}^{M}\pi_{m}=1$. To avoid trivial solutions, we assume $0<\pi_{m}<1$ for all $m$. At each time step, only $K$ cells ($1\leq K\leq M$) can be observed. Let $\mathbf{P}_{m}$ denote the probability measure under hypothesis $H_{m}$, and let $\mathbf{E}_{m}$ represent the expectation operator with respect to the measure $\mathbf{P}_{m}$.

The stopping time $\tau$ is defined as the time when the decision-maker concludes the search by declaring the target’s location. Let $\delta\in\{1,2,\ldots,M\}$ be a decision rule, where $\delta=m$ indicates that the decision-maker declares $H_{m}$ to be true. Define $\phi(n)\in\{1,2,\ldots,M\}^{K}$ as the selection rule specifying the $K$ cells chosen for observation at time $n$. The time-series vector of selection rules is denoted by $\boldsymbol{\phi}=(\phi(n),n=1,2,\ldots)$. Let $\textbf{y}_{\phi(n)}(n)$ represent the vector of observations obtained from the selected cells $\phi(n)$ at time $n$, and let $\textbf{y}(n)=\{\phi(t),\textbf{y}_{\phi(t)}(t)\}_{t=1}^{n}$ represent the collection of all cell selections and corresponding observations up to time $n$. A deterministic selection rule $\phi(n)$ at time $n$ is a mapping from $\textbf{y}(n-1)$ to $\{1,2,\ldots,M\}^{K}$. Alternatively, a randomized selection rule $\phi(n)$ maps $\textbf{y}(n-1)$ to probability mass functions over $\{1,2,\ldots,M\}^{K}$.

An admissible strategy $\Gamma$ for the sequential change point anomaly detection problem is characterized by the tuple $\Gamma=(\tau,\delta,\boldsymbol{\phi})$. Note that we seek a search strategy that does not rely on knowledge of $\tau_{c}$ and assumes no prior knowledge about it.

We begin by defining the error probabilities associated with a sequential decision strategy $\Gamma$. In classical change point detection involving a single process, the decision rule declares a change has occurred once sufficient evidence is gathered. In this setting, only false alarm events can occur, which correspond to declaring a change before it actually happens. After the change point, all subsequent decisions are correct. The objective in this case is to strike a balance between minimizing the detection delay, i.e., the time elapsed between the actual change point and the declaration time, and minimizing the false alarm probability.

In contrast, for anomaly change point detection involving multiple processes, as considered in this paper, the objective is not only to detect whether a change has occurred but also to identify the anomalous process in which the change occurred. As a result, errors arise from two types of events, depending on whether the change point has occurred at or before the stopping time $\tau$: false alarms and missed detections. The false alarm probability is the probability of declaring an anomaly in one of the $M$ cells before the change point occurs (when all processes are still in their normal states). Conversely, the missed detection probability is the probability of incorrectly identifying a non-anomalous cell as the target after the change point has occurred (when one process is in an anomalous state, but the decision-maker fails to detect it and instead declares another process as anomalous).

Formally, under strategy $\Gamma$ and hypothesis $H_{m}$, the false alarm probability is given by:

and the miss detection probability is given by:

Hence, the error probability under hypothesis $H_{m}$ is given by:

Finally, the overall error probability under strategy $\Gamma$ is given by:

Note that in the special case of $M=1$, i.e., a single anomalous process, missed detection events do not occur. Consequently, the error probability reduces to the false alarm probability (1).

Let $\textbf{E}(\left(\tau-\tau_{c}\right)^{+}|\Gamma;\tau_{c})=\sum_{m=1}^{M}\pi_{m}\textbf{E}_{m}(\left(\tau-\tau_{c}\right)^{+}|\Gamma;\tau_{c})$ be the average detection delay under $\Gamma$, where $x^{+}=\max\{x,0\}$. We adopt the Bayes risk framework, as utilized in both active hypothesis testing and change point detection formulations [4, 25, 28, 52, 9, 29], by assigning a cost of $c$ for each observation made after the change point and a loss of $1$ for a wrong declaration. The risk under strategy $\Gamma$ when hypothesis $H_{m}$ is true and change point $\tau_{c}$, is thus given by:

The average risk is given by:

The objective is to find a strategy $\Gamma$ that minimizes the Bayes risk $R(\Gamma)$ over all possible realizations of $\tau_{c}$ without knowledge of its value:

The SCPA algorithm is structured into exploration and exploitation epochs, as described below.

1. 1.

   Phase 1: Sequential Round-Robin Exploration: Observe the cells sequentially in a round-robin manner, collecting $y_{m}(n)$ (the observation from cell $m$ at time $n$), and estimate the cell parameter using the last $N$ observations, $\tilde{\textbf{y}}_{m}\triangleq\{y_{m}(r_{1}),...,y_{m}(r_{N})\}$, through an unconstrained maximum likelihood estimator (MLE)

   $$\hat{\theta}_{m}(n)\triangleq\arg\max_{\theta\in\Theta}f(\tilde{\textbf{y}}_{m}|\theta).$$

   (10)

   Here, $N$ is a predefined parameter, and its selection will be discussed later in the algorithm description.
   If $|\{m:\hat{\theta}_{m}(n)\not\in\Theta^{(0)}\}|=1$ (i.e., there is exactly one cell suspected of having experienced a change point), proceed to Phase 2. Otherwise, return to Phase 1.

2. 2.

   Phase 2: Exploitation with Targeted Parameter Estimation: Let $T$ denote the most recent time at which Phase 1 was exited, and let $\hat{m}(n)=\{m:\hat{\theta}_{m}(n)\not\in\Theta^{(0)}\}$ represent the index of the single cell whose MLE falls outside $\Theta^{(0)}$. Observe cell $\hat{m}(n)$. Based on the observations $\overline{\textbf{y}}_{\hat{m}(n)}(n)\triangleq\{y_{\hat{m}(n)}(T+1),...,y_{\hat{m}(n)}(n)\}$ estimate the cell parameter using the unconstrained MLE:

   $$\hat{\theta}_{\hat{m}(n)}(n)\triangleq\arg\max_{\theta\in\Theta}f(\overline{\textbf{y}}_{\hat{m}(n)}(n)|\theta).$$

   (11)

   If $\hat{\theta}_{\hat{m}(n)}(n)\in\Theta^{(0)}$, return to Phase 1. Otherwise, proceed to Phase 3.

3. 3.

   Phase 3: Sequential Testing: Let

   $$\hat{\theta}_{m}^{(0)}(n)\triangleq\arg\max_{\theta\in\Theta^{(0)}}f(\overline{\textbf{y}}_{m}(n)|\theta)$$

   (12)

   be the constrained MLE for cell $m$ to be in a normal state, and

   $$\begin{array}[]{l}\displaystyle S_{m}(n)\triangleq\sum_{t=T+2}^{n}\ell_{m}^{(\hat{\theta}_{m}(t-1),\hat{\theta}_{m}^{(0)}(n))}(t)\vspace{0.2cm}\\ \displaystyle\hskip 28.45274pt=\sum_{t=T+2}^{n}\log\frac{f(y_{m}(t)|(\hat{\theta}_{m}(t-1))}{f(y_{m}(t)|\hat{\theta}_{m}^{(0)}(n))}\end{array}$$

   (13)

   be the sum of the adaptive LLR (SALLR) of cell $m$ at time n used to confirm hypothesis $m$.

   If $S_{\hat{m}(n)}(n)\geq-\log(c)$ stop the test and declare $\delta=\hat{m}(n)$ as the anomalous cell, otherwise go to Phase 2.

We start by analyzing the SCPA algorithm in the setting where the parameters of both the anomalous and non-anomalous distributions are unknown. The following theorem establishes its asymptotic optimality:

Here, we assume that the parameter under the null hypothesis, $\theta=\theta^{(0)}\in\Theta^{(0)}$, is known and equal for the non-anomalous distribution across all cells. This setup models many anomaly detection scenarios, where the decision maker can infer the pre-change distribution parameters, which represent the typical distribution before the change, while there is uncertainty regarding the distribution after the change point (i.e., under abnormal conditions). To utilize this information, we substitute the estimation of the parameter $\theta^{(0)}$ in the SALLR statistics (13) with its known true value:

The following theorem establishes the asymptotic optimality of SCPA algorithm in this setting.

We note that having knowledge of the parameter for the non-anomalous distribution enhances the algorithm’s performance. This improvement is evident from the fact that $D(\theta^{(1)}||\theta^{(0)})>D(\theta^{(1)})$, which implies that the Bayes risk stated in Theorem 2 is smaller than the risk presented in Theorem 1.

To prove the theorem, we introduce the following definitions: