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)¶
- 奠基工作:核嵌入与MMD(2006–2012)
- Gretton et al. (2006, 2007, 2012a) 提出最大均值差异(MMD)及其核版本,将分布嵌入到一个可再生核 Hilbert 空间(RKHS),用 \(\|\mu_P - \mu_Q\|_{\mathcal{H}_k}\) 作为检验统计量。核函数为特征性(characteristic)时,MMD 是度量的(Sriperumbudur et al., 2010),但该框架对高维的适用性未初探。
-
Harchaoui, Bach & Moulines (2007) 提出基于核 Fisher 判别分析的检验,与 MMD 互补。
-
高维渐近与分析(2015–2021)
- Ramdas et al. (2015) 系统分析了高斯核 MMD(gMMD)和能量距离在高维均值差异备择下的 power,发现 gMMD 的 power 严重依赖带宽选择,且对高维“弱信号”场景可能不如专门针对均值差异的 Hotelling \(T^2\) 类检验;首次明确提出了高维下的适应性(adaptivity) 与计算-统计折中问题。
- Li & Yuan (2019) 证明了高斯核检验对光滑备择是 minimax 最优的,但要求带宽随维数发散,且结论主要针对固定维数 \(p\) 或 \(p\) 增长但备择函数具有高光滑性;这为高斯核的通用性提供了理论佐证,但未覆盖实际中更常见的“非光滑”偏离。
- Chakraborty & Zhang (2021) 构造了一类新的距离度量(新距离,ND),解决了在 HDLSS 下能量距离只能检测均值与协方差迹的缺陷,并确保新度量对低维边际分布完全刻画;但计算复杂度仍为 \(O(N^2 p)\),且对非欧氏空间不适用。
-
Gao & Shao (2021) 提出了学生化 MMD(studentized sample MMD),得到了当 \((p, n, m) \to \infty\) 时的中心极限定理,显式刻画了收敛速率,并指出此速率可随维数增加而提高;但其检验统计量本质上仍是单一核的 MMD,对特定偏离模式(如方差差异但均值相近)的 power 仍有局限。
-
近期其他非参数方法(与本文并列的竞争路线):
- 图基检验(Friedman & Rafsky, 1979; Chen & Friedman, 2017):利用最小生成树或相似图构造检验,适用于非欧氏数据,但对位置与尺度偏移的 power 不均衡。
- 球散度(Pan et al., 2018):基于球面距离的度量,无需矩假设,但仅对低维有效。
- 分类器两样本检验(Lopez-Paz & Oquab, 2016):利用分类器学习判别边界,但 null 分布需靠重抽样,且 classifier 的选择引入额外灵活性。
子线索聚类¶
- A. 核/距离度量类(MMD、能量距离、新距离、学生化MMD):主要依赖RKHS或欧氏距离,理论成熟,但高维下 power 对偏离模式敏感。
- B. 图/图论类:利用观测间的相似图,非参数且可处理非欧氏数据,但构造图本身引入复杂依赖。
- C. 分类器类:灵活,但缺乏清晰的理论 power 分析。
本文属于 A 类,但特针对中高维下“均值+方差-协方差联合偏离”这一常见模式,修改核统计量以提升对更广泛备择的适应性。
这个方向在追问的核心问题¶
- 高维下检验 power 的最优性:如何构造一个在均值差异、协方差差异、高阶矩差异等多种偏离模式下都保持高 power 的检验?现有方法往往只对一类偏离最优。
- 适应性(adaptivity):能否自动检测未知的偏离类型并选择最佳核/带宽?
- 计算可扩展性:非参数两样本检验通常涉及 \(O(N^2)\) 的核/距离计算,如何对大规模数据集(\(N \sim 10^5\))有效?
- 分布自由(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的高斯分布,但方差不同:
-
然而,当维数变高且使用高斯核时,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\) 的组合能捕捉均值向量的范数差和协方差矩阵的特征值偏差。
这样,读者已抓住核心:本文不是提出新的核,而是利用核自差与核交叉差的不同组合来覆盖均值+方差两种偏离模式。
三、这篇论文做了什么¶
三句话¶
- 研究问题:对中高维数据的两样本检验,推广经典 MMD 使其同时检测均值差异与方差-协方差结构差异,克服 MMD 在协方差偏离时 power 低的缺陷。
- 核心方法:提出广义核两样本检验(GK),将统计量分解为核自差(\(D\))和核交叉差(\(C\))两个分量(均基于核函数),并构造一个联合统计量;另提出低计算成本的替代程序(基于部分求和)。
- 主要结论:理论分析(主要侧重于渐近 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-统计量的区分——决定收敛类型。
- 平方和型统计量的卡方极限——通过方差估计的相合性和投影部分的渐近独立性。
真实例子与应用¶
本文有两个真实数据应用:
- 分子形状比较(Musk vs Non-musk)
- 数据:UCI 的 “Musk” 数据集。每个分子用 168 维特征描述(形状、电荷等),推断它是否是类麝香分子(musk)与否。
- 做法:将 musk 样本(约 476 个)作为 \(P\),non-musk(约 300 个)作为 \(Q\),应用 GK 检验(和对比方法)比较两分布。
- 结果:GK 的 p-value 显著小于 0.05(比其他方法更小)且稳定;power 比较通过交叉验证显示 GK 的拒绝率远高于 MMD 和 studentized MMD。
-
想说明:当分布之间可能有多种矩差异时(均值可能相近但协方差不同),GK 能检测出差异。
-
JFK 出租车行程比较
- 数据:纽约市出租车数据集,2019 年 1 月和 2 月从 JFK 出发的行程。每个行程由起点和终点经纬度构成(2 维位置向量),比较两个月的分布。
- 做法:提取样本(每月约 1000 个),用 GK 检验。
- 结果:GK 检验发现两个月的分布有显著差异,而传统 MMD 在相同显著性水平下未能拒绝。
- 想说明:即使维数低(2 维),GK 仍能检测到某些 MMD 遗漏的差异(本例中可能是行程目的地的分散程度即方差变化)。
🔎 结论是否比证明窄¶
是,存在两处: 1. Theorem 1 的渐近正态性在证明中要求核函数有界(如高斯核在紧支撑上),但文中声称适用于任意无界特征核(例如多项式核),这是不严谨的——无界核的渐近性质未在证明中覆盖。 2. power 一致性(Theorem 2)只证明了检验是相合的,没有 power 收敛的速度。文中却常说“substantial power improvements”,这个说法来自模拟,而非理论保证。对于高维下的 minimax 最优性(如 Li & Yuan 2019 达到的),本文完全没有涉及。
四、开放问题(点到为止,扎根具体语句)¶
-
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 那样)? -
高维下方差估计的理论性质
本文使用 jackknife 估计标准差,但未给出在高维环境(\(p \gg N\))下该估计的相合性条件。Gao & Shao (2021) 给出了学生化 MMD 的 CLT 所需的条件,本文是否可以在类似框架下给出 GK 方差估计的渐近一致性?扎根:Section 3.2 的方差估计仅给出了直觉,无定理。 -
非高斯核或无限带宽的行为
本文所有实验使用高斯核,但理论对一般特征核成立。问题是:能否针对更窄的核(如 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”。 -
计算-统计折中
本文提出了低计算成本的 fastGK(使用子采样),但未分析其 power 损失与计算量的 trade-off。研究者可基于自己的高维 U-统计量计算复杂度视角(treewidth/einsum),刻画 fastGK 的近似误差率与计算图成本的关系。扎根:Section 4 的 fastGK 是用部分求和逼近,可看作 \(O(N^{1.5})\) 的近似,但 power 损失是否达到统计最优?需要更系统分析。
Maintained by 陈星宇 · Homepage · Source on GitHub