集成学习通过构建多个“好而不同”的弱学习器（基学习器）来共同完成学习任务，可以用于分类、回归等机器学习任务。根据个体学习器生成方式的不同，集成学习有两种形式，一种是基学习器之间的联系紧密，存在强依赖关系，必须串行训练，这种集成学习方法的代表是Boosting；另一种是基学习器之间没有强依赖关系，可以并行训练生成，这种集成学习方法的代表是Bagging和Ramdom Forest（随机森林）。这篇文章主要介绍Boosting方法，包括多用于处理分类问题的Adaboost，可分类可回归的GBDT提升树算法，GBDT在这几年的变形xgBoost算法。

1、Boosting方法

Boosting方法即提升树方法，其结构可以概括为：提升树=加法模型+前向分步算法。题目中提到的三种集成学习方法均可以理解为提升树模型+不同的损失函数构成的算法，AdaBoost是使用指数损失函数的分类算法，传统的GBDT是使用平方误差损失函数的回归算法（也可用于分类），xgBoost是GBDT的扩展。下面解释提升树的结构。

1.1 加法模型

集成学习的特点是训练多个基学习器，这些基学习器本身是弱学习器，它们可能仅仅对样本的某一个特征具有较好的拟合能力，那么最后怎样得到一个综合效果好的学习器呢？答案是把它们组合起来，这里的组合多指的是对所有训练出来的学习器进行线性求和，可以是直接相加（权重相同），也可以带权相加。提升模型可以表示为决策树的加法模型：

$f_{M} (x)=\sum_{m=1}^M\beta _{i} T(x_{i} ,\Theta _{m} )\\$

上式的含义即训练生成的M个基学习器（决策树）根据一定的权重比例相加，得到提升树模型。

1.2 前向分步算法

先理解一下前向分步算法提出的必要性：

在给定了数据集 $D=\left\{(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})\right\}$ 和损失函数的条件下，要得到效果最好的集成学习模型，需要使经验风险极小化（损失函数极小化），即：

$\min_{\beta _{m} ,\Theta _{m} } \sum_{i=1}^N L(y_{i} ,\sum_{m=1}^M \beta _{m} T(x_{i} ,\Theta _{m} ))\\$

由于直接计算这个最小化问题很复杂很复杂，所以我们换种思路，采取一种类似“贪心”的方法，从前往后，从第一个学习器开始，每一步仅仅优化一个学习器，这样逐步逼近最终的目标，就可以使问题变得可解。这就是前向分步算法的来历和思路。

前向分步算法的算法描述如下：

摘自李航《统计学习方法》p.144

这样，在M次循环中，逐个将每个基学习器的参数求解出来，最后得到加法模型。

2、 AdaBoost

基本思路：初始化第一个基学习器后，每次根据上一个学习器的训练结果改变样本分布，对上次分类错的样本投入更多关注（赋予更高权重），如此重复。AdaBoost算法的最终表示为：

$H(x)=\sum_{t=1}^T\beta _{t} h_{t}(x )\\$

其损失函数一般为指数损失函数： $\frac{1}{\vert D \vert } \sum_{m=1}^M e^{-f(x)h(x)}$ 。

从这个角度来看，AdaBoost=带权加法模型+前向分步算法+指数损失函数，其算法描述摘取了周志华《机器学习》的一段，如下：

摘自周志华《机器学习》p.174

3、 GBDT（梯度提升决策树）

这里的GBDT指一般的GBDT，GBDT还有很多变形，这里不讨论。GBDT也是一种提升树的算法策略，所以它依然采用加法模型和前向分步算法。在损失函数方面，一般采用的是平方误差（由于平方误差的一阶导数恰好是残差，所以我们说GBDT是拟合残差的一种方法）。综上可知，GBDT=加法模型+前向分步算法+平方损失函数。

3.1 提升树算法（回归问题）

回归问题的提升树算法描述如下：

摘自李航《统计学习方法》p.148

注意到算法8.3的2.(a)这一步是计算的残差，一般的来讲，这一步应该是计算损失函数的负梯度，如果损失函数采用的是平方损失函数，那么其负梯度恰好是残差。所以这个算法可以理解为采用平方损失函数的GBDT模型的算法流程。下面看一个《统计学习方法》中关于提升树算法的一个例子，有条件的可以直接打开该书的第149页：

摘自李航《统计学习方法》p.149

3.2 选择特征

GBDT可以处理回归问题和分类问题，采用的基学习器一般是CART TREE，选择这种二叉树作为弱学习器的一个充分条件就是CART TREE满足低方差、高偏差的要求，正好对应了GBDT是通过减小偏差来达到经验误差极小化。

GBDT如何选择特征，其实就是在问CART TREE是如何生成的。在前面的例8.2中，已经写出了选择特征的方式。选择特征包含选择哪个特征和选择该特征的哪个切分点两个问题。传统的GBDT采取的是暴力法，遍历M个特征，在每个特征中，再遍历每个可能的切分点，对于每一个切分点，计算这种切分方式产生的损失函数的值，两次遍历之后即可获得损失函数的最小值和它对应的切分特征、切分点。

3.3 GBDT处理分类问题

前面提到的算法、例子都是适用于回归问题，因为回归问题中的残差才是有意义的，代表损失函数的负梯度值，而分类问题中的残差是类别A-类别B，这是没有意义的。那么如何处理分类问题呢？答案是one-hot编码+多次回归。

假设处理的问题是一个二分类问题，那么对分类情况进行编码，如由 $y_{i} \in \left\{ 0,1 \right\}$ 改为 $y_{i} \in \left\{ [1,0],[0,1] \right\}$ ，如果是三分类问题就是 $y_{i} \in \left\{ [1,0,0],[0,1,0],[0,0,1] \right\}$ ，以此类推。以三分类（多分类）问题为例，在训练的时候，同时训练三个分类器，相应的样本也根据其类别在相应的维度上改为 $(x_{i} ,0)$ 或 $(x_{i} ,1)$ ，比如， $x_{i}$ 的实际分类结果是第1类，那么三个分类器得到的样本分别是 $(x_{i} ,1),(x_{i} ,0),(x_{i} ,0)$ 。最终可以通过softmax层产生概率，从而判断某个样本是属于哪一类。

3.4 其他问题

GBDT的加法模型不同于AdaBoost的一点是加权系数均为1，其加法模型的表达为：

$f_{M} (x)=\sum_{m=1}^M T(x_{i} ,\Theta _{m} )\\$

由于GBDT的基学习器是高偏差的，而且学习过程是不断的拟合残差，所以它的缺点很明显，就是对异常值特别敏感。

GBDT在实际运用的时候，有两种变体，即“Shrinkage”和“Bagging”。“Shrinkage”是一种正则化方法，为了防止过拟合，在每一步 $f_{m} (x)$ 产生时，不直接在上次训练的基础上加上残差，而是添加一个系数，即：

$f_{m} (x)=f_{m-1} (x)+\lambda *T(x,\Theta _{m}) \\$

这样会减缓拟合速率，也会防止过拟合的发生。

“Bagging”是加入随机性，在拟合残差的时候随机选择一部分残差进行拟合，而不是拟合所有样本残差，通常选择50%-60%的残差进行拟合。

4、xgBoost

xgBoost是由GDBT发展而来，所以在该算法的很多方面和GBDT有相似之处。xgBoost=加法模型+前向分步算法+损失函数（正则化项）。

4.1 模型推导

前面提到xgBoost也是应用了加法模型，所以其集成模型的表示为：

$\hat{y} _{i} =\sum_{m=1}^M f_{m} (x_{i})\\$

与GBDT最直观的不同，就是xgBoost使用的目标函数包含了正则化项，用于防止过拟合的发生，其目标函数（损失函数）为：

$L=\sum_{i}l(\hat{y} _{i},y_{i} )+\sum_{a}\Omega (f_{k} )\\\Omega (f_{k} )=\Upsilon *T+\frac{1}{2} \lambda \vert \vert \omega \vert \vert ^2$

其中， $\Omega (f_{k} )$ 为正则化项， $\Upsilon 、\lambda$ 为惩罚系数，用于调参， $T$ 为第K棵树的节点的总个数， $\omega$ 为每棵树叶子结点的score。在对此损失函数优化的过程中，采用的依然是前向分步算法，使用“贪心”的思想使得每一步得到的树都使当前的损失函数最小，这里不多赘述。

下面对损失函数展开推导，考虑平方误差损失函数：

$L=\sum_{i=1}^n l(y_{i},\hat{y}^{(t)} _{i})+\sum_{i=1}^T\Omega (f_{k} )\\=\sum_{i=1}^nl(y_{i},\hat{y} _{i}^{(t-1)}+f_{t}(x_i) )+\Omega (f_{t} )+constant\\=\sum_{i=1}^n(y_{i} -{y} _{i}^{(t-1)}-f_{t}(x_i) )^2+\Omega (f_{t} )+constant$

上面的公式中，第二行的 $constant$ 包括前t-1次的模型中的正则项，因为前t-1次的模型已经确定，所以正则项的值也是一个定值。第三行的 $y_{i} -{y} _{i}^{(t-1)}$ 即残差，对这个平方项按泰勒展开，并定义 $g_{i} =∂_{\hat{y} ^{(t-1)}} l(y_i,\hat{y} ^{(t-1)}),h_{i} =∂^2_{\hat{y} ^{(t-1)}} l(y_i,\hat{y} ^{(t-1)})$ ，消除常数项可得：

$L^t=\sum_{i=1}^N [g_if_t(x_i)+\frac{1}{2} h_if^2_t(x_i)]+\Omega (f_t)\\$

对这个公式进行细分，由于每棵树的所有样本不重复地分布在所有叶子结点上，所以引入叶子结点，定义 $I_j$ 为叶子结点上的样本集合。

摘自知乎参考文献5

这就是最终得到的第t棵树的损失函数表示。

4.2 特征选择与切分

xgBoost定义了自己的切分指标 $Gain$ :

$Gain=\frac{1}{2} [\frac{G^2_L}{H_L+\lambda } +\frac{G^2_R}{H_R+\lambda } -\frac{G^2_L+G^2_R}{H_L+H_R+\lambda } ]-\gamma\\$

结点分裂后计算Gain的值，值越大，表示目标函数减小的越多，其中 $\gamma$ 表示切分后模型复杂度的增量。使用这种方法去查找最优切分特征和最优切分点。类似于GBDT的特征切分，xgBoost的特征切分方法之一是暴力法，遍历所有特征，再遍历可能的切分点，选择最大的Gain值进行切分。时间复杂度为 $O(DK*nlogn)$ ，其中 $D$ 为特征维度， $K$ 为基学习器的个数， $nlogn$ 为对特征值排序的时间复杂度。这样做最明显的缺点就是当数据量很大时，可能出现计算缓慢、数据无法同时加载到内存等问题。尤其是当数据量大到无法一次性加载到内存中时，不断的访问内存极大地损耗了时间成本。xgBoost还有一种特征选择方法，称为“近似算法”。近似算法的思想是对样本集按每个特征的特征值分布进行分批操作，一个批次称为一个“桶(buckets)”，桶内的 $G_L、G_R$ 为内部样本的累加，这样的分批操作减少了候选切分点的个数，使得计算更简便。