跳转至

Non-splitting Neyman-Pearson Classifiers

讲者: Jingming Wang
会场: Recent Developments in Statistical Methods and Learning
报告题目: Non-Splitting Neyman-Pearson Classifiers
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

这个子方向是 Neyman-Pearson (NP) 分类范式。它解决的根本问题是：在二分类任务中，当两类错误（第一类错误：将类0误判为类1；第二类错误：将类1误判为类0）的代价严重不对称时，如何构造一个分类器，使得第一类错误被严格控制在用户指定的水平 α 以下，同时最小化第二类错误。这与传统的“最小化总体误分率”的风险最小化范式有本质区别。当前该方向的成熟度：理论框架（NP oracle不等式）已建立，已有若干实用算法（如NP umbrella算法），但所有现有算法都依赖一个共同的、有代价的步骤——样本分裂。

发展脉络（history）

  1. 奠基工作：NP 分类的理论框架与 oracle 不等式

    • Rigollet and Tong (2011)：首次为NP分类提出了理论评价标准——NP oracle不等式。它要求一个样本分类器以高概率满足：第一类误差 ≤ α，且第二类误差接近最优（即NP oracle的第二类误差）。这为后续所有NP分类器的理论分析提供了基准。
    • Tong (2013)：提出了第一个满足NP oracle不等式的plug-in分类器，但依赖于参数假设。
    • Zhao et al. (2016)：将NP分类推广到高维稀疏设定（Naive Bayes模型），并首次提出了“检测条件”（detection condition），证明了该条件对于实现递减的 excess type II error 是必要的。

  2. 主要进展：实用算法与样本分裂的固化

    • Tong, Feng, and Li (2018)：提出了NP umbrella算法，这是一个里程碑式的非参数方法。它适用于任何“评分型”分类方法（如逻辑回归、SVM、随机森林）。其核心思想是：用一部分数据（混合类0和类1）训练评分函数 ŝ(·)，再用留出的类0样本的评分值来构造阈值。该算法通过二项式分布的上界，保证了第一类误差以高概率被控制。然而，这个算法明确依赖于样本分裂，因为留出的类0样本的评分值在条件于ŝ(·)后是独立的，这是其阈值构造和概率上界推导的基础。
    • Tong et al. (2020)：提出了基于LDA模型的参数化NP分类器（pNP-LDA），其阈值构造依赖于t统计量，同样需要样本分裂来保证独立性。
    • Scott (2019) 和 Tian and Feng (2021)：将NP范式推广到领域自适应和多分类问题，但这些推广也继承了样本分裂的框架。

  3. 当前 Frontier 与本文的位置

    • 当前瓶颈：所有现有NP分类器都依赖样本分裂，这导致两个问题：(i) 用于训练评分函数的数据减少，降低了评分函数的质量；(ii) 当类0样本量很小时，分裂后用于阈值构造的样本更少，甚至无法满足最小样本量要求（如NP umbrella算法要求留出至少 ⌈log δ / log(1-α)⌉ 个类0样本）。“非分裂策略”一直是该领域的“愿望清单”。
    • 本文的位置：本文是首次尝试在NP范式下实现非分裂策略。作者选择从线性判别分析（LDA）模型入手，因为该模型是分类中最经典的参数模型之一，且其结构（高斯分布、共同协方差矩阵）使得分析样本内依赖成为可能。作者通过推导一个关于样本协方差矩阵逆的二次型泛函的定量中心极限定理（CLT），成功构造了无需分裂的NP分类器 eLDA。

子线索聚类

  1. NP分类的理论与算法：这条线索关注NP范式的理论框架（NP oracle不等式）、算法设计（NP umbrella, pNP-LDA）及其推广（领域自适应、多分类）。核心工作是 Rigollet and Tong (2011), Tong (2013), Zhao et al. (2016), Tong et al. (2018, 2020), Scott (2019), Tian and Feng (2021)。
  2. 高维LDA分类器：这条线索关注在高维（p 与 n 可比或更大）设定下，如何构造有效的LDA分类器。核心挑战是样本协方差矩阵不可逆或估计不准。主要方法包括稀疏LDA（Shao et al., 2011; Witten and Tibshirani, 2012; Cai and Zhang, 2019）、正则化LDA（Fan et al., 2012; Wang and Jiang, 2018）、以及基于旋转的方法（Hao et al., 2015）。本文的eLDA也属于此类，但它是第一个在NP范式下、无需样本分裂的LDA分类器。
  3. 随机矩阵理论（RMT）工具：本文的技术核心依赖于RMT。被引用的关键RMT工作包括：
    • Bloemendal et al. (2014, 2016)：证明了样本协方差矩阵的各向同性局部律（isotropic local law），为本文提供了估计Green函数及其二次型的高概率界。
    • Erdős et al. (2013)：引入了随机控制（stochastic domination）的概念，本文用它来简洁地表达高概率界。

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

  1. 如何在不分裂样本的情况下，保证第一类误差的高概率控制？ 这是本文直接回答的问题。现有方法依赖分裂带来的独立性，非分裂策略必须处理评分函数与阈值估计之间的复杂依赖。
  2. 在非分裂策略下，excess type II error 的衰减速率是多少？ 本文给出了答案：当 p/n → 0 时，excess type II error 趋于0；当 p/n → r₀ ∈ (0,1) 时，它趋于0当且仅当 Mahalanobis 距离 Δ_d 发散。
  3. NP分类器在高维（p > n）设定下的理论性质如何？ 本文只处理了 p/n < 1 的情形。对于 p > n，需要引入特征筛选或结构假设（如稀疏性），这是未来工作。
  4. 如何将非分裂策略推广到更复杂的模型（如QDA）或非参数方法？ 本文的LDA模型是起点，但非分裂策略的通用性是一个开放问题。

⚠️ 作者的 framing

  • 作者的缺口 frame：作者将现有NP分类器的核心缺陷 frame 为“样本分裂导致的数据利用不充分和更高的第二类误差”。他们将自己的工作 frame 为“首次实现非分裂策略”，从而“更高效地利用数据”。他们通过一个简单的数值例子（Table 1）直观地展示了eLDA相比分裂方法pNP-LDA的巨大优势（第二类误差从0.7638降至0.4478）。
  • 被淡化或回避的竞争路线：作者明确指出，对于非参数NP umbrella算法，“没有方法能刻画一般的依赖关系”，因此“几乎没有潜力扩展到非分裂场景”。这实际上是将非分裂策略的可行性限定在了参数模型（如LDA）上。他们回避了讨论在非参数设定下实现非分裂策略的可能性。
  • 什么明显该被引/该存在、却没出现在intro里？ 作者在讨论高维LDA分类器时，引用了大量相关工作。但值得注意的是，他们没有引用任何关于“样本外误差估计”或“数据再利用”的文献，例如关于交叉验证、自助法（bootstrap）或经验过程理论中处理依赖数据的经典工作。这些方法在理论上也可能用于构造非分裂的阈值，但作者选择了从随机矩阵理论出发，直接分析样本内统计量的分布。这是一个值得研究者去查的张力点：是否存在更通用的、基于重抽样或经验过程的非分裂NP分类方法？

张力

未见明显对立引用。所有被引工作都承认样本分裂是NP分类的通用做法，并在此基础上进行改进。本文是第一个挑战这一共识的工作。

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

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

  • 符号：

    • Y ∈ {0, 1}: 类别标签。
    • X ∈ ℝᵖ: p维特征向量。
    • φ(·): 分类器，将X映射到{0, 1}。
    • R₀(φ) = P(φ(X) ≠ Y | Y=0): 第一类误差（population-level）。
    • R₁(φ) = P(φ(X) ≠ Y | Y=1): 第二类误差（population-level）。
    • α ∈ (0,1): 用户指定的第一类误差上界。
    • δ ∈ (0,1): 用户指定的第一类误差违反概率上界。
    • µ₀, µ₁ ∈ ℝᵖ: 类0和类1的均值向量。
    • Σ ∈ ℝᵖˣᵖ: 共同的协方差矩阵（正定）。
    • µ_d = µ₁ - µ₀: 均值差向量。
    • Δ_d = µ_dᵀ Σ⁻¹ µ_d: Mahalanobis距离，衡量两类之间的分离程度。
    • Φ(·): 标准正态分布的累积分布函数。Φ⁻¹(1-α) 是其 (1-α) 分位数。
    • n₀, n₁: 类0和类1的样本量。n = n₀ + n₁。
    • p: 特征维度。
    • r = p/n: 维度-样本量比。
    • S₀ = {X⁰₁, ..., X⁰_{n₀}}, S₁ = {X¹₁, ..., X¹_{n₁}}: 可观测的独立同分布样本。
    • Ŝ: 样本协方差矩阵。
    • µ̂₀, µ̂₁: 样本均值向量。
    • µ̂_d = µ̂₁ - µ̂₀: 样本均值差。
    • Â = Ŝ⁻¹ µ̂_d: 样本判别方向。
    • φ*_α(·): NP oracle分类器，即理论上最优的分类器，其形式为 1I( (Σ⁻¹µ_d)ᵀ x > √Δ_d Φ⁻¹(1-α) + µ_dᵀ Σ⁻¹ µ₀ )。

  • 模型：线性判别分析（LDA）模型。数据生成机制为：

    • (X | Y=0) ~ N(µ₀, Σ)
    • (X | Y=1) ~ N(µ₁, Σ) 其中 µ₀, µ₁, Σ 是未知参数。

  • 可观测数据：研究者能观测到的是来自两个类别的独立样本 S₀ 和 S₁。想要但观测不到的是 µ₀, µ₁, Σ 这些总体参数，以及NP oracle分类器 φ*_α 本身。分类任务的目标就是基于可观测样本，构造一个接近 φ*_α 的样本分类器。

第二步：讲最小内核

本文的核心思路可以浓缩为以下最简特例：固定特征维度 p（即 p = O(1)），且 p/n → 0。在这个特例下，问题大大简化，但核心思想不变。

  • 核心问题：在LDA模型下，NP oracle分类器 φ*_α(x) 的阈值是 T* = √Δ_d Φ⁻¹(1-α) + µ_dᵀ Σ⁻¹ µ₀。一个自然的想法是用样本估计量 Â 和 µ̂₀ 来构造一个样本阈值 T̂。然而，直接plug-in会导致第一类误差无法控制，因为 T̂ 可能小于 T*，从而使得第一类误差超过 α。

  • 关键想法：构造一个比 T* 略大的样本阈值 Ĉ_α，使得 P(Ĉ_α ≥ T*) ≥ 1-δ。这样，用 Ĉ_α 作为阈值，就能以高概率保证第一类误差 ≤ α。

  • 如何实现：

    1. 构造一个接近 T* 的估计量 F̂：作者首先构造了一个 T* 的相合估计 F̂(Ŝ, µ̂₀)。在 p 固定的情况下，F̂ 可以简化为 F̂ = √(ÂᵀŜÂ) Φ⁻¹(1-α) + Âᵀµ̂₀。当 n 很大时，F̂ 会趋近于 T*，但它的随机误差可正可负。
    2. 刻画 F̂ - T* 的渐近分布：作者证明了 F̂ - T* 是渐近正态的，均值为0，方差为 V/n，其中 V 是一个可估计的量。即： √n (F̂ - T*) / √V → N(0, 1)。
    3. 构造保守阈值 Ĉ_α：利用这个渐近正态性，我们可以构造一个比 F̂ 更大的阈值： Ĉ_α = F̂ + √(V/n) Φ⁻¹(1-δ)。 因为 P( (F̂ - T*) / √(V/n) ≤ Φ⁻¹(1-δ) ) ≈ 1-δ，所以 P( T* ≤ F̂ + √(V/n) Φ⁻¹(1-δ) ) ≈ 1-δ。这就保证了 Ĉ_α 以高概率大于 T*。

  • 为什么难：在非分裂设定下，F̂ 和 T* 都依赖于同一个样本协方差矩阵 Ŝ 和样本均值 µ̂₀。因此，F̂ - T* 的分布分析非常复杂，因为它涉及到 Ŝ⁻¹ 的二次型及其与样本均值的交叉项。作者需要利用随机矩阵理论中的局部律和定量CLT来精确刻画这个差值的分布，这在之前的工作中是没有的。

  • 最小内核总结：本文在数学上干的事就是：在LDA模型下，推导出 F̂ - T* 的渐近正态分布（均值和方差都有显式表达式），并利用这个结果构造一个保守的、无需样本分裂的阈值，从而得到一个新的NP分类器 eLDA。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在LDA模型下，构造了第一个无需样本分裂的Neyman-Pearson分类器，解决了现有NP分类器因样本分裂导致数据利用不充分、第二类误差偏高的问题。
  2. 核心工具/方法：利用随机矩阵理论，推导了一个关于样本协方差矩阵逆的二次型泛函的定量中心极限定理（CLT），并基于此构造了一个保守的、以高概率控制第一类误差的阈值。
  3. 主要结论：提出的eLDA分类器能以高概率（≥ 1-δ）保证第一类误差 ≤ α。当 p/n → 0 时，其excess type II error（与NP oracle的差距）趋于0；当 p/n → r₀ ∈ (0,1) 时，excess type II error趋于0当且仅当Mahalanobis距离 Δ_d 发散。

关键设定与假设

  • Assumption 1:
    • (i) 维度与样本量：p/n → r₀ ∈ [0, 1)，且 n₀/n > c₀, n₁/n > c₁ 对某正常数 c₀, c₁ 成立。这保证了样本协方差矩阵 Ŝ 可逆（因为 p < n），且两类样本量都足够大。
    • (ii) Mahalanobis距离：Δ_d = µ_dᵀ Σ⁻¹ µ_d ≥ c₂ > 0。这保证了两类之间有足够的分离度，是分类问题有意义的基本条件。
  • 与已有文献的对比：
    • 相比NP umbrella算法 (Tong et al., 2018)：本文的假设更强（LDA模型 vs. 无分布假设），但去掉了样本分裂的要求。
    • 相比pNP-LDA (Tong et al., 2020)：两者都基于LDA模型，但pNP-LDA需要样本分裂来构造t统计量，而本文不需要。
    • 相比高维LDA文献 (Shao et al., 2011; Cai and Zhang, 2019)：这些工作通常关注最小化总体误分率，而本文关注NP范式下的第一类误差控制。此外，本文没有施加稀疏性假设，而是允许 p/n → r₀ ∈ (0,1)，这是一个更一般的设定。

主要结果

  • Theorem 1 (eLDA的主要定理)：

    • 设定：在Assumption 1下，对于任意 α, δ ∈ (0,1)，定义eLDA分类器 φ̂_α(x) = 1I(Âᵀx > Ĉ_α)，其中 Ĉ_α 由公式(3.4)定义。
    • 结论 (i) - 第一类误差控制：存在常数 C₁, C₂ > 0，使得对任意 ε ∈ (0, 1/2) 和 D > 0，当 n 足够大时，有 P(R₀(φ̂_α) > α) ≤ δ + C₁ n^{-1/2 + ε} + C₂ n^{-D}。 这意味着第一类误差超过 α 的概率被控制在 δ 附近（加上一个随 n 增大的小项）。
    • 结论 (ii) - 第二类误差：
      • 当 p/n → 0 时，excess type II error R₁(φ̂_α) - R₁(φ*_α) ≤ C (r + n^{-1/2 + ε}) √Δ_d exp(-cΔ_d/2)。这保证了当样本量足够大时，eLDA的表现接近NP oracle。
      • 当 p/n → r₀ ∈ (0,1) 时，给出了excess type II error的显式上下界。下界表明，如果 Δ_d 是常数阶的，则excess type II error不会衰减到0；上界表明，如果 Δ_d 发散，则excess type II error会趋于0。这是NP分类文献中首次给出excess type II error的下界结果。

  • Corollary 1 (feLDA)：当 p = O(1) 时，给出了一个简化版的分类器feLDA，其阈值构造更简单，且具有与Theorem 1类似的理论保证。

证明路线与技术技巧

  • 整体路线：

    1. Green函数表示：首先，利用Woodbury矩阵恒等式，将 Ŝ⁻¹ 表示为关于数据矩阵 X 的Green函数 G₁(z) = (XXᵀ - z)⁻¹ 的形式（公式D.6）。这使得所有感兴趣的二次型（如 ÂᵀŜÂ, Âᵀµ̂₀）都可以用 G₁ 及其与 X 的乘积的二次型来表示。
    2. 局部律展开：利用随机矩阵理论中的各向同性局部律（Proposition 1），对Green函数的二次型进行展开。例如，uᵀG₁(z)v 可以近似为 m₁(z) uᵀv，误差为 O≺(n^{-1/2} r^{1/2})。通过这种展开，可以推导出 ÂᵀŜÂ, Âᵀµ̂₀ 等量的一阶展开式（Lemma 3），从而构造出 F̂。
    3. 定量CLT：为了刻画 F̂ - T* 的分布，需要进行二阶展开。关键步骤是证明一个关于Green函数二次型线性组合的定量中心极限定理（Proposition D.1）。这个定理表明，一个形如 P（公式D.21）的统计量是渐近正态的，且其收敛速度是 O≺(n^{-1/2})。
    4. 构造保守阈值：基于定量CLT，可以计算出 F̂ - T* 的渐近方差 V̂，并构造出 Ĉ_α = F̂ + √(V̂/n) Φ⁻¹(1-δ)。证明 Ĉ_α ≥ T* 以高概率成立，从而完成第一类误差控制的证明。最后，利用 ÂᵀŜÂ 和 ÂᵀΣÂ 的关系，推导出第二类误差的界。

  • 关键跳跃点：

    • 从一阶展开到二阶展开：一阶展开只能得到相合估计，但为了得到渐近分布，必须精确捕捉到 F̂ - T* 中 O_p(n^{-1/2}) 阶的随机项。这需要将Green函数展开到二阶，并处理复杂的交叉项。
    • 定量CLT的证明：证明 P 的渐近正态性（Proposition D.1）是整个证明中最吃功夫的部分。作者使用了高斯积分by parts（Stein's method的一种变体）来推导 P 的特征函数所满足的微分方程，从而证明其收敛到正态分布的特征函数，并给出收敛速率。

  • 技术技巧点名：

    • 随机矩阵理论：
      • 各向同性局部律 (Isotropic Local Law, Proposition 1)：用于估计Green函数及其二次型的高概率界。这是整个技术分析的基石。
      • 随机控制 (Stochastic Domination, Definition 1)：一种简洁的符号，用于表达“以高概率被某个量控制”的关系，简化了概率界的书写。
      • Green函数 (Green function / Resolvent)：将样本协方差矩阵的逆与数据矩阵联系起来，使得可以利用谱理论进行分析。
    • 高斯积分by parts (Gaussian Integration by Parts)：用于计算高斯随机变量函数的期望，是证明CLT的核心工具。作者巧妙地将其应用于Green函数的二次型，推导出特征函数的微分方程。
    • Woodbury矩阵恒等式：用于将 Ŝ⁻¹ 展开为Green函数的表达式。

真实例子与应用

  • 模拟实验：

    • 数据：从LDA模型生成，协方差矩阵为AR(1)结构。
    • 方法：将eLDA和feLDA与五种现有的分裂NP分类器（pNP-LDA, NP-LDA, NP-sLDA, NP-svm, NP-penlog）进行比较。
    • 结果：
      • 在小样本量（如 n₀=20）下，只有eLDA、feLDA和pNP-LDA可以运行，而eLDA和feLDA的第二类误差远小于pNP-LDA。
      • 在维度增加时，eLDA的第一类误差始终被控制在 α 以下，而feLDA在p较大时失效。eLDA的第二类误差在所有方法中通常是最小的。
      • 违反率：eLDA的观测违反率（type I error violation rate）非常接近目标 δ，而其他分裂方法则过于保守（违反率远小于δ）。
    • 说明：这些模拟验证了理论结果，并展示了eLDA在数据利用效率上的优势，尤其是在类0样本量小或维度较高时。

  • 真实数据：

    • 肺癌数据集：181个样本，12533个基因。类0（MPM，罕见且致命）样本量31，类1（ADCA）样本量150。
    • 癌症数据集 (Su et al., 2001)：174个样本，12533个基因。类0样本量83，类1样本量91。
    • 处理：由于p远大于n，先通过t检验筛选出40个基因。由于类0样本量小，只有eLDA和pNP-LDA可以运行。
    • 结果：在两个数据集上，eLDA都显著优于pNP-LDA。pNP-LDA的第二类误差为1（即把所有样本都判为类1），而eLDA的第二类误差分别为0.104和0.437，同时第一类误差仍被控制在α=0.01以下。
    • 说明：这些例子展示了eLDA在真实应用中，当类0样本稀缺时，相比现有参数化分裂方法的巨大优势。

🔎 结论是否比证明窄

  • 是。Theorem 1的结论 (ii) 关于excess type II error的界，在 p/n → r₀ ∈ (0,1) 时，给出了一个依赖于 Δ_d 发散的条件。这意味着如果两类之间的Mahalanobis距离是常数阶的，即使样本量很大，eLDA的第二类误差也无法趋近于NP oracle。作者在Remark 1中明确指出了这一点，并说明这与之前文献中的“检测条件”是一致的。这个结论比“eLDA总是优于分裂方法”这种泛泛的claim要窄得多，它揭示了在维度与样本量可比时，NP分类问题的固有困难。

四、开放问题

  1. 扩展到 p > n 的设定：本文只处理了 p/n < 1 的情形。作者在Discussion中明确指出，未来工作可以结合特征筛选方法（如Fan and Song, 2010; Li et al., 2012）或对LDA模型施加稀疏性假设，来处理 p > n 的情况。扎根点：Section 7, "For future works, we can work in settings where p is larger than n by selecting features via various marginal screening methods... and/or may add structural assumptions to the LDA model."

  2. 推广到更复杂的模型：本文基于LDA模型。作者提到可以推广到二次判别分析（QDA）模型。扎根点：Section 7, "To accommodate diverse applications, one might also construct classifiers based on more complicated models, such as the quadratic discriminant analysis (QDA) model..."

  3. 非分裂策略的通用性：本文的非分裂策略高度依赖于LDA模型和随机矩阵理论工具。一个开放问题是，能否为更一般的评分型分类方法（如逻辑回归、神经网络）设计非分裂的NP分类器？作者在introduction中认为NP umbrella算法“has little potential to be extended to the non-splitting scenario”，但这并不意味着其他非参数方法不可能。扎根点：Section 1, "...the NP umbrella algorithm... has little potential to be extended to the non-splitting scenario, simply because there is no way to characterize the general dependence."

  4. 非高斯情形的理论：模拟实验（Example 3）显示，在t分布下，eLDA的表现变得保守，且当样本量增大时，被非参数NP umbrella算法超越。这表明eLDA的理论保证对高斯假设是敏感的。一个开放问题是，能否在更弱的分布假设下（如亚高斯分布）建立类似的理论结果。扎根点：Appendix E.2, "We believe this phenomenon is due to the fine calibration of the LDA model in the development of eLDA and feLDA, which leads to conservative results in heavy-tail distribution settings."

Maintained by 陈星宇 · Homepage · Source on GitHub

评论