跳转至

Adaptive novelty detection with false discovery rate guarantee

作者: Ariane Marandon, Lihua Lei, David Mary, Etienne Roquain
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://doi.org/10.1214/23-aos2338

一、领域脉络与小综述

这个方向是什么

本文所处的子方向是半监督新颖性检测（semisupervised novelty detection），其根本统计问题是：给定一组来自"典型"（正常）分布的样本，如何判断新观测是否来自该分布（即是否为"新颖"或"异常"）。该问题的特殊性在于：我们只有正常类的样本，没有（或极少有）异常类的样本，因此无法直接训练一个二分类器。该方向的核心挑战是：在不假设正常分布的具体参数形式的前提下，构造一个既能控制错误发现率（FDR）、又具有统计功效的检测程序。该方向当前处于活跃发展阶段，主要驱动力来自 conformal inference 与多重检验（multiple testing）两个领域的交叉融合。

发展脉络（history）

  • 奠基工作：Benjamini-Hochberg (1995)。FDR 控制的奠基性程序，为后续所有"在多重检验中控制错误率"的工作提供了基准框架。本文的 FDR 控制目标直接继承自此。
  • 关键进展：Benjamini-Hochberg 的 p 值自适应变体（如 Storey 2002, Blanchard & Roquain 2009）。这些工作表明，若知道或能估计零假设的比例 π₀，可以显著提升检验功效。本文的"对零假设比例自适应"变体直接受此启发。
  • 关键进展：conformal inference 的 p 值构造（Vovk et al. 2005; Lei et al. 2018）。conformal 方法利用可交换性（exchangeability）构造有限样本有效的 p 值，无需分布假设。本文的"仅假设可交换性"设定直接继承自此。
  • 关键进展：split conformal 与 data splitting（Papadopoulos et al. 2002; Lei & Wasserman 2014）。将样本分为训练集和校准集，用校准集构造 p 值，避免过拟合。本文的 AdaDetect 采用类似的样本分割策略。
  • 当前 frontier：将 conformal p 值与多重检验程序结合。Bates et al. (2021) 的 "e-BH" 程序和 Mary & Roquain (2022) 的工作表明，conformal 构造的 p 值可以嵌入 FDR 控制框架。本文的 AdaDetect 是这一方向的直接延伸，其核心创新在于用数据自适应方式学习 p 值变换，而非预先指定。
  • 本文的位置：在已有工作中，p 值函数（如 conformal p 值）通常是预先固定的。本文提出用数据自适应方式学习 p 值变换，将检验功效集中在区分正常与异常的方向上，同时保持有限样本 FDR 控制。这是对"p 值函数必须预先指定"这一隐含假设的突破。

子线索聚类

  1. FDR 控制理论：Benjamini-Hochberg (1995)、Storey (2002)、Blanchard & Roquain (2009)。这一簇关注如何在多重检验中控制错误率，核心工具是 p 值的排序与阈值选择。
  2. Conformal inference：Vovk et al. (2005)、Lei et al. (2018)、Bates et al. (2021)。这一簇关注如何在可交换性假设下构造有限样本有效的 p 值或置信集，无需分布假设。
  3. 半监督新颖性检测：本文的直接应用场景。这一簇关注如何仅用正常样本检测异常，常见方法包括 one-class SVM、isolation forest 等，但通常缺乏有限样本错误率保证。
  4. 数据自适应 p 值变换：本文的核心贡献。这一簇关注如何从数据中学习 p 值函数，以提升功效，同时保持错误率控制。

这个方向在追问的核心问题

  1. 如何在无分布假设下控制 FDR？ 当前主流方法是利用可交换性构造 conformal p 值，再嵌入 BH 程序。已知瓶颈是：conformal p 值的离散性可能导致 FDR 控制保守，功效损失。
  2. 如何提升检测功效？ 当前主流方法是选择更好的"非一致性得分"（nonconformity score），如分类器的概率输出。已知瓶颈是：得分函数的选择通常依赖领域知识，且与 FDR 控制的交互复杂。
  3. 如何自适应零假设比例？ 当前主流方法是估计 π₀ 并调整阈值。已知瓶颈是：π₀ 的估计在低功效场景下不稳定，可能破坏 FDR 控制。
  4. 如何平衡数据自适应与错误率控制？ 这是本文的核心问题：p 值变换若从数据中学习，可能引入过拟合，破坏可交换性。本文的解法是样本分割：用一部分数据学习变换，另一部分数据构造 p 值。

⚠️ 作者的 framing（必须明确标注成"这是作者的说法"）

作者将缺口 frame 成："经典 FDR 控制程序往往预先指定 p 值函数，这限制了功效；AdaDetect 通过数据自适应学习变换，将功效集中在区分正常与异常的方向上。" 这是作者的说法，其隐含假设是：数据自适应变换不会破坏可交换性（通过样本分割保证）。作者淡化的竞争路线包括：(a) 直接优化非一致性得分函数（如深度异常检测），这类方法通常缺乏有限样本保证；(b) 基于核方法的无分布检测（如 MMD），这类方法通常需要选择核函数，且不直接控制 FDR。值得研究者去查的问题：为什么 intro 中没有引用 recent work on "e-values" 与 "e-BH" 在异常检测中的应用（如 Wang & Ramdas 2022）？这些工作提供了另一种不依赖 p 值的 FDR 控制框架，可能与本文形成竞争。

张力

未见明显对立引用。但存在一个潜在张力：conformal inference 的 p 值构造依赖可交换性，而数据自适应变换（即使通过样本分割）可能引入对训练数据的依赖，导致校准集上的 p 值不再精确均匀。作者通过样本分割规避了这一点，但代价是功效损失（训练集和校准集各用一半数据）。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

符号： - \( X_1, \dots, X_n \)：来自正常分布 \( P \) 的 i.i.d. 样本（"典型"测量），可观测。 - \( X_{n+1}, \dots, X_{n+m} \)：待检测的观测，其中一部分可能来自异常分布 \( Q \)，可观测。 - \( H_i \)：第 \( i \) 个待检测观测是否为异常的指示变量（0 = 正常，1 = 异常），不可观测，是我们要推断的对象。 - \( \pi_0 \)：待检测观测中正常观测的比例，不可观测，是我们要估计或自适应的对象。 - \( \mathcal{A} \)：被检测为"新颖"（异常）的观测的索引集合，是决策变量。 - \( \text{FDP} = |\mathcal{A} \cap \mathcal{H}_0| / (|\mathcal{A}| \vee 1) \)：错误发现比例，其中 \( \mathcal{H}_0 \) 是正常观测的索引集合。 - \( \text{FDR} = \mathbb{E}[\text{FDP}] \)：错误发现率，是我们要控制的量。 - \( s(x) \)：非一致性得分函数（nonconformity score），越大表示越可能异常。 - \( \hat{s} \)：从训练集 \( X_1, \dots, X_n \) 学习到的得分函数。 - \( \hat{p}_i \)：第 \( i \) 个待检测观测的 conformal p 值，定义为 \( \hat{p}_i = (1 + \sum_{j=1}^n \mathbf{1}\{\hat{s}(X_j) \le \hat{s}(X_{n+i})\}) / (n+1) \)。

模型： - 数据生成机制：\( X_1, \dots, X_n \sim P \) i.i.d.；\( X_{n+1}, \dots, X_{n+m} \) 中，正常观测来自 \( P \)，异常观测来自 \( Q \)，但哪些是异常未知。 - 关键假设：可交换性——在给定 \( H_i \) 的条件下，正常观测的联合分布与 \( X_1, \dots, X_n \) 可交换。这是 conformal inference 的核心假设，比参数分布假设弱得多。 - 要估的对象：\( \mathcal{A} \)（哪些观测是异常），以及 \( \pi_0 \)（正常比例）。

可观测数据： - 研究者实际能观测到：\( X_1, \dots, X_n \)（正常样本）和 \( X_{n+1}, \dots, X_{n+m} \)（待检测样本）。 - 研究者观测不到：\( H_i \)（哪些是异常）、\( \pi_0 \)（正常比例）、以及异常分布 \( Q \) 的任何信息。

第二步：讲最小内核

最简特例：假设 \( n = 100 \)，\( m = 10 \)，正常分布 \( P = \mathcal{N}(0, 1) \)，异常分布 \( Q = \mathcal{N}(2, 1) \)，且 \( \pi_0 = 0.8 \)（即 10 个待检测观测中 8 个正常，2 个异常）。我们不知道 \( P \) 和 \( Q \) 的具体形式，只知道 \( X_1, \dots, X_{100} \) 来自 \( P \)。

核心问题：如何从这 110 个观测中，检测出那 2 个异常，同时保证 FDR ≤ 0.1？

最小内核的解法： 1. 学习得分函数：用 \( X_1, \dots, X_{100} \) 训练一个分类器（如 logistic regression），将 \( X_1, \dots, X_{100} \) 标为"正常"（标签 0），将 \( X_{101}, \dots, X_{110} \) 标为"异常"（标签 1）。但这里有个问题：我们不知道哪些待检测观测是异常，所以不能直接这样训练。AdaDetect 的解法是：将待检测观测全部标为"异常"，训练一个分类器区分"正常"和"待检测"。 2. 构造 conformal p 值：对每个待检测观测 \( X_{n+i} \)，计算 \( \hat{p}_i = (1 + \sum_{j=1}^n \mathbf{1}\{\hat{s}(X_j) \le \hat{s}(X_{n+i})\}) / (n+1) \)。直观上，如果 \( X_{n+i} \) 的得分比大多数正常样本都大，则 \( \hat{p}_i \) 很小，说明它很可能是异常。 3. 应用 BH 程序：将 \( \hat{p}_1, \dots, \hat{p}_m \) 排序，用 Benjamini-Hochberg 程序在水平 \( \alpha = 0.1 \) 下选择阈值，拒绝所有 \( \hat{p}_i \le \hat{q} \) 的观测。

为什么这个特例能体现核心思想：在这个特例中，关键步骤是用数据自适应方式学习得分函数。如果预先固定 \( s(x) = x \)（即直接用观测值作为得分），则当 \( P \) 和 \( Q \) 的均值差异不大时，功效会很低。AdaDetect 通过训练分类器，将得分函数集中在区分正常与异常的方向上（即均值差异的方向），从而提升功效。这个特例揭示了全文的核心机制：数据自适应学习得分函数 + conformal p 值 + BH 程序 = 有限样本 FDR 控制 + 功效提升。

为什么成立：关键在于样本分割。将 \( X_1, \dots, X_n \) 分为两部分：一部分（训练集）用于学习 \( \hat{s} \)，另一部分（校准集）用于构造 p 值。由于校准集与训练集独立，且校准集中的正常样本与待检测观测中的正常样本可交换，因此 \( \hat{p}_i \) 在零假设下（即 \( X_{n+i} \) 正常时）是（近似）均匀分布的。这保证了 BH 程序的 FDR 控制性质。

三、这篇论文做了什么

三句话

① 研究了什么问题：在半监督新颖性检测中，如何构造一个能在有限样本下控制 FDR、且不依赖分布假设的检测程序。② 核心工具 / 方法：将 conformal inference 的 p 值构造与多重检验的 BH 程序结合，并用数据自适应方式学习 p 值变换（即非一致性得分函数），以提升功效。③ 主要结论：AdaDetect 在仅假设可交换性的条件下，对任意概率分类算法都能实现有限样本 FDR 控制；进一步提出对零假设比例自适应的变体，在保持 FDR 控制的同时提升功效；在合成数据和真实数据（包括天体物理学应用）上验证了方法的有效性。

关键设定与假设

  • 设定：\( X_1, \dots, X_n \sim P \) i.i.d.（正常样本），\( X_{n+1}, \dots, X_{n+m} \) 为待检测观测，其中正常观测来自 \( P \)，异常观测来自 \( Q \)。目标是检测异常观测，控制 FDR。
  • 核心假设：
  • 可交换性：在给定异常指示 \( H_i \) 的条件下，正常观测的联合分布与 \( X_1, \dots, X_n \) 可交换。这是 conformal inference 的标准假设，比参数分布假设弱得多。
  • 样本分割：将 \( X_1, \dots, X_n \) 分为训练集和校准集。训练集用于学习得分函数 \( \hat{s} \)，校准集用于构造 p 值。这一假设保证了 p 值的有效性。
  • 得分函数的任意性：\( \hat{s} \) 可以是任何概率分类算法的输出（如 logistic regression、random forest、神经网络），只要它满足一定的正则条件（如对称性）。
  • 相比已有文献的放宽 / 强化：相比经典的 conformal anomaly detection（如 Lei et al. 2018），本文放宽了得分函数必须预先指定的限制，允许数据自适应学习；相比经典的 BH 程序，本文将 p 值的构造从"预先固定"推广到"数据自适应"，同时保持 FDR 控制。

主要结果

  • 定理 1（FDR 控制）：在可交换性和样本分割假设下，AdaDetect 对任意得分函数 \( \hat{s} \) 和任意水平 \( \alpha \in (0,1) \)，有 \( \text{FDR} \le \alpha \)。这是有限样本保证，不依赖样本量或分布形式。
  • 定理 2（零假设比例自适应）：提出对 \( \pi_0 \) 自适应的变体，在保持 FDR 控制的同时，功效不低于非自适应版本。具体地，通过估计 \( \pi_0 \) 并调整 BH 阈值，可以在 \( \pi_0 < 1 \) 时提升功效。
  • 定理 3（功效分析）：在一定的备择假设下，AdaDetect 的功效不低于预先指定得分函数的 conformal 方法。这说明了数据自适应学习的优势。
  • 数值实验：在合成数据上，AdaDetect 相比固定得分函数的 conformal 方法，在多种分布设定下功效显著提升，同时 FDR 控制在名义水平附近。在真实数据（包括天体物理学数据集）上，AdaDetect 检测出已知的异常天体，且 FDR 控制良好。

证明路线与技术技巧

整体路线： 1. 构造 conformal p 值：对每个待检测观测 \( X_{n+i} \)，定义 \( \hat{p}_i = (1 + \sum_{j \in \mathcal{I}_{\text{cal}}} \mathbf{1}\{\hat{s}(X_j) \le \hat{s}(X_{n+i})\}) / (|\mathcal{I}_{\text{cal}}| + 1) \)，其中 \( \mathcal{I}_{\text{cal}} \) 是校准集。利用可交换性证明在零假设下 \( \hat{p}_i \) 是（近似）均匀分布的。 2. 应用 BH 程序：将 \( \hat{p}_1, \dots, \hat{p}_m \) 排序，用 BH 程序在水平 \( \alpha \) 下选择阈值。利用 BH 程序的 FDR 控制性质，结合 p 值的均匀性，证明 FDR ≤ \( \alpha \)。 3. 数据自适应学习：将得分函数 \( \hat{s} \) 视为从训练集学习的函数。由于训练集与校准集独立，且校准集与待检测观测中的正常观测可交换，因此 \( \hat{s} \) 的随机性不影响 p 值的均匀性。这保证了 FDR 控制对任意 \( \hat{s} \) 成立。 4. 零假设比例自适应：估计 \( \pi_0 \)（如 Storey 2002 的方法），将 BH 阈值调整为 \( \hat{q} = \max\{q : \hat{\pi}_0 q \cdot m / |\{i : \hat{p}_i \le q\}| \le \alpha\} \)。证明这保持了 FDR 控制，同时提升了功效。

关键技巧： - 样本分割：将数据分为训练集和校准集，是保证数据自适应不破坏可交换性的关键。这是 conformal inference 的标准技巧，但本文将其与 BH 程序结合。 - p 值的超均匀性：利用可交换性证明 \( \hat{p}_i \) 在零假设下满足 \( \mathbb{P}(\hat{p}_i \le t) \le t \)（超均匀性），这是 BH 程序 FDR 控制的充分条件。 - π₀ 估计的稳健性：使用截断估计器 \( \hat{\pi}_0 = (1 + \sum_{i=1}^m \mathbf{1}\{\hat{p}_i > \lambda\}) / (m(1-\lambda)) \)，并证明其对 \( \lambda \) 的选择不敏感。

真实例子与应用

  • 天体物理学应用：作者使用斯隆数字巡天（SDSS）的光谱数据，目标是检测异常天体（如类星体、特殊恒星）。将已知的正常恒星作为训练集，待检测观测为未知天体。AdaDetect 成功检测出已知的异常天体，且 FDR 控制在名义水平附近。这个例子展示了方法在高维、非参数设定下的实用性。
  • 合成数据实验：作者在多种分布设定下（如高斯混合、重尾分布）比较了 AdaDetect 与固定得分函数的 conformal 方法。结果显示，AdaDetect 在功效上显著提升（例如，在信噪比中等时，功效从 0.3 提升到 0.7），同时 FDR 控制在名义水平附近。

🔎 结论是否比证明窄

  • 定理 1 的 FDR 控制：证明是严格的，但依赖于样本分割。作者在讨论中提到，如果不进行样本分割（即用全部数据学习得分函数并构造 p 值），FDR 控制可能失效。这是一个明确的限制。
  • 定理 3 的功效分析：证明是在特定的备择假设下（如位置偏移）进行的，对于更一般的备择假设（如尺度变化、非线性变换），功效优势未严格证明。作者在文中承认这一点，称"功效优势在更一般的设定下需要进一步研究"。
  • π₀ 自适应变体：FDR 控制的证明依赖于 \( \hat{\pi}_0 \) 的估计精度。作者证明了对 \( \lambda \) 的选择不敏感，但未给出 \( \hat{\pi}_0 \) 在低功效场景下的理论保证。

四、开放问题

  1. 不分割样本的 FDR 控制：本文的 FDR 控制依赖于样本分割。若不分割样本（即用全部数据学习得分函数并构造 p 值），FDR 控制是否仍能成立？作者在讨论中暗示这可能失效，但未给出反例或修正方法。扎根于定理 1 的证明和讨论部分。

  2. 更一般备择假设下的功效分析：定理 3 的功效优势仅在位置偏移假设下证明。对于更一般的异常类型（如尺度变化、相关结构变化），AdaDetect 的功效优势是否成立？扎根于定理 3 的证明和作者关于"需要进一步研究"的陈述。

  3. π₀ 估计的精度与 FDR 控制的交互：π₀ 自适应变体的 FDR 控制依赖于 \( \hat{\pi}_0 \) 的估计精度。在低功效场景下，\( \hat{\pi}_0 \) 的估计可能不稳定，是否会导致 FDR 失控？扎根于定理 2 的证明和数值实验中对 \( \lambda \) 选择的讨论。

  4. 得分函数的选择与 FDR 控制的鲁棒性：本文对得分函数 \( \hat{s} \) 的任意性给出了理论保证，但实际中得分函数的选择（如神经网络 vs. 随机森林）是否会影响 FDR 控制的精度？扎根于数值实验中不同分类器的比较。

提示：要确认这些是否是真 gap，建议去读近 5 年 conformal inference 与多重检验交叉领域的近期工作（如 Wang & Ramdas 2022 的 e-BH 方法、Bates et al. 2021 的 e-values 框架），看它们是否已解决上述问题。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论