Boosting 的间隔理论

形式陈述 ​

本页把AdaBoost公理库AdaBoost 算法AdaBoost · Adaptive Boosting通过提高误分样本权重，依次组合弱分类器为加权二元投票。的加权投票视为归一化 score 间隔公理库线性分类器与几何间隔Linear classifier · Geometric margin用仿射超平面分类，并以缩放不变的几何间隔衡量分离余量。，并用基类的VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。支付统计复杂度。

设基分类器类 $H\subseteq \{-1,+1{\}}^{\mathcal{X}}$ 的 VC 维为 $d$。任意有限加权投票写成

$$F(x)=\sum _{t=1}^T{\alpha }_t{h}_t(x),h_t\in H.$$

分类不随所有系数同比缩放而改变，因此真正有意义的是

$${\rho }_F(x,y)=\frac{yF(x)}{\sum _t|{\alpha }_t|}.$$

若 ${\alpha }_t\ge 0$ 且和为 $1$，$F$ 是 $H$ 的凸组合，${\rho }_F=yF(x)\in [-1,1]$。${\rho }_F>0$ 表示分类正确，数值越大表示组成投票越一致；未除以 $\sum _t|{\alpha }_t|$ 的投票值可通过重复同一分类器任意放大，不能作为 margin 证书。

一种标准 margin 界 ​

存在普适常数 $C$，使对任意 $0<\delta <1$，以至少 $1-\delta$ 的概率，对所有 $F\in \mathrm{conv}(H)$ 和所有 $0<\theta \le 1$ 同时有

$${\text{Pr}}_D({\rho }_F(X,Y)\le 0)\le {\widehat{\text{Pr}}}_S({\rho }_F(X,Y)\le \theta )+C[\frac{1}{\theta }\sqrt{\frac{d\log \left(em/d\right)}{m}}+\sqrt{\frac{\log \left(1/\delta \right)}{m}}],$$

其中 $d>m$ 时把增长函数界换成平凡上界。更经典的离散化证明可能出现额外 $\log m$ 因子；公式的版本会随基类、margin 损失与 simultaneous-$\theta$ 处理改变，但三部分不会改变：低 margin 训练比例、按 $1/\theta$ 放大的基类复杂度、置信项。

证明图像 ​

用 ramp 函数

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

夹住零一错误：$\mathbf{1}[r\le 0]\le {\varphi }_{\theta }(r)\le \mathbf{1}[r\le \theta ]$。它是 $1/\theta$-Lipschitz，所以一致泛化偏差按 $1/\theta$ 放大。凸包的线性上确界总在极点取得，故其 Rademacher 复杂度与基类 $H$ 相同；再由 VC 增长函数控制 $H$ 在样本上的复杂度，就得到上式。经典证明也可随机抽取有限个基分类器近似凸组合，再对增长函数和抽样误差使用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。。

这个推导解释了为何界不显式含轮数 $T$：增加轮数扩大了表示方式，却没有扩大凸包上任意线性函数的最大值。代价转而由实际形成的 margin 分布承担。

直觉

训练错误只区分 margin 的正负，间隔分布还记录预测离翻转边界多远。boosting 轮数增加不会扩大凸包在线性上确界下的复杂度，但它会改变样本 margin 尾部；泛化界因此把注意力从轮数转到实际形成的分布。

例子与边界

多数函数的间隔分布 ​

在 $\mathcal{X}=\{-1,+1{\}}^n$ 上用坐标分类器 $h_j(x)=x_j$，标签是多数函数 $y=\mathrm{sign}(\sum _j{x}_j)$，取均匀投票 $F(x)=n^{-1}\sum _j{x}_j$。所有奇数 $n$ 的训练点都被正确分类，但 margin 并不相同：只多一个正坐标的点有 $\rho =1/n$，全体坐标同号的点有 $\rho =1$。前者翻转一个坐标就可能越过决策边界，后者则要翻转超过一半坐标。训练错误同为零，margin 分布却记录了投票离失效还有多远。

当选择 $\theta$ 时存在真实权衡：增大 $\theta$ 会把更多勉强正确的训练点计入第一项，却缩小 $1/\theta$ 复杂度惩罚；减小 $\theta$ 则相反。不能只汇报平均 margin，因为少量接近零或为负的尾部正是分类错误所在。

定理没有说明什么 ​

大训练 margin 不是无条件证书；样本量、基类 VC 维和数据依赖选择仍在界中。AdaBoost 也不保证总在最大化最小 margin：其坐标下降轨迹优化指数损失，长期行为与显式最大 margin 算法并非同一定理。

本页的归一化投票 margin 与 fat-shattering 尺度公理库Fat-shattering 维Fat-shattering dimension · fat dimension以尺度参数衡量实值函数类在逐点阈值两侧保留固定间隔并实现全部符号模式的能力。相关但不等同；前者评价一个 boosting 组合在标注样本上的分布，后者评价整个实值函数类在任意点集上的尺度化打散能力。

推论与应用

对每个阈值 $\theta$，低 margin 训练比例与 $1/\theta$ 复杂度形成可计算折中；要在数据后选择 $\theta$，必须使用同时覆盖阈值的界或额外并集控制公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。。这比只报告平均 margin 更能看见脆弱尾部。

间隔理论解释了训练错误归零后继续组合仍可能改善证书，但不宣称 AdaBoost 总会最大化最小间隔。若基类复杂、标签含噪或权重可为负，还需使用与相应投票类匹配的界。

参考资料

• Robert Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee, “Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods,” 1998.
• Peter L. Bartlett and Shahar Mendelson, “Rademacher and Gaussian Complexities: Risk Bounds and Structural Results,” Journal of Machine Learning Research 3, 2002, pp. 463–482.