间隔泛化界

形式陈述 ​

带标签间隔 ​

二分类器只记录 $\mathrm{sign}f(x)$ 时，训练点位于决策边界哪一侧已经足够决定训练错误，却不足以描述扰动后的可靠性。带标签间隔

同时记录方向和距离：它为负表示误分类，接近零表示判断脆弱，较大的正值表示该点在函数尺度下远离边界。间隔泛化界用训练样本中“小于某个阈值 $\gamma$ 的比例”替代纯训练错误。

线性间隔界 ​

设输入取值于带 Borel 结构的实可分Hilbert 空间理路Hilbert 空间Hilbert space关于内积诱导范数完备的实或复内积空间。，$Y\in \{-1,+1\}$，且 $\Vert X\Vert \le R$ 几乎处处。固定有限常数 $B,R\ge 0$，考虑齐次线性打分理路线性分类器与几何间隔Linear classifier · Geometric margin用仿射超平面分类，并以缩放不变的几何间隔衡量分离余量。

取 $m\ge 1$，令 $S=((x_i,y_i){)}_{i=1}^m$ 为来自同一固定联合分布的IID 样本理路独立同分布样本IID sample · Independent and identically distributed sample以乘积分布描述来自同一总体的独立重复观测。。预测在分数非负时取 $+1$，否则取 $-1$，并记 $R_{0\text{-}1}(w)=\text{Pr}(h_w(X)\ne Y)$。定义经验低间隔率

一个标准的Rademacher 泛化界理路Rademacher 泛化界Rademacher generalization bound用样本上的 Rademacher 复杂度给出对整个有界实值函数类同时成立的数据依赖总体风险上界。版本表明：对任意预先固定的 $\gamma >0$ 和 $0<\delta <1$，以至少 $1-\delta$ 的概率，同时对所有 $\Vert w\Vert \le B$ 有

这里使用下文指定的 ramp 和 $1/m$、无外层绝对值的复杂度约定。可分性使范数球具有可数稠密子集；总体 ramp 风险和经验 ramp 风险对 $w$ 连续，故相应上确界可由这个可数子集决定。界的结构是：总体错误不超过经验低间隔率，加上由归一化半径 $BR/\gamma$ 和置信度产生的复杂度项。

推导骨架 ​

取截断 ramp 函数

零分数可能预测正确，所以真实 0–1 损失先由非正间隔指示函数上界；ramp 再满足

函数 ${\varphi }_{\gamma }$ 是 $1/\gamma$-Lipschitz。先将 ${\varphi }_{\gamma }$ 减去常数 ${\varphi }_{\gamma }(0)=1$，再应用收缩引理理路Rademacher 收缩引理Rademacher contraction lemma · Ledoux–Talagrand contraction principle逐坐标 Lipschitz 变换至多按 Lipschitz 常数放大标量函数类的 Rademacher 复杂度。；加回公共常数不改变符号期望。对带标签向量 $y_i{x}_i$，用线性类复杂度的范数计算理路Rademacher 复杂度Rademacher complexity · empirical Rademacher complexity通过拟合随机符号理解函数类复杂度，推导线性类、有限类和泛化界，并说明损失类与数据依赖选择的区别。，并注意固定标签可吸收到 Rademacher 符号中，可得

这一步在一般 Hilbert 空间仍成立：有限个样本向量张成有限维子空间，将 $w$ 投影到该子空间保留全部样本分数且不增范数，随后就是同一欧氏范数计算。因此 ramp 类的经验复杂度至多为 $BR/(\gamma \sqrt{m})$。将它代入上面所引经验 Rademacher 泛化界的 $2\hat{\mathfrak{R}}+3\sqrt{\log \left(2/\delta \right)/(2m)}$ 版本，再用夹逼回到分类错误，恰得显示的常数。这条证明清楚说明了 $1/\gamma$ 来自代理函数斜率，而不是凭经验加入的惩罚。