2025-11-19T13:13:14.244069

Finite-Horizon Quickest Change Detection Balancing Latency with False Alarm Probability

Huang, Veeravalli

A finite-horizon variant of the quickest change detection (QCD) problem that is of relevance to learning in non-stationary environments is studied. The metric characterizing false alarms is the probability of a false alarm occurring before the horizon ends. The metric that characterizes the delay is \emph{latency}, which is the smallest value such that the probability that detection delay exceeds this value is upper bounded to a predetermined latency level. The objective is to minimize the latency (at a given latency level), while maintaining a low false alarm probability. Under the pre-specified latency and false alarm levels, a universal lower bound on the latency, which any change detection procedure needs to satisfy, is derived. Change detectors are then developed, which are order-optimal in terms of the horizon. The case where the pre- and post-change distributions are known is considered first, and then the results are generalized to the non-parametric case when they are unknown except that they are sub-Gaussian with different means. Simulations are provided to validate the theoretical results.

academic

Finite-Horizon Quickest Change Detection Balancing Latency with False Alarm Probability

基本信息

论文ID: 2511.12803
标题: Finite-Horizon Quickest Change Detection Balancing Latency with False Alarm Probability
作者: Yu-Han Huang and Venugopal V. Veeravalli (University of Illinois Urbana-Champaign)
分类: cs.IT, math.IT, stat.ML
编译时间: November 18, 2025
论文链接: https://arxiv.org/abs/2511.12803

摘要

本文研究了与非平稳环境学习相关的有限时域快速变化检测（QCD）问题的一个变体。文章采用虚警概率作为虚警指标，采用延迟（latency）作为检测延迟指标——即检测延迟超过该值的概率被上界约束到预定水平的最小值。目标是在保持低虚警概率的同时最小化延迟。在预设的延迟和虚警水平下，文章导出了任何变化检测程序都需要满足的延迟通用下界，并开发了关于时域阶数最优的变化检测器。首先考虑已知前后变化分布的情况，然后推广到非参数情况——仅知道分布为具有不同均值的次高斯分布。仿真验证了理论结果。

研究背景与动机

1. 要解决的核心问题

本文研究有限时域快速变化检测问题，在以下新指标体系下平衡检测性能：

虚警指标：时域内发生虚警的概率 P∞(τ ≤ T)
延迟指标：延迟（latency）ℓ，定义为使得检测延迟超过该值的概率不超过预设水平δD的最小值

2. 问题的重要性

传统QCD问题通常假设：

无限时域：不符合实际应用中的有限时域场景
期望延迟最小化：而非控制延迟超过阈值的概率
平均虚警时间：而非虚警概率

新问题设定在以下应用中更为关键：

分段平稳环境中的在线学习：如分段平稳赌博机问题、分段平稳有限时域情节马尔可夫决策过程
需要重启的算法：检测到环境变化后需要重启，必须同时控制虚警概率和检测延迟概率

3. 现有方法的局限性

经典CuSum和SR测试：使用常数阈值，在大时域下虚警概率趋近于1
Lai (1998)的工作：仅部分解决了虚警概率问题，窗口大小不覆盖整个时域且依赖于虚警水平
缺乏理论界：对于同时控制虚警概率和延迟概率的问题，缺乏性能下界和阶数最优算法

4. 研究动机

为分段平稳环境学习提供理论基础
建立新问题设定下的性能基准（下界）
开发实用的阶数最优检测算法

核心贡献

新问题形式化：提出了平衡虚警概率和延迟的有限时域QCD问题（公式3），其中延迟定义为检测延迟超过该值的概率不超过δD的最小值
通用下界：导出了任何变化检测器必须满足的延迟通用下界（定理1）： $\ell \geq \left(\frac{1}{K} + o(1)\right)\left[\log(T) + \log\left(\frac{1}{\delta_F}\right) + \log(1-\delta_F-\delta_D) + o(1)\right]$ 其中 $K = \log\left(\mathbb{E}_{f_1}\left[\frac{f_1(X)}{f_0(X)}\right]\right)$
已知分布的阶数最优检测器：提出时变阈值CuSum（TVT-CuSum）和时变阈值SR（TVT-SR）测试，证明其延迟为O(log T)，与下界阶数匹配（定理2）
非参数检测器：将方法推广到未知分布情况，提出广义似然比（GLR）和广义Shiryaev-Roberts（GSR）测试，在次高斯假设下达到O(log T)延迟（定理3，推论1）
实验验证：通过仿真验证了理论结果，展示了算法的阶数最优性

方法详解

任务定义

问题设定：

观测序列：{Xn : n ∈ T}，在有限时域T内顺序观测
变化点：ν ∈ m+1, T，其中m为预变化窗口（用于估计预变化分布）
分布变化： $X_n \sim \begin{cases} f_0, & n \in [\nu-1] \\ f_1, & n \in [\nu, T] \end{cases}$

性能指标：

延迟（公式2）： $\ell := \min\{d \in [T] : P_\nu(\tau \geq \nu+d) \leq \delta_D, \forall \nu \in [m+1, T-d]\}$
虚警概率：P∞(τ ≤ T)

优化目标（公式3）： $\min_\tau \ell \quad \text{s.t.} \quad P_\infty(\tau \leq T) \leq \delta_F$

模型架构

1. TVT-CuSum测试（已知分布）

CuSum统计量（递归形式）： $C_n = \max\{C_{n-1}, 0\} + \log\left(\frac{f_1(X_n)}{f_0(X_n)}\right), \quad C_0 = 0$

时变阈值： $\beta_C(n, \delta_F, r) := \log\left(\frac{\zeta(r)}{n^r\delta_F}\right), \quad \zeta(r) = \sum_{i=1}^\infty i^{-r}$

停止时间（公式12）： $\tau_{C,r} := \inf\{n \in \mathbb{N} : C_n \geq \beta_C(n, \delta_F, r)\}$

关键特性：

计算复杂度：每时间步O(1)
阈值随时间对数增长，控制虚警概率

2. TVT-SR测试（已知分布）

SR统计量（递归形式）： $S_n = (S_{n-1} + 1)\frac{f_1(X_n)}{f_0(X_n)}, \quad S_0 = 0$

时变阈值： $\beta_S(n, \delta_F, r) := \beta_C(n, \delta_F, r) + \log n$

停止时间（公式14）： $\tau_{S,r} := \inf\{n \in \mathbb{N} : \log S_n \geq \beta_S(n, \delta_F, r)\}$

3. GLR测试（未知分布）

GLR统计量（公式21）： $G_n = \sup_{k \in [n]} kD(\hat{\mu}_{1:k}; \hat{\mu}_{1:n}) + (n-k)D(\hat{\mu}_{k+1:n}; \hat{\mu}_{1:n})$

其中 $D(x;y) := (x-y)^2/(2\sigma^2)$ 是高斯分布的KL散度， $\hat{\mu}_{m:n}$ 是经验均值。

阈值函数（公式23）： $\beta_{GLR}(n, \delta_F) := 6\log(1+\log(n)) + \frac{5}{2}\log\left(\frac{4n^{3/2}}{\delta_F}\right) + 11$

停止时间： $\tau_{GLR} := \inf\{n \in \mathbb{N} : G_n \geq \beta_{GLR}(n, \delta_F)\}$

预变化窗口长度要求（公式29）： $m \geq \frac{8\sigma^2}{\Delta^2}\beta(T, \delta_F)$

4. GSR测试（未知分布）

GSR统计量（公式25）： $W_n = \sum_{k=1}^n \exp(kD(\hat{\mu}_{1:k}; \hat{\mu}_{1:n}) + (n-k)D(\hat{\mu}_{k+1:n}; \hat{\mu}_{1:n}))$

阈值： $\beta_{GSR}(n, \delta_F) := \beta_{GLR}(n, \delta_F) + \log n$

技术创新点

1. 时变阈值设计

创新：阈值随时间对数增长，而非常数阈值

解决问题：常数阈值在大时域下虚警概率趋近1
理论依据：利用Ville不等式和超鞅性质

关键引理2（附录A）：序列 $\left\{\frac{1}{(j+k)^r}\prod_{i=j}^{j+k}\frac{f_1(X_i)}{f_0(X_i)}\right\}_{k=0}^\infty$ 在P∞下是非负超鞅

2. 非参数推广策略

创新：用广义似然比替代似然比

GLR统计量：通过最大化似然估计未知参数
引理1：将GLR统计量表示为经验均值的函数，便于利用次高斯性质

3. 浓度不等式应用

创新：结合混合鞅技术（Kaufmann & Koolen, 2021）

引理5：对于i.i.d.次高斯序列，建立经验KL散度的浓度不等式
引理6：构造非负混合鞅使得异常事件可用鞅值界定

4. 延迟分析技术

创新：分解延迟事件为三个不相交事件

事件A：早检测但对数似然比大
事件B：早检测但对数似然比小
利用测度变换和Markov不等式分别界定

实验设置

数据集

合成数据：

预变化分布：N(0, 1)（均值0，方差1的高斯分布）
后变化分布：N(1, 1)（均值1，方差1的高斯分布）
变化间隔：∆ = 1
时域范围：T ∈ {5000, 10000, 20000, 50000, 100000}

评价指标

经验延迟计算：

对候选变化点集合 M ⊆ m+1, T-ℓ 中的每个变化点
进行2×10^5次试验
记录检测延迟 τ - ν
取所有变化点上100(1-δD)百分位数的最大值
候选集合：M = {m+1+nT/10 : n ∈ ℕ, m+1+nT/10 ≤ T}

对比方法

TVT-CuSum测试（r参数设置）
TVT-SR测试（r参数设置）
GLR测试（下采样实现）
理论下界（定理1）
理论上界（定理2和3）

实现细节

虚警水平：δF = 0.01
延迟水平：δD = 0.01
预变化窗口：m = T - 1000（对于GLR测试）
GLR下采样窗口：700个时间步（公式34） $G'_n := \sup_{k \in [n-700, n]} \log\frac{\sup_{\mu'_0}\prod_{i=1}^k f_{\mu'_0}(X_i) \sup_{\mu'_1}\prod_{i=k+1}^n f_{\mu'_1}(X_i)}{\sup_\mu \prod_{i=1}^n f_\mu(X_i)}$

实验结果

主要结果

图1展示的关键发现：

阶数最优性验证：所有测试的经验延迟与log T呈线性关系，验证了O(log T)的阶数最优性
性能排序：
- TVT-CuSum < TVT-SR < GLR（延迟从小到大）
- 已知分布的测试优于未知分布的测试
界的松紧度：
- 下界较松：理论下界与经验值存在明显差距
- GLR上界最松：定理3的上界与GLR经验值差距最大
- TVT-CuSum和TVT-SR上界较紧：定理2的上界与经验值差距较小

具体数值示例（从图1读取）

以T = 100000为例（近似值）：

理论下界：约35
TVT-CuSum经验值：约55
TVT-SR经验值：约60
GLR经验值：约75
GLR理论上界：约200+

实验发现

1. 线性对数关系

所有测试的延迟都呈现 ℓ = a·log(T) + b 的形式，其中：

斜率a反映了算法效率
TVT-CuSum的斜率最小（最优）

2. 已知vs未知分布的性能差距

GLR测试的延迟约为TVT-CuSum的1.4倍
说明分布未知带来的性能损失是可接受的
GLR测试仍保持O(log T)阶数最优性

3. 理论界的改进空间

下界松弛的可能原因：

证明中未施加测试对时域T无知的条件
TVT-CuSum可能还有改进空间

GLR上界松弛的原因：

证明技术较为保守
使用的浓度不等式可能不够紧

4. 实用性验证

所有测试成功控制虚警概率在δF以下
延迟控制在可接受范围
计算复杂度合理（TVT-CuSum和TVT-SR为O(1)每步）

结论与讨论

主要结论

理论下界：建立了有限时域QCD问题的延迟下界 Ω(log T)，为任何检测器提供了性能基准
阶数最优算法：
- 已知分布：TVT-CuSum和TVT-SR达到O(log T)延迟
- 未知分布：GLR和GSR在次高斯假设下达到O(log T)延迟
实用价值：
- 算法计算高效（递归实现）
- 成功控制虚警概率和延迟概率
- 适用于分段平稳环境学习
推广性：结果可推广到独立但不同分布的次高斯噪声（备注2）

局限性

1. 理论界的松紧度

下界较松：与经验值差距约1.5倍
GLR上界很松：与经验值差距超过2.5倍
原因分析：
- 下界证明未考虑时域无知约束
- GLR分析使用的浓度不等式较保守

2. 分布假设

次高斯假设：虽然覆盖有界分布，但不包括重尾分布
参数已知：需要知道次高斯参数σ²
均值变化：仅考虑均值变化，未考虑方差或其他参数变化

3. 计算复杂度

GLR统计量：无递归结构，直接计算为O(n²)
下采样权衡：实验中使用700步窗口，可能影响性能
GSR统计量：更难计算，实验中未报告

4. 单变化点假设

当前理论针对单个变化点
分段平稳环境有多个变化点，需要重复应用

未来方向

1. 改进理论界

收紧下界：考虑时域无知约束
收紧GLR上界：使用更精细的浓度不等式
可能方向：信息论方法、精确渐近分析

2. 改进GLR测试

更紧的阈值设计：减小与TVT-CuSum的性能差距
高效计算：探索近似递归算法
自适应窗口：动态调整下采样窗口大小

3. 推广分布假设

更一般的分布族：超越次高斯
未知参数：不需要知道σ²
多参数变化：方差、形状参数等

4. 多变化点扩展

理论分析：多变化点情况下的累积延迟和虚警
自适应重启：检测后如何最优重启
变化点数量估计

5. 应用研究

分段平稳赌博机：集成到实际算法
强化学习：分段平稳MDP
其他领域：金融、生物医学信号处理等

深度评价

优点

1. 问题形式化的创新性 ⭐⭐⭐⭐⭐

新颖的指标体系：虚警概率+延迟概率，比传统期望指标更适合实际应用
有限时域设定：更贴近实际应用场景
明确的应用动机：与分段平稳学习紧密结合

2. 理论贡献的完整性 ⭐⭐⭐⭐⭐

下界：提供性能基准
上界：给出可达算法
阶数匹配：证明算法的阶数最优性
从已知到未知：完整的推广路径

3. 证明技术的严谨性 ⭐⭐⭐⭐⭐

超鞅构造（引理2）：巧妙利用Ville不等式
事件分解（附录B）：将复杂事件分解为可处理的部分
混合鞅技术（引理6）：引入前沿技术
测度变换：经典但有效的分析工具

4. 方法的实用性 ⭐⭐⭐⭐

计算高效：TVT-CuSum和TVT-SR每步O(1)
易于实现：递归形式简单
参数选择：阈值函数明确，无需调参
鲁棒性：GLR方法适用于未知分布

5. 实验验证的充分性 ⭐⭐⭐⭐

多个时域规模：T从5000到100000
充分的重复：每个设置2×10⁵次试验
理论对比：与理论界对比
可视化清晰：图1清楚展示对数线性关系

不足

1. 理论界的松紧度 ⭐⭐⭐

下界与经验值差距：约1.5倍
GLR上界过松：超过2.5倍差距
影响：限制了理论的指导价值
改进空间：作者已在文中承认并讨论

2. GLR计算复杂度 ⭐⭐⭐

无递归结构：直接计算O(n²)
下采样方案：实验中使用但缺乏理论分析
GSR未实现：仅报告GLR结果
实用性影响：限制了大规模应用

3. 实验设置的局限 ⭐⭐⭐

单一分布族：仅测试高斯分布
固定参数：δF = δD = 0.01，未探索参数敏感性
候选变化点采样：M只包含T/10间隔的点
缺少对比：未与其他有限时域方法对比（可能因为缺少此类方法）

4. 分布假设的限制 ⭐⭐⭐

次高斯假设：排除重尾分布
已知σ²：实际中可能未知
均值变化：未考虑其他参数变化
推广性：限制了应用范围

5. 写作的完整性 ⭐⭐⭐⭐

主要结果清晰：但证明细节全在附录
符号较多：需要仔细追踪
实验细节：下采样实现描述不够详细
总体清晰：结构合理，逻辑流畅

影响力

1. 对领域的理论贡献 ⭐⭐⭐⭐⭐

新问题范式：为有限时域QCD建立了新的理论框架
性能基准：提供了其他研究者对比的标准
技术工具：证明技术可用于相关问题
长期价值：基础性贡献

2. 对应用的实用价值 ⭐⭐⭐⭐

分段平稳学习：直接应用于赌博机、强化学习
即插即用：算法可直接集成
性能保证：理论保证降低应用风险
局限：GLR的计算复杂度需要解决

3. 可复现性 ⭐⭐⭐⭐

算法明确：递归公式清晰
阈值函数：完全指定
实验设置：参数和方法描述充分
代码未公开：但实现应该不困难

4. 后续研究价值 ⭐⭐⭐⭐⭐

改进理论界：明确的研究方向
高效GLR算法：实际需求
推广到其他分布：自然扩展
多变化点理论：重要未来方向

适用场景

1. 理想适用场景 ✅

分段平稳赌博机：需要检测环境变化并重启
有限时域决策：明确的时间限制
次高斯观测：如有界奖励
均值变化：环境变化体现为均值漂移

2. 需要调整的场景 ⚠️

无限时域：可能需要修改阈值函数
重尾分布：需要不同的理论工具
方差变化：需要修改统计量
多变化点：需要重复应用和累积分析

3. 不适用场景 ❌

连续变化：而非突变
未知时域：算法假设T存在（虽然不利用）
极端实时性要求：GLR的O(n²)可能太慢
非独立观测：如时间序列相关性

参考文献（关键文献）

Moustakides (1986): CuSum测试的精确最优性
Pollak (1985) & Lorden (1971): 经典QCD准则
Lai (1998): 窗口内虚警概率控制
Kaufmann & Koolen (2021): 混合鞅和时间均匀浓度不等式
Besson et al. (2022): 分段平稳赌博机的变化检测
Ville (1939): Ville不等式（超鞅最大值界）

总结

本文在有限时域快速变化检测问题上做出了重要的理论贡献，提出了更符合实际应用需求的新指标体系（虚警概率+延迟），建立了性能下界，并开发了阶数最优的检测算法。理论严谨，证明技术巧妙，实验验证充分。主要不足在于理论界较松和GLR计算复杂度高，但这些也为后续研究提供了明确方向。该工作为分段平稳环境学习提供了坚实的理论基础，具有重要的学术价值和应用潜力。

推荐指数: ⭐⭐⭐⭐⭐ (5/5)

适合对序列分析、统计检测、在线学习感兴趣的研究者
对于从事分段平稳问题研究的学者必读
为实际系统设计者提供了理论指导和实用工具