AdaBoosts算法原理

我们带着问题去思考：

弱学习器的权重系数 α 如何计算？
样本点的权重系数 w 如何更新？
学习的误差率 e 如何计算？
最后使用的结合策略是什么？

一、AdaBoost基本原理介绍

1,1AdaBoost分类问题

以二分类为例，假设给定一个二类分类的训练数据集 $chi = left { (x_{1}, y_{1}), (x_{2}, y_{2}),...,(x_{n}, y_{n}) ight }$ ，其中 $x_{i}$ 表示样本点， $y_{i}$ 表示样本对应的类别，其可取值为｛-1，1｝。AdaBoost算法利用如下的算法，从训练数据中串行的学习一系列的弱学习器，并将这些弱学习器线性组合为一个强学习器。AdaBoost算法描述如下：

输入：训练数据集 $chi = left { (x_{1}, y_{1}), (x_{2}, y_{2}),...,(x_{n}, y_{n}) ight }$

输出：最终的强分类器G(x)

（1）初始化训练数据的权重分布值：（ $D_{m}$ 表示第m个弱学习器的样本点的权值），也就是说初始化的权重都是 (1/n)

$D_{1}=(w_{11},...,w_{1i},...,w_{1N}),$ $w_{1i}=1/N,$ $i=1,2,...,N$

（2）对M个弱学习器，m=1，2，...，M：

（a）使用具有权值分布 $D{_{m}}$ 的训练数据集进行学习，得到基本分类器 $G{_{m}}(x)$ ，其输出值为｛-1，1｝；

（b）计算弱分类器 $G{_{m}}(x)$ 在训练数据集上的分类误差率 $e{_{m}}$ ，其值越小的基分类器在最终分类器中的作用越大

其中， $I(G{_{m}}(x{_{i}}) eq y{_{i}})$ 取值为0或1，取0表示分类正确，取1表示分类错误。其中就等于分类错误的权重*分类错误的个数

（c）计算弱分类器 $G{_{m}}(x)$ 的权重系数 $alpha {_{m}}$ ：（这里的对数是自然对数）

一般情况下 em 的取值应该小于0.5，因为若不进行学习随机分类的话，由于是二分类错误率等于0.5，当进行学习的时候，错误率应该略低于0.5。当 em 减小的时候 am 的值增大，而我们希望得到的是分类误差率越小的弱分类器的权值越大，对最终的预测产生的影响也就越大，所以将弱分类器的权值设为该方程式从直观上来说是合理地，具体的证明 am 为上式请继续往下读

（d）更新训练数据集的样本权值分布：

对于二分类，弱分类器 $G{_{m}}(x)$ 的输出值取值为｛-1，1｝， $y{_{i}}$ 的取值为｛-1，1｝，所以对于正确的分类 $y{_{i}}G{_{m}}(x)>0$ ，对于错误的分类 $y{_{i}}G{_{m}}(x)<0$ ，由于样本权重值在[0，1]之间，当分类正确时 $w{_{m+1,i}}$ 取值较小，而分类错误时 $w{_{m+1,i}}$ 取值较大，而我们希望得到的是权重值高的训练样本点在后面的弱学习器中会得到更多的重视，所以该上式从直观上感觉也是合理地，具体怎样合理，请往下读

其中， $Z{_{m}}$ 是规范化因子，主要作用是将 $W{_{mi}}$ 的值规范到0-1之间，使得 $sum_{i=1}^{N}{W{_{mi}}} = 1$ 。

（3）上面我们介绍了弱学习器的权重系数α如何计算，样本的权重系数W如何更新，学习的误差率e如何计算，接下来是最后一个问题，各个弱学习器采用何种结合策略了，AdaBoost对于分类问题的结合策略是加权平均法。如下，利用加权平均法构建基本分类器的线性组合：

得到最终的分类器：

以上就是对于AdaBoost分类问题的介绍，接下来是对AdaBoost的回归问题的介绍

1.2AdaBoost回归问题

AdaBoost回归问题有许多变种，这里我们以AdaBoost R2算法为准

（1）我们先看看回归问题的误差率问题，对于第m个弱学习器，计算他在训练集上的最大误差（也就是每次训练后，计算预测值和真实值的差的最大值）：

$E{_{m}}=max|y{_{i}}-G{_{m}}(x{_{i}})|$ $i=1,2,...,N$

然后计算每个样本的相对误差：（计算相对误差的目的是将误差规范化到[0，1]之间）

$e{_{mi}}=frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}}$ ，显然 $0leq e{_{mi}}leq 1$

这里是误差损失为线性时的情况，如果我们用平方误差，则 $e{_{mi}}=frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}^2}^2$ ，如果我们用指数误差，则 $e{_{mi}}=1-exp(frac{-y{_{i}}+G{_{m}}(x{_{i}})}{E{_{m}}})$

最终得到第k个弱学习器的误差率为：

$e{_{m}}=sum_{i=1}^{N}{w{_{mi}}e{_{mi}}}$ ，表示每个样本点的加权误差的总和即为该弱学习器的误差。

（2）我们再来看看弱学习器的权重系数α，如下公式：

$alpha {_{m}}=frac{e{_{m}}}{1-e{_{m}}}$

（3）对于如何更新回归问题的样本权重，第k+1个弱学习器的样本权重系数为：

$w{_{m+i,i}}=frac{w{_{mi}}}{Z{_{m}}}alpha {_{m}}^{1-e{_{mi}}}$

其中 $Z{_{k}}$ 是规范化因子： $Z{_{m}}=sum_{i=1}^{N}{w{_{mi}}alpha {_{m}}^{1-e{_{mi}}}}$

（4）最后是结合策略，和分类问题不同，回归问题的结合策略采用的是对加权弱学习器取中位数的方法，最终的强回归器为：

$G(x)=sum_{m=1}^{M}{g(x)lnfrac{1}{alpha {_{m}}}}$ ，其中 $g(x)$ 是所有 $alpha {_{m}}G{_{m}}(x)$ 的中位数（m=1，2，...，M）。

这就是AdaBoost回归问题的算法介绍，还有一个问题没有解决，就是在分类问题中我们的弱学习器的权重系数 $alpha {_{m}}$ 是如何通过计算严格的推导出来的。

1.3AdaBoost前向分步算法

在上两节中，我们介绍了AdaBoost的分类与回归问题，但是在分类问题中还有一个没有解决的就是弱学习器的权重系数 $alpha {_{m}}=frac{1}{2}ln{frac{1-e{_{m}}}{e{_{m}}}}$ 是如何通过公式推导出来的。这里主要用到的就是前向分步算法，接下来我们就介绍该算法。

从另一个角度讲，AdaBoost算法是模型为加法模型，损失函数为指数函数，学习算法为前向分步算法时的分类问题。其中，加法模型表示我们的最终得到的强分类器是若干个弱分类器加权平均得到的，如下：

$f(x)=sum_{m=1}^{M}{alpha {_{m}}G{_{m}}(x)}$

损失函数是指数函数，如下：

$L(y,f(x))=exp(-yf(x))$

学习算法为前向分步算法，下面就来介绍AdaBoost是如何利用前向分布算法进行学习的：

（1）假设进过m-1轮迭代前向分布算法已经得到 $f{_{m-1}}(x)$ ：

$f{_{m-1}}=f{_{m-2}}(x)+alpha {_{m-1}}G{_{m-1}}(x)$

$=alpha {_{1}}G{_{1}}(x)+...+alpha {_{m-1}}G{_{m-1}}(x)$

在第m轮的迭代得到 $alpha {_{m}}$ ， $G{_{m}}(x)$ 和 $f{_{m}}(x)$ .

$f{_{m}}(x)=f{_{m-1}}(x)+alpha {_{m}}G{_{m}}(x)$

目标是使前向分布算法得到的 $alpha {_{m}}$ 和 $G{_{m}}(x)$ 使 $f{_{m}}(x)$ 在训练数据集T上的指数损失最小，即

$(alpha {_{m}},G{_{m}}(x))=arg underset{alpha ,G}{min}sum_{i=1}^{N}exp(-y{_{i}}(f{_{m-1}}(x{_{i}})+alpha G(x{_{i}})))$

$=argunderset{alpha ,G}{min}sum_{i=1}^{N}ar{w}{_{mi}}exp(-y{_{i}}alpha G(x{_{i}}))$ ${color{Red} (1)}$

上式即为我们利用前向分步学习算法得到的损失函数。其中， $ar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x{_{i}}))$ 。因为 $ar{w}{_{mi}}$ 既不依赖 $alpha$ 也不依赖于G，所以在第m轮迭代中与最小化无关。但 $ar{w}{_{mi}}$ 依赖于 $f{_{m-1}}(x)$ ，随着每一轮的迭代而发生变化。

上式达到最小时所取的 $alpha ^{_{*}}{_{m}}$ 和 $G ^{_{*}}{_{m}}(x)$ 就是AdaBoost算法所得到的 $alpha {_{m}}$ 和 $G{_{m}}(x)$ 。

（2）首先求分类器 $G ^{_{*}}{_{m}}(x)$ ：

我们知道，对于二分类的分类器G(x)的输出值为-1和1， $y{_{i}} eq G{_{m}}(x{_{i}})$ 表示预测错误， $y{_{i}}= G{_{m}}(x{_{i}})$ 表示正确，每个样本点都有一个权重值，所以对于一个弱分类器的输出则为： $G{_{m}}(x)=sum_{i=1}^{N}ar{w}{_{mi}}I(y{_{i}} eq G{_{m}}(X{_{i}}))$ ，我们的目标是使损失最小化，所以我们的具有损失最小化的第m个弱分类器即为：

$G^{_{*}}{_{m}}(x)=arg underset{G}{min}sum_{i=1}^{N}ar{w}{_{mi}}I(y{_{i}} eq G(x{_{i}}))$ 其中， $ar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x{_{i}}))$

为什么用 $I(y{_{i}} eq G(x{_{i}}))$ 表示一个弱分类器的输出呢？因为我们的AdaBoost并没有限制弱学习器的种类，所以它的实际表达式要根据使用的弱学习器类型来定。

此分类器即为Adaboost算法的基本分类器 $G{_{m}}(x)$ ，因为它是使第m轮加权训练数据分类误差率最小的基本分类器。

（3）然后就是来求 $alpha ^{_{*}}{_{m}}$ ，

将 $G ^{_{*}}{_{m}}(x)$ 代入损失函数（1）式中，得：

$alpha {_{m}}=sum_{i=1}^{N}ar{w}{_{mi}}exp(-y{_{i}}alpha{_{m}} G^{_{*}}{_{m}}(x{_{i}}))$

我们的目标是最小化上式，求出对应的 $alpha ^{_{*}}{_{m}}$ 。

$sum_{i=1}^{N}ar{w}{_{mi}}exp(-y{_{i}}alpha{_{m}} G^{_{*}}{_{m}}(x{_{i}}))$

$=sum_{y{_{i}}=G{_{m}}(x{_{i}})}ar{w{_{mi}}}e^{_{-alpha }}+sum_{y{_{i}} eq G{_{m}}(x{_{i}})}ar{w{_{mi}}}e^{_{alpha }}$

$=e^{_{-alpha }}sum_{y{_{i}}=G{_{m}}(x{_{i}})}ar{w}{_{mi}}+e^{_{alpha }}sum_{y{_{i}} eq G{_{m}}(x{_{i}})}ar{w}{_{mi}}$

$=e^{_{-alpha }}(sum_{i=1}^{N}ar{w}{_{mi}}-sum_{y{_{i}} eq G{_{m}}(x{_{i}})}ar{w}{_{mi}})+e^{_{alpha }}sum_{y{_{i}} eq G{_{m}}(x{_{i}})}ar{w}{_{mi}}$

$=(e^{_{alpha }}-e^{_{-alpha }})sum_{y{_{i}} eq G{_{m}}(x{_{i}})}ar{w}{_{mi}}+e^{_{-alpha }}sum_{i=1}^{N}ar{w}{_{mi}}$

$=(e^{_{alpha }}-e^{_{-alpha }})sum_{i=1}^{N}ar{w}{_{mi}}I(y{_{i}} eq G{_{m}}(x{_{i}}))+e^{_{-alpha }}sum_{i=1}^{N}ar{w}{_{mi}}$ ${color{Red} (2)}$

由于， $e{_{m}}=frac{sum_{i=1}^{N}ar{w}{_{mi}}I(y{_{i}} eq G{_{m}}(x{_{i}}))}{sum_{i=1}^{N}ar{w}{_{mi}}}$

注意：这里我们的样本点权重系数 $ar{w}{_{mi}}$ 并没有进行规范化，所以 $sum_{i=1}^{m}ar{w}{_{mi}} eq 1$

（2）式为： $(e^{_{alpha }}-e^{_{-alpha }})e{_{m}}sum_{i=1}^{N}ar{w}{_{mi}}+e^{_{-alpha }}sum_{i=1}^{N}ar{w}{_{mi}}$

则我们的目标是求：

$alpha {_{m}}=argunderset{alpha }{min}(e^{_{alpha }}-e^{_{-alpha }})e{_{m}}sum_{i=1}^{N}ar{w}{_{mi}}+e^{_{-alpha }}sum_{i=1}^{N}ar{w}{_{mi}}$

上式求 $alpha$ 偏导，并令偏导等于0，得：

$(e^{_{alpha }}+e^{_{-alpha }})e{_{m}}sum_{i=1}^{N}ar{w}{_{mi}}-e^{_{-alpha }}sum_{i=1}^{N}ar{w}{_{mi}}=0$ ，进而得到：

$(e^{_{alpha }}+e^{_{-alpha }})e{_{m}}-e^{_{-alpha }}=0$ ，求得： $alpha ^{_{*}}{_{m}}=frac{1}{2}lnfrac{1-e{_{m}}}{e{_{m}}}$ ，其中 $e{_{m}}$ 为误差率:

$e{_{m}}=frac{sum_{i=1}^{N}ar{w}{_{mi}}I(y{_{i}} eq G{_{m}}(x{_{i}}))}{sum_{i=1}^{N}ar{w}{_{mi}}}=sum_{i=1}^{N}w{_{mi}}I(y{_{i}} eq G(x{_{i}}))$

（4）最后看样本权重的更新。

利用前面所讲的 $f{_{m}}(x)=f{_{m-1}}(x)+alpha {_{m}}G{_{m}}(x)$ ，以及权值 $ar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x))$

可以得到如下式子：

$ar{w}{_{m+1,i}}=ar{w}{_{mi}}exp(-y{_{i}}alpha {_{m}}G{_{m}}(x{_{i}}))$

这样就得到了我们前面所讲的样本权重更新公式。

1.4 AdoBoost算法的正则化

为了防止过拟合，AdaBoost算法中也会加入正则化项，这个正则化项我们称之为步长也就是学习率。定义为v，对于前面的弱学习器的迭代有：

$f{_{m}}(x)=f{_{m-1}}(x)+alpha {_{m}}G{_{m}}(x)$

加入正则化项，就变成如下：

$f{_{m}}(x)=f{_{m-1}}(x)+valpha {_{m}}G{_{m}}(x)$

v的取值范围为(0，1]。对于同样的训练集学习效果，较小的v意味着我们需要更多的弱学习器的迭代次数。通常我们用学习率和迭代最大次数一起来决定算法的拟合效果。

到这里，我们的AdaBoost算法介绍完毕。

二、AdaBoost算法流程描述

2.1 AdaBoost分类问题的算法流程描述

关于AdaBoost的分类问题，sklearn中采用的是SAMME和SAMME.R算法，SAMME.R算法是SAMME算法的变种。sklearn中默认采用SAMME.R，原因是SAMME.R算法比SAMME算法收敛速度更快，用更少的提升迭代次数实现了更低的测试误差。接下来我们先介绍AdaBoost的分类算法流程，可以将二元分类算法视为多元分类算法的一个特例。

2.1.1SAMME算法流程描述：

（1）初始化样本点的权重为：

$D_{1}=(w_{11},...,w_{1i},...,w_{1N}),$ $w_{1i}=1/N,$ $i=1,2,...,N$

（2）对于m=1,2,..,M

（a）使用带有权重的样本来训练一个弱学习器 $G{_{m}}(x)$ ;

（b）计算弱分类器 $G{_{m}}(x)$ 的分类误差率：

（c）计算弱分类器的系数：

其中，K表示K元分类，可以看出当K=2时， $ln(K-1)=0$ ，余下的 $alpha {_{m}}$ 与我们二元分类算法所描述的弱分类器系数一致。

（d）更新样本的权重分布：

（3）构建最终的强分类器：

2.1.2 SAMME.R算法流程描述：

输入：样本集 $T=left { (x{_{1}},y{_{1}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) ight }$ ，输出为 $left { -1,1 ight }$ ，弱分类器的迭代次数为M，样本点的个数为N。

输出：最终的强分类器 $G(x)$

（1）初始化样本点的权重为：

$D_{1}=(w_{11},...,w_{1i},...,w_{1N}),$ $w_{1i}=1/N,$ $i=1,2,...,N$

（2）对于m=1,2,..,M

（a）使用带有权重的样本来训练一个弱学习器 $G{_{m}}(x)$ ;

（b）获得带有权重分类的概率评估：

$P{_{mk}}(x{_{i}})=Prob{_{w}}(c=k|x{_{i}})$ ，

其中 $P{_{mk}}(x{_{i}})$ 表示第m个弱学习器将样本 $x{_{i}}$ 分为第k类的概率。k=1，2，...，K，K表示分类的类别个数。

（c）使用加权概率推导出加法模型的更新，然后将其应用于数据：

$h{_{mk}}(x)=(K-1)(logP{_{mk}}(x)-frac{1}{K}sum_{ar{k}=1}^{K}logP{_{mar{k}}}(x))$ ， $k=1,2,...,K$

（d）更新样本点权重系数：

（e）标准化样本点权重 $w$ ;

（3）构建最终的强分类器：

$G(x)=sign(argunderset{K}{max}sum_{m=1}^{M}h{_{mk}}(x))$ ，表示使 $sum_{m=1}^{M}h{_{mk}}(x))$ 最大的类别即为我们所预测的类别。

2.2AdaBoost回归问题的算法流程描述

在sklearn中，回归使用的算法为 AdaBoost.R2算法，具体的流程描述如下：

输入：样本集 $T=left { (x{_{1}},y{_{1}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) ight }$ ，输出为 $left { -1,1 ight }$ ，弱分类器的迭代次数为M，样本点的个数为N。

输出：最终的强分类器 $G(x)$

（1）初始化样本点的权重为：

$D_{1}=(w_{11},...,w_{1i},...,w_{1N}),$ $w_{1i}=1/N,$ $i=1,2,...,N$

（2）对于m=1,2,..,M

（a）使用具有权重 $D{_{m}}$ 的样本集来训练数据，得到弱学习器 $G{_{m}}(x)$

（b）计算训练集上的最大误差

$E{_{k}}=max|y{_{i}}-G{_{m}}(x{_{i}})|$ ， $i=1,2,...,N$

（c）计算每个样本点的相对误差：

如果是线性误差：则 $e{_{mi}}=frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}}$

如果是平方误差，则 $e{_{mi}}=frac{(y{_{i}}-G{_{m}}(x{_{i}}))^2}{E{_{m}}^2}$

如果是指数误差，则 $e{_{mi}}=1-exp(frac{-|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}})$

（d）计算回归误差率：

$e{_{m}}=sum_{i=1}^{N}w{_{mi}}e{_{mi}}$

（c）计算弱学习器的系数：

$alpha {_{m}}=frac{e{_{m}}}{1-e{_{m}}}$

（d）更新样本集的权重分布：

$w{_{m+1,i}}=frac{w{_{mi}}}{Z{_{m}}}alpha {_{m}}^{1-e{_{mi}}}$ ，其中 $Z{_{m}}$ 是规范化因子， $Z{_{m}}=sum_{i=1}^{N}w{_{mi}}alpha {_{m}}^{1-e{_{mi}}}$

（3）构建最终的强学习器：

$G(x)=sum_{m=1}^{M}{g(x)lnfrac{1}{alpha {_{m}}}}$ ，其中 $g(x)$ 是所有 $alpha {_{m}}G{_{m}}(x)$ 的中位数（m=1，2，...，M）。

三、AdaBoost算法的优缺点

3.1 优点

（1）不容易发生过拟合；

（2）由于AdaBoost并没有限制弱学习器的种类，所以可以使用不同的学习算法来构建弱分类器；

（3）AdaBoost具有很高的精度；

（4）相对于bagging算法和Random Forest算法，AdaBoost充分考虑的每个分类器的权重；

（5）AdaBoost的参数少，实际应用中不需要调节太多的参数。

3.2 缺点

（1）AdaBoost迭代次数也就是弱分类器数目不太好设定，可以使用交叉验证来进行确定。

（2）数据不平衡导致分类精度下降。

（3）训练比较耗时，每次重新选择当前分类器最好切分点。

（4）对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。