弱可学习与强可学习

“弱”衡量的是保证离随机猜测有多远，不是模型看起来简单，也不是一次实验中的准确率略高。Boosting 能够反复利用统一优势，把许多方向不同的微小改进组合起来；若优势小到指数级，所需调用次数也会失去多项式效率。

若弱学习器每次错误率至多 $0.49$，优势只有 $\gamma =0.01$，单次规则显然离任意小错误还很远。Boosting 通过提高此前错分点的权重，让后续规则修补不同区域，再以加权投票组合；典型轮数按 $1/{\gamma }^2$ 增长，所以同样“略好于随机”中的优势大小具有真实计算代价。

只在一份固定训练集上做到 $49\mathrm{\%}$ 错误不构成弱学习保证：算法可能利用偶然噪声，换一个重加权分布就退化到 $60\mathrm{\%}$。形式定义要求对接口允许的每个分布都存在统一优势和置信保证。另一方面，弱分类器不必结构简单；大模型也可以只获得弱优势。但满足本页的高效弱学习定义，还必须检查其多项式样本、训练和求值成本。

多类、不可知和带噪设定的随机基准与保证形式不同，不能直接复用 $1/2-\gamma$。同样，置信放大能改变失败概率，却不能把不存在的统一优势凭空制造出来。

弱到强 Boosting 归约理路弱到强 Boosting 归约boosting reduction · weak-to-strong learning通过改变样本分布聚焦当前难点，把略优于随机的弱学习器归约为任意精度强学习器。会反复对样本分布重加权并调用弱学习器；因此接口必须保证弱学习器对这些分布都有效，而不只是初始训练分布上略好。Schapire 的结果说明经典 PAC 接口下弱、强可学习的计算能力等价，AdaBoost理路AdaBoost 算法AdaBoost · Adaptive Boosting通过提高误分样本权重，依次组合弱分类器为加权二元投票。则给出一条具体的重加权与组合路线；margin 和噪声鲁棒性仍属于后续定理，不能塞回定义。