跳转至

A bipartite ranking approach to the two-sample problem

作者: Stephan Clémençon, Myrto Limnios, Nicolas Vayatis
来源: Electronic Journal of Statistics
主题: 数理统计 / 假设检验
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么： 非参数两样本检验的核心统计问题是：给定两组独立样本，判断它们是否来自同一个未知分布 \(P\)。当数据维度 \(d \geq 2\) 时，由于 \(\mathbb{R}^d\) 缺乏自然序，一维秩检验的天然优势（分布无关、对局部偏移敏感）无法直接延拓；而基于经验分布差异（如 KS 统计量、MMD）的方法在高维下受维度诅咒影响，检验功效急剧下降。本子方向致力于在高维设定下，寻找既能保留秩检验分布无关性，又能规避多维序缺失与维度诅咒的检验框架，当前处于从“高维功效衰减的理论解释”向“基于测度运输/似然比投影的新检验构造”过渡的阶段。

发展脉络： - 奠基工作：一维秩检验理论（Wilcoxon/Mann-Whitney，见 Serfling 1980, van der Vaart 1998）建立了分布无关性与局部最优性；高维两样本检验的核/距离方法奠基（Gretton et al. 2006 MMD；Székely et al. 2007 distance correlation）将检验统计量建立在 RKHS 均值映射或距离协方差上，提供了大偏差界与渐近分布。 - 主要进展与瓶颈揭示：Ramdas et al. (2014) 明确指出，基于核与距离的非参数检验在“公平替代假设”下，其功效随维度 \(d\) 增加呈多项式衰减，揭示了估计统计量与检验其是否为零之间的硬度差异；Chakraborty & Chaudhuri (2014, 2015) 将空间符号与秩延拓至无穷维/高维，证明了在特定混合条件下均值检验与符号秩检验渐近功效相同，但依赖坐标间弱相关假设。 - 当前 frontier：测度运输框架下的多维秩构造（Chernozhukov et al. 2017; Hallin et al. 2021; Deb & Sen 2019）通过最优传输映射定义多维秩/符号，恢复了严格分布无关性，并构造了 distance covariance/energy statistic 的多维秩版本；Carpentier et al. (2018) 与 Lam-Weil et al. (2019) 在稀疏线性回归与离散分布上给出了局部 minimax 检验速率的精确刻画。 - 本文的位置：Clémençon et al. (2021) 建立了两样本线性秩过程的浓度不等式；本文在此基础上，将二部排序与两样本检验结合，提出“先学似然比投影、后做一维秩检验”的两步法，声称通过学习评分函数将高维数据投影至一维，绕过维度诅咒与多维序缺失。

子线索聚类： 1. 核/距离方法与高维硬度分析：Gretton et al. (2006), Székely et al. (2007), Harchaoui et al. (2007), Ramdas et al. (2014)。这一簇在 RKHS 或距离空间构造检验统计量，Ramdas et al. 揭示其高维功效衰减。 2. 多维秩/符号/深度构造：Chernozhukov et al. (2017), Hallin et al. (2021), Deb & Sen (2019), Mosler (2012), Chakraborty & Chaudhuri (2014, 2015), Hallin & Paindaveine (2008), Lung-Yut-Fong et al. (2011)。这一簇试图通过深度、空间符号或测度运输恢复多维秩的分布无关性与最优性。 3. 排序学习与 U-统计量理论：Clémençon et al. (2006), Clémençon et al. (2021)。这一簇将排序风险定义为 U-统计量，建立 U-过程的浓度不等式与经验最小化快速收敛率，为本文的评分函数学习与秩过程浓度提供技术基础。

核心追问： 1. 高维两样本检验的 minimax 检验速率是什么？与估计速率的分离如何刻画？（Carpentier et al. 2018; Lam-Weil et al. 2019 在特定模型给出了精确回答，一般连续分布尚开放。） 2. 如何在 \(\mathbb{R}^d\) (\(d \geq 2\)) 上定义严格分布无关且对局部偏移敏感的秩检验？（Deb & Sen 2019; Hallin et al. 2021 给了测度运输答案，但计算与渐近分布复杂。） 3. 基于核/距离的方法在高维功效衰减是否可补救？投影/排序能否绕过？（Ramdas et al. 2014 指出衰减；本文声称投影可绕过。）

⚠️ 作者的 framing： - 作者将缺口 frame 为：经典基于经验分布差异的方法受维度诅咒影响，而一维秩检验在恰当设计下可检测微小偏移，但多维缺乏自然序；因此“学习似然比投影+一维秩检验”是显然的下一步。 - 被淡化/回避的竞争路线：测度运输多维秩（Deb & Sen 2019; Hallin et al. 2021）仅在引用中提及深度与测度运输概念，未与其严格分布无关性及渐近最优性直接对比；Ramdas et al. (2014) 的高维硬度分析未被引用，其“公平替代假设下功效衰减”的结论可能对本文“不受维度影响”的声称构成挑战。 - 明显该被引却未出现的：Ramdas et al. (2014)（高维功效衰减的关键理论依据）；一般连续分布上两样本检验的 minimax 速率工作（如 Arias-Castro et al. 2018 或相关泛函自适应检验）；半参数效率界在两样本检验中的刻画（如 Bahadur 等渐近比较理论）。这些缺失使得“不受维度影响”的声称缺乏与 minimax 界的直接对照。

张力： 未见明显对立引用。但隐含张力：Ramdas et al. (2014) 证明核/距离检验在高维公平替代下功效多项式衰减，而本文声称投影法“not much affected by the dimensionality”——两者结论是否矛盾取决于“公平替代假设”的定义差异（Ramdas 要求随 \(d\) 增长信号衰减，本文假设排序模型偏差可控、信号强度固定）。研究者应核查本文替代假设是否随 \(d\) 变化，否则“不受维度影响”的声称可能仅在信号不衰减的设定下成立。

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

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

  • \(P\) 与 \(Q\)：\(\mathbb{R}^d\) 上的两个未知分布（待检验对象）。
  • \(H_0\)：零假设 \(P = Q\)；\(H_1\)：替代假设 \(P \neq Q\)。
  • \(X_1, \ldots, X_n\)：来自 \(P\) 的可观测独立样本（标签赋为负，\(Y=0\)）。
  • \(Z_1, \ldots, Z_m\)：来自 \(Q\) 的可观测独立样本（标签赋为正，\(Y=1\)）。
  • \(s: \mathbb{R}^d \to \mathbb{R}\)：评分函数，将高维数据投影至一维实数。
  • \(s^*(x)\)：最优评分函数，定义为似然比 \(dQ/dP(x)\)（或其任意单调变换），是排序的 Bayes 规则。
  • \(R_n, S_m\)：样本分拆——将 \(X\) 样本分为 \(R_n\)（训练集）与 \(X \setminus R_n\)（检验集），\(Z\) 样本分为 \(S_m\)（训练集）与 \(Z \setminus S_m\)（检验集）。
  • \(\hat{s}\)：在训练集 \((R_n, S_m)\) 上通过二部排序算法学到的评分函数。
  • \(U_{N, \hat{s}}\)：两样本线性秩统计量，基于检验集上 \(\hat{s}\) 的评分值计算。
  • \(N\)：总样本量 \(N = n + m\)。
  • \(d\)：数据维度。
  • 潜在/不可观测量：\(P\) 与 \(Q\) 的密度比 \(dQ/dP\)（若存在）是潜在的最优评分 \(s^*\)，只能通过排序算法逼近；\(P\) 与 \(Q\) 的具体分布形式不可观测，检验需分布无关性。

模型：数据生成机制为 \(X_i \sim P\) 独立，\(Z_j \sim Q\) 独立，两组样本独立。评分函数 \(s\) 的排序风险定义为 \(\mathbb{P}(s(X) < s(Z)) + \frac{1}{2}\mathbb{P}(s(X) = s(Z))\)，最小化此风险的 \(s\) 即为似然比的单调变换。学习步骤假设排序模型（如 VC 类 \(\mathcal{S}\)）的偏差 \(\sup_{s \in \mathcal{S}} |R(s) - R(s^*)|\) 可控。

可观测数据：研究者实际观测到的是两组高维样本 \(\{X_i\}_{i=1}^n\) 与 \(\{Z_j\}_{j=1}^m\)，以及通过训练集学到的评分函数 \(\hat{s}\) 在检验集上的评分值 \(\{\hat{s}(X_i)\}_{i \notin R_n}\) 与 \(\{\hat{s}(Z_j)\}_{j \notin S_m}\)。不可观测的是真实似然比 \(s^*\) 与分布 \(P, Q\) 的具体形式。

第二步：最小内核——\(d=1\) 且 \(s^*\) 已知时的特例

剥掉所有高维、学习偏差与分拆假设，最小内核是：\(d=1\)，评分函数 \(s\) 就是数据本身（\(s(x)=x\)），且已知 \(s^*=s\)（无学习偏差），两样本 Wilcoxon 秩和检验。

在此特例下： - 要证的命题退化为：在 \(H_0: P=Q\) 下，Wilcoxon 秩和统计量 \(U_N = \frac{1}{nm} \sum_{i \notin R_n} \sum_{j \notin S_m} \mathbb{I}(X_i < Z_j)\) 的分布不依赖 \(P\)（分布无关性），且在 \(H_1: P \neq Q\) 下，\(U_N\) 偏离其零假设期望 \(\frac{1}{2}\)，偏离幅度由 \(\mathbb{P}(X < Z) - \frac{1}{2}\) 决定。 - 证明路线：\(U_N\) 是 \(U\)-统计量，核为 \(h(x,z) = \mathbb{I}(x < z)\)。在 \(H_0\) 下，\(X\) 与 \(Z\) 同分布，秩的联合分布完全由样本量决定（置换分布），故分布无关性成立。浓度不等式退化为 Hoeffding 界：\(|U_N - \frac{1}{2}| \leq O(1/\sqrt{N})\) 依高概率。 - 为什么成立：一维数据有自然序，\(\mathbb{I}(x < z)\) 直接捕捉了 \(P\) 与 \(Q\) 的分布差异（若 \(Q\) 右偏，则 \(\mathbb{P}(X < Z) > \frac{1}{2}\)）。秩统计量将分布差异压缩为可检验的信号。

本文的一般情形只是这个特例的“加壳”： 1. \(d \geq 2\) 时无自然序，故需学习评分函数 \(\hat{s}\) 将 \(\mathbb{R}^d\) 投影至 \(\mathbb{R}\)，逼近似然比 \(s^*\) 的排序能力。 2. \(\hat{s}\) 未知需从数据学习，故需样本分拆以避免过拟合，训练集学 \(\hat{s}\)，检验集算秩。 3. \(\hat{s}\) 有学习偏差，故需浓度不等式控制 \(|U_{N, \hat{s}} - U_{N, s^*}|\)，这依赖于 Clémençon et al. (2021) 的两样本秩过程浓度界。

核心数学困难在于：学习偏差 \(\hat{s} - s^*\) 如何通过秩过程传导至检验统计量的偏差。秩统计量对评分函数的依赖是非线性的（通过排序诱导），控制此传导需要将秩过程视为评分函数类上的随机过程，并建立其关于 VC 类的浓度界。

三、这篇论文做了什么

三句话： 1. 研究了高维两样本检验问题，提出基于二部排序的两步法：先学习评分函数逼近似然比投影，再对评分执行一维秩检验。 2. 核心工具是两样本线性秩过程的非渐近浓度不等式（Clémençon et al. 2021）与排序经验最小化的收敛分析。 3. 主要结论是：在排序模型偏差可控的假设下，两步法检验统计量的第一类错误受控且第二类错误收敛速率为 \(O(1/\sqrt{N})\)，声称不受维度 \(d\) 直接影响。

关键设定与假设：

在第二节最小记号基础上补全： - 评分函数类 \(\mathcal{S}\)：VC 维有限的实值函数类（如线性评分、树形评分），用于排序学习。 - 排序风险 \(R(s)\)：\(R(s) = \mathbb{P}(s(X) < s(Z)) + \frac{1}{2}\mathbb{P}(s(X) = s(Z))\)，Bayes 风险 \(R(s^*)\) 对应似然比的单调变换。 - 经验排序风险 \(\hat{R}(s)\)：在训练集 \((R_n, S_m)\) 上计算的 \(U\)-统计量，\(\hat{R}(s) = \frac{1}{|R_n||S_m|} \sum_{x \in R_n} \sum_{z \in S_m} \mathbb{I}(s(x) < s(z)) + \frac{1}{2}\mathbb{I}(s(x) = s(z))\)。 - \(\hat{s}\)：\(\hat{R}(s)\) 在 \(\mathcal{S}\) 上的最小化者（经验排序风险最小化）。 - 假设 1（排序模型偏差可控）：\(\mathcal{S}\) 包含 \(s^*\) 或逼近误差 \(\epsilon_{\mathcal{S}} = \inf_{s \in \mathcal{S}} R(s) - R(s^*)\) 有限。统计含义：评分函数类足够丰富，能逼近似然比的排序能力；若 \(\epsilon_{\mathcal{S}}\) 大，则投影损失排序信息，检验功效下降。相比已有文献，这是本文特有的假设，将检验功效与排序学习偏差绑定。 - 假设 2（样本分拆）：训练集与检验集独立。统计含义：避免 \(\hat{s}\) 过拟合导致的检验偏差；这是标准样本分拆假设。 - 假设 3（分布连续性）：\(P\) 与 \(Q\) 连续，评分 \(s(X)\) 与 \(s(Z)\) 无结。统计含义：简化秩统计量定义，避免结的处理；可放宽但技术更复杂。

主要结果：

  1. 定理：检验统计量的浓度界（核心理论结果）
  2. 陈述：在 \(H_0\) 下，对 VC 类 \(\mathcal{S}\) 上的经验排序风险最小化者 \(\hat{s}\)，检验集上的两样本秩统计量 \(U_{N, \hat{s}}\) 满足：
    \[\mathbb{P}\left(|U_{N, \hat{s}} - \frac{1}{2}| > t\right) \leq C_1 e^{-C_2 N t^2} + \text{learning deviation term}\]
    其中学习偏差项为 \(O(\sqrt{V / N_{\text{train}}})\)，\(V\) 为 VC 维，\(N_{\text{train}} = |R_n| + |S_m|\)。
  3. 直觉：秩统计量在零假设下围绕 \(\frac{1}{2}\) 波动，波动由两部分贡献——秩过程的随机波动（指数衰减）与评分函数学习偏差（由训练样本量与 VC 维控制）。
  4. 必要条件：VC 维有限、训练集与检验集独立、\(H_0\) 成立。

  5. 解决的技术难点：将秩统计量对评分函数的依赖解耦为“若 \(s^*\) 已知时的秩波动”与“\(\hat{s}\) 替代 \(s^*\) 引起的偏差”，后者通过两样本秩过程的浓度界控制。

  6. 定理：第二类错误保证（在 \(H_1\) 下）

  7. 陈述：在 \(H_1: P \neq Q\) 下，若排序模型偏差 \(\epsilon_{\mathcal{S}}\) 可控且信号强度 \(\Delta = R(s^*) - \frac{1}{2}\) 足够大（\(\Delta > \epsilon_{\mathcal{S}} + c/\sqrt{N}\)），则检验功效趋于 1，速率 \(O(1/\sqrt{N})\)。
  8. 直觉：似然比评分 \(s^*\) 能将 \(P\) 与 \(Q\) 的分布差异转化为排序差异 \(\Delta\)；若学习偏差不吞噬 \(\Delta\)，则一维秩检验可检测此差异。
  9. 必要条件：\(\Delta > \epsilon_{\mathcal{S}} + c/\sqrt{N}\)，即信号必须大于学习偏差加随机波动。

  10. 解决的技术难点：将高维分布差异的检测条件转化为排序风险差异的可检测性，并证明学习偏差不破坏此转化。

  11. 推论：维度无关性声称

  12. 陈述：浓度界与第二类错误界中不显含维度 \(d\)，仅依赖 VC 维 \(V\) 与样本量 \(N\)。
  13. 直觉：评分函数将高维数据投影至一维，维度诅咒被“转移”至排序学习步骤的 VC 维；若 VC 维不随 \(d\) 增长（如线性评分 \(V = d+1\)，则 \(V\) 随 \(d\) 增长），则声称失效。
  14. ⚠️ 此声称的隐含条件：VC 维 \(V\) 不随 \(d\) 增长，或增长极慢。线性评分的 VC 维为 \(d+1\)，此时界中隐含 \(d\)；作者未明确讨论此点。

证明路线与技术技巧：

  • 整体路线（5 步）：
  • 样本分拆：将 \((X, Z)\) 分为训练集 \((R_n, S_m)\) 与检验集，训练集学 \(\hat{s}\)，检验集算秩 \(U_{N, \hat{s}}\)。
  • 学习偏差控制：通过 Clémençon et al. (2006) 的排序经验最小化收敛率，证明 \(\hat{R}(\hat{s})\) 逼近 \(R(s^*)\)，偏差 \(O(\sqrt{V/N_{\text{train}}})\)。
  • 秩过程浓度界：调用 Clémençon et al. (2021) 的两样本线性秩过程浓度不等式，对 VC 类 \(\mathcal{S}\) 上的 \(\{U_{N, s}\}_{s \in \mathcal{S}}\) 建立 \(\sup_{s \in \mathcal{S}} |U_{N, s} - R(s)|\) 的界。
  • 解耦学习与检验：将 \(|U_{N, \hat{s}} - \frac{1}{2}|\) 分解为 \(|U_{N, s^*} - \frac{1}{2}| + |U_{N, \hat{s}} - U_{N, s^*}|\)，前者由秩过程浓度控制（随机波动），后者由学习偏差控制（\(\hat{s}\) 替代 \(s^*\)）。

  • 组合界：将学习偏差界与秩过程浓度界相加，得到 \(U_{N, \hat{s}}\) 的总浓度界，进而构造拒绝域与功效保证。

  • 关键跳跃点：

  • 引理：两样本秩过程关于 VC 类的均匀浓度界（Clémençon et al. 2021 的核心结果）。难点在于秩统计量 \(U_{N, s}\) 对 \(s\) 的依赖是非线性的（通过 \(\mathbb{I}(s(x) < s(z))\)），需将 \(\{U_{N, s}\}_{s \in \mathcal{S}}\) 视为随机过程，并建立其关于指标类 \(\mathcal{S}\) 的均匀收敛。作者通过将秩过程重写为 \(U\)-统计量过程，并调用 Hoeffding 分解与经验过程理论（VC 类的覆盖数界）绕过非线性依赖。

  • 解耦步骤：将 \(\hat{s}\) 视为随机指标，需控制“双重随机性”（数据驱动指标 + 秩过程随机性）。作者通过样本分拆使 \(\hat{s}\) 仅依赖训练集，与检验集独立，从而将 \(\hat{s}\) 视为固定指标应用秩过程浓度界，再通过训练集上的学习偏差界覆盖 \(\hat{s}\) 的随机性。

  • 技术技巧点名：

  • U-统计量 Hoeffding 分解：用于将秩过程 \(U_{N, s} - R(s)\) 分解为线性项与退化项，线性项由经验过程理论控制，退化项由 Bernstein 型界控制。
  • VC 类覆盖数界：用于建立秩过程关于评分函数类的均匀收敛，覆盖数的对数 \(\log N(\epsilon, \mathcal{S})\) 控制均匀偏差。
  • 样本分拆：用于解耦学习步骤与检验步骤的随机性，是避免过拟合的标准技术。
  • 排序经验最小化收敛率（Clémençon et al. 2006）：用于控制 \(\hat{s}\) 的学习偏差，依赖 U-过程的浓度不等式与快速收敛条件。

真实例子与应用：

  • 模拟实验：
  • 数据/场景：高维正态分布两样本检验，\(P = \mathcal{N}(0, I_d)\)，\(Q = \mathcal{N}(\mu, I_d)\)，\(\mu\) 为稀疏偏移向量（仅少数坐标非零）；维度 \(d\) 从 10 到 1000，样本量 \(n=m=100\) 至 500。
  • 方法应用：训练集学线性评分函数 \(\hat{s}(x) = \hat{w}^T x\)（通过排序经验最小化或 SVM 变体），检验集对 \(\hat{s}(X)\) 与 \(\hat{s}(Z)\) 执行 Wilcoxon 秩和检验。
  • 结果：在 \(d\) 增长时，本文方法功效下降缓慢，MMD 与 distance correlation 功效急剧下降；在稀疏偏移 \(\mu\) 下，线性评分能有效捕捉信号。

  • 想说明什么：验证投影法在高维下优于基于距离/核的方法，展示线性评分对稀疏偏移的适应性。

  • 真实数据实验：

  • 数据/场景：人脸识别数据集（引用了 Wang et al. 2018 RFW 数据集，但实际实验可能用其他人脸/图像数据），检验不同种族/性别的人脸特征分布是否相同。
  • 方法应用：将人脸特征向量（高维）赋予种族标签，学习排序评分，检验评分分布差异。
  • 结果：本文方法检测到分布差异，MMD 在高维特征下功效不足。
  • 想说明什么：展示方法在真实高维数据上的实用性，验证排序投影对分布偏移的敏感性。

🔎 结论是否比证明窄： - 维度无关性声称：摘要与引言中声称“not much affected by the dimensionality”，但证明中的界依赖 VC 维 \(V\)；若评分函数类为线性函数（\(V = d+1\)），则界中隐含 \(d\)，此时声称仅在 \(V\) 不随 \(d\) 增长的评分类（如固定维树形评分）下严格成立。作者未在主定理中明确此条件，仅在实验中用线性评分（\(V\) 随 \(d\) 增长）验证，存在声称宽于证明的风险。 - 排序模型偏差可控假设：定理在 \(\epsilon_{\mathcal{S}}\) 可控下证明，但摘要泛泛声称方法“capable of detecting small departures”，未明确 \(\epsilon_{\mathcal{S}}\) 可控是必要条件。若 \(\mathcal{S}\) 不包含 \(s^*\) 的良好逼近，则投影损失排序信息，检验可能失效。

四、开放问题（点到为止，扎根具体语句）

  1. VC 维随 \(d\) 增长时的精确检验速率：本文界依赖 VC 维 \(V\)，线性评分下 \(V = d+1\)；要证在 \(V \asymp d\) 时，两步法的检验速率是否仍优于 MMD 的多项式衰减（Ramdas et al. 2014），需建立 \(d\) 与 \(N\) 的显式权衡。扎根点：摘要“not much affected by the dimensionality”与定理中 VC 维依赖的张力。

  2. 排序模型偏差 \(\epsilon_{\mathcal{S}}\) 的 minimax 估计速率：\(\epsilon_{\mathcal{S}}\) 是检验功效的关键瓶颈，但本文将其视为已知可控参数；要估 \(\epsilon_{\mathcal{S}}\) 在一般分布下的 minimax 速率，并据此自适应选择评分类 \(\mathcal{S}\)。扎根点：假设 1（排序模型偏差可控）未提供 \(\epsilon_{\mathcal{S}}\) 的估计或自适应机制。

  3. 与测度运输多维秩检验的功效对比：Deb & Sen (2019) 与 Hallin et al. (2021) 的测度运输秩检验是严格分布无关的竞争路线；要在相同替代假设下对比两步法与测度运输秩的功效与计算代价。扎根点：引言提及深度与测度运输但未对比，仅与 MMD 对比。

  4. 半参数效率界在投影秩检验中的可达性：一维秩检验在局部替代下可达渐近效率界；要证本文两步法在排序偏差 \(\epsilon_{\mathcal{S}} \to 0\) 时是否可达两样本检验的半参数效率界。扎根点：引言声称“preserves the advantages of univariate rank tests”，但未讨论效率界可达性。

（要确认某条是否真 gap，建议读 Deb & Sen 2019、Hallin et al. 2021、Ramdas et al. 2014 的 intro——若都指向 VC 维依赖与排序偏差的开放性，则为共识；若互相打架则为机会。）

Maintained by 陈星宇 · Homepage · Source on GitHub

评论