Sequential Design of Experiments for Anomaly Detection

Wang, Chao

Sequential Design of Experiments for Anomaly Detection

Abstract

This dissertation focuses on the sequential design of experiments for anomaly detection. Specifically, the problem of detecting a few anomalous processes among a large number of processes is considered. The rare events may represent opportunities with exceptional returns or anomalies associated with high costs or potential catastrophic consequences. Examples include financial trading opportunities and transmission opportunities in dynamic spectrum access, endogenous extreme events or exogenous attacks in communication and computer networks, etc. For all these applications, the problem of searching for the rare has the following defining features: (i) the massive search space; (ii) the need for high detection accuracy, especially in terms of missing a rare event; (iii) the time sensitivity of the problem, either due to the transient nature of opportunities or the urgency for taking recourse measures in the face of anomalies. The goal is thus to detect the rare events as quickly and as reliably as possible when the total number of hypotheses is large and the observations are probabilistic thus inherently ambiguous. The performance measure of interest is sample complexity (the total number of observations which represents the detection delay) with respect to the size of the search space and the required detection accuracy. The key to a sublinear scaling in the problem size is to exploit the hierarchical structure of the search space inherent to many applications. In the first part of the dissertation, we develop an algorithm for the anomaly detection of which the sample complexity is in optimal scaling with the size of the search space. We consider the case where the observations from all the processes are noiseless. The anomaly detection problem falls into the general class of the group testing problem. We consider the quantitative group testing problem where the objective is to identify defective items in a given population based on results of tests performed on subsets of the population. Under the quantitative group testing model, the result of each test reveals the number of defective items in the tested group. We establish the optimal nested test plan in closed form which achieves the minimum number of tests by nested test plans. This optimal nested test plan is also order-optimal among all test plans as the population size approaches infinity. Using heavy-hitter detection as a case study, we show via simulation examples orders of magnitude improvement of the group testing approach over two prevailing sampling-based approaches in detection accuracy and counter consumption. In the second part of the dissertation, we develop an algorithm for the anomaly detection problem of which the sample complexity achieves optimal scaling with the size of the search space as well as the accuracy requirements. We consider the case where the observations from the processes are noisy and the noisy observations are specific by general distributions. Aggregated observations can be taken from a chosen subset of processes, where the chosen subset conforms to a binary tree structure. The random observations are drawn from a general distribution that may depend on the size of the chosen subset and the number of anomalous processes in the subset. We propose a sequential search strategy by devising an information-directed random walk (IRW) on the tree-structured observation hierarchy. Subject to a reliable constraint, the proposed policy is shown to be asymptotically optimal in terms of detection accuracy. Furthermore, it achieves the optimal logarithmic-order sample complexity in the in terms of the size of the search space provided that the Kullback-Liebler divergence between aggregated observations in the presence and the absence of anomalous processes are bounded away from zero at all levels of the tree structure as the size of the search space approaches infinity. Sufficient conditions on the decaying rate of the aggregated observations to pure noise under which a sublinear scaling in the size of the search space is preserved are also identified for the Bernoulli case. The algorithms proposed in both of the two parts are adaptive test plans which are deterministic with search actions explicitly specified at each given time. They involve little online computation beyond calculating the sample mean or the sum log-likelihood ratio. The inherent tree structure of the also leads to low memory requirement. They are thus particularly attractive for online applications.

Date Issued

2018-05-30

Keywords

heavy hitter detection; sequential design of experiments; Applied mathematics; Electrical engineering; active hypothesis testing; adaptive test plan; anomaly detection; group testing

Committee Chair

Zhao, Qing

Committee Member

Tong, Lang
Tang, Ao

Degree Discipline

Electrical and Computer Engineering

Degree Name

Ph. D., Electrical and Computer Engineering

Degree Level

Doctor of Philosophy

Types

dissertation or thesis