提升方法（boosting）和AdaBoost详解

概念

提升方法是一种思想：针对一个任务，将多个专家的建议适当的综合起来来做判断，这样比一个单独的专家的判断更有力，类似于“三个臭皮匠顶个诸葛亮”。

对于一个分类任务来讲，求解一个粗糙简单的弱分类器比求解精准分类的强分类器要简单的多，意思就是得到训练弱分类器比较简单，提升方法就是从弱分类器中不断的学习误差，每一个弱分类器都会学习之前一系列分类器的误差，这样可以得到一系列的弱分类器，组合这些弱分类器得到一个强分类器，这就是提升方法。

提升方法需要解决的问题

大多数提升方法是改变训练数据的概率分布，针对不同的训练数据的分布调用弱学习算法来学习一系列的弱分类器，所以对于提升方法来讲，它需要解决两个问题：

• 1、如何确定数据集的权重，或者说是概率分布？
• 2、这些弱分类器该如何来组合？

上述是《统计学习方法》中介绍的，细致来分的话，有几个具体的问题Boosting算法没有详细说明。

• 1、如何计算学习误差率e?
• 2、如何得到弱学习器权重系数α?
• 3、如何更新样本权重D?
• 4、使用何种结合策略？

只要是boosting大家族的算法，都要解决这4个问题。那么Adaboost是怎么解决的呢？具体往下看。

AdaBoost算法

AdaBoost针对上述第一个问题的思路就是提高那些被分类错误的数据样本的权重，让它们在下一轮的训练过程中备受关注，降低训练正确的数据样本的权重，于是被错误分类的数据样本就不断的被“分而治之”，AdaBoost中的“Ada”意思为Adaptive。
针对第二个问题的思路就是针对每个分类器采用加权多数表决的方式，加大分类错误率极小的弱分类器的权重，让它们在表决中起关键性作用，同样减小分类错误率大的弱分类器的权重，让它影响较小，具体算法流程如下所示。
输入：$T=(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$， y i ∈ { 1 , ? 1 } y_i \in \{1,-1\} yi?∈{ 1,?1}，弱学习算法

• 初始化数据分布权重，$D_1=(w_{11},w_{12},w_{13},...,w_{1i},...,w_{1n})$，$w_{1i}=\frac{1}{n},i=1,2,3,...,n$

• 对m初始化，$m=1,2,3...,m$，下列步骤循环
  （1）用具有权重$D_m$的数据训练集来学习算法，得到一个基本的分类器：
  G m ( x ) : X → { ? 1 , 1 } G_m(x):X\to\{-1,1\} Gm?(x):X→{ ?1,1}
  （2）计算$G_m$在训练数据集上的分类误差：
  $$e_m=P(G_m(x_i)!=y_i)=\sum _{i=1}^n{w}_{mi}I(G_m(x_i)!=y_i)$$
  $e_m$其实是表示分类错误的样本权重求和，其中$G_m(x_i)$表示分类器的输出，书中应该直接认为$G_m(x_i)$就是一个分类结果，直接输出分类结果，比如-1、1，所以才有后面的$y_i!=G_m(x_i)$。

  （3）计算$G_m(x)$的系数
  $$a_m=\frac{1}{2}\log \frac{1?e_m}{e_m}$$
  取自然对数，也就是$lo{g}_e$，也可以写为$ln$，这里$a_m$是分类器的权重，从上述公式可以看出，$e_m<\frac{1}{2}$，$a_m>0$，$a_m$是一个递减函数，$e_m$误差越小，权重越大。
  （4）更新训练数据集的权重：
  $$w_{m+1,i}=\frac{w_{m,i}}{Z{?}_m}exp(?a_m{y}_i{G}_m(x_i))$$
  一个样本都有一个权重，样本权重可以简化为如下：
  $$w_{m+1,i}=\{\begin{array}{ll}\frac{w_{m,i}}{Z{?}_m}{e}^{?a_m}& y_i==G_m(x_i)\\ \frac{w_{m,i}}{Z{?}_m}{e}^{a_m}& y_i!=G_m(x_i)\end{array}$$
  误差分类的样本的权重被放大了$e^{2a_m}=\frac{e_m}{1?e_m}$倍，在下一轮学习中将会起更大的作用。那另一方面最后一个分类器的误差应该是最小的，分类也是最准确的。 其中$Z_m$是一个规范化因子，它使$D_m$成为了一个概率分布：
  $$\begin{array}{rl}{Z}_m& =\sum _{i=1}^{n}exp(?a_m{y}_i{G}_m(x_i))\\ & =\sum _{i=1}^n{e}^{(?a_m{y}_i{G}_m(x_i))}\end{array}$$
  则下一轮样本权重为：
  $$D_{m+1}=(w_{m+1,1},w_{m+1,2},w_{m+1,3},...,w_{m+1,n})$$

• 最后构建基本分类器的线性组合：
  $$\begin{gathered} f(x)=\sum _{i=1}^m{a}_m{G}_m(x) \\ G(x)=sign(f(x))=sign(\sum _{m=1}^m{a}_m{G}_m(x)) \end{gathered}$$

举例说明

参考统计学习方法这本书上的例子来研究一个例子，首先看下数据集吧：

采用最基本的分类器，按照x来分隔样本，选择一个阈值$v$来分隔样本，得到两个样本区间：$x>v$和$x<v$：

• 第一轮分类器训练初始化权重 D 1 = { w 1 , 1 , w 1 , 2 , w 1 , 3 , . . . , w 1 , 10 } D_{1}=\{w_{1,1},w_{1,2},w_{1,3},...,w_{1,10}\} D1?={ w1,1?,w1,2?,w1,3?,...,w1,10?}，其中每个$w_{1,i}=\frac{1}{10}=0.1$，在数据权重分布为$D_1$的样本上，得到$v$=2.5时分类误差率最低，这个$v$值似乎不是唯一确定的，得到基本分类器：
  $$G_1(x)=\{\begin{array}{ll}1& \text{x>=2.5}\\ ?1& \text{x<2.5}\end{array}$$

于是分类误差率是$e_1=p(G_1(x_i)!=y_i)=0.3$，该分类器的系数为$a_1=\frac{1}{2}\log \frac{1?e_m}{e_m}=0.4236$，得到$f(x_i)=0.4236G(x_i)$分类器，经过$sign(f(x_i))$函数有三个分类错误。

• 第二轮，首先更新一下数据集的权重，根据第一轮的结果来更新数据集权重，
  $$w_{2,i}=\frac{w_{m,i}}{Z{?}_m}exp(?a_m{y}_i{G}_m(x_i))$$
  得到 D 2 = { 0.0715 , 0.0715 , 0.0715 , 0.0715 , 0.0715 , 0.0715 , 0.1666 , 0.1666 , 0.1666 , 0.0715 } D_2=\{0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666 ,0.1666,0.0715\} D2?={ 0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715}，在$D_2$分类器上开始学习弱分类器，得到阈值$v$=8.5时分类器误差最小，
  $$G_1(x)=\{\begin{array}{ll}1& \text{x>=8.5}\\ ?1& \text{x<8.5}\end{array}$$
  分类误差$e_2=0.2146$，分类器$G_2$的权重系数$a_2=0.6496$，得到$f(x_i)=0.4236?G_1(x_i)+0.6496?G_2(x_i)$分类器，经过$sign(f(x_i))$函数有三个分类错误。

• 第三轮，首先更新一下数据集的权重，根据第二的结果来更新数据集权重，得到 D 3 = { 0.0455 , 0.0455 , 0.0455 , 0.1667 , 0.1667 , 0.1667 , 0.1060 , 0.1060 , 0.1060 , 0.0455 } D_3=\{0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455\} D3?={ 0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455}，在$D_3$分类器上开始学习弱分类器，得到阈值$v$=5.5时分类器误差最小，
  $$G_1(x)=\{\begin{array}{ll}1& \text{x>=8.5}\\ ?1& \text{x<8.5}\end{array}$$
  分类误差$e_3=0.182$，分类器$G_3$的权重系数$a_3=0.7514$，得到$f(x_i)=0.4236?G_1(x_i)+0.6496?G_2(x_i)+0.7514?G_3(x_i)$分类器，经过$sign(f(x_i))$函数分类全部正确。

总结

优点：

• 不容易发生过拟合
• Adaboost是一种有很高精度的分类器
• 当使用简单分类器时，计算出的结果是可理解的。
• 可以使用各种方法构建子分类器，Adaboost算法提供的是框架。

缺点：

• 训练时间过长
• 执行效果依赖于弱分类器的选择
• 对样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

总结一下：

• 分类结束的条件是所有样本分类正确，那如果永远不能完全分类正确，该如何？可以设置一个最小分类误差，分类误差小于某个值的时候就停止了。
• 如果一个样本有多个特征，那么样本的权重是不是对于每个特征来讲都是一样的？这个问题并没有博客重点讲解，书中也没有分析，似乎是默认样本权重就是特征权重，反向思考，这个不一样也似乎是没必要的，本来也是用来判断样本的权重，但仔细意向，很多样本可能是某些特征有问题，不一定是整体的样本维度，但综合来来看，AdaBoost似乎是没有考虑具体的特征因素，所以还是理解为此权重就是样本所有特征的权重。
• 上述问题中还有一个问题，在AdaBoost算法来说，文章一开始默认$G(x_i)$输出得到分类结果，如果是回归问题，得到的数值与$y_i$是有误差的，这个该如何来调整算法？
• 每次一个分类器都要用全部样本学习，对于弱分类器学习来讲，时间及速度上影响不大，强分类器的学习时间会就会比加大。
• 书中有一章讲解了AdaBoost算法训练误差分析，在这一章中证明了AdaBoost算法的训练误差是指数下降的。

AdaBoost算法是模型为模型为加法模型、损失函数维指数函数、学习算法为前向分分布算法时的二分类数学方法。

参考博客

《统计学习基础》