对称化与 Ghost Sample

形式陈述 ​

总体期望理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。 $Pf$ 看不见，样本均值 $P_{m}f$ 看得见。对称化引入一份只存在于证明中的独立IID ghost sample理路独立同分布样本IID sample · Independent and identically distributed sample以乘积分布描述来自同一总体的独立重复观测。 $S^{\prime }$，用它的经验均值代替总体期望；随后随机交换每对 $(Z_i,Z_i^{\prime })$，把两样本差变成 Rademacher 符号和。未知分布没有消失，但它被推到对样本的外层期望中。

以下函数类 $\mathcal{F}$ 非空、抽样前固定，函数可测并具有可积包络，相关上确界也假定可测；有界可数类是一个直接满足这些条件的情形。

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$，对每个 $f$ 用同一个随机上确界作上界，再取期望，

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

随机符号步骤 ​

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

再用 $\underset{f}{sup}(A_f+B_f)\le \underset{f}{sup}{A}_f+\underset{f}{sup}{B}_f$ 和两份样本同分布，可把右侧控制为两个相同的 Rademacher 过程，产生常见的因子 $2$。采用 ${\mathfrak{R}}_m(\mathcal{F})={\mathbb{E}}_{S,\sigma }\underset{f}{sup}{m}^{-1}\sum _i{\sigma }_{i}f(Z_i)$ 的约定时，所得单边界就是 $2{\mathfrak{R}}_m(\mathcal{F})$。若要控制绝对偏差，应把类扩大为 $\mathcal{F}\cup (-\mathcal{F})$，再应用同一论证；不能在公式中悄悄插入绝对值而仍假装复杂度定义未变。

有界类的概率版本 ​

这一概率版本另假定有固定的可数决定子类：下述各上确界在该子类上取值不变。若还满足 $0\le f\le 1$，则当 $m{\epsilon }^2\ge 2$ 时，

在左侧坏事件上，可测地选取一个偏差严格大于 $\epsilon$ 的见证 $f$；可数类可取枚举中第一个见证，可分版本用同一可数子类处理。固定原样本后，这个 $f$ 对独立 $S^{\prime }$ 是固定函数。其 ghost 均值方差至多 $1/(4m)$，Chebyshev 不等式理路Chebyshev 不等式Chebyshev's inequality随机变量偏离均值至少给定距离的概率由方差除以距离平方控制。给出

在此事件上，三角不等式保证 $|P_m^{\prime }f-P_{m}f|>\epsilon /2$；对原样本积分即得因子 $2$。概率版本多用了有界性与数值条件，不能仅由前面的期望不等式直接宣称成立。