Sequential anomaly detection under sampling constraints

Tsopelakos, Aristomenis

Permalink

https://hdl.handle.net/2142/120538 Copy

Description

Title

Sequential anomaly detection under sampling constraints

Author(s)

Tsopelakos, Aristomenis

Issue Date

2023-04-21

Director of Research (if dissertation) or Advisor (if thesis)

Fellouris, Georgios

Doctoral Committee Chair(s)

Fellouris, Georgios

Committee Member(s)

• Hajek, Bruce
• Milenkovic, Olgica
• Moustakidis, George

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

sequential anomaly detection, sequential multiple hypothesis testing, sampling design under constraints, generalized error metrics, composite hypothesis testing.

Abstract

The problem of sequential anomaly detection is considered, where multiple data sources are monitored in real-time, and the goal is to identify the ones that exhibit outlying statistical behavior, when it is not possible to sample all sources at all times. A detection scheme in this context requires specifying not only when to stop sampling and which sources to identify as anomalous upon stopping but also which sources to sample at each time instance until stopping. A novel formulation for this problem is proposed, in which the number of anomalous sources is not necessarily known in advance and the number of sampled sources per time instance is not necessarily fixed. Instead, an arbitrary lower bound and an arbitrary upper bound are assumed on the number of anomalous sources, and the fraction of the expected number of samples over the expected time until stopping is required not to exceed an arbitrary, user-specified level. In addition to this sampling constraint, the probabilities of at least one false alarm and at least one missed detection are controlled below user-specified tolerance levels. A general criterion is established for a policy to achieve the minimum expected time until stopping to a first-order asymptotic approximation as the two familywise error rates go to zero. Moreover, asymptotic optimality is established for two families of sampling policies. In the first family, named as probabilistic family, each sampling rule chooses each source at each time instance with a probability that depends on past observations only through the current estimate of the subset of anomalous sources. In the second family, named as ordering family, each sampling rule decides the sources to sample based on the ordering of the likelihood ratio statistics, where randomization may be applied only for the treatment of the decimal part of the sampling size. The detection policies can also be adapted to treat generalized error metrics. We examine two error metrics: in the first one, we control the probability of a prescribed number of misclassification errors, and in the second one, both the probabilities of a number of false alarms and a number of missed detections. We also study the sequential anomaly detection problem from the perspective of the composite hypotheses setting. In the composite hypotheses setting, the samples collected from each source follow the model of a distribution parameterized by a parameter that belongs to one of two disjoint subsets of a compact Euclidean space. The two candidate subsets are not necessarily the same for each source. If the parameter belongs to the first subset, we characterize the source as outlying; otherwise, we characterize it as regular. The samples received from different sources are independent of each other. In all frameworks, we provide simulations that compare the performance of the sampling rules from both families for small fixed thresholds on the error probabilities.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Aristomenis Tsopelakos

Owning Collections