集成学习【二】

随机森林

1. 随机森林算法背后的思想是群体智慧的体现，它通过随机的 行采样 和 列采样 构造不同的训练集，建立一个决策树森林，利用加权平均方式或多数表决的方式得到最后的预测结果，能够并行学习，对噪声和异常数据具有很好的过滤作用，因此有很广泛的应用。

2. 随机森林的 行采样 和 列采样 都是为了减小模型之间的相关性使基学习器变得不同从而减小集成模型的方差。这种随机性会导致随机森林的偏差有所增加（相比于单棵决策树），因此随机森林的单棵树都会采用很深的决策树，并不进行剪枝操作，以减小每棵树的偏差，这使得每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从全部特征中选择部分来让每一棵决策树学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终再通过投票或平均得到结果。这也正是群体智慧的体现。

3. 随机森林是 Bagging 的一种扩展变体，与 Bagging 相比：

   • Bagging 中基学习器的 多样性 来自于样本扰动。> 样本扰动来自于对初始训练集的随机采样。

   • 随机森林中的基学习器的多样性不仅来自样本扰动，还来自属性扰动。

   • 传统决策树在选择划分属性时，是在当前结点的属性集合（假定有 $n$ 个属性）中选择一个最优属性。

   • 随机森林中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 $k$ 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。（通常建议 $k=log_2n$）

这使得最终集成的泛化性能可以通过个体学习器之间差异度的增加而进一步提升。

1. Extra Tree

Extra Tree与Random Forest的十分相似，其主要区别如下：

• RF会随机采样来作为子决策树的训练集，而Extra Tree每个子决策树采用原始数据集训练。

• RF在选择划分特征的阈值时会和传统决策树一样，基于信息增益、信息增益率、基尼系数、均方差等原则来选择最优> 的threshold。Extra Tree则是随机选择threshold来划分决策树。

由于Extra Tree是随机选择特征点进行划分，所以最后得到的决策树规模会大于RF生成的决策树，Extra Tree决策树的偏差更大，但方差会减少，泛化能力比RF更强。

AdaBoost

1. AdaBoost 是基于 Boosting 的思想，通过多个弱分类器的线性组合来得到强分类器，训练时重点关注被错分的样本，准确率高的弱分类器权重大。

2. 在训练过程中，它不改变所给的训练数据，而是不断改变训练数据权值的分布，使得被误分类的数据再后一轮的分类中受到更大的关注。

3. 采用加权多数表决的方法，加大分类误差率小的弱分类器的权值，使其在最后的表决中起更大的作用，减小分类误差率大的弱分类器的权值，使其在最后的表决中起较小的作用。所有弱分类器的权值之和并不为 $1$，是通过最后结果的符号来决定实例的类别，该结果的绝对值表示分类的确信度。

Adaboost 还有另外一种理解，即可以认为其模型是加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。

加法模型：多个基函数线性组合得到的模型

前向分步算法：对于加法模型，从前往后，每一步只学习一个基函数及其系数，而不是一次性学习所有的基函数，从而简化优化的复杂度。

算法步骤

考虑如下形式的二分类训练集：

$$(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \dots, (x^{(N)}, y^{(N)})$$

其中 $x^{(i)}\in R^d$ 为第 $i$ 个样本的特征向量，$y^{(i)}\in -1, +1$

AdaBoost算法的步骤如下：

1. 初始化样本权重:

$$D_1=(w_{1,1}, w_{1,2}, \dots, w_{1,N}), w_{1,k}=\frac{1}{N},k=1,2,\dots,N$$

1. 对 $m=1,2,\dots,M$，重复以下操作，得到 $M$ 个学习器：

   （1） 按照样本权重分布 $D_m$ 在训练集上得到第 $m$ 个基学习器 $G_m(x)$

   $$G_m(x):map(R^d) ~ to ~ {-1, +1}$$

   （2） 计算 $G_m(x)$ 在训练集上的加权分类误差率：

   $$e_m=\sum_{i=1}^{N}w_{m,i}I(G_m(x^{(i)}) \not= y^{(i)}) \tag{1}$$

   （3） 计算 $G_m(x)$ 的系数：

   $$\alpha_m=\frac{1}{2}log(\frac{1-e_m}{e_m}) \tag{2}$$

   （4）更新样本权重 $D_{m+1}$:

   $$D_{m+1}=(w_{m+1,1}, w_{m+1,2}, \dots, w_{m+1,N})$$ $$w_{m+1,i}=\frac{w_{m,i}exp(-\alpha_my^{(i)}G_m(x^{(i)})}{Z_m} \tag{3}$$

   其中 $Z_m$ 为归一化因子：$Z_m=\sum_{i=1}^{N}w_{m,i}exp(-\alpha_my^{(i)}G_m(x^{(i)})$

2. 构建最终的分类器的线性组合：

$$f(x)=\sum_{m=1}^{M}\alpha_mG_m(x)\tag{4}$$

1. 最终用于决策的分类器为：

$$G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_mG_m(x)) \tag{5}$$

AdaBoost算法的解释

从理论上解释 AdaBoost 算法设置样本权重 $w_{m,i}$ 和分类器权重 $\alpha_m$ 的原因。

前向分步算法

AdaBoost 算法的最终模型的表达式为：

$$f(x)=\sum_{m=1}^{M}\alpha_mG_m(x)$$

可以看到，这是一个“加性模型”，我们希望这个模型在训练集上的经验误差最小，即：

$$min\sum_{i=1}^{N}\ell(y^{(i)},f(x^{(i)})) \tag{6}$$

通常这是一个复杂的优化问题。前向分步算法求解这一优化问题的基本思路为：如果从前往后，每一步只学习一个基学习器
$G_m(x)$ 及其权重$\alpha_m$，不断迭代得到最终的模型，那么我们可以简化问题的复杂度。

具体的，当我们经过 $m-1$ 轮迭代得到最优模型 $f_{m-1}(x)$ 时，因为：

$$f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)\tag{7}$$

此时，优化目标为：

$$min\sum_{i=1}^{N}\ell(y^{(i)},f_{m-1}(x^{(i)})+\alpha_mG_m(x^{(i)}))\tag{8}$$

算法证明

下面证明当损失函数为指数损失函数时，上述加性模型的学习步骤如上所示。

指数损失函数：

$$\ell(y,f(x))=exp(-yf(x)) \tag{9}$$

可以证明，指数损失时分类任务0/1损失函数的一致替代损失函数。由于指数损失函数有更好的数学性质，例如处处可微，所以我们用它替代0/1损失作为优化目标。

将损失函数代入 $(8)$ 式，则优化目标为：

$$\underset{\alpha_m,~G_m(x)}{argmin}\sum_{i=1}^{N}exp[-y^{(i)}(f_{m-1}(x^{(i)})+\alpha_mG_m(x^{(i)}))] \tag{10}$$

由于 $y^{(i)}f_{m-1}(x^{(i)})$ 与优化的变量无关，如果令：

$$w_{m,i}=exp(-y^{(i)}f_{m-1}(x^{(i)})) \tag{11}$$

则 $(10)$ 等价于：

$$\underset{\alpha_m,~G_m(x)}{argmin}\sum_{i=1}^{N}w_{m,i}exp(-y^{(i)}\alpha_mG_m(x^{(i)})) \tag{12}$$

这里的 $w_{m,i}$ 其实与算法是一致的。

我们分两步来求解 $(12)$ 所示的优化问题的最优解 $\alpha_m$ 和 $G_m(x)$：

1. $\forall \alpha_m \gt 0$ 求 $\hat{G_m(x)}$:

$$\hat{G_m(x)}=\underset{G_m(x)}{argmin}\sum_{i=1}^{N}w_{m,i}I(G_m(x^{(i)})\not =y^{(i)}) \tag{13}$$

1. 求解 $\hat{\alpha_m}$：

$$\begin{aligned} \sum_{i=1}^{N}w_{m,i}exp(-y^{(i)}\alpha_mG_m(x^{(i)}))&=exp(-\alpha_m)\sum_{i=1}^{N}w_{m,i}I(G_m(x^{(i)})=y^{(i)}) \\ &+ exp(\alpha_m)\sum_{i=1}^{N}w_{m,i}I(G_m(x^{(i)})\not =y^{(i)}) \\ &=[exp(\alpha_m)-exp(-\alpha_m)]\sum_{i=1}^{N}w_{m,i}I(G_m(x^{(i)})\not =y^{(i)}) \\ &+ exp(-\alpha_m)\sum_{i=1}^{N}w_{m,i} \end{aligned}$$

对上式关于 $\alpha_m$ 求导并令其为 $0$:

$$[exp(\alpha_m)+exp(-\alpha_m)]\sum_{i=1}^{N}w_{m,i}I(G_m(x^{(i)})\not =y^{(i)})-exp(-\alpha_m)\sum_{i=1}^{N}w_{m,i}=0 \tag{15}$$

解得：

$$\hat{\alpha_m}=\frac{1}{2}log(\frac{1-e_m}{e_m}) \tag{16}$$

其中 $e_m$ 为加权误差率：

$$e_m=\frac{\sum_{i=1}^{N}w_{m,i}I(G_m(x^{(i)}) \not= y^{(i)})}{\sum_{i=1}^{N}w_{m,i}} \tag{17}$$

可见，只需将权重进行归一化，便得到 AdaBoost 算法中的加权误差率

1. 最后来看看每一轮样本权值的更新：

$$\begin{aligned} w_{m+1,i}=exp(-y^{(i)}f_m(x^{(i)}))&=exp(-y^{(i)}[f_{m-1}(x^{(i)})+\alpha_mG_m(x^{(i)})]) \\ &=w_{m,i}exp(-y^{(i)}\alpha_mG_m(x^{(i)})) \end{aligned}$$

将权重进行归一化，便得到 AdaBoost 算法中的权重更新公式

1. 为防止过拟合，AdaBoost 通常会加入正则化项。该正则化项称作步长或者学习率，定义为 $\eta$，此时模型的更新为:

$$f_m(x)=f_{m-1}(x)+\eta\alpha_mG_m(x) \tag{19}$$

GBDT

GBDT 是基于 Boosting 的思想，串行地构造多棵决策树来进行数据的预测，它是在损失函数所在的函数空间中做梯度下降，即把待求的决策树模型当作参数，每轮迭代都去拟合损失函数在当前模型下的负梯度，从而使得参数朝着最小化损失函数的方向更新。

GBDT 可以看作是 AdaBoost 的一个推广，AdaBoost 是通过错分数据点来识别问题，通过调整错分数据点的权重来改进模型，GBDT 是通过负梯度来识别问题，通过计算负梯度来改进模型，实际上，负梯度绝对值大的样例同样会在之后的训练中受到更大的关注，因为它造成的损失更容易在最后的损失函数中占很大的比重，因此，需要更多地偏向于它去减小损失。这也是 GBDT 和 AdaBoost 相似的一个点，而相比 AdaBoost, Gradient Boosting 可以使用更多类型的损失函数，因此可以解决更多的问题。

XGBoost

XGBoost是梯度提升树的一种高效系统实现，是对 GBDT 进一步的改进，包括对代价函数进行了二阶泰勒展开，在代价函数里加入了正则项，借鉴了随机森林的列采样方法，支持并行计算等。

• 传统 GBDT 在优化时只用到一阶导数信息，XGBoost 则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。此外，XGBoost 工具支持自定义代价函数，只要函数可一阶和二阶求导。

• XGBoost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点权重的 $L2$ 范数。从 Bias-variance tradeoff 角度来讲，正则项降低了模型的 variance，使学习出来的模型更加简单，防止过拟合，这也是 XGBoost 优于传统 GBDT 的一个特性。

• Shrinkage（缩减），相当于学习速率（XGBoost 中的eta）。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把 eta 设置得小一点，然后迭代次数设置得大一点。

• 列抽样，XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。

• 对缺失值的处理。对于特征的值有缺失的样本，XGBoost 可以自动学习出它的分裂方向。

• 支持并行。XGBoost 的并行不是树粒度的并行，XGBoost 也是一次迭代完才能进行下一次迭代的。XGBoost 的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost 在训练之前，预先对数据进行了排序，然后保存为 Block 结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个 Block 结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

• 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以 XGBoost 还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

LightGBM

LightGBM 是一个实现 GBDT 算法的分布式高效框架。它通过 leaf-wise 分裂方法进行决策树的生成，通过基于直方图的算法寻找特征分割点，并支持并行学习，能够更高效的处理大数据。

要减少训练的复杂度，可以通过减少特征量和数据量来实现，即从行和列两个角度来减少数据，同时要尽可能少的影响最后的精度。在 LightGBM 中，就是这样做的，对应着 GOSS 和 EFB。

• Gradient-based One-Side Sampling (GOSS)：GBDT 虽然没有数据权重，但每个数据实例有不同的梯度，根据计算信息增益的定义，梯度大的实例对信息增益有更大的影响，因此在下采样时，我们应该尽量保留梯度大的样本（预先设定阈值，或者最高百分位间），随机去掉梯度小的样本。此措施在相同的采样率下比随机采样获得更准确的结果，尤其是在信息增益范围较大时。

• Exclusive Feature Bundling (EFB)：通常在真实应用中，虽然特征量比较多，但是由于特征空间十分稀疏，许多特征几乎是互斥的，EFB 通过捆绑互斥的特征，并将捆绑问题归约到图着色问题，通过贪心算法求得近似解，以减少特征数量。

• 对于树的分裂方法，它通过 leaf-wise 分裂产生比 level-wise 分裂更复杂的树，能够实现更高的准确率。虽然这样有时候会导致过拟合，但可以通过设置 max-depth 参数来防止过拟合的发生。（每一次的生长都是选取分裂增益最高的节点，而不是对一层中的所有节点都进行分裂）。

• 其次，它使用基于直方图的算法，将连续的特征值分桶装进离散的箱子(Bins)，并通过直方图做差加速计算兄弟节点的直方图，能够加速训练过程，并实现更少的内存占用。