AdaBoost［2］

         Boosting最初是受统计学的启发，导出generalization error的上界，但是，这些上界太松而不能得到实际值，实际的boosting效果要比只用边界的结论要好的多。Friedman et al对boosting给出了一个独特的，简单的解释，它使用顺序最小化指数误差函数来说明。

         考虑一个如下定义的指数误差函数(下一篇讲它的来历)：

    

其中f_m(x)是一个基分类器y_l(x)的线性结合，y_l(x)形式如下：

          

并且t_n属于{-1,1}是目标值。我们的目标对权重系数alpha_l和基分类器y_l(x)的参数最小化E。

         这里并不对全局误差函数进行最小化，而是我们假设基分类器y₁(x),…,y_m-1(x)是固定的，它们的系数alpha₁,…,alpha_m-1也是固定的。所以我们只用对alpha_m和y_m(x)进行最小化。将基分类器y_m(x)的贡献分离出来，我们可以将误差函数写成如下形式：

           

因为我们只对alpha_m和y_m(x)最优化，所以其中系数w_n^(m)=exp{-t_nf_m-1(x_n)}可以视为是常量。如果我们令T_m为y_m(x)正确分类的数据点，而M_m为y_m(x)错误分类的数据点，那么我们可以重写误差函数为：

            

当我们对y_m(x)对上面公式进行最小化时，第二项是常量，而第一项前面的因子不会影响最小值，所以它等价于最小化(14.15)。类似的对alpha_m最小化，我们可以得到在(14.17)中通过(14.16)定义的epsilon_m。

         从(14.22)中我们可以看到，得到alpha_m和y_m(x)，数据点的权重可以通过下式更新：

          

使用如下事实：

           

我们看到权重w_n^(m)在一下次迭代中使用：

           

因为exp(-alpha_m/2)独立于n，它对于所有的数据点都赋相同的权重，所以它可以被丢弃，然后就可以得到(14.18)。

         最后，当所有的基分类器都训练后，新的数据通过(14.21)定义的函数将基分类器结合起来，再根据结果的符号来分类。因为因子1/2不影响符号，所以它可以被省略，与(14.19)相同。