Boosting/AdaBoost —— 多级火箭助推

Boosting（提升）

Boosting 是一类算法的统称，它们的主要特点是使用一组弱分类器来构造一个强分类器。弱分类器意思是预测的准确性不高，可能只比随便乱猜稍好一点。强分类器指准确性较高的分类器。简单来说的话，Boosting 可以理解为俗话所说的“三个臭皮匠顶个诸葛亮”。

Boosting 并没有规定具体的实现方法，不过大多数实现算法会有以下特点：

1. 通过迭代生成多个弱分类器
2. 将这些弱分类器组合成一个强分类器，通常会根据各弱分类器的准确性设置相应的权重
3. 每生成一个弱分类器，会重新设置训练样本的权重，被错误分类的样本会增加权重，正确分类的样本会减少权重，即后续生成的分类器将更多的关注之前分错的样本。（不过也有些算法会对总是分错的样本降低权重，视之为噪音）

Boosting家族有一系列算法，常见的比如 AdaBoost、GDBT、XGBoost，还有 BrownBoost、LogitBoost、RankBoost 等等。

Bagging/Boosting/Stacking

顺便说一下几种集成学习（Ensemble）方法的区别，集成方法是指构造多种模型，并通过一定的方法组合起来，综合下来的预测效果高于单个模型的预测效果。

集成学习有几种方式，Boosting原理 中有几张图很直观，借用在这里。

Bagging/投票
Bagging 是一种投票机制，先生成多个模型，然后让它们投票决定最终的结果。典型的比如随机森林算法。

image

Boosting/迭代提升
Boosting 是迭代生成模型，每个模型要基于上一次模型的效果。每次迭代，模型会关注之前的模型预测效果不好的那些样本。本文下面要讲述的就属于这类算法。

image

Stacking/多层叠加
Stacking 是多层叠加的意思。也是先生成多个模型，但是用这些模型的预测结果作为下一层模型的输入，有点像多层神经网络的意思。

image

AdaBoost（Adaptive Boosting/自适应增强）

AdaBoost 是上述 Boosting 思想的一种具体实现算法，一般采用决策树作为弱分类器。那么看一下 AdaBoost 是如何实现迭代生成一系列弱分类器、调整样本权重，以及设置弱分类器权重从而构造出一个强分类器的。

AdaBoost 算法步骤

以离散型AdaBoost(Discrete AdaBoost) 为例：
假设有N个样本 (x1,y1), (x2,y2)…(xN,yN)，其中 y1...yN ∈{-1, 1}，即二分类问题。

1. 设每个样本初始权重相同，都是 1/N。即各样本的权重 w1...wN = 1/N
2. 训练分类器时Loss函数采用指数误差 image

3. 开始进行T次迭代（每次生成一个弱分类器ht，t=1...T）
   3.1 对第t次迭代，使用样本（考虑各样本权重为(w1...wN)）训练得到一个弱分类器ht。ht预测的输出也是 {-1, 1}。
   

   3.2 ht对样本分类的错误率为 image ，即所有误分类样本（ht(xi) != yi）的权重的和。
   3.3 计算该分类器 ht 在最终的强分类器中的权重 image

   。这个公式意味着ht的预测准确率越高，在强分类器中的权重越大（下文还有说明）。
   

   3.4 迭代中的强分类器 image
   3.5 更新样本权重，对所有样本计算 image ，其中 image 是 第t轮迭代（当前迭代）第 i 个样本的权重， image 是该样本下一轮(t+1)的权重。这个公式意味着正确的样本将减少权重，错误的样本将增加权重（下文还有说明）。
   3.6 将所有样本的权重重新归一化，即使得所有样本的权重和为1。可知 (t+1)轮所有样本权重和为 image ，令 image ，即可使得 image
   3.7 t = t + 1，进行下一轮迭代
4. 迭代完成后，得到强分类器 image

   ，sign是符号函数，使得输出是 {-1, 1}。

上面的步骤中，我们讨论几个问题：

1. 步骤 3.3 中，分类器权重 image

   ，该函数图像如下图所示。当错误率 εt 越小，系数 αt 越大，意味着误差小（准确性高）的分类器，在最后的强分类器中有更大的权重。反之，当误差 εt 越大，系数 αt 越小，即在强分类器中的权重较小。另外可以看出当分类器的 错误率 < 0.5 时，αt > 0；如果分类器的 错误率 > 0.5，意味着该分类器预测反了，此时 αt < 0 将该分类器的预测结果反过来使用。

image

2. 步骤 3.5 中，样本权值更新 image 。这里面 yi 是样本的标签，ht(xi) 是分类器对 xi 的预测，如果预测正确，则两者都等于1 或都等于 -1，所以乘积为1，如果预测错误，则乘积为 -1。公式可以改写为 image ，这个分段函数的指数部分的图像如下。如果分类器的 αt > 0，我们看函数图像中 > 0 的部分，如果分类正确，指数函数的值将 < 1（黄线），乘以权重后将减少权重的值，即分类正确的样本将减少权重；如果分类错误，指数函数的值将 > 1（蓝线），即分类错误的样本将增加权重。如果 αt < 0，看函数图像中 < 0 的部分，指数函数的值反过来了，但此时分类器也预测反了，所以结果依然是正确的样本将减少权重，错误的样本将增加权重。

image

AdaBoost的优点

AdaBoost 几乎可以“开箱即用”，因为它是自适应的，对参数不会太敏感。
它在一定程度上可以避免“维度灾难”，我理解主要是 AdaBoost 只需要构造弱分类器，比如决策树的话，可以只使用那些比较重要的特征，树的深度很浅，运行速度较快。
同时多个弱分类器的集成还能提升模型的预测能力。

AdaBoost的缺点

比较明显的一点是对噪音和异常数据比较敏感，因为算法中会对分类错误的样本持续提升关注。

AdaBoost公式推导

前面算法中直接给了几个公式，比如分类器的权重 α 和 样本权重更新公式，为什么采用这样的计算公式，我们来推导一下。

假设有N个样本 (x1,y1), (x2,y2)…(xN,yN)，其中 y1...yN ∈{-1, 1}，即二分类问题。有一系列分类器k 可以线性组合成一个强分类器C，在第 m-1 次迭代，分类器：

image

这里C是强分类器，k是弱分类器，α 是 k在 C中的权重，下标 1...m-1 是迭代的轮次。注意这里所用的记号与前面算法步骤中的公式的记号有不同，注意各自的含义。

接下来第m轮分类器

image

因为是采用迭代的方法逐个构造分类器k，所以在第m轮，可以认为 C(m-1) 已经是确定的了，现在需要的是找到一个好的 km 及其系数 αm。

对分类器 Cm 采用指数型误差

image
令 m=1时 image ，m>1时 image ，上式可写为
image 如果km预测正确，则 image ，如果km预测错误，则 image ，因此上式再分裂为预测正确和预测错误的项：
image (公式1)
image

(公式2)

我们希望找到合适的 km 和 αm 使得 E最小。

1. 先考虑 km。在公式2中，只有 image 的值受 km 的影响，也就是说，要最小化E，对于km来说，就是要构造一个最小化 image 的分类器 km。

2. 考虑 αm。用公式1对 αm 求导，当导数 = 0 时 E有最小值。

   
   image
   image
   image
   image 如果令错误率 image
   则 image

3. 另外看下更新样本权重。
   

   由于 image ，于是 image
   image
   image
   image
   image
   所以 image

参考

深入浅出ML之Boosting家族
维基百科 —— Boosting (machine learning)
维基百科 —— AdaBoost