集成模型

集成模型

集成模型简单的总结,后续有时间再继续完善

集成模型主要目的就是为了降低模型的不确定性,通常来说集成模型可以分成两大类:

  • Bagging:这类方法的代表是随机森林
  • Boosting:这类方法的代表是GBDT和XGBoost

注意深度学习中用到的Dropout,其也可以理解为集成模型。随着每个mini-batch随机丢弃一些神经元,其最终会得到不同的网络结构,最终将其集成起来。

Bagging vs Boosting

相同点:两者都可以理解为base learning,且weak(指单个模型效果不太好)

不同点:bagging模型weak的原因是overfitting,而boosting模型weak的原因是underfitting。

实际两者基本的构筑都是基于决策树。

Bagging

Bagging主要是通过平均带来方差的减少(variance reduction)。假设有N个模型,每个模型再预测时的方差为$ \sigma^2 $ 。则通过N个模型一起预测时的方差是(平均):$\frac{\sigma^2}N$ 。

其代表方法随机森林区别于决策树的地方在于:构建树之前需要随机采样。这里包含了样本与特征2个方面。样本随机通常采用Bootstrap方法。

Random Forests = Bagging w. trees + random feature subsets

直观上理解就是, 采用 bootsrap 方法, 训练 多个决策树, 最后对所有的结果进行投票。

Boosting

Boosting算法本质是通过学习一个个弱分类器,在之前分类器的基础上不断迭代,最终集成提升为强分类器。boosting方法大致可以分为两种:

  • Adaptive boosting: 通过分类误差率来调整样本的权重,经过迭代不断更新样本权重(提高错误样本权重,降低正确样本权重)(同时适用于基分类器)。最后将多个分类器组合在一起。
  • Gradient boosting : 基于残差来优化,不断更新迭代。最后将多个分类器组合在一起。

这里将主要讨论一下Gradient boosting方法。

CART回归树

GBDT使用的决策树基础是CART回归树,由于其每次迭代要拟合的是梯度值,属于连续值,所以不可以使用CART分类树。为了很好的评判拟合程序,选择使用平方误差(MSE)。

回归树的生成算法:

输入:训练数据集D:
输出:回归树 $f(x)$.
在训练数据集所在的输入空间中,递归的将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二叉决策树:
(1)选择最优切分变量$j$与切分点$s$,求解

$$ \min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right] $$

遍历变量$j$,对固定的切分变量$j$扫描切分点$s$,选择使得上式达到最小值的对$(j,s)$。$c_1,c_2$表示生成的左右两棵子树的均值。

(2)用选定的对$(j,s)$划分区域并决定相应的输出值:

$$ R_{1}(j, s)=x\left|x^{(j)} \leq s, R_{2}(j, s)=x\right| x^{(j)}>s $$ $$ \hat{c_{m}}=\frac{1}{N} \sum_{x_{1} \in R_{m}(j, s)} y_{i}, x \in R_{m}, m=1,2 $$

(3)继续对两个子区域调用步骤(1)和(2),直至满足停止条件(特定迭代次数或值满足某些条件)。
(4)将输入空间划分为$M$个区域 $R_1,R_2,...R_M$ ,生成决策树:

$$ f(x)=\sum_{m=1}^{M} \hat{c}_{m} I\left(x \in R_{m}\right) $$

提升树

提升树的精髓就是利用残差作为新的样本,不断去迭代决策树,最终使用投票等方法得出最终结果。这是一种基础的思想,后续算法都是再次基础上改进得来。

加法模型与前向分布算法,以决策树作为基函数

提升树算法:

输入:训练数据集$D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}$

输出:提升树$f_M(x)$

(1) 初始化$f_0(x)=0$

(2) For $m=1,2,……M$

​ (a) 针对每个样本$(x_i,y_i)$,计算残差

$$ r _ { m , i } = y _ { i } - f _ { m - 1 } ( x _ { i } ) , i = 1 , 2 , \cdots , N $$

​ (b) 利用 $\left\{\left(x_{i}, r_{m, i}\right)\right\}_{i=1,2, \ldots, N}$ 训练出一个决策树(回归树),得到$T ( x ; \Theta _ { m } )$

​ (c) 更新$f_{m}(x)=f_{m-1}(x)+T\left(x ; \Theta_{m}\right)$

(3) 完成以上迭代,即可得到提升树

$$ f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right) $$

GBDT

GBDT(Gradient Boosting Decision Tree),梯度提升树。结合上面两种思想构建而成。

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

精髓:利用最速下降的近似方法,具体指利用损失函数的负梯度拟合一个回归树。

GBDT算法

输入:训练数据集$D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}$;损失函数$L(y,f(x))$`$.

输出:梯度提升树$\hat(x)$

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

(2) For $m=1,2,……M$

​ (a) 针对每个样本$(x_i,y_i)$,计算残差

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

​ (b) 利用$\left\{\left(x_{i}, r_{m, i}\right)\right\}_{i=1,2, \ldots, N}$ 训练出第$m$棵回归树$T_m$,其叶节点划分的区域为$R_{m, j}, j=1,2, \ldots, J$

​ (c) 对于回归树的每一个叶节点,计算器输出值

$$ 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), j=1,2, \ldots, J $$

​ (d) 更新$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) $$

实际使用时需要定义一个学习率$\alpha$。且如果损失函数选用的是平方损失函数(MSE),其负梯度就是提升树中的直接相减的残差$y-f(x_i)$,但这仅仅是特殊情况。

XGBoost

XGBoost(eXtreme Gradient Boosting) 极端梯度提升,既可运用于分类,也可运用于回归。

XGBoost是对GBDT的进一步改进。传统GBDT在优化时只用到一阶导数信息, Xgboost则对损失函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。
XGBOOST在损失函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的 score的L2模的平方和。从 Bias-variance tradeoff角度来讲,正则项降低了模型的 variance,使学习出来的模型更加简单,防止过拟合,这也是 Xgboost优于传统GBDT的一个特性。

相比于前面的不断迭代树求最优函数的推导,XGBoost可以反向去理解,先构造出一个最优的函数,进而最后再去反推树的形状。

  1. 如何构造目标函数

类似于上面介绍的方法,最终预测值都是采用累加的方法

假设已经训练好了K棵树,则对于第i个样本的(最终)预测值为:

$$ \hat{y}_{i}=\phi\left(X_{i}\right)=\sum_{k=1}^{K} f_{k}\left(X_{i}\right), f_{k} \in \mathcal{F} $$

目标函数定义为两个部分,损失函数和控制每棵树复杂度的正则项:

$$ \mathcal{L}(\phi)=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{k} \Omega\left(f_{k}\right) $$

对于回归问题,Loss可以选择MSE,对于分类问题,可以选择CrossEntropy,根据实际情况来选择

根据前$k-1$棵树去构建第$k$棵树,则可以表示为:

$$ \hat{k}_{i}^{(t)}=\hat{k}_{i}(t-1)+f_{k}\left(x_{i}\right) $$

那么目标函数变化为:

$$ \begin{aligned} \mathcal{L}(\phi) &=\sum_{i}^{n} l\left(y_{i}, \hat{y}_{i}^{(k)}\right)+\sum_{k=1}^{K} \Omega\left(f_{k}\right) \\ &=\sum_{i}^{n} l\left(y_{i}, \hat{y}_{i}^{(k-1)}+f_{k}\left(X_{i}\right)\right)+\sum_{k=1}^{K-1} \Omega\left(f_{K}\right)+\Omega\left(f_{K}\right)\end{aligned} $$

前K-1棵树的复杂度无意义,则第K棵树目标函数表示为:

$$ \begin{aligned} \mathcal{L}^{(K)} &=\sum_{i}^{n} l\left(y_{i}, \hat{y}_{i}^{(k-1)}+f_{k}\left(X_{i}\right)\right)+\Omega\left(f_{K}\right)\end{aligned} $$

目的就是最小化这个式子

  1. 目标函数的近似

这里用到二阶的泰勒公式

$$f ( x + \Delta x ) \approx f ( x ) + f ^ { \prime } ( x ) \Delta x + \frac { 1 } { 2 } f ^ { \prime \prime } ( x ) \Delta x ^ { 2 }$$

将$f_k(X_i)$看作$\Delta x$(为何可以这样?因为每棵树迭代相加提升的数值很小,可以这样去理解)。则第K棵树目标函数转化为:

$$ \mathcal{L}^{(K)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}_{i}^{(K-1)}\right)+g_{i} f_{K}\left(X_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(X_{i}\right)\right]+\Omega\left(f_{K}\right) $$

其中$g_{i}=\partial_{\hat{y}^{(K-1)}}\left(y_{i}, \hat{y}^{(K-1)}\right), h_{i}=\partial_{ \hat{y}^{(K-1)}}^{2}\left(y_{i}, \hat{y}^{(K-1)}\right)$

  1. 将树的结构引入目标函数

树的复杂度定义如下:

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

其中$T$衡量节点的个数,$\sum_{j=1}^{T} w_{j}^{2}$衡量了节点的值。定义$f_K(x) = W_{q(x)}$

$$ \begin{aligned} \mathcal{L}^{(K)} & \simeq \sum_{i=1}^{n}\left[g_{i} f_{K}\left(X_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(X_{i}\right)\right]+\Omega\left(f_{K}\right) \\ &=\sum_{i=1}^{n}\left[g_{i} w_{q\left(x_{i}\right)}+\frac{1}{2} h_{i} w_{q\left(x_{i}\right)}^{2}\right]+\gamma T+\lambda \frac{1}{2} \sum_{j=1}^{T} w_{j}^{2} \\ &=\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 \end{aligned} $$

Tips:第二至三步:将所有节点1到n的循环改写成单独叶节点$I_J$1到T的循环(优点:去除下标,包含二次项)

$G_{j}=\sum_{i \in I_{j}} g_{i}, H_{j}=\sum_{i \in I_{j} }g_{i}$,代入上式:

$$ \mathcal{L}^{(K)}=\sum_{j=1}^{T}\left[G_{j} w_{j}+\frac{1}{2}\left(H_{j}+\lambda\right) w_{j}^{2}\right]+\gamma T $$

根据一元二次方程,每个叶子结点的$score w_j$的解为:

$$w _ { j } ^ { * } = - \frac { G _ { j } } { H _ { j } + \lambda }$$ $$L ^ { ( K ) } = - \frac { 1 } { 2 } \sum _ { j = 1 } ^ { T } \frac { G _ { j } ^ { 2 } } { H _ { j } + \lambda } + \gamma T$$
  1. 优化方法(使用贪心算法)

接下来的目标就是学习寻找树的形状,一一例举进行比较不现实。由于已经推导出第K棵树最优结果$L^{(K)}$,因此可以使用贪心算法,相较于上一步$L^{(K)}_{old}$,不断寻找最优$L^{(K)}_{new}$,目标是使得两者间差距最大。

因此对于一个叶子节点进行分裂,分裂先后得到的增益函数可以表示为:

$$ G a i n=\frac{1}{2}\left[\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}-\frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}\right]-\gamma $$

第一项为左节点的score,第二项为右节点的score,第三项为上一步骤的score(如果不做分裂),第四项是多出来分支的附加项。式子等同于:

$$ \mathcal{L}_{\text {split }}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_{L}} g_{i}\right)^{2}}{\sum_{i \in I_{L}} h_{i}+\lambda}+\frac{\left(\sum_{i \in I_{R}} g_{i}\right)^{2}}{\sum_{i \in I_{R}} h_{i}+\lambda}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma $$

论文中构造树的算法步骤如图:

但是一个个位移寻找过慢,算法优化后采用一块块进行位移计算。对于每个特征,只考察候选切分点(分位点),减少计算复杂度。根据候选切分点把当前结点的样本放入对应的桶中,对每个桶的G,H进行累加。最后在候选切分点集合上贪心查找,论文描述如下:

具体如何选取切分点,这里使用$h$,二阶梯度加权,细节部分参考论文,就不细写了。

XGBoost同样有很多优化,例如Shrinkage,列抽样,稀疏值处理等等,也不细展开了,具体详见论文。

不过在使用XGBoost这个库时,对于回归问题,假设迭代K轮,总共生成K棵树。然而对于分类问题,迭代K轮,C分类问题,总共生成CK棵树。原因是分类最后使用softmax函数,针对每一个类别都会生成一棵树,即单次迭代就会生成C棵树,后将对应类别的值相加再求softmax,才能得到类似分类的结果。

还有个LightGBM,其使用了一堆方法对XGBoost进行优化 ,速度快,且内存占用较低,想了解的自己看论文去吧。


这里仅仅是对自己学习的简单整理,还有很多地方不完善,后续根据情况再继续补补吧。

参考

李航《统计学习方法》

GBDT算法原理以及实例理解

XGBoost论文解读

AdaBoost、GBDT、RF、XGboost、LightGBM的对比分析

XGBoost原始论文:XGBoost: A Scalable Tree Boosting System

LightGBM原始论文:LightGBM: A Highly Efficient Gradient Boosting Decision Tree