弱可学习与强可学习

形式区别 ​

二分类弱学习器在规定的任意输入分布上，以足够置信度输出错误率至多 $1/2-\gamma$ 的规则，其中优势 $\gamma >0$ 至少为表示规模的逆多项式。强学习器则对任意 $\epsilon ,\delta$ 达到 PAC 错误至多 $\epsilon$。

“弱”不是模型参数少或经验表现普通，而是相对随机猜测有统一、可量化的优势。若 $\gamma$ 指数级微小，把优势放大到强精度可能需要指数轮次，不能称高效弱学习。

经典可实现弱学习可写成：对任意目标 $c\in \mathcal{C}$、任意输入分布 $D$，使用多项式样本和时间后，以至少 $2/3$ 概率输出 $h$ 满足

$${\text{Pr}}_{X\sim D}[h(X)\ne c(X)]\le \frac{1}{2}-\gamma (n).$$

置信常数可放大，关键是优势 $\gamma (n)\ge 1/\mathrm{poly}(n)$ 对所有允许分布统一成立。强学习则把右端换成任意输入精度 $\epsilon$。

Boosting 归约会反复对样本分布重加权并调用弱学习器；因此接口必须保证弱学习器对这些规定分布仍有效，而不只是初始训练分布上略好。多类、不可知和带噪设定的随机基准与保证形式不同，不能直接复用 $1/2-\gamma$。

Schapire 的弱到强结果说明在经典 PAC 接口下两者计算能力等价，但具体算法、margin 和噪声鲁棒性属于后续定理，不应塞进定义。

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

只在一份固定训练集上做到 $49\mathrm{\%}$ 错误不构成弱学习保证：算法可能利用偶然噪声，换一个重加权分布就退化到 $60\mathrm{\%}$。形式定义要求对接口允许的每个分布都存在统一优势和置信保证。另一方面，弱分类器不必结构简单；一个计算昂贵的大模型只要形式保证停在固定优势，也仍是“弱学习器”。

参考资料

• Robert Schapire, “The Strength of Weak Learnability,” 1990.
• Yoav Freund, Robert Schapire, “A Decision-Theoretic Generalization of On-Line Learning,” JCSS, 1997.