乱谈府

乱谈府

集成模型

545
2021-05-22
集成模型

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

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

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

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

Bagging vs Boosting

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

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

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

Bagging

Bagging主要是通过平均带来方差的减少(variance reduction)。假设有N个模型,每个模型再预测时的方差为 σ2\sigma^2 。则通过N个模型一起预测时的方差是(平均):σ2N\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)f(x).
在训练数据集所在的输入空间中,递归的将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二叉决策树:

  1. 选择最优切分变量jj与切分点ss,求解

minj,s[minc1xiR1(j,s)(yic1)2+minc2xiR2(j,s)(yic2)2]\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]

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

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

R1(j,s)=xx(j)s,R2(j,s)=xx(j)>sR_{1}(j, s)=x\left|x^{(j)} \leq s, R_{2}(j, s)=x\right| x^{(j)}>s

cm^=1Nx1Rm(j,s)yi,xRm,m=1,2\hat{c_{m}}=\frac{1}{N} \sum_{x_{1} \in R_{m}(j, s)} y_{i}, x \in R_{m}, m=1,2

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

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

提升树

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

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

提升树算法:

输入:训练数据集D={(x1,y1),(x2,y2),,(xN,yN)}D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}

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

  1. 初始化f0(x)=0f_0(x)=0

  2. For m=1,2,Mm=1,2,……M

  • 针对每个样本(xi,yi)(x_i,y_i),计算残差

rm,i=yifm1(xi),i=1,2,,Nr _ { m , i } = y _ { i } - f _ { m - 1 } ( x _ { i } ) , i = 1 , 2 , \cdots , N

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

  • 更新fm(x)=fm1(x)+T(x;Θm)f_{m}(x)=f_{m-1}(x)+T\left(x ; \Theta_{m}\right)

  1. 完成以上迭代,即可得到提升树

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

GBDT

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

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

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

GBDT算法

输入:训练数据集D={(x1,y1),(x2,y2),,(xN,yN)}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))L(y,f(x)).

输出:梯度提升树f^(x)\hat{f}(x)

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

  2. For m=1,2,Mm=1,2,……M

  • 针对每个样本(xi,yi)(x_i,y_i),计算残差

rm,i=[L(yi,f(xi))f(xi)]f(x)=fm1(x)),i=1,2,,Nr_{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

  • 利用{(xi,rm,i)}i=1,2,,N\left\{\left(x_{i}, r_{m, i}\right)\right\}_{i=1,2, \ldots, N} ,训练出第mm棵回归树TmT_m,其叶节点划分的区域为Rm,j,j=1,2,,JR_{m, j}, j=1,2, \ldots, J

  • 对于回归树的每一个叶节点,计算器输出值

cm,j=argmincxiRm,jL(yi,fm1(xi)+c),j=1,2,,Jc_{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

  • 更新fm(x)=fm1(x)+j=1Jcm,jI(xRm,j)f_{m}(x)=f_{m-1}(x)+\sum_{j=1}^{J} c_{m, j} I\left(x \in R_{m, j}\right)
  1. 得到最终的梯度提升回归树

f^(x)=fM(x)=m=1Mj=1Jcm,jI(xRm,j)\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),其负梯度就是提升树中的直接相减的残差yf(xi)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个样本的(最终)预测值为:

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

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

L(ϕ)=il(y^i,yi)+kΩ(fk)\mathcal{L}(\phi)=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{k} \Omega\left(f_{k}\right)

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

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

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

那么目标函数变化为:

L(ϕ)=inl(yi,y^i(k))+k=1KΩ(fk)=inl(yi,y^i(k1)+fk(Xi))+k=1K1Ω(fK)+Ω(fK)\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棵树目标函数表示为:

L(K)=inl(yi,y^i(k1)+fk(Xi))+Ω(fK)\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+Δx)f(x)+f(x)Δx+12f(x)Δx2f ( x + \Delta x ) \approx f ( x ) + f ^ { \prime } ( x ) \Delta x + \frac { 1 } { 2 } f ^ { \prime \prime } ( x ) \Delta x ^ { 2 }

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

L(K)i=1n[l(yi,y^i(K1))+gifK(Xi)+12hifK2(Xi)]+Ω(fK)\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)

其中gi=y^(K1)(yi,y^(K1)),hi=y^(K1)2(yi,y^(K1))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. 将树的结构引入目标函数

树的复杂度定义如下:

Ω(fK)=γT+12λj=1Twj2\Omega\left(f_{K}\right)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2}

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

L(K)i=1n[gifK(Xi)+12hifK2(Xi)]+Ω(fK)=i=1n[giwq(xi)+12hiwq(xi)2]+γT+λ12j=1Twj2=j=1T[(iIjgi)wj+12(iIjhi+λ)wj2]+γT\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的循环(优点:去除下标,包含二次项)

Gj=iIjgi,Hj=iIjgiG_{j}=\sum_{i \in I_{j}} g_{i}, H_{j}=\sum_{i \in I_{j} }g_{i},代入上式:

L(K)=j=1T[Gjwj+12(Hj+λ)wj2]+γT\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

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

wj=GjHj+λw _ { j } ^ { * } = - \frac { G _ { j } } { H _ { j } + \lambda }

L(K)=12j=1TGj2Hj+λ+γTL ^ { ( K ) } = - \frac { 1 } { 2 } \sum _ { j = 1 } ^ { T } \frac { G _ { j } ^ { 2 } } { H _ { j } + \lambda } + \gamma T

  1. 优化方法(使用贪心算法)

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

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

Gain=12[GL2HL+λ+GR2HR+λ(GL+GR)2HL+HR+λ]γ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(如果不做分裂),第四项是多出来分支的附加项。式子等同于:

Lsplit =12[(iILgi)2iILhi+λ+(iIRgi)2iIRhi+λ(iIgi)2iIhi+λ]γ\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进行累加。最后在候选切分点集合上贪心查找,论文描述如下:

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

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