Accurate Evaluation of Quickest Changepoint Detectors via Non-parametric Survival Analysis

技术摘要：通过非参数生存分析准确评估最速变点检测器

问题陈述

最速变点检测（QCD）是涵盖从工业质量控制到流行病学及无线传感器网络等各个领域的关键任务。QCD 模型的性能传统上使用两个主要指标进行评估：平均运行长度（ARL），代表误报的平均时间；以及平均检测延迟（ADD），代表变化发生后检测到变化的平均时间。

尽管 ARL 和 ADD 是理论和模拟研究中的标准最优性准则，但有限且不规则的序列长度严重阻碍了它们在真实世界数据集上的应用。在实际场景中，序列往往在检测到变化或发生误报之前就被截断。传统的估计量，如低偏 ARL（LB-ARL）和 LB-ADD，通常会丢弃那些在观测范围内未能触发警报的序列。这种排除会导致显著的负偏差和高方差，特别是在序列长度较短或高度不规则的情况下，使得可靠的模型评估和选择变得困难。

方法论

为了克服这些局限性，作者提出了一个新颖的框架，将 QCD 与生存分析进行类比，具体利用非参数方法来处理右删失数据。

1. 类比构建：

   • ARL 语境：将序列视为“患者”，检测点（$\tau$）视为“事件时间”，变点（$\nu$）与序列长度（$T$）中的较小值视为“删失时间”。
   • ADD 语境：对于存在变点的序列，检测延迟（$\Delta\tau = \tau - \nu$）是事件时间，变点后的剩余序列长度（$T - \nu$）是删失时间。

2. 提出的估计量（KM-ARL 和 KM-ADD）：
   作者将Kaplan-Meier 估计量（KME）（一种用于在删失条件下估计生存函数的标准非参数工具）适配到 QCD 设定中。

   • KME 不再丢弃截断的序列，而是利用直到删失时间的所有可用信息。
   • KM-ARL定义为检测点估计生存函数 $\hat{S}_{ARL}(t)$ 在范围 $[0, a]$ 上的积分。
   • KM-ADD类似地定义为检测延迟估计生存函数 $\hat{S}_{ADD}(t)$ 的积分。
   • 这些估计量是非参数的，不需要对底层数据分布（例如指数衰减）做出任何假设，这与之前的参数化方法不同。

3. 理论分析：
   本文推导了估计偏差的严格界限，将其分解为有限样本偏差和截断偏差。

   • 有限样本偏差：证明在独立删失假设成立的情况下（适用于不向前看的在线 QCD 模型），随着数据集大小（$N$）的增加，该偏差呈指数级衰减。
   • 截断偏差：作者证明 KM 估计量的截断偏差严格小于（负值更小）传统 LB 估计量的截断偏差。
   • 渐近无偏性：证明除非需要超出观测支持范围进行外推，否则这些估计量是渐近无偏的。

主要贡献

1. 新颖估计量：引入 KM-ARL 和 KM-ADD，这是非参数估计量，使得能够在具有有限且不规则序列长度的真实世界数据集上评估 QCD 模型。
2. 理论保证：推导了估计偏差界限并证明了渐近无偏性（在特定条件下），为在 QCD 评估中使用生存分析奠定了理论基础。
3. 实用价值：通过在模拟数据（高斯和泊松过程）和真实世界数据（WISDM Actitracker）上的实验，展示了与基线估计量（LB-ARL/ADD）相比，估计偏差降低且鲁棒性增强。
4. 开源实现：提供即用型 Python 代码，以方便从业者进行实证和直观的模型选择。

实验结果

作者使用以下数据将提出的指标与传统估计量进行了评估：

• 模拟数据：具有不同变点分布和序列长度（包括恒定和不规则长度）的高斯和泊松过程。
• 真实世界数据：WISDM Actitracker 数据集，包含超过 51,000 条人类活动序列，具有高度不规则的长度（范围从 1 到 54,401 帧）。

发现：

• 准确性：与 LB-ARL 和 LB-ADD 相比，KM-ARL 和 KM-ADD 提供了显著更准确的真实 ARL 和 ADD 估计值，特别是在重度删失场景下（例如短序列或高检测阈值）。
• 鲁棒性：与传统估计量在有效序列数量因截断而下降时表现出高方差和不稳定性不同，KM 估计量通过利用 Kaplan-Meier 估计量的风险集机制使用完整数据集，从而保持了稳定性。
• 模型选择：提出的指标促成了更清晰的 ARL-ADD 权衡曲线，使得在各种 QCD 算法（包括 CUSUM、EWMA 和 NP-FOCuS）之间进行更可靠的实证模型选择成为可能。

意义与主张

本文将自己定位为对机器学习中可重复且可解释的评估这一更广泛目标的贡献。作者认为，如果没有针对现实世界约束（如不规则序列长度）的原则性估计方法，性能的提升可能是虚幻的。

通过架起 QCD 与生存分析之间的桥梁，这项工作提供了一种方法，能够：

• 消除对数据分布的任意假设需求。
• 减轻由序列截断引入的严重偏差。
• 使得在以前被认为因过于不规则或过短而无法使用标准指标的数据集上评估 QCD 模型成为可能。

作者谦逊地指出，虽然他们的方法能有效处理不规则长度，但仍需要带有变点标签的数据集，并假设在线模型具有独立删失。他们建议，对于存在依赖删失或极端截断的场景，可能需要使用基于 Copula 的方法或参数化外推进行进一步扩展。