Quickest Change Detection in Parametric Models With 1-Bit Measurements

技术摘要：参数模型下基于 1-bit 测量的最快变化检测

问题定义
本文研究了在数据受限于 1-bit 量化测量场景下的在线变化点检测问题。该设定涉及来自参数族 $p_X(x; \theta)$ 的独立同分布 (i.i.d.) 观测序列 $\{X_t\}$。当发生变化时，分布从已知的变化前参数 $\theta_0$ 转移到未知的变化后参数 $\theta_1 \in \Theta_1$，变化发生的时间 $\kappa$ 是未知的。

至关重要的是，原始观测值 $X_t$ 无法直接获取。相反，传感节点应用一个自适应 1-bit 量化器，生成基于阈值 $\tau_t$ 的二进制测量值 $B_t \in \{-1, 1\}$：
$$B_t = \begin{cases} 1 & \text{若 } X_t \leq \tau_t \\ -1 & \text{若 } X_t > \tau_t \end{cases}$$
阈值 $\tau_t$ 可以根据过去的观测值进行自适应选择。目标是设计一个联合策略，通过选择阈值序列 $\{\tau_t\}$ 和停止时间 $T$，在满足变化前分布下的平均运行长度 (ARL) 约束（即 $E_\infty[T] \geq \gamma$）的同时，最小化最坏情况平均检测延迟 (WADD)。

理论下界
作者为任何使用 1-bit 测量的程序建立了一个基础的检测延迟下界。他们定义了 1-bit Kullback-Leibler (KL) 散度 $KL(\theta, \tau)$，即在特定阈值 $\tau$ 下，由变化后参数 $\theta$ 诱导的量化分布与变化前参数 $\theta_0$ 诱导的分布之间的散度。

令 $K_{LM} = \max_{\tau} KL(\theta, \tau)$ 为所有可能阈值下可实现的极大 KL 散度。定理 1 表明，当 ARL 约束 $\gamma \to \infty$ 时，最小检测延迟的下界为：
$$\inf_{(\pi, T)} WADD(T) \geq \frac{\log \gamma}{K_{LM}} (1 + o(1))$$
这意味着最优检测延迟与误报约束呈对数关系，并且与单次 1-bit 测量所能获得的最大信息增益成反比。

提出的方法论：AQuTe-CUSUM
为了逼近该下界，本文提出了 自适应量化阈值 CUSUM (AQuTe-CUSUM) 算法。该方法以滑动窗口方式运行，以处理未知的变化后参数 $\theta_1$：

1. 参数估计： 对于时间 $t > w$（其中 $w$ 是固定的窗口大小），算法利用最近 $w$ 个量化观测值 $\{B_{t-w}, \dots, B_{t-1}\}$ 及其对应的阈值进行极大似然估计 (MLE)：
   $$\hat{\theta}_{t-1} = \arg \max_{\theta \in \Theta_1} \sum_{s=t-w}^{t-1} \log p_B(B_s; \theta, \tau_s)$$
2. 自适应阈值选择： 利用当前的估计值 $\hat{\theta}_{t-1}$，算法选择下一个阈值 $\tau_t$，以最大化 1-bit KL 散度：
   $$\tau_t = \arg \max_{\tau \in [\tau_{min}, \tau_{max}]} KL(\hat{\theta}_{t-1}, \tau)$$
3. 检测统计量更新： 算法采用窗口限制的 CUSUM 统计量 $S_t$，累积估计的变化后分布与已知变化前分布之间的对数似然比：
   $$S_t = S_{t-1}^+ + \log \frac{p_B(B_t; \hat{\theta}_{t-1}, \tau_t)}{p_B(B_t; \theta_0, \tau_t)}$$
   当 $S_t$ 超过预设阈值 $\nu = \log \gamma$ 时，过程停止。

主要贡献与结果
在满足一系列正则性条件（假设 A1–A6，包括参数空间的紧致性、似然函数的平滑性以及通过 1-bit 测量实现参数的可辨识性）下，本文为 AQuTe-CUSUM 程序提供了严格的理论保证。

• 平均运行长度 (ARL)： 引理 1 证明，通过设置检测阈值 $\nu = \log \gamma$，可以确保满足误报约束（即 $E_\infty[T] > \gamma$）。
• 检测延迟： 定理 2 阐明，如果窗口大小 $w$ 随 $\gamma$ 增长，满足 $w = o(\log \gamma)$ 且 $w \to \infty$，则 AQuTe-CUSUM 的 WADD 满足：
  $$WADD(T) \leq \frac{\log \gamma}{K_{LM}} (1 + o(1))$$
  这一结果表明，所提算法在一阶渐近意义上是优化的，达到了定理 1 中推导出的理论下界。

数值评估
作者使用两个参数模型验证了理论发现：

1. 高斯分布： 对于 $X_t \sim N(\theta, 1)$，最优阈值通过数值方法求得。仿真显示，AQuTe-CUSUM 的检测延迟紧密追踪信息论下界，尤其是在中等窗口大小（如 $w=10$）的情况下。
2. 泊松分布： 对于 $X_t \sim \text{Poi}(\theta)$，阈值优化在离散整数值上进行。与高斯情形类似，该算法展示了与最优 1-bit CUSUM 界限相当的性能。

意义与范围
本文声称其重要性在于将快速变化检测理论扩展到了资源受限的环境中，即在仅有 1-bit 量化数据且变化后分布未知的情况下。通过联合优化量化阈值和检测统计量，该方法克服了固定量化器带来的信息损失。

作者在文中明确指出了局限性和未来方向：

• 分析假设高斯情形为连续参数空间，泊松情形为离散参数空间；针对连续与离散阈值集的统一分析仍有待未来研究。
• 实际约束（例如阈值变化的频率限制，或当最优阈值缺乏闭式解时需要高效近似）被确定为未来的研究领域。
• 估计器的相合性依赖于特定条件（例如具有信息量的阈值）；如果这些条件被违反（例如在对称分布的中位数处使用固定阈值），则可能无法实现一致估计。

总而言之，本文提出了一种具有理论依据的算法，在 1-bit 量化且参数未知的情况下，实现了变化检测的一阶渐近最优性，填补了自适应感知与序贯假设检验之间的空白。