• 对m=1, 2, .., M
    1. 使用具有权值 Dm
    • 的训练数据集学习，得到基本分类器 Gm(x)

  • 计算 Gm(x)
    • 在数据集上的分类误差率， em=P(Gm(xi)≠yi)=∑NiwmiI(Gm(xi)≠yi)

  • 计算 Gm(x)
    • 的系数 αm=12ln1−emem

  • 更新数据集的权值分布 Dm+1=(wm+1,1,wm+1,2,..,wm1,N)
    • ，其中 wm+1,i=wmiZme−αmyiGm(xi) ， Zm=∑Niwmie−αmyiGm(xi)

  • 构建基本分类器的线性组合 f(x)=∑MmαmGm(x)

  • 得到最终的分类器 G(x)=sign(f(x))

    AdaBoost例子

    复（sang）杂（xin）难（bing）懂（kuang）的数学公式太不直观了，下面看个AdaBoost例子。

    数据集

    序号 1 2 3 4 5 6 7 8 9 10
    x 0 1 2 3 4 5 6 7 8 9
    y 1 1 1 -1 -1 -1 1 1 1 -1

    弱分类器

    假设弱分类器由x<v或x>v产生，v将数据集划分分两个部分，这两个部分的误差率最低。

    计算过程

    1. 初始化权值分布 D1=(w11,w12,..,w110),w1i=0.1

  • 对m=1
    1. v=2.5时误差率为0.3，最小，基本分类器为 G1={1,x<2.5−1,x>2.5

  • G1(x)
    • 的误差率为0.3，其系数为 α1=12ln1−0.30.3=0.4236

  • 计算 Z1=110(7e−0.4236+3e0.4236)=0.9165

    • 正确分类的样本 w2i=w1iZ1e−α1yi=0.10.9165e−0.4236=0.0715
    未正确分类的样本 w2i=0.10.9165e0.4236=0.1666
    更新权值分布为 D2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)

  • f1(x)=0.4236G1(x)
    • ，在 sign(f1(x))
    1. 上有3个误差点
  • 对m=2
    1. 2.5处的误差率为3×0.1666（6,7,8三个点分类错误），8.5处的错误率为3×0.0715=0.2145，所以8.5处有最小误差率，基本分类器为 G2={1,x<8.5−1,x>8.5

  • G2(x)
    • 的误差率为0.2145，其系数为 α2=12ln1−0.21450.2145=0.6496

  • 更新权值分布，同上，得 D2=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.04555)

  • f2(x)=0.4236G1(x)+0.6496G2(x)
    • ，在 sign(f2(x))
    1. 上有3个误差点
  • 对m=3，计算方法同上，最后得到 f3(x)=0.4236G1(x)+0.6496G2(x)+0.7514G3(x)
    • ，在 sign(f3(x)) 上有0个误差点，其中 G3={1,x<5.5−1,x>5.5

  • 至此计算结束，得到最终分类器 G(x)=sign(f3(x))=sign(0.4236G1(x)+0.6496G2(x)+0.7514G3(x))

    AdaBoost优点

    • AdaBoost是一种有很高精度的分类器
    • AdaBoost可以支持各种方式构建的弱分类器，如上文中的x<v这样的分类器，AdaBoost提供的是框架
    • 构造弱分类器简单，不用进行特征筛选
    • 不用担心过拟合

    AdaBoost与决策树的结合则形成了提升树（boosting tree），AdaBoost使得决策树的准确率大大提高，可与SVM相媲美。

    后记

    关于AdaBoost的收敛性证明和用前向分步算法进行解释，个人认为属于理论研究的范围，作为一个生产者，我只要会用并且知道可以收敛并且能够理论上解释的通即可（其实是短时间内看不懂啊混蛋。。）。

    参考资料

    • 《统计学习方法》李航,2012