Active hypothesis testing on a tree: Anomaly detection under hierarchical observations
Active hypothesis testing on a tree: Anomaly detection under hierarchical observations
复制标题
树上的主动假设检验：分层观察下的异常检测
DOI：
10.1109/isit.2017.8006677
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Qing Zhao
中科院分区：
文献类型：
--
作者：
Chao Wang;Kobi Cohen;Qing Zhao
研究了在大量的M个进程中检测出少数异常进程的问题。每次都可以从所选的过程子集中获取聚合的观察结果，其中所选的子集符合给定的二叉树结构。随时间的推移，随机观察值具有一般分布，该分布可能取决于所选子集的大小和子集中异常过程的数量。目标是在可靠性约束下最小化样本复杂性（即表示检测延迟的预期观察数）的顺序搜索策略。开发了一个序列测试，结果是在树上有偏差的随机行走，并且在检测精度方面显示为渐近最优。此外，它在M中实现了最优的对数阶样本复杂度，前提是当M趋于无穷时，存在和不存在异常过程的聚合观测之间的Kullback-Liebler散度在树结构的所有层次上都远离零。在伯努利情况下，还确定了聚集观测到纯噪声的衰减率的充分条件，在此条件下，M的亚线性尺度保持不变。
The problem of detecting a few anomalous processes among a large number of M processes is considered. At each time, aggregated observations can be taken from a chosen subset of processes, where the chosen subset conforms to a given binary tree structure. The random observations are i.i.d. over time with a general distribution that may depend on the size of the chosen subset and the number of anomalous processes in the subset. The objective is a sequential search strategy that minimizes the sample complexity (i.e., the expected number of observations which represents detection delay) subject to a reliability constraint. A sequential test that results in a biased random walk on the tree is developed and is shown to be asymptotically optimal in terms of detection accuracy. Furthermore, it achieves the optimal logarithmic-order sample complexity in M 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 M approaches infinity. Sufficient conditions on the decaying rate of the aggregated observations to pure noise under which a sublinear scaling in M is preserved are also identified for the Bernoulli case.
DOI：
10.1007/978-1-4419-9473-8
发表时间：
2011-01-01
期刊：
INTRODUCTION TO HEAVY-TAILED AND SUBEXPONENTIAL DISTRIBUTION
影响因子：
--
作者：
Foss, Sergey;Korshunov, Dmitry;Zachary, Stan
通讯作者：
Zachary, Stan
影响因子：
2.5
作者：
Heydari, Javad;Tajer, Ali;Poor, H. Vincent
通讯作者：
Poor, H. Vincent