弱到强 Boosting 归约

形式陈述 ​

本页形式化弱到强可学习性理路弱可学习与强可学习Weak learnability · Strong learnability区分以固定优势胜过随机猜测与达到任意 PAC 精度的学习目标。，并以乘法重加权理路乘法权重更新方法multiplicative weights update · MWU以指数方式降低高损失动作的权重，并用总权重势函数给出累计性能保证。组织对弱学习 oracle 的自适应调用。

在经典、可实现、分布无关的二分类 PAC 模型中，输入与目标具有规定的有限编码，且允许输出可多项式表示和求值的组合假设。若存在对所有输入分布都有效、优势至少为规模逆多项式的高效弱学习器，则存在达到任意 $0<\epsilon ,\delta <1$ 的高效强学习器。这是弱—强等价定理；它不要求强学习器仍输出单个基分类器。关键不是把同一次弱学习独立重复后投票，而是每轮改变样本权重，让后来的学习器看到当前组合仍处理不好的区域。

Oracle 接口 ​

把弱学习器视为 oracle：给定目标概念下的一个重加权分布 $D_t$，它返回 $h_t$，满足

booster 维护分布 $D_t$ 或等价权重，调用 oracle，依据 $h_t$ 的错误重新加权，再把 $h_1,\dots ,h_T$ 组合成最终分类器。对一个显式有限训练集，可按已知权重直接重采样。若 $D_t$ 是原总体分布的重加权，则拒绝采样还要有可计算的接受概率及足够大的接受率下界；算法必须将其时间、样本与失败概率一起核算。

这里的量词是归约成立的核心：存在统一的逆多项式优势下界 $\gamma$ 与多项式样本/时间界，使得对每个允许分布 $D_t$ 和每个目标概念，弱学习器都以规定置信度返回上述假设。booster 产生的 $D_t$ 依赖此前所有 $h_s$，所以“只在原始分布上平均有优势”不满足接口。每轮 oracle 失败概率还要取可求和分配，才能让整条自适应调用链以高概率成功。

势能下降机制 ​

在有限训练集上，给每个点按当前 margin 赋指数权重，可具体实现上述重加权步骤。若每轮加权错误为 $0<{\epsilon }_t\le 1/2-\gamma$，AdaBoost 训练误差界理路AdaBoost 训练误差界AdaBoost training error bound · AdaBoost exponential loss boundAdaBoost 的训练零一错误由每轮归一化常数乘积控制，并在持续弱优势下按优势平方和指数下降。证明归一化因子

因此 $O({\gamma }^{-2}\log \left(1/\epsilon \right))$ 轮足以把该训练分布的错误控制到 $\epsilon$；零错误轮直接返回完美规则。这个势能计算解释有限样本实现的轮数，不单独证明总体 PAC 保证。

完整的高效弱—强定理还要选择多项式大小的训练样本、控制组合假设的表示与泛化误差，并把每次弱调用和分布模拟的失败概率合并。经典证明完成了这些步骤；不能把任意重加权规则配上可能指数慢的拒绝采样，就称为它的高效实现。