集成(ensemble)学习通过构建并结合多个学习器来完成学习任务。为了使集成后的学习器获得更好的性能，个体学习器在保证一定的准确性(不用过高，但不能太低)的同时，还需具有一定的多样性。即个体学习器要“好而不同”。

根据个体学习器的生成方式，集成学习大致分为两大类。

Bagging(Bootstrap aggregating 引导聚集)
- 个体学习器间不存在强依赖关系，可并行化地生成
- 用于减少方差
Boosting
- 个体学习器间存在强依赖关系，必须串行化地生成。具体算法有AdaBoost、GBM、GBDT、XGBoost、LightGBM等
- 用于减少偏差

还有一种竞赛中常用的

Stacking
- 异质(个体学习器类型不同)集成
- 用于提升预测结果

接下来重点介绍集成学习中的Boosting。 Boosting是一类可将弱学习器(学习的正确率略优于随机猜测的学习器)提升为强学习器的方法，其常采用加性模型，并利用前向分步算法极小化损失函数进行求解。下面分别介绍Boosting家族的几个典型算法。

前向分步算法

考虑加性模型(additive model)

$f\left( x \right) =\sum_{m=1}^M{\beta _mb\left( x;\gamma _m \right)}$

其中 $b\left( x;\gamma _m \right)$ 为基函数， $\gamma _m$ 为基函数的参数， $\beta _m$ 为基函数的系数。

在给定训练数据及损失函数 $L\left( Y,f\left( X \right) \right)$ 的条件下，通过极小化损失函数来确定加性模型，即

$\underset{\beta _m,\gamma _m}{\min}\sum_{i=1}^N{L\left( y_i,\sum_{m=1}^M{\beta _mb\left( x_i;\gamma _m \right)} \right)}$

以上优化问题通常采用前向分步算法来求解。具体地，从前向后，每一步只求解(学习)一个基函数及其系数，即 $\underset{\beta ,\gamma}{\min}\sum_{i=1}^N{L\left( y_i,\beta b\left( x_i;\gamma \right) \right)}$ ，直至求解完所有的基函数及其系数。

具体算法步骤如下：

输入：训练数据集 $T=\left\{ \left( x_1,y_1 \right) ,\left( x_2,y_2 \right) ,\cdots ,\left( x_N,y_N \right) \right\}$ ;损失函数 $L\left( Y,f\left( X \right) \right)$ ;基函数集 $\left\{ b\left( x;\gamma \right) \right\}$ ;

输出：加性模型 $f\left( x \right)$

(1)初始化 $f_0\left( x \right) =0$

(2)对下述操作迭代$m=1,2,\cdots,M$次

(a) 极小化损失函数

$\left( \beta _m,\gamma _m \right) =\underset{\beta ,\gamma}{arg\min}\sum_{i=1}^N{L\left( y_i,f_{m-1}\left( x_i \right) +\beta b\left( x_i;\gamma \right) \right)}$

得到参数 $\beta _m,\gamma _m$

(b) 更新

$f_m\left( x \right) =f_{m-1}\left( x \right) +\beta _mb\left( x;\gamma _m \right)$

(3)得到最终的加性模型

$f\left( x \right) =f_M\left( x \right) =\sum_{m=1}^M{\beta _mb\left( x;\gamma _m \right)}$

AdaBoost

AdaBoost是前向分步算法的一种特例。其是由基本分类器组成的加性模型，损失函数为指数函数。其基本思想为：先从初始训练数据集中训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的样本在下一轮训练中受到更多的关注，然后基于重新调整后的样本分布进行下一个基学习器的训练。如此重复进行，直至基学习器的数目达到事先指定的值$M$，最终结合$M$个基学习器的输出，得到最终的结果。具体地

输入：训练数据集 $T=\left\{ \left( x_1,y_1 \right) ,\left( x_2,y_2 \right) ,\cdots ,\left( x_N,y_N \right) \right\},y_i\in \left\{ -1,1 \right\}$ ;迭代轮次$M$;

输出：加性模型 $G\left( x \right)$

(1)初始化训练数据的权值分布

$D_1=\left( w_{11},\cdots ,w_{1i},\cdots ,w_{1N} \right) ,w_{1i}=\frac{1}{N},i=1,2,\cdots ,N$

(2)对下述操作迭代$m=1,2,\cdots,M$次

(a)基于权值分布 $D_m$ 的训练数据集，学习一个基分类器 $G_m(x)$

(b)计算 $G_m(x)$ 在训练数据集上的误分率

$e_m=P\left( G_m\left( x_i \right) \ne y_i \right) =\sum_{i=1}^N{w_{mi}I\left( G_m\left( x_i \right) \ne y_i \right)}$

(c)计算 $G_m(x)$ 的系数

$\alpha _m=\frac{1}{2}\log \frac{1-e_m}{e_m}$

说明： $\alpha _m$ 表示 $G_m(x)$ 在最终分类器中的重要性。且 $\alpha _m$ 随着 $e_m$ 的减小而增大，即误分类率越小的基分类器在最终的分类器中的权重越大。

(d)更新训练数据集的权值分布

$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_{mi}}{Z_m}\exp \left( -\alpha _my_iG_m\left( x_i \right) \right)$ $Z_m=\sum_{i=1}^N{w_{mi}}\exp \left( -\alpha _my_iG_m\left( x_i \right) \right)$

说明： 被基分类器 $G_m(x)$ 误分的样本的权值在下一轮更新时其权重增大，而被正确分类的样本在下一轮权值更新时将变小。即误分类样本在下一轮训练中起更大的作用。

(3)构建基分类器的线性组合

$f\left( x \right) =\sum_{m=1}^M{\alpha _mG_m\left( x \right)}$

得到最终分类器

$G\left( x \right) =\text{si}gn\left( f\left( x \right) \right)$

具体数值例子见李航的统计学习方法。

GBDT

GBDT中的基学习器只能是 $CART$ 模型。其在迭代时，假设在 $t-1$ 轮迭代得到的强学习器为 $f_{t-1}(x)$ ，损失函数为 $L(y,f_{t-1}(x))$ ，在$t$轮迭代的目标是找到一个 $CART$ 基学习器 $h_t(x)$ ，让$t$轮的损失 $L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x))$ 最小。即让$t$轮迭代得到的基学习器尽可能地拟合前$t-1$轮所得到的强学习器的偏差(残差)。

为了能在各种损失函数中统一的拟合损失，$Friedman$提出用损失函数的负梯度来近似各轮迭代中的损失值，从而方便各轮迭代中基学习器的确定。

基于上面的思路，现总结下GBDT的回归算法的过程。(分类算法的输出值是不连续的类别值，需一定的处理才能使用负梯度，具体参考梯度提升树(GBDT)原理小结中的分类算法)

输入： 训练集样本 $T=\left\{ \left( x_1,y_1 \right) ,\left( x_2,y_2 \right) ,\cdots ,\left( x_m,y_m \right) \right\}$ ;最大迭代次数$T$;损失函数 $L$

输出： 强学习器 $f(x)$

(1) 初始化基(弱)学习器

$f_0\left( x \right) =\underset{c}{arg\min}\sum_{i=1}^m{L\left( y_i,c \right)}$

(2) 对下述操作迭代 $t=1,2,\cdots,T$ 次

(a) 计算负梯度

$r_{ti}=-\left[ \frac{\partial L\left( y_i,f\left( x_i \right) \right)}{\partial f\left( x_i \right)} \right] _{f\left( x \right) =f_{t-1}\left( x \right)},i=1,2,\cdots ,m$

说明： $r_{ti}$ 表示第$t$轮中第$i$个样本预测误差(残差)的近似表示。

(b) 根据 $(x_i,r_{ti}) (i=1,2,\cdots,m)$ 训练第$t$棵回归树(基学习器)，其对应的叶节点区域为 $R_{tj},j=1,2,\cdots,J。$ 其中 $J$ 为回归树的叶节点的个数(编号/索引)。

$c_{tj}=\underset{c}{arg\min}\sum_{x_i\in R_{tj}}{L\left( y_i,f_{t-1}\left( x_i \right) +c \right)}$

则本轮决策树的拟合函数为

$h_t\left( x \right) =\sum_{j=1}^J{c_{tj}I\left( x\in R_{tj} \right)}$

(d) 更新强学习器

$f_t\left( x \right) =f_{t-1}\left( x \right) +h_t\left( x \right)$

(3) 得到最终的强学习器

$f\left( x \right) =f_T\left( x \right) =f_0\left( x \right) +\sum_{t=1}^T{h_t\left( x \right)}$

XGBoost

XGBoost是GBDT的一种高效实现，相比GBDT，XGBoost主要从以下三个方面做了优化，有“竞赛大杀器”之称

算法本身的优化：在基学习器选择上，相比GBDT只支持CART模型，XGBoost可支持其他的模型。在损失函数上，除了本身的损失，还加上了正则化部分。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度(一阶泰勒)展开，而XGBoost损失函数对误差部分做二阶泰勒展开，精度更高。
运行效率的优化：基学习器的并行选择；特征值的排序分组，加速IO
健壮性的优化: 增加了缺失值及过拟合的处理

下面主要记录自己对算法本身优化的理解。且基学习器依然以CART进行推导建模。

符号说明

令 $x_i\in \mathbb{R}^d,(i=1,2,\cdots,n)$ 表示第$i$个训练样本， $y_i$ 表示第$i$个样本的真实值， $\hat{y}_i$ 表示第$i$个样本的预测值，且有 $\hat{y}_i=\sum_{k=1}^K{f_k\left( x_i \right)}$ ，表示由$K$棵树组成的强学习器对第$i$个训练样本的预测值， $f_k$ 为待确定的模型参数，表示样本特征到预测值的一种映射函数。

由上述符号说明，令目标函数：

$Obj=\sum_{i=1}^n{l\left( y_i,\hat{y}_i \right)}+\sum_{k=1}^K{\varOmega \left( f_k \right)}$

其中 $\sum_{i=1}^n{l\left( y_i,\hat{y}_i \right)}$ 表示训练损失， $\sum_{k=1}^K{\varOmega \left( f_k \right)}$ 表示树的复杂度。

接下来通过优化( $min$ )上述目标函数来确定每个基学习器$f$。又 $\hat{y}_i$ 为加性模型，可利用前向分步算法进行目标函数的优化。

在第$t$轮的预测值可重写为

$\hat{y}_i^{\left( t \right)}=\hat{y}_i^{\left( t-1 \right)}+f_t\left( x_i \right)$

其中 $\hat{y}_i^{\left( t-1 \right)}$ 表示前$t-1$轮的预测值，为已知值， $f_t\left( x_i \right)$ 为第$t$轮待确定的模型参数。

进一步地，第$t$轮的目标函数为

$Obj^{\left( t \right)}=\sum_{i=1}^n{l\left( y_i,\hat{y}_i^{\left( t \right)} \right)}+\sum_{i=1}^t{\varOmega \left( f_i \right)}$ $=\sum_{i=1}^n{l\left( y_i,\hat{y}_i^{\left( t-1 \right)}+f_t\left( x_i \right) \right)}+\varOmega \left( f_t \right) +cons\tan t$

利用泰勒公式,上式可近似为

$Obj^{\left( t \right)}\approx \sum_{i=1}^n{\left[ l\left( y_i,\hat{y}_i^{\left( t-1 \right)} \right) +g_if_t\left( x_i \right) +\frac{1}{2}h_if_{t}^{2}\left( x_i \right) \right]}+\varOmega \left( f_t \right) +cons\tan t \quad (1)$

其中 $g_i=\partial _{\hat{y}_i^{\left( t-1 \right)}}l\left( y_i,\hat{y}_i^{\left( t-1 \right)} \right) ,h_i=\partial _{\hat{y}_i^{\left( t-1 \right)}}^{2}l\left( y_i,\hat{y}_i^{\left( t-1 \right)} \right)$

说明

$f\left( x+\varDelta x \right) \approx f\left( x \right) + f^{'}\left( x \right) \varDelta x + \frac{1}{2}f^{''}\left( x \right) \varDelta x^2$

令 $f\left( x \right) =l\left( y_i,\hat{y}_i^{\left( t-1 \right)} \right)$ ， $f\left( x+\varDelta x \right) =l\left( y_i,\hat{y}_i^{\left( t-1 \right)}+f_t\left( x_i \right) \right)$ 可推出式(1)

在式$(1)$中， $l\left( y_i,\hat{y}_i^{\left( t-1 \right)} \right),g_i,h_i,constant$ 都为已知值，因此第$t$轮的目标函数可重写为

$\underset{f_t}{arg\min}\sum_{i=1}^n{\left[ g_if_t\left( x_i \right) +\frac{1}{2}h_if_{t}^{2}\left( x_i \right) \right]}+\varOmega \left( f_t \right) \quad (2)$

现在的问题是如何表示式$(2)$中的$f(x)$，即如何将树参数化。具体地，有如下定义

$f_t\left( x \right) =w_{q\left( x \right)},w\in \mathbb{R}^T,q:\mathbb{R}^d\rightarrow \left\{ 1,2,\cdots ,T \right\}$

其中 $q(x)$ 表示样本点到叶子编号的映射，它描述了树的结构(分割点及分割点的阈值)， $w_{q\left( x \right)}$ 表示某个叶节点内所有样本的权重值(平均值)，$T$表示叶节点的总数。 $f_t$ 对应的复杂度表示为

$\varOmega \left( f_t \right) =\gamma T+\frac{1}{2}\lambda \sum_{j=1}^T{w_{j}^{2}}$

将 $f_t\left( x \right)$ 及 $\varOmega \left( f_t \right)$ 代入式 $(2)$ 有

$\underset{w_j}{arg\min}\sum_{i=1}^n{\left[ g_iw_{q\left( x_i \right)}+\frac{1}{2}h_iw_{q\left( x_i \right)}^{2} \right]}+\gamma T+\frac{1}{2}\lambda \sum_{j=1}^T{w_{j}^{2}} \quad (3)$

令叶节点$j$中的所有样本集为 $I_j=\left\{ i\left\| q\left( x_i \right) =j \right. \right\}$ ，则式$(3)$按叶节点重新分组后的表达式为

$\underset{w_j}{arg\min}\sum_{j=1}^T{\left[ \left( \sum_{i\in I_j}{g_i} \right) w_j+\frac{1}{2}\left( \sum_{i\in I_j}{h_i}+\lambda \right) w_{j}^{2} \right]}+\gamma T \quad (4)$

说明式$(4)$为相互独立的$T$个二次方函数。

为了后面表述方便，令 $G_j=\sum_{i\in I_j}{g_i},H_j=\sum_{i\in I_j}{h_i}$ ，则式$(4)$可进一步简化为

$\underset{w_j}{arg\min}\sum_{j=1}^T{\left[ G_jw_j+\frac{1}{2}\left( H_j+\lambda \right) w_{j}^{2} \right]}+\gamma T \quad (5)$

由二次函数的性质可知，式$(5)$(最终的损失函数)在 $w_{j}^{*}=-\frac{G_j}{H_j+\lambda}$ 时，损失值最小： $Obj = -\frac{1}{2}\sum_{j=1}^T{\frac{G_{j}^{2}}{H_j+\lambda}}+\gamma T$ 。

说明

函数 $f\left( x \right) =ax^2+bx+c$ 在 $x=-\frac{b}{2a}$ 处取得最值。

$w_{j}^{*}$ 只给出了在第$t$轮迭代时，第$t$棵树各个叶节点的最优权重(平均值)对应的损失函数。还需进一步确定其形状(结构)。构建过程与普通决策树的构建过程类似。具体地，每次分裂节点时，最大程度的减小分裂前损失函数的损失。即假设当前节点左右子树的一阶导二阶导的和分别为 $G_L,H_L,G_R,H_R,$ 则最大化下式

$Gain = -\frac{1}{2}\frac{\left( G_L+G_R \right) ^2}{H_L+H_R+\lambda}+\gamma J-\left( -\frac{1}{2}\frac{G_{L}^{2}}{H_L+\lambda}-\frac{1}{2}\frac{G_{R}^{2}}{H_R+\lambda}+\gamma \left( J+1 \right) \right)$

整理上式可得

$Gain = \frac{1}{2}\frac{G_{L}^{2}}{H_L+\lambda}+\frac{1}{2}\frac{G_{R}^{2}}{H_R+\lambda}-\frac{1}{2}\frac{\left( G_L+G_R \right) ^2}{H_L+H_R+\lambda}-\gamma \quad (6)$

式$(6)$为树节点划分依据，相当于ID3中的信息增益。具体地，依此选取样本集中的某个特征及该特征的某个值，分别计算划分前( $G_L+G_R,H_L+H_R$ )与划分后( $G_L,H_L,G_R,H_R$ )节点对应的一阶导与二阶导的和，使得 $Gain$ 最大的某个特征的某个值即为当前节点的划分点。划分后的节点递归地进行上述操作，直到 $Gain$ 满足某个限制阀值后停止划分，最终得到$t$轮的基学习器 $f_t(x)$ 。

至此，分析完了如何在一个轮次中获得基学习器的过程。

基于上述分析，现总结XGBoost的具体流程：

输入： 训练集样本 $T=\left\{ \left( x_1,y_1 \right) ,\left( x_2,y_2 \right) ,\cdots ,\left( x_m,y_m \right) \right\}$ ;最大迭代次数$T$;损失函数 $L$ ;正则化系数 $\lambda ,\gamma$

输出： 强学习器 $f(x)$

(1) 初始化基学习器

$f_0(x)=0$

(2) 对下述操作迭代 $t=1,2,\cdots,T$ 次

(a) 针对每个样本$i$，计算第$t$轮损失函数$L$关于 $f_{t-1}(x_i)$ 的一阶导数 $g_{ti}$ ,二阶导数 $h_{ti}$ ,然后可得所有样本的一阶导数和 $G_t=\sum_{i=1}^m{g_{ti}}$ 与二阶导数和 $H_t=\sum_{i=1}^m{h_{ti}}$

(b) 基于上述 $Gain$ 准则，进行样本点的划分，最终得到本轮的基学习器 $h_t(x)$

$f_t(x) = f_{t-1}(x) + h_t(x)$

(3)得到最终的强学习器

$f(x) = f_T(x) = f_0(x) + \sum_{t=1}^T{h_t\left( x \right)}$

不考虑深度学习，则XGBoost是算法竞赛中最热门的算法，它将GBDT的优化走向了一个极致。

LightGBM

微软在XGBoost基础上又出了LightGBM，在内存占用和运行速度上又做了不少优化，但是从算法本身来说，优化点则并没有XGBoost多。如果在使用XGBoost遇到的内存占用或者运行速度问题，那么可以尝试LightGBM。

实战

基于XGBoost的信用借贷

Load_Prediction.ipynb

LoanStats3a_2.csv

carlos9310

Boosting

前向分步算法

AdaBoost

GBDT

XGBoost

LightGBM

实战

参考

Search

Post Directory