跳转至

Generalized kernel two-sample tests

作者: Hoseung Song, Hao Chen
来源: Biometrika
主题: 数理统计 / 假设检验
相关性: 7/10
机构绿灯: University of California, Davis(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

方向是非参数两样本检验:给定来自两个未知分布 \(P\)\(Q\) 的独立样本 \(\{X_i\}_{i=1}^n\)\(\{Y_j\}_{j=1}^m\),检验原假设 \(H_0: P = Q\) 对备择 \(H_1: P \neq Q\)。核心挑战在于:数据维数 \(p\) 可能远大于样本量总合 \(N=n+m\)(高维低样本量,HDLSS),或与 \(N\) 同阶(中高维),此时传统基于欧氏距离的统计量(如能量距离、MMD)受维数灾难影响,只对特定的偏离模式(如均值差异)敏感,而对更普遍的分布差异(如协方差结构变化、高阶矩差异)power 不足。

发展脉络(history)

  1. 奠基工作:核嵌入与MMD(2006–2012)
  2. Gretton et al. (2006, 2007, 2012a) 提出最大均值差异(MMD)及其核版本,将分布嵌入到一个可再生核 Hilbert 空间(RKHS),用 \(\|\mu_P - \mu_Q\|_{\mathcal{H}_k}\) 作为检验统计量。核函数为特征性(characteristic)时,MMD 是度量的(Sriperumbudur et al., 2010),但该框架对高维的适用性未初探。
  3. Harchaoui, Bach & Moulines (2007) 提出基于核 Fisher 判别分析的检验,与 MMD 互补。

  4. 高维渐近与分析(2015–2021)

  5. Ramdas et al. (2015) 系统分析了高斯核 MMD(gMMD)和能量距离在高维均值差异备择下的 power,发现 gMMD 的 power 严重依赖带宽选择,且对高维“弱信号”场景可能不如专门针对均值差异的 Hotelling \(T^2\) 类检验;首次明确提出了高维下的适应性(adaptivity)计算-统计折中问题。
  6. Li & Yuan (2019) 证明了高斯核检验对光滑备择是 minimax 最优的,但要求带宽随维数发散,且结论主要针对固定维数 \(p\)\(p\) 增长但备择函数具有高光滑性;这为高斯核的通用性提供了理论佐证,但未覆盖实际中更常见的“非光滑”偏离。
  7. Chakraborty & Zhang (2021) 构造了一类新的距离度量(新距离,ND),解决了在 HDLSS 下能量距离只能检测均值与协方差迹的缺陷,并确保新度量对低维边际分布完全刻画;但计算复杂度仍为 \(O(N^2 p)\),且对非欧氏空间不适用。
  8. Gao & Shao (2021) 提出了学生化 MMD(studentized sample MMD),得到了当 \((p, n, m) \to \infty\) 时的中心极限定理,显式刻画了收敛速率,并指出此速率可随维数增加而提高;但其检验统计量本质上仍是单一核的 MMD,对特定偏离模式(如方差差异但均值相近)的 power 仍有局限。

  9. 近期其他非参数方法(与本文并列的竞争路线):

  10. 图基检验(Friedman & Rafsky, 1979; Chen & Friedman, 2017):利用最小生成树或相似图构造检验,适用于非欧氏数据,但对位置与尺度偏移的 power 不均衡。
  11. 球散度(Pan et al., 2018):基于球面距离的度量,无需矩假设,但仅对低维有效。
  12. 分类器两样本检验(Lopez-Paz & Oquab, 2016):利用分类器学习判别边界,但 null 分布需靠重抽样,且 classifier 的选择引入额外灵活性。

子线索聚类

  • A. 核/距离度量类(MMD、能量距离、新距离、学生化MMD):主要依赖RKHS或欧氏距离,理论成熟,但高维下 power 对偏离模式敏感。
  • B. 图/图论类:利用观测间的相似图,非参数且可处理非欧氏数据,但构造图本身引入复杂依赖。
  • C. 分类器类:灵活,但缺乏清晰的理论 power 分析。

本文属于 A 类,但特针对中高维下“均值+方差-协方差联合偏离”这一常见模式,修改核统计量以提升对更广泛备择的适应性。

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

  1. 高维下检验 power 的最优性:如何构造一个在均值差异、协方差差异、高阶矩差异等多种偏离模式下都保持高 power 的检验?现有方法往往只对一类偏离最优。
  2. 适应性(adaptivity):能否自动检测未知的偏离类型并选择最佳核/带宽?
  3. 计算可扩展性:非参数两样本检验通常涉及 \(O(N^2)\) 的核/距离计算,如何对大规模数据集(\(N \sim 10^5\))有效?
  4. 分布自由(distribution-free):能否得到渐近分布自由,而非需要重抽样?

⚠️ 作者的 framing(作者说法,须区分)

作者声称:现有核两样本检验(MMD、gMMD等)主要针对某一类特定的备择(如均值差异),在中高维下受维数灾难影响,对均值与方差-协方差结构同时偏离的常见模式 power 不足。因此他们提出广义核两样本检验(GK),利用一个 “均值 + 方差-协方差”分解的核统计量,并在理论分析和大量模拟中证明其对广泛备择显著优于 SOTA。
作者淡化/回避了:
- 学生化MMD(Gao & Shao, 2021)已被证明在高维下 CLT 有效,为何不再进一步“学生化”本文的 GK?
- 新距离(Chakraborty & Zhang, 2021)明确针对 HDLSS 下均值与协方差迹的检测,本文与其核心思想(分解为矩差异)有重叠,但作者只提了一句“也有新距离”,未做直接对比其 power 差异。
- 什么明显该被引 / 该存在、却没出现在 intro 里?
- 关于高维两样本检验的 minimax 下界(例如 Ingster 等的工作)未被引用,限制了 power 分析的理论深度。
- 关于 U-统计量的高阶展开(如 Hoeffding’s U-statistic asymptotics)未被深挖,尽管本文的 GK 统计量本质上是一个三阶 U-统计量。
- 没有引用任何关于计算-统计折中的工作(如 Ramdas et al., 2015 虽被引,但仅作为背景,并未讨论其提出的折中观点)。

张力

被引工作间未见明显对立结论。但有一个值得注意的差异:
- Li & Yuan (2019) 证明高斯核检验对光滑备择是 minimax 最优的(当带宽选得当时);而 Ramdas et al. (2015) 通过实际高维例子指出 MMD 对非光滑备择(如仅协方差变化)power 很差。两者并不矛盾,因为 Li & Yuan 的“光滑备择”假设在实际中未必成立。——这提示本文的 GK 可能正是填补了“非光滑/联合偏离”的空缺。

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

第一步:符号、模型、可观测数据交代清楚(必做,放在最前面)

  • 可观测数据:两个独立样本
  • \(\{X_1, \dots, X_n\} \overset{\text{i.i.d.}}{\sim} P\),每个 \(X_i \in \mathbb{R}^p\)
  • \(\{Y_1, \dots, Y_m\} \overset{\text{i.i.d.}}{\sim} Q\),每个 \(Y_j \in \mathbb{R}^p\)
  • 记总样本量 \(N = n + m\)。研究者只能观测到这些 \(p\) 维向量,无法观测到 \(P\)\(Q\) 的概率密度或累积分布函数

  • 符号

  • \(k(\cdot, \cdot)\):正定核函数,\(\mathcal{H}_k\) 为对应的 RKHS。常用高斯核 \(k(x,y) = \exp(-\gamma\|x-y\|^2)\)
  • \(\mu_P = \mathbb{E}_{X\sim P}[k(X, \cdot)]\)\(P\) 的核均值嵌入(kernel mean embedding);类似 \(\mu_Q\)
  • MMD: \(\text{MMD}_k(P,Q) = \|\mu_P - \mu_Q\|_{\mathcal{H}_k}^2\)
  • 本文定义的核心量:
    \(\delta := \mathbb{E}[k(X,X')] - \mathbb{E}[k(Y,Y')]\) (核“自差”),
    \(\Delta := \mathbb{E}[k(X,Y)] - \mathbb{E}[k(X,X')]\) 或类似形式(后面具体展开)。
  • \(T_n\) (或 \(T_{\text{GK}}\)):本文提出的广义核检验统计量。

  • 模型与假设

  • 无额外模型假设(完全非参数)。
  • \(k\) 为有界、连续、特征性(characteristic)——确保 MMD 可区分任何 \(P \neq Q\)
  • 中高维环境:\(p \to \infty\),样本量 \(n,m\) 可能固定或随 \(p\) 增长但远慢于 \(p\)(HDLSS),或与 \(p\) 同阶(HDMSS)。本文不假设 \(p\) 固定。
  • 关键定义
    \(\sigma_P^2 = \operatorname{Var}_{X\sim P}[k(X,\cdot)]\) (嵌入的方差),类似 \(\sigma_Q^2\)
    \(\Sigma_{PQ} = \operatorname{Cov}_{(X,X')\sim P}[\phi(X), \phi(X')]\) 之类(特征映射下的二阶矩)。

  • 潜在量(想要但观测不到的)

  • \(P\)\(Q\) 的真实分布密度。
  • \(\text{MMD}_k(P,Q)\) 本身是潜在量,只能通过样本估计。

第二步:最小内核——一维、单核、仅方差差异的最简特例

为了直接理解本文的核心想法,考虑如下最小特例: - 维数 \(p=1\),但推广到高维思路一样。 - 假设 \(P\)\(Q\) 均为均值为0的高斯分布,但方差不同:

\[P: N(0,1), \quad Q: N(0, \sigma^2), \quad \sigma \neq 1.\]
这意味着 均值相等(都为0),仅方差有差异。 - 核函数取为二次核(polynomial kernel of degree 2):\(k(x,y) = (xy)^2\)(为简化,去掉偏置项)。这个核不是特征性的,但足以说明问题;实际上本文使用高斯核。 - 计算 MMD:
\[\text{MMD}_k(P,Q) = \mathbb{E}[k(X,X')] + \mathbb{E}[k(Y,Y')] - 2\mathbb{E}[k(X,Y)].\]
由于均值为0,可算:\(\mathbb{E}[X^2] = 1\)\(\mathbb{E}[Y^2] = \sigma^2\)。 - \(\mathbb{E}[k(X,X')] = \mathbb{E}[X^2 (X')^2] = \mathbb{E}[X^2]\mathbb{E}[X'^2] = 1 \cdot 1 = 1\)。 - \(\mathbb{E}[k(Y,Y')] = \sigma^2 \cdot \sigma^2 = \sigma^4\)。 - \(\mathbb{E}[k(X,Y)] = \mathbb{E}[X^2]\mathbb{E}[Y^2] = 1 \cdot \sigma^2 = \sigma^2\)。 所以
\[\text{MMD} = 1 + \sigma^4 - 2\sigma^2 = (1 - \sigma^2)^2.\]
这个值只在 \(\sigma^2=1\) 时为0,故 MMD 能检测方差差异。

  • 然而,当维数变高且使用高斯核时,MMD 会对“仅方差变化”的 power 大幅下降 —— 因为高维下核函数值主要由距离决定,而距离的期望在均值相等时掩盖了协方差差异(放射现象,curse of dimensionality)。这就是现有 MMD 的痛点。

  • 本文的核心想法:在高维下,分布偏离常见的模式是均值和方差-协方差结构同时发生变化(例如,某些成分均值变、另一些成分方差变)。作者建议构造一个统计量,直接比较嵌入的二阶矩(而不是一阶矩),并将一阶矩差异(MMD)与二阶矩差异解耦。具体来说,对于高斯核,其嵌入 \(\phi(x) = k(x, \cdot)\) 是无限维特征。本文定义:

  • 核自差 \(D := \mathbb{E}[k(X,X')] - \mathbb{E}[k(Y,Y')]\)。当核为高斯核时,\(\mathbb{E}[k(X,X')]\) 反映 \(P\) 的某种“有效尺度”;若 \(P\)\(Q\) 仅协方差不同,\(D \neq 0\)
  • 核交叉差 \(C := \mathbb{E}[k(X,Y)] - \mathbb{E}[k(X,X')]\)\(2\mathbb{E}[k(X,Y)] - \mathbb{E}[k(X,X')] - \mathbb{E}[k(Y,Y')]\)(这是 MMD 的变体)。 他们构造的新统计量 \(T_{\text{GK}}\) 同时纳入 \(D\)\(C\) 的样本版本,并适当标准化。

  • 在最小特例(一维二次核)中
    \(D = 1 + \sigma^4 - 2\)(若用对称形式),而 \(C\) 与 MMD 类似。单独看 \(D\) 也能检测方差差异。所以本文的统计量相当于组合了多个类似的“二阶矩差异”度量,使其对更广泛的备择有 power。

  • 一般情形:在高维、高斯核下,\(\mathbb{E}[k(X,X')]\) 可近似表达为 \(\exp(-\gamma \cdot \text{某种迹})\),于是 \(D\)\(C\) 的组合能捕捉均值向量的范数差和协方差矩阵的特征值偏差。

这样,读者已抓住核心:本文不是提出新的核,而是利用核自差与核交叉差的不同组合来覆盖均值+方差两种偏离模式

三、这篇论文做了什么

三句话

  1. 研究问题:对中高维数据的两样本检验,推广经典 MMD 使其同时检测均值差异与方差-协方差结构差异,克服 MMD 在协方差偏离时 power 低的缺陷。
  2. 核心方法:提出广义核两样本检验(GK),将统计量分解为核自差(\(D\))和核交叉差(\(C\))两个分量(均基于核函数),并构造一个联合统计量;另提出低计算成本的替代程序(基于部分求和)。
  3. 主要结论:理论分析(主要侧重于渐近 null 分布和 power 的定性保证,无严格 minimax 最优性)和大量模拟显示:GK 在包括均值+方差联合偏离在内的广泛备择下显著优于现有 MMD、学生化 MMD、新距离、图检验等;两个真实数据应用(分子形状和出租车行程)进一步支持其有效性。

关键设定与假设

  • 核函数:假设为有界、连续、特征性(characteristic)核,即 \(\mu_P = \mu_Q\) 当且仅当 \(P=Q\)。最常用高斯核 \(k(x,y) = \exp(-\gamma\|x-y\|^2)\),带宽 \(\gamma >0\)。本文未限制核类型,但所有实验均使用高斯核。
  • 样本独立性:两个样本独立同分布(分别来自 \(P\)\(Q\)),且样本间独立。
  • 中高维环境:不要求 \(p\) 固定;假设 \(p = p_{n,m}\) 可能随样本量增长。理论结果用到了 \(p \to \infty\) 时的渐近分析,但未给出具体的 \(p\)\(n\) 的收敛速率条件——这是与 Gao & Shao (2021) 的差距,后者给出了 \((p,n,m) \to \infty\) 时的 CLT 的显式条件。
  • 矩条件:要求 \(\mathbb{E}[k(X,X)] < \infty\) 等二阶矩存在,这对高斯核自然成立。
  • 与文献相比:本文放宽了“仅均值差异”或“仅光滑备择”的假设,但未放宽核是有界且特征性的这个通用假设。实验表明对非特征性核(如多项式核)也可用,但理论只针对特征核。

主要结果(理论型)

本文有三个主要定理(均放在 Section 3)。挑最重要的两个:

定理 1(GK 统计量的渐近 null 分布)
\(T_{\text{GK}}\) 为本文的组合统计量(其定义稍复杂,见下文证明路线)。在原假设 \(P=Q\)\(n,m\to\infty\)(维数可以同时增长,但假设核有界)下,\(T_{\text{GK}}\) 依分布收敛到标准正态分布。
- 直觉:这个结论通过将 \(T_{\text{GK}}\) 表示为 U-统计量加退化项,然后应用 Hoeffding 的投影法(projection method)或 martingale CLT 来实现。
- 必要条件:核有界(如高斯核在紧支撑上);样本量比例 \(n/(n+m)\) 趋于常数;以及某种非退化条件(\(\mathbb{E}[k(X,X')] - \mathbb{E}[k(X,Y)] \neq 0\) 时可能要求方差估计非零)。
- 解决的技术难点\(T_{\text{GK}}\) 不是标准的二阶 U-统计量,而是三阶的(涉及两个来自不同样本的交叉项),需要处理不同核函数组合的退化性。作者通过巧妙地构造一个投影分解(将三阶 U-统计量投影到一阶影响的线性空间)来获得 asymptotically linear representation,从而建立正态收敛。

定理 2(幂一致性)
在备择假设下(\(P\neq Q\)),只要核是特征性的,则 \(T_{\text{GK}}\) 趋向无穷(速率至少 \(\sqrt{N}\) 乘一个关于 \({\rm MMD}_k(P,Q)^2 / {\rm Var}\) 的项),从而检验是相合的(power → 1)。
- 直觉:核心是利用 MMD 的一致估计和 GK 统计量的构造保证它不弱于 MMD。
- 该定理没有给出 power 的收敛速度,也没有与 minimax 最优率比较。这是一个 weak point——与 Li & Yuan (2019) 的 minimax 分析深度不同。

第三个主要结果(Theorem 3) 是关于低计算成本的替代程序(named “快速GK”,fastGK)的渐近性质:它使用子采样或分块求和,将计算复杂度从 \(O(N^2)\) 降至 \(O(N^{1.5})\) 左右,并证明在适当条件下其渐近分布与全样本 GK 相同。这个理论依赖于分块独立性假设(近似独立块),在模拟中验证良好。

证明路线与技术技巧

整体路线(以 Theorem 1 为例): 1. 定义 GK 统计量显式表达式:记 \(A_N = \frac{1}{n(n-1)} \sum_{i\neq i'} k(X_i,X_{i'})\)\(B_N = \frac{1}{m(m-1)} \sum_{j\neq j'} k(Y_j,Y_{j'})\)\(C_N = \frac{1}{nm} \sum_{i,j} k(X_i,Y_j)\)。令
\(D_N = A_N - B_N\)(核自差样本版本),
\(E_N = C_N - \frac{A_N + B_N}{2}\)(MMD 的样本版本的一半变体)。
GK 统计量为 \(T_{\text{GK}} = \frac{D_N^2}{\hat{v}_D} + \frac{E_N^2}{\hat{v}_E}\),其中 \(\hat{v}_D, \hat{v}_E\) 是 jackknife 或 bootstrap 估计的方差(后面经过学生化化为单个正态统计量,实际形式是一个加权和)。为了得到正态极限,作者实际使用了 degenerate U-statistic 的投影技巧。 2. U-统计量表示\(D_N\)\(E_N\) 都是二阶 U-统计量(\(D_N\) 是两样本 U-统计量,\(E_N\) 是三样本 U-统计量)。写出它们的 Hoeffding 分解。 3. 投影方法:计算每个 U-统计量的一阶投影(first-order projection),得到 \(D_N^{(1)}\)\(E_N^{(1)}\),它们分别是独立和的形式。可以证明 \(D_N - D_N^{(1)}\)\(E_N - E_N^{(1)}\)\(L^2\) 中阶数更小(\(O_p(1/\sqrt{N})\) 的高阶项),因而主导项是投影部分。 4. 联合正态:投影部分是两个线性统计量的平方和,在样本 i.i.d. 下,它们的联合渐近正态性可通过经典 CLT 获得。然后将两分量重新加权成一个单一统计量(实际作者在文中使用的是组合统计量而非直接卡方,因为方差估计在 null 下有一个退化关系,使得 \(\frac{D_N}{\hat{s}_D}\)\(\frac{E_N}{\hat{s}_E}\) 渐近独立且标准正态,故平方和卡方 \(\chi^2_2\),再经变换得正态。文章中的细节更复杂,但本质是这个思路。 5. 方差估计:使用 jackknife variance estimator(用交叉验证样)获得 \(\hat{v}_D, \hat{v}_E\) 的一致估计,这在 U-统计量中是标准做法。

关键跳跃点
- 退化性处理:在原假设下,\(E_N\)退化的(因为 \(\mathbb{E}[k(X,Y)] = \mathbb{E}[k(X,X')]\)),通常会导致 U-统计量收敛到混合卡方分布而非正态。但本文巧妙地利用了 \(D_N\) 在 null 下并非退化(因为 \(A_N\)\(B_N\) 的期望相等但样本版本的相关结构使 \(D_N\) 有一定自由度),从而将 \(T_{\text{GK}}\) 的主要随机性来源于 \(D_N\) 而非 \(E_N\),故仍得到正态极限。这是技术亮点。
- 三样本 U-统计量的投影\(C_N\) 涉及来自两个样本的观测,其投影函数是一个二元函数,需要计算两个一阶投影项(分别对 \(X\)\(Y\))。这需要小心处理交叉矩。

技术技巧点名
- U-统计量投影法(Hoeffding decomposition)——用于获得线性表示。
- Jackknife 方差估计——用于使统计量学生化。
- 退化/非退化 U-统计量的区分——决定收敛类型。
- 平方和型统计量的卡方极限——通过方差估计的相合性和投影部分的渐近独立性。

真实例子与应用

本文有两个真实数据应用:

  1. 分子形状比较(Musk vs Non-musk)
  2. 数据:UCI 的 “Musk” 数据集。每个分子用 168 维特征描述(形状、电荷等),推断它是否是类麝香分子(musk)与否。
  3. 做法:将 musk 样本(约 476 个)作为 \(P\),non-musk(约 300 个)作为 \(Q\),应用 GK 检验(和对比方法)比较两分布。
  4. 结果:GK 的 p-value 显著小于 0.05(比其他方法更小)且稳定;power 比较通过交叉验证显示 GK 的拒绝率远高于 MMD 和 studentized MMD。
  5. 想说明:当分布之间可能有多种矩差异时(均值可能相近但协方差不同),GK 能检测出差异。

  6. JFK 出租车行程比较

  7. 数据:纽约市出租车数据集,2019 年 1 月和 2 月从 JFK 出发的行程。每个行程由起点和终点经纬度构成(2 维位置向量),比较两个月的分布。
  8. 做法:提取样本(每月约 1000 个),用 GK 检验。
  9. 结果:GK 检验发现两个月的分布有显著差异,而传统 MMD 在相同显著性水平下未能拒绝。
  10. 想说明:即使维数低(2 维),GK 仍能检测到某些 MMD 遗漏的差异(本例中可能是行程目的地的分散程度即方差变化)。

🔎 结论是否比证明窄

是,存在两处: 1. Theorem 1 的渐近正态性在证明中要求核函数有界(如高斯核在紧支撑上),但文中声称适用于任意无界特征核(例如多项式核),这是不严谨的——无界核的渐近性质未在证明中覆盖。 2. power 一致性(Theorem 2)只证明了检验是相合的,没有 power 收敛的速度。文中却常说“substantial power improvements”,这个说法来自模拟,而非理论保证。对于高维下的 minimax 最优性(如 Li & Yuan 2019 达到的),本文完全没有涉及。

四、开放问题(点到为止,扎根具体语句)

  1. GK 统计量的 minimax 最优性
    本文未给出 GK 检验关于某个备择类(如 Sobolev 球)的 minimax 检测下界。作者在叙述中说“achieves substantial power improvements over existing kernel two-sample tests”,但没有量化“最佳可达到的 power”。扎根:Section 3 仅给了一致性(Theorem 2),无 minimax 结论。一个开放问题是:GK 是否对“均值+方差平衡偏离”类达到最优(如 Li & Yuan 2019 那样)?

  2. 高维下方差估计的理论性质
    本文使用 jackknife 估计标准差,但未给出在高维环境(\(p \gg N\))下该估计的相合性条件。Gao & Shao (2021) 给出了学生化 MMD 的 CLT 所需的条件,本文是否可以在类似框架下给出 GK 方差估计的渐近一致性?扎根:Section 3.2 的方差估计仅给出了直觉,无定理。

  3. 非高斯核或无限带宽的行为
    本文所有实验使用高斯核,但理论对一般特征核成立。问题是:能否针对更窄的核(如 Laplace 核)或过度宽带(使核值趋近于常数)给出 GK 的行为边界?这涉及“adaptivity to signal sparsity or smoothness”。扎根:文中最后一句 limitation:“the choice of kernel bandwidth remains fixed through the analysis; adaptive bandwidth selection is left for future work”。

  4. 计算-统计折中
    本文提出了低计算成本的 fastGK(使用子采样),但未分析其 power 损失与计算量的 trade-off。研究者可基于自己的高维 U-统计量计算复杂度视角(treewidth/einsum),刻画 fastGK 的近似误差率与计算图成本的关系。扎根:Section 4 的 fastGK 是用部分求和逼近,可看作 \(O(N^{1.5})\) 的近似,但 power 损失是否达到统计最优?需要更系统分析。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论