集成学习记录(bagging, random forest, GBDT, XGBoost, adaboost)

一、综述

最近学习从bagging到xgboost过了一遍，效果是还是和之前一样，看的时候似懂非懂，可又不知道问题出在哪里。下面就做个笔记，如果有人看到给点建议互相交流学习更好啦！
言归正传，集成学习（ensemble learning），顾名思义通过构建并结合多个学习器来完成学习任务。本次主要是从bagging，随机森林，boosting（adaboost， GDBT, XGBOOST）几个部分分别讲解。如果有不对的地方欢迎指正。

二、Bagging，Random Forest及结合策略

2.1 Bagging

Bagging是一种并行式的集成学习方法，即基学习器的训练之间没有前后顺序可以同时进行，Bagging使用“有放回”采样的方式选取训练集，对于包含m个样本的训练集，进行m次有放回的随机采样操作，从而得到m个样本的采样集，这样训练集中有接近36.8%的样本没有被采到如公式（1）。按照相同的方式重复进行，我们就可以采集到T个包含m个样本的数据集，从而训练出T个基学习器，最终对这T个基学习器的输出进行结合。
$\lim _{m \rightarrow \infty}\left(1-\frac{1}{m}\right)^{m} \mapsto \frac{1}{e} \approx 0.368 \tag{2.1}$
Bagging算法的流程如下所示（借用西瓜书的图）：
集成学习记录(bagging, random forest, GBDT, XGBoost, adaboost)
Bagging的原理如图：

2.2 Random Forest

随机森林（Random Forest）是Bagging的一个拓展体，它的基学习器固定为决策树，多棵树也就组成了森林，而“随机”则在于选择划分属性的随机，随机森林在训练基学习器时，也采用有放回采样的方式添加样本扰动，同时它还引入了一种属性扰动，即在基决策树的训练过程中，在选择划分属性时，RF先从候选属性集中随机挑选出一个包含K个属性的子集，再从这个子集中选择最优划分属性，一般推荐K=log2（d）。
这样随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，从而进一步提升了基学习器之间的差异度。相比决策树的Bagging集成，随机森林的起始性能较差（由于属性扰动，基决策树的准确度有所下降），但随着基学习器数目的增多，随机森林往往会收敛到更低的泛化误差。同时不同于Bagging中决策树从所有属性集中选择最优划分属性，随机森林只在属性集的一个子集中选择划分属性，因此训练效率更高。
集成学习记录(bagging, random forest, GBDT, XGBoost, adaboost)
随机森林步骤：

step1：以Bagging从样本中选取n个样本。
step2：从所有的属性d中随机选择个属性(k<d)，然后从k个属性中选择最佳分割属性作为节点建立CART决策树。
step3：重复上面两步骤M次，建立M棵CART决策树。
step4：这M棵决策树构成随机森林，将得到的结果进行投票得到最终结果。

2.3 结合策略

结合策略指的是在训练好基学习器后，如何将这些基学习器的输出结合起来产生集成模型的最终输出，下面将介绍一些常用的结合策略：

2.3.1 平均法（回归问题）

简单平均法：
$H(\boldsymbol{x})=\frac{1}{T} \sum_{i=1}^{T} h_{i}(\boldsymbol{x})\tag{2.2}$
加权平均法：

易知简单平均法是加权平均法的一种特例，加权平均法可以认为是集成学习研究的基本出发点。由于各个基学习器的权值在训练中得出，一般而言，在个体学习器性能相差较大时宜使用加权平均法，在个体学习器性能相差较小时宜使用简单平均法。

2.3.2 投票法（分类问题）

绝对多数投票法（必须占一半以上）
$H(\boldsymbol{x})=\left\{\begin{array}{ll}{c_{j},} & {\text { if } \sum_{i=1}^{T} h_{i}^{j}(\boldsymbol{x})>0.5 \sum_{k=1}^{N} \sum_{i=1}^{T} h_{i}^{k}(\boldsymbol{x})} \\ {\text { reject, }} & {\text { otherwise. }}\end{array}\right.\tag{2.3}$
相对多数投票法（票数最多即可）
$H(\boldsymbol{x})=c_{\arg \max } \sum_{i=1}^{T} h_{i}^{j}(\boldsymbol{x})\tag{2.4}$
加权投票法

绝对多数投票法（majority voting）提供了拒绝选项，这在可靠性要求很高的学习任务中是一个很好的机制。同时，对于分类任务，各个基学习器的输出值有两种类型，分别为类标记和类概率。

一些在产生类别标记的同时也生成置信度的学习器，置信度可转化为类概率使用，一般基于类概率进行结合往往比基于类标记进行结合的效果更好，需要注意的是对于异质集成，其类概率不能直接进行比较，此时需要将类概率转化为类标记输出，然后再投票。

2.3.3 学习法

学习法是一种更高级的结合策略，即学习出一种“投票”的学习器，Stacking是学习法的典型代表。Stacking的基本思想是：首先训练出T个基学习器，对于一个样本它们会产生T个输出，将这T个基学习器的输出与该样本的真实标记作为新的样本，m个样本就会产生一个mT的样本集，来训练一个新的“投票”学习器。投票学习器的输入属性与学习算法对Stacking集成的泛化性能有很大的影响，书中已经提到：投票学习器采用类概率作为输入属性，选用多响应线性回归（MLR）一般会产生较好的效果。
集成学习记录(bagging, random forest, GBDT, XGBoost, adaboost)

2.3.4 多样性（diversity）

在集成学习中，基学习器之间的多样性是影响集成器泛化性能的重要因素。因此增加多样性对于集成学习研究十分重要，一般的思路是在学习过程中引入随机性，常见的做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动。

数据样本扰动，即利用具有差异的数据集来训练不同的基学习器。例如：有放回自助采样法，但此类做法只对那些不稳定学习算法十分有效，例如：决策树和神经网络等，训练集的稍微改变能导致学习器的显著变动。
输入属性扰动，即随机选取原空间的一个子空间来训练基学习器。例如：随机森林，从初始属性集中抽取子集，再基于每个子集来训练基学习器。但若训练集只包含少量属性，则不宜使用属性扰动。
输出表示扰动，此类做法可对训练样本的类标稍作变动，或对基学习器的输出进行转化。
算法参数扰动，通过随机设置不同的参数，例如：神经网络中，随机初始化权重与随机设置隐含层节点数。

三、Boosting

3.1 Adaboost

AdaBoost是最著名的Boosting族算法。开始时，所有样本的权重相同，训练得到第一个基分类器。从第二轮开始，每轮开始前都先根据上一轮基分类器的分类效果调整每个样本的权重，上一轮分错的样本权重提高，分对的样本权重降低。之后根据新得到样本的权重指导本轮中的基分类器训练，即在考虑样本不同权重的情况下得到本轮错误率最低的基分类器。重复以上步骤直至训练到约定的轮数结束，每一轮训练得到一个基分类器。
adaboost步骤：
给定训练集数据集：
$\begin{array}{l}{D=\left\{\left(x^{(1)} \cdot y^{(1)}\right) . \cdots\left(x^{(N)}, y^{(N)}\right)\right\}} \\ {\quad x^{(i)} \in R^{n}, \quad y \in\{+1,-1\}}\end{array}\tag{3.1}$
$\text { For each data } x^{\text {(i) }} \text { , there is an associated weight w}^{(i)} \in R$

step1：初始化
$\begin{array}{l}{W=\left(w^{(1)}, w^{(2)}, \ldots w^{(N)}\right)} \\ {w^{(i)}=\frac{1}{N}, i=1,2 \cdots N}\end{array}\tag{3.2}$
step2：令 $k=1,2, \cdots \cdot k$ ，k表示迭代的次数，因为是串行嘛，也可以说是分类器序号，anyway。 $G_{k}(x)$ 是一个弱分类器，比如决策树，朴素贝叶斯等等。那么每一个 $G_{k}(x)$ 产生的error可以记为：
$\begin{aligned} e_{k} &=P\left(G_{k}\left(x^{(i)}\right) \neq y^{(i)}\right) \\ &=\sum_{i} w^{(i)} I\left(G_{k}\left(x^{(i)}\right) \neq y^{(i)}\right) \end{aligned}\tag{3.3}$
(这里不等号出问题，不知道怎么破。强迫症好想用手填上去mmp)
然后再用error去更新每个弱分类其权重更新公式： $\alpha_{k}=\frac{1}{2} \ln \left(\frac{1-e_{k}}{e_{k}}\right)\tag{3.4}$
step3：在第k个分类器进行训练后，更新每个数据权重，也可以理解为第k轮训练。
$\begin{aligned} w_{k}=&\left(w_{k}^{(1)} w_{k}^{(2)} \cdots w_{k}^{(N)}\right) \\ w_{k+1}^{(i)} &=\frac{w_{k}^{(i)}}{z_{k}} \exp \left(-\alpha_{k} y^{(i)} G_{k}\left(x^{(i)}\right)\right) \end{aligned}\tag{3.5}$
关于公式(3.5)里的 $\exp \left(-\alpha_{k} y^{(i)} G_{k}\left(x^{(i)}\right)\right)$ 可以理解为如下：
$\begin{array}{ll}{\text { if } y^{(i)}=G_{k}\left(x^{(i)}\right)} & {w_{k}^{(i)} \cdot \frac{1}{e^{\alpha_{k}}} } \\ {\text { if } y^{(i)} \neq G_{{k}}\left(x^{(i)}\right)} & {w_{k}^{(i)} \cdot e^{\alpha_{k}}}\end{array}\tag{3.6}$ 其实就是增大被分类错误的数据的权重，减少分类正确的权重。
公式（3.5）中的 $z_{k}$ 是归一化系数让最后所有的权重满足加和为1： $z_{k}=\sum_{i=1}^{N} w_{k}^{(i)} \exp \left(-\alpha_{k}y^{(i)} G_{k}\left(x^{(i)}\right)\right)\tag{3.7}$
step4：在最后的分类器中：
$\begin{array}{l}{f(x^{(i)})=\sum_{k=1}^{k} \alpha_{k} G_{k}\left(x^{(i)}\right)} \\ {G\left(x^{(i)}\right)=\operatorname{sign}\left(f\left(x^{(i)})\right)\right.}\end{array}\tag{3.8}$
其实，个人感觉，adaboost就是一个在训练过程中不断纠错的过程，反正我这么理解的（胡说的）给一张图感受下过程:

3.2 GBDT(Gradient Boosting Decision Tree)

Gradient Boosting是boosting中的一大类算法，其基本思想是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有的模型中。
其模型F定义为加法模型：
$F(x ; w)=\sum_{t=0}^{T} \alpha_{t} h_{t}\left(x ; w_{t}\right)=\sum_{t=0}^{T} f_{t}\left(x ; w_{t}\right)\tag{3.9}$
其中，x为输入样本，h为分类回归树，w是分类回归树的参数， $\alpha$ 是每棵树的权重。
GBDT通过最小化损失函数求解最优模型：
$F^{*}=\underset{F}{\arg \min } \sum_{i=0}^{N} L\left(y_{i}, F\left(x_{i} ; w\right)\right)\tag{3.10}$
具体算法步骤如图：
集成学习记录(bagging, random forest, GBDT, XGBoost, adaboost)
和线性回归的梯度下降法类似，只不过这里更新的思想变成了每次都让loss的输出的残差值变小，代价函数残差值越小，说明我们的分类器拟合的效果越好，那么问题就变成了怎么让loss变小呢？（大神们的脑洞的确我们get不到，）线性回归时只不过是通过迭代 $\theta_j$ 来使代价函数向着最小值方向走。这里只不过把函数 $F(x_i)$ 作为了自变量，即线性回归里的 $\theta_j$ 。其实整个GDBT和XGBoost类似，都是把整个函数作为自变量（叫自变量亲切点）。一张描述比较清楚的图：
集成学习记录(bagging, random forest, GBDT, XGBoost, adaboost)

3.3 XGBoost

终于到了重中之重，这里我看了两天才看明白，具体是，哈哈哈菜鸡毕竟是菜鸡，但是要实话实说啊。先看作者给的一个例子,其实作者就是想告诉大家，训练两个树，最后的输出结果加和就是结果了就是这么简单粗暴。。。
集成学习记录(bagging, random forest, GBDT, XGBoost, adaboost)
上面只是给出了最后决策阶段的方法，中间理论还需要推到一下，emmmm。给定数据集 $D=\{(x_i, y_i)\}$ ，我们需要使用k棵树进行预测：
$\hat{y}_{i}=\sum_{k=1}^{K} f_{k}\left(x_{i}\right), \quad f_{k} \in \mathcal{F}\tag{3.11}$
这里的 $\mathcal{F}$ 表示Space of functions containing all Regression trees，其实就是所有的回归树的和。
XGBoost的损失函数（这里叫目标函数）：
$O b j=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}\right)+\sum_{k=1}^{K} \Omega\left(f_{k}\right)\tag{3.12}$
其中 $\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}\right)$ 表示的training loss, $\sum_{k=1}^{K} \Omega\left(f_{k}\right)$ 表示正则化项，来控制拟合的空间维度。其实作者在这里详细表述了bias和variance之间的对抗关系，而作者的目标是如何让两者拼命地优化，既能控制过拟合，又能提高精度。(我就不仔细说了，大家可以看看原作者ppt，可以私信我，或者评论我看到就给发了哈)
接下来看看如何优化这个损失函数，因为我们的变量是trees，instead of just numerical vectors。所以我们不能直接使用类似SGD的方法进行优化。所以作者提出了一种叫做Additive Training的方法:
集成学习记录(bagging, random forest, GBDT, XGBoost, adaboost)
其中 $\hat{y}_{i}^{(t)}$ 表示Model at training round t， $\hat{y}_{i}^{(t-1)}$ 表示Keep functions added in previous round， $f_t(x_i)$ 表示New function。而我们需要做的就是在第t轮训练中确定f_t(x_i)$。