Boosting学习（一）——PAC学习模型到Boosting

• PAC ( Probably Approximately Correct)可能近似正确学习模型
• 因为我们不能指望学习能够零错误，并且也不能要求对任意数据的预测能够成功，但是我们需要将错误率和预测失败率控制在一定范围内，也就是近似正确，而不是以1为指标的。
• 定义 (PAC Model)：我们称一个 concept class C 是 PAC 可学习 的，如果存在一个算法 L ，使得对任意的 target concept c∈C ，以及任意 X 上的分布 μ ，和任意 0<ϵ<1/2 、0<δ<1/2 ，在给定 oracle EX(c,μ) 以及 ϵ、δ 的情况下，L 能够以至少 1−δ 的概率得到一个 hypothesis concept h∈C ，满足误差 E(h)≤ϵ 。 如果 L 的运行时间复杂度关于 1/ϵ 、1/δ 、输入空间 X 的维度以及 target concept c 的大小是多项式的，我们则称 C 是 efficiently PAC learnable 的。
• 强可学习：一个多项式的学习算法，正确率很高（>(1-ϵ)）。
• 弱可学习：一个多项式学习算法，正确率仅比随机猜想略高。
• 弱可学习可以提升为强可学习。
• 弱学习器提升为强学习器的过程称为Boosting。
• Boosting可以产生一系列的学习器，后产生的学习器的训练集取决于之前的产生的学习器，之前被误判的示例在之后获得较大的概率。