不完全 U 统计量 | Codeboy's Blog

形式陈述

有 $n\ge m$ 个IID观测，对称 $m$ 元核 $h\in L^2(P^m)$ ，总体目标为 $\theta=Eh$ 。记所有大小 $m$ 的无序索引子集为 $\mathcal I$ ， $K=\binom nm$ ，完整统计量为

U=\frac1K\sum_{I\in\mathcal I}h(X_I).

核求值昂贵时，从 $\mathcal I$ 中独立、均匀、有放回地抽取 $I_1,\ldots,I_B$ ，抽索引的随机源独立于原始资料 $D=(X_1,\ldots,X_n)$ 。定义

\widetilde U_B=\frac1B\sum_{b=1}^B h(X_{I_b}),\qquad \tau_D^2=\frac1K\sum_{I\in\mathcal I}(h(X_I)-U)^2.

每个子集内部索引互异，只有不同子集抽取之间允许重复；允许子集内部重复会把目标换成含对角项的V型规则。条件于资料，核值组成固定有限总体，所以

E(\widetilde U_B\mid D)=U,\qquad \operatorname{Var}(\widetilde U_B\mid D)=\frac{\tau_D^2}{B}.

因此 $E\widetilde U_B=\theta$ 。这里有两种无偏性：对固定资料的完整核平均无偏，以及对重新抽取资料时的总体核期望无偏。二者的误差条不能混用。

总方差的两张账

令 $v=\operatorname{Var}(U)$ 、 $\sigma_h^2=\operatorname{Var}(h(X_1,\ldots,X_m))$ 。由于每个子集的核具有相同总体分布，

E\tau_D^2=E\left[\frac1K\sum_Ih(X_I)^2-U^2\right]=\sigma_h^2-v.

由全方差，

\operatorname{Var}(\widetilde U_B) =v+\frac{\sigma_h^2-v}{B} =\left(1-\frac1B\right)v+\frac{\sigma_h^2}{B}.

第一项 $v$ 是同一份资料所能达到的完整U统计误差；第二项是省核调用所付的额外计算方差。把 $B$ 加大只减少第二项，不能生成新的独立原始观测。另一方面，把随机核行当总体IID只算 $\sigma_h^2/B$ ，会少算共享资料带来的 $(1-1/B)v$ ； $B=1$ 时两式恰好相同，因为这时确实只返回一个核值。

不放回抽子集的精确修正

若从 $K>1$ 个子集中均匀不放回抽取 $1\le B\le K$ 个，令 $H_I=h(X_I)$ 。其入样指示满足 $E\xi_I=B/K$ ，异对子集的 $E\xi_I\xi_J=B(B-1)/(K(K-1))$ 。把 $B^{-1}\sum_I\xi_IH_I$ 展开平方，可得

\operatorname{Var}(\widetilde U_B\mid D) =\frac{K-B}{B(K-1)}\tau_D^2,

\operatorname{Var}(\widetilde U_B) =v+\frac{K-B}{B(K-1)}(\sigma_h^2-v).

这正是有限总体抽样设计作用于固定核值总体的修正。 $B=K$ 时每个子集都访问一次，计算误差为零；有放回抽 $B=K$ 次通常仍重复一些、漏掉一些，计算误差并不为零。若 $K=1$ ，只有一个核值，条件计算误差恒零，应直接计算，不能使用含 $K-1$ 的式子。

直觉

原始资料随机地产生一张巨大的核值表；随后算法随机选表中的一些行。第一层改变整张表，第二层只在固定表里抽行。条件于表后，抽取可IID；对原始资料不条件化时，所有被选核值仍共用同一份资料。

与“先丢掉大半原始观测，再计算剩余观测的全部子集”不同，不完全U可以让所有原始观测都有机会进入计算。两者即使使用同样数量的核调用，数据覆盖和协方差也不相同。是否有更便宜的代数恒等式，还应在抽样之前检查。

例子与边界

三个观测的完整条件枚举

固定资料 $(0,1,3)$ ，取二阶核 $h(x,y)=(x-y)^2/2$ 。三个核值为 $(1/2,9/2,2)$ ，完整平均 $U=7/3$ ，以分母3计算的核表方差为

\tau_D^2=\frac13\left[\left(-\frac{11}6\right)^2+ \left(\frac{13}6\right)^2+\left(-\frac13\right)^2\right]=\frac{49}{18}.

只算 $B=2$ 个子集。有放回时9个等概率有序抽取，平均的条件方差为 $49/36$ ；不放回时3种等概率无序选择，方差为 $49/72$ ，恰好减半。比如选到第一、第三核值，返回 $5/4$ ，偏离完整平均 $7/3$ ；该次偏离不否定抽索引的条件无偏性。

如果有放回抽3次，条件方差仍为 $49/54$ ；不放回抽全3个则精确得到 $7/3$ 。这项计算没有估计总体方差参数的抽样风险，因为本题资料始终固定。

相同线性核预算，退化核损失完全不同

令 $X_i$ 为Rademacher， $n=100$ 。先用 $h(x,y)=(x+y)/2$ ，完整U就是样本均值， $v=1/100$ ，单核方差 $\sigma_h^2=1/2$ 。有放回抽 $B=100$ 对时，总方差为

\frac{99}{100}\frac1{100}+\frac1{200}=\frac{149}{10000}.

它保持 $n^{-1}$ 方差阶，但相对完整U增加49%。提高到 $B=1000$ ，总方差为 $1049/100000$ ；“相同收敛阶”不等于“相同方差常数”。此核本可线性时间精确计算，抽对只是校验公式，不是推荐实现。

改用完全退化核 $h(x,y)=xy$ 。由二阶投影旧页， $v=1/\binom{100}2=1/4950$ ， $\sigma_h^2=1$ 。仍取 $B=100$ ，总方差变为

\frac{99}{100}\frac1{4950}+\frac1{100}=\frac{51}{5000}=0.0102.

完整核方差约0.000202，而抽对误差把它拉回 $n^{-1}$ 量级，损失约50.49倍。非退化学习问题中的线性核预算经验，不能直接套给零假设下的退化检验。

高阶退化怎样决定预算门槛

对固定阶、固定非恒定核，Hoeffding分解若首个非零投影秩为 $r$ ，则 $v\asymp n^{-r}$ ，而 $\sigma_h^2-v\to\sigma_h^2>0$ 。有放回额外误差为 $\Theta(B^{-1})$ ，因此：

$B=\Theta(n^r)$ 可以保留方差阶，通常改变常数与极限分布
要使计算扰动相对于原 $n^{-r/2}$ 尺度在 $L^2$ 中可忽略，需要 $B/n^r\to\infty$
$B=o(n^r)$ 时，计算抽样误差占主导

对三阶Rademacher乘积核 $xyz$ ， $r=m=3$ ， $n=6$ 时 $K=20$ 、完整方差 $1/20$ 。有放回抽 $B=6$ ，总方差为 $5/24$ ；不放回抽6个的方差为 $1/6$ 。纯canonical $m$ 阶核满足 $v=\sigma_h^2/K$ ，不放回公式正好化为 $\sigma_h^2/B$ ，只有接近全算才能保留接近完整核的常数。

完全退化情况下，有放回要求 $B\gg n^m$ 才能忽略计算误差，已超过完整枚举的核数量；这提示应改用无重复枚举、代数化简或重新设计估计器，而不是机械追求“随机抽更多”。

推论与应用

可执行协议与MCSE的解释

有放回时，每轮独立均匀抽取一个大小 $m$ 的无序索引集合，计算核并在线更新均值、平方差。可先抽 $m$ 个互异索引并排序，或用经验证的组合编号采样器；必须保证每个子集等概率。一般核调用为 $B$ 次，索引采样与核内部费用另外计。保留原始数据需相应存储，在线核累加器本身只需常数个标量。

固定资料后，抽索引是一次普通Monte Carlo。 $B\ge2$ 时被抽核值的样本方差 $s_B^2/B$ 无偏估计条件计算方差 $\tau_D^2/B$ 。它不是总体目标 $\theta$ 的总方差估计。不放回时应使用 $(1-B/K)s_B^2/B$ ，其中 $s_B^2$ 是分母 $B-1$ 的样本方差； $B=1$ 时无法从一行估计核表方差。

在同一份资料上重复很多抽子集运行，只能验证计算层的MCSE；要检验总体覆盖，必须重抽原始资料，或建立恰当投影、重采样与校准理论。若实际目的是MMD检验，改变核抽样设计还会改变零分布，不能直接套完整MMD的阈值。

必须重新分析的变体

非均匀选子集且仍直接平均，会把条件中心从 $U$ 改成加权核平均。若用已知正包含概率修正，可构造其他无偏估计，但方差还涉及联合包含概率；本页均匀公式不再适用。按观察到的核值决定下次是否接受、偏爱大核值而不纠权、使用固定确定性稀疏图而称之为均匀随机抽样，都不满足当前协议。

自测：固定资料后同一索引对子被抽到两次，两个核值可能完全相同，这是否违背条件IID？不违背，有放回独立抽取有限总体允许相同结果；独立性描述随机抽取协议，不要求结果彼此不同。但若强制第二次重复第一次索引，才会破坏独立性。

参考资料

Stephan Clémençon, Aurélien Bellet, Igor Colin，Scaling-up Empirical Risk Minimization: Optimization of Incomplete U-statistics，JMLR 17(76)，2016，1–36，§3.1 Definition 5与式(21)方差分解、§3.4其他抽样设计。本文限定固定单核，不把论文的函数类学习界直接当作本页点态方差结论。
William G. Cochran，Sampling Techniques，3rd ed.，1977，Chapter 2，简单随机不放回抽样；本页以入样指示重新推导有限总体修正。
固定阶Hoeffding分解提供退化秩和完整统计量的方差阶，计算抽样误差由本页单独加入。

形式陈述 ​

总方差的两张账 ​

不放回抽子集的精确修正 ​

三个观测的完整条件枚举 ​

相同线性核预算，退化核损失完全不同 ​

高阶退化怎样决定预算门槛 ​

可执行协议与MCSE的解释 ​

必须重新分析的变体 ​

反向链接