间隔泛化界

从“分对了”到“离边界多远” ​

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

$$yf(x)$$

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

线性间隔界 ​

设 $X$ 位于 Hilbert 空间，$\Vert x\Vert \le R$，考虑齐次线性打分

$$f_w(x)=⟨w,x⟩,\Vert w\Vert \le B.$$

对样本 $S=((x_i,y_i){)}_{i=1}^m$，定义经验低间隔率

$${\hat{R}}_{\gamma }(w)=\frac{1}{m}\sum _{i=1}^m\mathbf{1}\{y_i⟨w,x_i⟩\le \gamma \}.$$

一个标准 Rademacher 版本表明：对任意固定 $\gamma >0$，以至少 $1-\delta$ 的概率，同时对所有 $\Vert w\Vert \le B$ 有

$$R_{0\text{-}1}(w)\le {\hat{R}}_{\gamma }(w)+\frac{2BR}{\gamma \sqrt{m}}+3\sqrt{\frac{\log \left(2/\delta \right)}{2m}}.$$

常数随 ramp loss 的具体定义而变化，稳定的结构是：总体错误不超过经验低间隔率，加上由归一化半径 $BR/\gamma$ 和置信度产生的复杂度项。

推导骨架 ​

取截断 ramp 函数

$${\varphi }_{\gamma }(u)=\{\begin{array}{ll}1,& u\le 0,\\ 1-u/\gamma ,& 0<u<\gamma ,\\ 0,& u\ge \gamma .\end{array}$$

它夹住 0–1 损失与低间隔指示函数：

$$\mathbf{1}\{u\le 0\}\le {\varphi }_{\gamma }(u)\le \mathbf{1}\{u\le \gamma \}.$$

函数 ${\varphi }_{\gamma }$ 是 $1/\gamma$-Lipschitz。对线性打分类应用收缩引理，并利用

$${\hat{\mathfrak{R}}}_S(\{x\mapsto ⟨w,x⟩:\Vert w\Vert \le B\})\le \frac{BR}{\sqrt{m}},$$

即可把 ramp loss 的总体均值控制为经验均值加 $BR/(\gamma \sqrt{m})$。最后用上面的夹逼回到分类错误。这条证明清楚说明了 $1/\gamma$ 来自代理函数斜率，而不是凭经验加入的惩罚。

数值尺度与归一化 ​

若将 $w$ 乘以常数 $c>0$，分类标签完全不变，原始间隔却也乘以 $c$。因此单说“间隔很大”没有尺度意义；必须同时固定 $\Vert w\Vert$、输入半径 $R$，或使用几何间隔

$$\frac{y⟨w,x⟩}{\Vert w\Vert }.$$

量 $BR/\gamma$ 在同步缩放 $w$ 与 $\gamma$ 时保持不变，正是界中真正的无量纲复杂度。

考虑二维中两条同样分对所有训练点的直线。第一条贴近一簇点，第二条位于两类之间的宽走廊中央。两者训练错误都是零，但在同一范数归一化下，第二条的最小间隔更大，允许用更大的 $\gamma$ 保持 ${\hat{R}}_{\gamma }=0$，从而得到更紧的界。这里比较的是可证明的扰动余量，不是对视觉上“更居中”的通用赞美。

数据后选择 $\gamma$ ​

上式对预先固定的 $\gamma$ 成立。若看完数据后在连续多个阈值中选择最漂亮的一个，必须为这次选择付费。常见做法是只考虑 dyadic 网格 ${\gamma }_j=2^{-j}$，再分配失败概率 ${\delta }_j$ 并取并集界；结果多出很小的对数项。直接把训练后最优 $\gamma$ 代入固定阈值定理，会遗漏选择偏差。

与其他间隔理论的边界 ​

本页控制的是线性或 Lipschitz 打分类的测试错误。Boosting 间隔理论公理库Boosting 的间隔理论Boosting margin theory · Boosting margin bound用加权投票的归一化训练间隔分布和基分类器复杂度控制总体分类错误，而不直接依赖 boosting 轮数。研究加权基学习器组合，归一化方式与复杂度项不同；不能只因都出现 $yf(x)$ 就复用同一公式。fat-shattering 维则把实值类在尺度 $\gamma$ 上的组合复杂度抽象出来，可覆盖超出 Hilbert 线性类的模型。

大间隔也不自动解决标签噪声。若训练集中有离群标记，强迫所有点获得正大间隔可能需要巨大范数并恶化 $BR/\gamma$；软间隔方法允许一部分低间隔点，正是经验项与复杂度项之间的权衡。该界是泛化保证，不说明寻找最优 $w$ 的算法一定高效。

参考资料

• Peter L. Bartlett and Shawe-Taylor, margin bounds for neural and linear classifiers.
• Vladimir Vapnik, Statistical Learning Theory, margin and structural risk chapters.
• Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, margin bounds chapter.