弱到强 Boosting 归约 | Codeboy's Blog

形式陈述

本页形式化弱到强可学习性，并以乘法重加权组织对弱学习 oracle 的自适应调用。

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

Oracle 接口

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

\Pr_{(X,Y)\sim D_t}[h_t(X)\ne Y]\le\frac12-\gamma.

booster 维护分布 $D_t$ 或等价权重，调用 oracle，依据 $h_t$ 的错误重新加权，再把 $h_1,\ldots,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(1/\varepsilon))$ 轮可把相应训练或分布误差压到 $\varepsilon$ 量级；具体样本复杂度还要乘上每次弱学习调用的需求并分配置信度。

直觉

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

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

例子与边界

弱优势必须对 booster 产生的每轮分布成立；只对原分布平均略优于随机不够。可实现 PAC 中的弱—强等价也不应无条件外推到噪声、受限假设类、分布漂移或计算受限 oracle。AdaBoost是实现这种思想的具体算法，不等于抽象归约本身。

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

推论与应用

AdaBoost 把抽象 oracle 归约实现为指数损失与样本权重更新，训练误差界给出 $O(\gamma^{-2}\log(1/\varepsilon))$ 轮数。间隔理论再处理组合后的样本外行为，三层结论不能压成一个“boosting 会泛化”的口号。

归约也说明强分类器可以落在弱类的加权组合之外，因此输出常是 improper。若弱学习器在某些重加权分布上失去优势，或重采样成本爆炸，归约的统计或计算前提便分别失败。

参考资料

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

形式陈述 ​

Oracle 接口 ​

势能下降机制 ​

反向链接

形式陈述

Oracle 接口

势能下降机制