Adaboost

Adaboost 算法详解

Adaboost 步骤概览

• 样本赋予权重1/N，得到第一个分类器。
• 计算该分类器的错误率，根据错误率赋予分类器权重（注意这里是分类器的权重）。
• 增加分错样本的权重，减小分对样本的权重（注意这里是样本的权重）。
• 然后再用新的样本权重训练数据，得到新的分类器。
• 多次迭代，直到分类器错误率为0或者整体弱分类器错误为0，或者到达迭代次数。
• 将所有弱分类器的结果加权求和，得到一个较为准确的分类结果。错误率低的分类器获得更高的决定系数，从而在对数据进行预测时起关键作用。

Adaboost 算法流程

给定一个样本数量为的数据集

%2C%20%5Cldots%2C%5Cleft(x%7Bm%7D%2C%20y%7Bm%7D%5Cright)%20%20%5Cright%20%5C%7D%0A#card=math&code=T%3D%20%5Cleft%20%5C%7B%5Cleft%28x%7B1%7D%2C%20y%7B1%7D%5Cright%29%2C%20%5Cldots%2C%5Cleft%28x%7Bm%7D%2C%20y%7Bm%7D%5Cright%29%20%20%5Cright%20%5C%7D%0A&id=m3UIm)

属于标记集合。

训练集的在第个弱学习器的输出权重为

%3D%5Cleft(w%7Bk%201%7D%2C%20w%7Bk%202%7D%2C%20%5Cldots%20w%7Bk%20m%7D%5Cright)%20%3B%20%5Cquad%20w%7B1%20i%7D%3D%5Cfrac%7B1%7D%7Bm%7D%20%3B%20i%3D1%2C2%20%5Cldots%20m%0A#card=math&code=D%28k%29%3D%5Cleft%28w%7Bk%201%7D%2C%20w%7Bk%202%7D%2C%20%5Cldots%20w%7Bk%20m%7D%5Cright%29%20%3B%20%5Cquad%20w%7B1%20i%7D%3D%5Cfrac%7B1%7D%7Bm%7D%20%3B%20i%3D1%2C2%20%5Cldots%20m%0A&id=c5vrH)

• 初始化训练样本的权值分布，每个训练样本的权值相同：

%3D%5Cleft(w%7B1%201%7D%2C%20w%7B1%202%7D%2C%20%5Cldots%20w%7B1%20m%7D%5Cright)%20%3B%20%5Cquad%20w%7B1%20i%7D%3D%5Cfrac%7B1%7D%7Bm%7D%20%3B%20i%3D1%2C2%20%5Cldots%20m%0A#card=math&code=D%281%29%3D%5Cleft%28w%7B1%201%7D%2C%20w%7B1%202%7D%2C%20%5Cldots%20w%7B1%20m%7D%5Cright%29%20%3B%20%5Cquad%20w%7B1%20i%7D%3D%5Cfrac%7B1%7D%7Bm%7D%20%3B%20i%3D1%2C2%20%5Cldots%20m%0A&id=IHtCA)

• 进行多轮迭代，产生个弱分类器。
  • 使用权值分布 的训练集进行训练，得到一个弱分类器

%20%3A%20%5Cquad%20%5Cchi%20%5Crightarrow%5C%7B-1%2C%2B1%5C%7D%0A#card=math&code=G_%7Bt%7D%28x%29%20%3A%20%5Cquad%20%5Cchi%20%5Crightarrow%5C%7B-1%2C%2B1%5C%7D%0A&id=gNP5b)

• 计算 #card=math&code=G_t%28x%29&id=q2PnV) 在训练数据集上的分类误差率（其实就是被 误分类样本的权值之和）:

%20%5Cneq%20y%7Bi%7D%5Cright)%3D%5Csum%7Bi%3D1%7D%5E%7Bm%7D%20w%7Bt%20i%7D%20I%5Cleft(G%7Bt%7D%5Cleft(x%7Bi%7D%5Cright)%20%5Cneq%20y%7Bi%7D%5Cright)%0A#card=math&code=e%7Bt%7D%3DP%5Cleft%28G%7Bt%7D%5Cleft%28x%7Bi%7D%5Cright%29%20%5Cneq%20y%7Bi%7D%5Cright%29%3D%5Csum%7Bi%3D1%7D%5E%7Bm%7D%20w%7Bt%20i%7D%20I%5Cleft%28G%7Bt%7D%5Cleft%28x%7Bi%7D%5Cright%29%20%5Cneq%20y_%7Bi%7D%5Cright%29%0A&id=hnqGq)

• 计算弱分类器 Gt(x) 在最终分类器中的系数(即分类器权重)

• 更新训练数据集的权值分布，用于下一轮t+1迭代

%3D%5Cleft(w%7Bt%2B1%2C1%7D%20%2Cw%7Bt%2B1%2C2%7D%20%2C%5Ccdots%20w%7Bt%2B1%2C%20i%7D%20%5Ccdots%2C%20w%7Bt%2B1%2C%20m%7D%5Cright)%0A#card=math&code=D%28t%2B1%29%3D%5Cleft%28w%7Bt%2B1%2C1%7D%20%2Cw%7Bt%2B1%2C2%7D%20%2C%5Ccdots%20w%7Bt%2B1%2C%20i%7D%20%5Ccdots%2C%20w%7Bt%2B1%2C%20m%7D%5Cright%29%0A&id=KryGI)

    其中 ![](https://g.yuque.com/gr/latex?Z_t#card=math&code=Z_t&id=zWT5i)是规范化因子，使得![](https://g.yuque.com/gr/latex?D(t%2B1)#card=math&code=D%28t%2B1%29&id=cUXss)成为一个概率分布（和为1）：

%5Cright)%0A#card=math&code=Z%7Bt%7D%3D%5Csum%7Bj%3D1%7D%5E%7Bm%7D%20w%7Bt%2Ci%7D%20%5Cexp%20%5Cleft%28-%5Calpha%7Bt%7D%20y%7Bi%7D%20G%7Bt%7D%5Cleft%28x_%7Bi%7D%5Cright%29%5Cright%29%0A&id=FpVc9)

• 集成个弱分类器为1个最终的强分类器：

%3D%5Coperatorname%7Bsign%7D%5Cleft(%5Csum%7Bt%3D1%7D%5E%7BT%7D%20%5Calpha%7Bt%7D%20G%7Bt%7D(x)%5Cright)%0A#card=math&code=G%28x%29%3D%5Coperatorname%7Bsign%7D%5Cleft%28%5Csum%7Bt%3D1%7D%5E%7BT%7D%20%5Calpha%7Bt%7D%20G%7Bt%7D%28x%29%5Cright%29%0A&id=GWweG)

算法面试题

？Adaboost分类模型的学习器的权重系数怎么计算的？

Adaboost是前向分步加法算法的特例，分类问题的时候损失函数指数函数。

1. 当基函数是分类器时，Adaboost的最终分类器是：
2. 目标是使前向分步算法得到的和#card=math&code=Gm%28x%29&id=A9rzl)使#card=math&code=f_m%28x%29&id=xQxWe)在训练数据集T上的指数损失函数最小，即 )%3Darg%20min%7B%5Calpha%2C%20G%7D%5Csum%7Bi%3D1%7D%5E%7BN%7Dexp%5B-y_i(f%7Bm-1%7D(xi)%2B%5Calpha%20G(x_i))%5D%0A#card=math&code=%28%5Calpha%2C%20G_m%28x%29%29%3Darg%20min%7B%5Calpha%2C%20G%7D%5Csum%7Bi%3D1%7D%5E%7BN%7Dexp%5B-y_i%28f%7Bm-1%7D%28xi%29%2B%5Calpha%20G%28x_i%29%29%5D%0A&id=mRsge)
   其中，%5D.#card=math&code=%5Chat%7Bw%7D%7Bmi%7D%3Dexp%5B-yi%20f%7Bm-1%7D%28xi%29%5D.&id=Lc5CI)为了求上式的最小化，首先计算#card=math&code=G_m%5E%2A%28x%29&id=Q1Vl8),对于任意的,可以转化为下式： )%0A#card=math&code=G%7Bm%7D%5E%2A%3Dargmin%7BG%7D%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D_%7Bmi%7DI%28y_i%20%5Cneq%20G%28x_i%29%29%0A&id=j4tc3)
   之后求,将上述式子化简，得到

%5D%0A%3D%20%5Csum%7By_i%20%3DG_m(x_i)%7D%5Chat%7Bw%7D%7Bmi%7De%5E%7B-%5Calpha%7D%2B%5Csum%7By_i%20%5Cneq%20G_m(x_i)%7D%7B%5Chat%7Bw%7D%7Bmi%7De%5E%7B%5Calpha%7D%7D%20%3D%20(e%5E%7B%5Calpha%7D%20-%20e%5E%7B-%20%5Calpha%7D)%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D%7Bmi%7DI(yi%20%5Cneq%20G(x_i))%20%2B%20e%5E%7B-%20%5Calpha%7D%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D%7Bmi%7D%0A#card=math&code=%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D%7Bmi%7Dexp%5B-y_i%20%5Calpha%20G%28x_i%29%5D%0A%3D%20%5Csum%7Byi%20%3DG_m%28x_i%29%7D%5Chat%7Bw%7D%7Bmi%7De%5E%7B-%5Calpha%7D%2B%5Csum%7By_i%20%5Cneq%20G_m%28x_i%29%7D%7B%5Chat%7Bw%7D%7Bmi%7De%5E%7B%5Calpha%7D%7D%20%3D%20%28e%5E%7B%5Calpha%7D%20-%20e%5E%7B-%20%5Calpha%7D%29%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D%7Bmi%7DI%28yi%20%5Cneq%20G%28x_i%29%29%20%2B%20e%5E%7B-%20%5Calpha%7D%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D_%7Bmi%7D%0A&id=F9Kd2)

将已经求得的#card=math&code=G_m%5E%2A%28x%29&id=HBsko)带入上式面，对求导并等于0，得到最优的.

其中是分类误差率:

)%7D%7B%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D%7Bmi%7D%7D%3D%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D%7Bmi%7DI(yi%20%5Cneq%20G_m(x_i))%0A#card=math&code=e_m%3D%5Cfrac%7B%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D%7Bmi%7DI%28y_i%20%5Cneq%20G_m%28x_i%29%29%7D%7B%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D%7Bmi%7D%7D%3D%5Csum%7Bi%3D1%7D%5E%7BN%7D%5Chat%7Bw%7D_%7Bmi%7DI%28y_i%20%5Cneq%20G_m%28x_i%29%29%0A&id=hyCNR)

Adaboost能否做回归问题？
输入: %2C(x_i%2C%20y_1)%2C…%2C(x_N%2C%20y_N)%7D#card=math&code=T%3D%7B%28x_i%2C%20y_1%29%2C%28x_i%2C%20y_1%29%2C…%2C%28x_N%2C%20y_N%29%7D&id=DACza), 弱学习器迭代次数。
输出：强分类器#card=math&code=f%28x%29&id=EBhQR).

1. 初始化权重， %3D%7Bw%7B11%7D%2Cw%7B12%7D%2C…%2Cw%7B1N%7D%7D%3B%20w%7B1i%7D%3D%5Cfrac%7B1%7D%7BN%7D%3B%20i%3D1%2C2%2C..%2CN%0A#card=math&code=D%281%29%3D%7Bw%7B11%7D%2Cw%7B12%7D%2C…%2Cw%7B1N%7D%7D%3B%20w%7B1i%7D%3D%5Cfrac%7B1%7D%7BN%7D%3B%20i%3D1%2C2%2C..%2CN%0A&id=Mhqe6)
2. 根据;
   • 学习得到#card=math&code=G_m%28x%29&id=S3MKi)
   • 计算训练集上最大误差 %7C%2C%20i%3D1%2C2%2C..%2CN%0A#card=math&code=E_m%3Dmax%7Cy_i-G_m%28x_i%29%7C%2C%20i%3D1%2C2%2C..%2CN%0A&id=OFzt8)
   • 计算样本的相对平方误差: )%5E2%7D%7BEm%5E2%7D%0A#card=math&code=e%7Bmi%7D%3D%5Cfrac%7B%28y_i-G_m%28x_i%29%29%5E2%7D%7BE_m%5E2%7D%0A&id=CJC6n)
   • 计算回归误差率:
   • 计算学习器系数:
   • 更新样本权重：
     其中是规范化因子，
3. 得到强学习器： %3D%5Csum%7Bm%3D1%7D%7BM%7DG%7Bm%7D%5E*(x)%0A#card=math&code=f%28x%29%3D%5Csum%7Bm%3D1%7D%7BM%7DG%7Bm%7D%5E%2A%28x%29%0A&id=sAVb1)

注: 不管是分类问题还是回归问题，根据误差改变权重就是Adaboost的本质，可以基于这个构建相应的强学习器。

为什么Adaboost方式能够提高整体模型的学习精度？

根据前向分布加法模型，Adaboost算法每一次都会降低整体的误差，虽然单个模型误差会有波动，但是整体的误差却在降低，整体模型复杂度在提高。

Adaboost的迭代次数(基学习器的个数)如何控制？

一般使用earlystopping进行控制迭代次数。

Adaboost算法中基学习器是否很重要，应该怎么选择基学习器？

sklearn中的adaboost接口给出的是使用决策树作为基分类器，一般认为决策树表现良好，其实可以根据数据的分布选择对应的分类器，比如选择简单的逻辑回归，或者对于回归问题选择线性回归。

训练过程中，每轮训练一直存在分类错误的问题，整个Adaboost却能快速收敛，为何？

每轮训练结束后，AdaBoost 会对样本的权重进行调整，调整的结果是越到后面被错误分类的样本权重会越高。而后面的分类器为了达到较低的带权分类误差，会把样本权重高的样本分类正确。这样造成的结果是，虽然每个弱分类器可能都有分错的样本，然而整个 AdaBoost 却能保证对每个样本进行正确分类，从而实现快速收敛。

Adaboost对噪声敏感吗？

在Adaboost训练过程中，Adaboost会使得难于分类样本的权值呈指数增长，训练将会过于偏向这类困难的样本，导致Adaboost算法易受噪声干扰。

Adaboost 的优缺点？

优点：能够基于泛化性能相当弱的的学习器构建出很强的集成，不容易发生过拟合。
缺点：对异常样本比较敏感，异常样本在迭代过程中会获得较高的权值，影响最终学习器的性能表现。

Adaboost和随机森林算法的异同点

随机森林和Adaboost算法都可以用来分类，它们都是优秀的基于决策树的组合算法。

• 相同之处
  • 二者都是Bootstrap自助法选取样本。
  • 二者都是要训练很多棵决策树。

• 不同之处

  • Adaboost是基于Boosting的算法，随机森林是基于Bagging的算法。
  • Adaboost后面树的训练，其在变量抽样选取的时候，对于上一棵树分错的样本，抽中的概率会加大。
  • 随机森林在训练每一棵树的时候，随机挑选了部分特征作为拆分特征，而不是所有的特征都去作为拆分特征。
  • 在预测新数据时，Adaboost中所有的树加权投票来决定因变量的预测值，每棵树的权重和错误率有关；随机森林按照所有树中少数服从多数树的分类值来决定因变量的预测值（或者求取树预测的平均值）。

    Adaboost和GBDT之间的区别？

• 相同点：

  Adaboost和GBDT都是通过减低偏差提高模型精度，都是前项分布加法模型的一种，

• 不同点:

  Adaboost每一个根据前m-1个模型的误差更新当前数据集的权重，学习第m个学习器；
  GBDT是根据前m-1个的学习剩下的label的偏差，修改当前数据的label进行学习第m个学习器，一般使用梯度的负方向替代偏差进行计算。

  参考资料：

1. 台湾清华大学李端兴教授2017年秋机器学习概论课程(CS 4602)PPT
2. 周志华 《机器学习》第8章 集成学习
3. July的博客
4. http://fornlp.com/周志华-《机器学习》-答案整理/