Boosting 的间隔理论

形式陈述 ​

本页研究有限加权投票的归一化间隔；AdaBoost理路AdaBoost 算法AdaBoost · Adaptive Boosting通过提高误分样本权重，依次组合弱分类器为加权二元投票。只是产生这类投票的一种算法，定理不依赖其训练轨迹。设非空、预先固定的基分类器类 $H\subseteq \{-1,+1{\}}^{\mathcal{X}}$ 的VC 维理路VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。为有限整数 $d\ge 0$，并假定相关上确界可测。训练集 $S=((X_i,Y_i){)}_{i=1}^m\sim D^m$ 是大小 $m\ge 1$ 的IID 样本理路独立同分布样本IID sample · Independent and identically distributed sample以乘积分布描述来自同一总体的独立重复观测。，$Y_i\in \{-1,+1\}$。

有限投票写成

把所有系数同乘正数不改变分类，归一化间隔定义为

它也有精确的几何间隔理路线性分类器与几何间隔Linear classifier · Geometric margin用仿射超平面分类，并以缩放不变的几何间隔衡量分离余量。解释：对这组有限基函数取特征向量 $\mathrm{\Psi }(x)=(h_1(x),\dots ,h_T(x))$，在特征空间用 ${\ell }_{\mathrm{\infty }}$ 距离，其对偶参数范数是 $\Vert \alpha {\Vert }_1=A$。这个距离位于投票特征空间，不是原输入空间的距离。

下面的风险界选取非负权重并令其和为 $1$，即 $F\in \mathrm{conv}(H)$。于是 ${\rho }_F=yF(x)\in [-1,1]$。固定平票规则后，真实分类错误被事件 ${\rho }_F\le 0$ 上界控制。

同时覆盖所有间隔阈值的界 ​

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

当 $1\le d\le m$ 时，$d_{\ast }=d$；这个约定也使零 VC 维和 $d>m$ 时的公式有定义。高复杂度时上界可能超过 $1$，可再与 $1$ 取小值。三项分别是低 margin 训练比例、基类复杂度和置信代价。

证明：ramp、凸包与阈值网格 ​

对固定 $\theta$，用 ramp 函数

夹住错误：$\mathbf{1}\{r\le 0\}\le {\varphi }_{\theta }(r)\le \mathbf{1}\{r\le \theta \}$。它在 $[0,1]$ 内取值且为 $1/\theta$-Lipschitz，故有界损失的 Rademacher 泛化界理路Rademacher 泛化界Rademacher generalization bound用样本上的 Rademacher 复杂度给出对整个有界实值函数类同时成立的数据依赖总体风险上界。与标量收缩引理理路Rademacher 收缩引理Rademacher contraction lemma · Ledoux–Talagrand contraction principle逐坐标 Lipschitz 变换至多按 Lipschitz 常数放大标量函数类的 Rademacher 复杂度。把固定阈值的复杂度代价控制为 $O({\hat{\mathfrak{R}}}_S(H)/\theta )$。收缩时减去公共常数 ${\varphi }_{\theta }(0)=1$；关于随机符号取期望后，这个公共平移不改变复杂度。

这里使用 $1/m$ 归一化、上确界内不加绝对值的Rademacher 复杂度理路Rademacher 复杂度Rademacher complexity · empirical Rademacher complexity通过拟合随机符号理解函数类复杂度，推导线性类、有限类和泛化界，并说明损失类与数据依赖选择的区别。。对每个符号向量，线性泛函在有限凸组合上的上确界与在 $H$ 上相同；不要求上确界实际取到。样本标签 $Y_i$ 乘到随机符号上也不改变其联合分布。再用Sauer–Shelah 增长界理路Sauer–Shelah 引理Sauer's lemma · Sauer–Shelah–Perles lemma把有限 VC 维转化为假设类在有限样本上的多项式标注数上界。与有限取值向量的 Rademacher 界，得到

$d=0$ 时 ${\mathrm{\Pi }}_H(m)=1$；$d>m$ 时用 ${\mathrm{\Pi }}_H(m)\le 2^m\le e^m$，同样满足最后一个界。

为允许看过数据后选择 $\theta$，取 ${\theta }_j=2^{-j}$，并给第 $j\ge 0$ 个阈值分配失败概率 $\delta /2^{j+1}$。可数并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。使所有网格界同时成立。对任意 $\theta$，选 ${\theta }_j\le \theta <2{\theta }_j$：经验低间隔比例不会增大，$1/{\theta }_j<2/\theta$。额外置信项中的 $\sqrt{j+1}$ 也被常数倍 $1/\theta$ 控制，而 $d_{\ast }\log \left(em/d_{\ast }\right)\ge 1$，因此可吸收到显示的第一项。这给出同一个普适 $C$ 下的同时阈值版本。

上述分析不显式使用轮数 $T$：增加有限项数没有改变凸包的线性上确界，但会改变实际形成的 margin 分布。