UC Davis

Sequential change-point analysis is a fundamental problem that arises in a variety of fields including network monitoring, power system, climate modeling, finance, image analysis, etc. Based on the sequential observations and additional information about observations, one of the main goals of change-point analysis is to detect the change point as quickly as possible. Beyond detecting the change, discovering what is the post-change status of the system is also important. In this dissertation, we study two sequential change point analysis problems. One is the two-stage sequential change point diagnosis (SCD) problem. The other is the data-driven quickest change point detection (QCD) problem.

In the first part, we study the two-stage SCD problem in the Bayesian setting. In the SCD problem, the data distribution will change at an unknown time, from distribution $f_0$ to one of the $I$ candidate distributions. We need to detect the change point as quickly as possible and identify the distribution after the change as accurately as possible. In existing work on SCD problems, one must detect the change and identify the distribution after the change at the same time. In practice, however, after we detect thechange, we may still have the opportunity to observe extra data samples with low unit cost, which may help us to make a more accurate identification decision. Motivated by this, we formulate a two-stage SCD problem. In this problem, we have two stopping times. The first stopping time is the time to raise an alarm once a change has been detected. After that, we can keep collecting more observations that have a low unit cost. The second stopping time is the time when we are ready to make the identification decision. Therefore, in our problem formulation, change detection and distribution identification become two different stages of the whole SCD procedure. The goal of a two-stage SCD rule is to minimize the total cost including delay, false alarm, and misdiagnosis probabilities. To solve the two-stage SCD problem, we first convert the problem into a two-ordered optimal stopping time problem. Using tools from optimal multiple stopping time theory, we obtain the optimal SCD rule. Moreover, to address the high computational complexity issue of the optimal SCD rule, we further propose a computationally efficient threshold-based two-stage SCD rule. By analyzing the asymptotic behaviors of the delay, false alarm, and misdiagnosis costs, we show that the proposed threshold SCD rule is asymptotically optimal as the per-unit delay costs go to zero. Furthermore, we extend the two-stage SCD problem to a sensor array setting where there is a sensor array with $L$ sensors monitoring the environment. Once a change happens in the environment, the change will propagate across the sensor array gradually. After detecting the change, we are allowed to continue observing more samples so that we can identify the distribution after the change more accurately. Similar to the single sensor case, we characterize the structure of the optimal diagnosis rule. But this rule has considerably high complexity. Therefore, we further propose a threshold rule SCD rule for the multi-sensor setting. In addition, we also prove that this threshold rule is asymptotically optimal as the per-unit delay costs go to zero.

In the second part, we study the Bayesian QCD problem and provide data-driven solutions for this problem. The optimal solutions to the QCD problem under different settings have been extensively studied. Most of these solutions require a priori information about the QCD model and i.i.d. data samples. However, in many real-world applications, these requirements may not be satisfied. In these situations, the optimal QCD rules are not available. This dissertation proposes two data-driven approaches for the online Bayesian QCD problem, including the deep Q-network (DQN) method and the Neural Monte Carlo (NMC) based data-driven change-point detection rule. The NMC-based method is guaranteed to converge. More importantly, these two methods work not only for i.i.d. data samples but also for non-i.i.d. data. Numerical results illustrate that the two proposed methods can detect the change point accurately and timely.