集成学习 | WXue

1 简介

集成学习（Ensemble learning）通过组合几种模型来提高机器学习的效果。构建并结合多个学习器，个体学习器要“好而不同”，一定的准确性/多样性。

2 提升方法

2.1 提升方法之Adaboost

一般过程：训练—基学习器—调整训练样本分布—重复得到更多基学习器 T个—将这T个基学习器加权结合。代表是Adaboost：提高那些被前一轮弱分类器分错的样本的权值。最后加权多数表决方法、加大分类误差率小的弱分类器的权值。属于序列集成。

算法（书P156）：

输入训练集$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$，其中实例$x_{i} \in \mathcal{X}=\mathbf{R}^{n}$，$y_i \in \mathcal{Y} = \left\{ -1,+1 \right\}$

1，初始化训练数据的权值分布为均匀分布。$w_{1i} = \frac{1}{N}$。

2，使用具有权值分布的$D_m$的训练数据集学习得到基分类器$G_{m}(x): \mathcal{X} \rightarrow\{-1,+1\}$。

3，计算$G_m(x)$在训练数据集上的分类误差率:

$e_{m}=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{m i} I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)$

计算得到$G_m(x)$的系数，它表示了$G_m(x)$在最终分类器中的重要性。他随$e_m$的减小而增大。

$\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}$

在更新训练数据集的权值分布

$D_{m+1}=\left(w_{m+1,1}, \cdots, w_{m+1, i}, \cdots, w_{m+1, N}\right)$ $w_{m+1, i}=\frac{w_{m i}}{Z_{m}} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right), \quad i=1,2, \cdots, N$

其中$Z_m$是规范化因子：

$Z_{m}=\sum_{i=1}^{N} w_{m i} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right)$

4，构建基分类器的线性组合 $f(x) = \sum_{m=1}^M \alpha_m G_m(x)$

得到最终分类器：

$G(x) = \operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right)$

2.2 提升方法之提升树 Boosting

采用加法模型（基函数的线性组合，基函数为树的时候叫Boosting tree），前向分步算法。减小偏差。

2.2.1 前向分步算法：

1，确定初始提升树$f_0(x) = 0$

2，第m步的模型是$f_m(x) = f_{m-1}(x) + T(x: \theta_m)$

这里需要通过经验风险极小化来确定下一棵决策树参数参数:

$\hat{\theta_m} = argmin_{\theta_m} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i:\theta_m))$

不同问题的提升树学习算法区别在于使用的损失函数不同。

问题	学习算法
回归树	平方误差（拟合残差）
分类问题	指数损失函数
一般决策问题	一般损失函数

对于二分类问题，提升树算法只需将Adaboost算法中基本分类器限制为二分类树即可。

2.2.2 回归问题的提升树，拟合残差

1，初始化$f0(x)=0$

2，对m=1,2..M计算残差，N是样本数。当前模型拟合数据的残差。

$r_{mi} = y_i -f_{m-1}(x_i), i=1.2..N$

拟合残差$r_{mi}$学习一个回归树$T(x: \theta_m)$。更新：

$f_m(x) = f_{m-1}(xi) + T(x: \theta_m)$

3，得到回归问题提升树

$f_M(x) = \sum_{m=1}^M T(x; \theta_m)$

2.2.3 一般决策问题GBDT

一般损失函数：

梯度提升gradientBoosting （GBDT）：利用最速下降法的近似方法，关键是利用损失函数的负梯度在当前模型的值

$-\left[\frac{\partial L\left(y, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{m-1}(x)}$

作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

过程：

输入训练集$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$，其中实例$x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}, y_{i} \in \mathcal{Y} \subseteq \mathbf{R}$

输出回归树： $\hat{f(x)}$

(1) 初始化

$f_{0}(x)=\arg \min _{c} \sum_{i=1}^{N} L\left(y_{i}, c\right)$

(2) 对m = 1,2…M

对 i = 1,2,…N 计算：

$r_{m i}=-\left[\frac{\partial L\left(y_{i}, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{m-1}(x)}$

对$r_{mi}$ 拟合一个回归树。得到第m棵树的叶节点区域$R_{m j}, j=1,2, \cdots, J$

对 j = 1,2 …J 计算：

$c_{m j}=\arg \min _{c} \sum_{x_{i} \in R_{m j}} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+c\right)$

更新

$f_{m}(x)=f_{m-1}(x)+\sum_{j=1}^{J} c_{m j} I\left(x \in R_{m j}\right)$

(3) 得到回归树

$\hat{f}(x)=f_{M}(x)=\sum_{m=1}^{M} \sum_{j=1}^{J} c_{m j} I\left(x \in R_{m j}\right)$

2.3 其他

XGBoost：

经过优化的分布式梯度提升（Gradient Boosting）库，实现了并行方式的决策树提升(Tree Boosting)。XGBoost采用的是level（depth）-wise生长策略，如下所示，能够同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合；但不加区分的对待同一层的叶子，带来了很多没必要的开销。

XGBoost使用的是pre-sorted算法，能够更精确的找到数据分隔点；XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

XGBoost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。