对称化与 Ghost Sample

概念图像 ​

总体期望 $Pf$ 看不见，样本均值 $P_{m}f$ 看得见。对称化引入一份只存在于证明中的独立样本 $S^{\prime }$，用它的经验均值代替总体期望；随后随机交换每对 $(Z_i,Z_i^{\prime })$，把两样本差变成 Rademacher 符号和。未知分布没有消失，但它被推到对样本的外层期望中。

Ghost sample 步骤 ​

令 $S=(Z_1,\dots ,Z_m)$ 与 $S^{\prime }=(Z_1^{\prime },\dots ,Z_m^{\prime })$ 独立同分布，$P_m,P_m^{\prime }$ 为对应经验算子。对函数类 $\mathcal{F}$，由 $Pf={\mathbb{E}}_{S^{\prime }}{P}_m^{\prime }f$ 和 Jensen 不等式，

$${\mathbb{E}}_S\underset{f\in \mathcal{F}}{sup}(Pf-P_{m}f)\le {\mathbb{E}}_{S,S^{\prime }}\underset{f\in \mathcal{F}}{sup}(P_m^{\prime }f-P_{m}f).$$

这里先对 $S^{\prime }$ 取条件期望，再把 supremum 移到期望之外，因此方向是“$\le$”。$S^{\prime }$ 不是可拿来调参的测试集，也不需要算法实际生成。

随机符号步骤 ​

令 ${\sigma }_i$ 独立均匀取 $\{-1,+1\}$，并独立于两份样本。由于每对 $(Z_i,Z_i^{\prime })$ 可交换，

$${\mathbb{E}}_{S,S^{\prime }}\underset{f}{sup}\frac{1}{m}\sum _i[f(Z_i^{\prime })-f(Z_i)]={\mathbb{E}}_{S,S^{\prime },\sigma }\underset{f}{sup}\frac{1}{m}\sum _i{\sigma }_i[f(Z_i^{\prime })-f(Z_i)].$$

再用 $\underset{f}{sup}(A_f+B_f)\le \underset{f}{sup}{A}_f+\underset{f}{sup}{B}_f$ 和两份样本同分布，可把右侧控制为两个相同的 Rademacher 过程，产生常见的因子 $2$。单边、双边以及是否把绝对值纳入类的定义，会改变这个常数。

具体用途 ​

对有界损失类 $\mathcal{F}=\{z\mapsto \ell (h,z):h\in \mathcal{H}\}$，上述转换把 $\mathbb{E}\underset{h}{sup}(R(h)-{\hat{R}}_S(h))$ 化为样本上的随机符号拟合能力。这正是Rademacher 复杂度公理库Rademacher 复杂度Rademacher complexity · empirical Rademacher complexity用随机正负号衡量函数类在给定样本上拟合无结构噪声的能力。出现的来源，而不是额外假设学习器能访问总体风险。

边界与技术条件 ​

$S^{\prime }$ 必须与 $S$ 独立且来自同一分布；时间序列或自适应采样不能照搬交换论证。若函数类本身由 $S$ 选择，交换 supremum 和条件期望前要明确条件结构。对不可数类，$\underset{f}{sup}$ 可能有可测性问题；严格处理可假设可分版本、使用 outer expectation，或验证类的可测包络。Fubini 定理公理库Fubini 定理Fubini's theorem在适当可积条件下，多重积分等于任意次序的迭代积分。只负责在可积条件下交换积分，不替代这些独立性与可测性要求。

参考资料

• Michel Ledoux, Michel Talagrand, Probability in Banach Spaces, Springer, 1991.
• Peter L. Bartlett, Shahar Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, JMLR, 2002.