弱到强 Boosting 归约

定理图像 ​

经典二分类 PAC 设置中，若弱学习器对它收到的每个允许分布都能以非平凡优势 $\gamma >0$ 学到假设，就可用多轮调用构造任意精度的强学习器。关键不是把同一次弱学习独立重复后投票，而是每轮改变样本权重，让后来的学习器看到当前组合仍处理不好的区域。

Oracle 接口 ​

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

$${\text{Pr}}_{(X,Y)\sim D_t}[h_t(X)\ne Y]\le \frac{1}{2}-\gamma .$$

booster 维护分布 $D_t$ 或等价权重，调用 oracle，依据 $h_t$ 的错误重新加权，再把 $h_1,\dots ,h_T$ 组合成最终分类器。若弱学习器只接收原始 IID 样本，可通过 rejection sampling 或按权重重采样模拟 $D_t$，并把模拟失败概率计入总置信度。

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

势能下降机制 ​

一种典型分析给每个训练点按当前 margin 赋指数权重。若 $h_t$ 在 $D_t$ 下具有优势，选择合适组合系数后，指数势能每轮乘上至多 $\sqrt{1-4{\gamma }^2}\le e^{-2{\gamma }^2}$。于是 $T=O({\gamma }^{-2}\log \left(1/\epsilon \right))$ 轮可把相应训练或分布误差压到 $\epsilon$ 量级；具体样本复杂度还要乘上每次弱学习调用的需求并分配置信度。

为什么普通多数重复不够 ​

若弱学习器总在同一块概率质量 $0.49$ 的区域系统性出错，独立重跑只会反复得到相关错误，多数票不会修复它。重加权把该区域在下一轮分布中的质量放大，迫使 oracle 的“对每个重加权分布仍有优势”前提发挥作用。这与概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。针对固定输入、相对独立随机错误的多数投票不同。

以决策桩为弱学习器时，一轮可能只找到“某个单一特征阈值”并略优于随机。若第一根桩把一群在该特征上重叠的正样本系统性判错，下一轮提高这些样本的权重，迫使新桩寻找另一特征上的切分；最终分类器是多根桩的加权组合，通常不再属于单根桩的输出类。这个例子展示的是分布接口和 improper 组合，而不是保证任意数据上的决策桩都有固定优势——若某个重加权分布下所有桩误差都不低于 $1/2$，弱学习前提当场失效。

边界 ​

弱优势必须对 booster 产生的每轮分布成立；只对原分布平均略优于随机不够。可实现 PAC 中的弱—强等价也不应无条件外推到噪声、受限假设类、分布漂移或计算受限 oracle。AdaBoost公理库AdaBoost 算法AdaBoost · Adaptive Boosting通过提高误分样本权重，依次组合弱分类器为加权二元投票。是实现这种思想的具体算法，不等于抽象归约本身。

归约的轮数只控制组合过程；总样本复杂度还取决于每轮如何从原分布模拟 $D_t$。当重加权把质量集中在原分布的稀有区域时，朴素 rejection sampling 的接受率可能很低，需要显式计算采样开销。忽略这一层可以得到统计上正确却计算上并非多项式时间的“归约”。

参考资料

• Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, 1990.
• Yoav Freund, Boosting a Weak Learning Algorithm by Majority, Information and Computation, 1995.