Active Sampling for the Quickest Detection of Markov Networks
Active Sampling for the Quickest Detection of Markov Networks
复制标题
DOI：
10.1109/tit.2021.3124166
复制
发表时间：
2022-04
影响因子：
2.5
通讯作者：
A. Tajer;Javad Heydari;H. Poor
中科院分区：
文献类型：
--
作者：
A. Tajer;Javad Heydari;H. Poor
考虑形成马尔可夫随机场(MRF)的$n$随机变量。马尔可夫随机场的真实模型是未知的，并且假定它属于一个二进制集合。其目标是对随机变量进行顺序采样(一次一个)，这样可以用最少的样本数来检测真实的MRF模型，同时并行地控制决策的可靠性。最优决策过程的核心要素是选择和采样随时间推移的随机变量的规则。这样的过程在每个时刻并自适应于收集的数据，选择预期对模型最有信息量的随机变量，从而使达成可靠决策所需的样本总数降至最低。现有的磁流变结构检测研究一般是对整个网络同时进行采样，而不考虑数据采集过程，而侧重于设计最优的检测规则。本文刻画了一般马尔可夫随机场的抽样过程，证明了抽样过程在大$n的渐近线上是最优的。设计抽样过程中的关键洞察力是设计一种信息测量方法，以捕捉决策随时间推移的内在统计相关性。此外，当MRF可以用非循环概率图模型建模时，抽样规则具有计算简单的形式。给出了一般情况下的性能分析，并在几种特殊情况下对结果进行了解释：高斯MRF、非渐近状态、受控(主动)感知的Chernoff规则和簇检测问题。
Consider $n$ random variables forming a Markov random field (MRF). The true model of the MRF is unknown, and it is assumed to belong to a binary set. The objective is to sequentially sample the random variables (one-at-a-time) such that the true MRF model can be detected with the fewest number of samples, while in parallel, the decision reliability is controlled. The core element of an optimal decision process is a rule for selecting and sampling the random variables over time. Such a process, at every time instant and adaptively to the collected data, selects the random variable that is expected to be most informative about the model, rendering an overall minimized number of samples required for reaching a reliable decision. The existing studies on detecting MRF structures generally sample the entire network at the same time and focus on designing optimal detection rules without regard to the data-acquisition process. This paper characterizes the sampling process for general MRFs, which is shown to be optimal in the asymptote of large $n$ . The critical insight in designing the sampling process is devising an information measure that captures the decisions’ inherent statistical dependence over time. Furthermore, when the MRFs can be modeled by acyclic probabilistic graphical models, the sampling rule is shown to take a computationally simple form. Performance analysis for the general case is provided, and the results are interpreted in several special cases: Gaussian MRFs, non-asymptotic regimes, Chernoff’s rule for controlled (active) sensing, and the problem of cluster detection.