Many industrial and security applications employ a suite of sensors for detecting abrupt changes in temporal behavior patterns. These abrupt changes typically manifest locally, rendering only a small subset of sensors informative. Continuous monitoring of every sensor can be expensive due to resource constraints, and serves as a motivation for the bandit quickest changepoint detection problem, where sensing actions (or sensors) are sequentially chosen, and only measurements corresponding to chosen actions are observed. We derive an information-theoretic lower bound on the detection delay for a general class of finitely parameterized probability distributions. We then propose a computationally efficient online sensing scheme, which seamlessly balances the need for exploration of different sensing options with exploitation of querying informative actions. We derive expected delay bounds for the proposed scheme and show that these bounds match our information-theoretic lower bounds at low false alarm rates, establishing optimality of the proposed method. We then perform a number of experiments on synthetic and real datasets demonstrating the effectiveness of our proposed method.
翻译:许多工业和安全应用都使用一套传感器来探测时间行为模式的突然变化。这些突然变化通常在当地显现,仅使一小部分传感器知情。由于资源限制,对每个传感器的持续监测费用可能很高,并成为强盗最快速变化点探测问题的动机,在这些问题上,测距行动(或传感器)是按顺序选择的,而且只观察到与所选择的行动相应的测量。我们从一般类别的有限参数概率分布的探测延迟中得出一个信息理论下限。我们然后提出一个计算高效的在线遥感计划,在探索不同感测选项的需要与利用查询信息行动之间实现无缝平衡。我们为拟议办法设定了预期的延迟界限,并表明这些界限与我们低的虚假警报率相匹配,从而确定了拟议方法的最佳性。我们随后对合成和真实数据集进行了一些实验,以证明我们拟议方法的有效性。