Boosting 的间隔理论

归一化间隔 ​

设基分类器类 $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 分布承担。

具体例子：多数函数的间隔分布 ​

在 $\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 组合在标注样本上的分布，后者评价整个实值函数类在任意点集上的尺度化打散能力。

参考资料

• Robert Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee, “Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods,” 1998.
• Peter Bartlett and Shahar Mendelson, 2002.