您的位置: 首页  >  文章  >  AdaBoost&GBDT（三）

AdaBoost&GBDT（三）

分类: 文章 • 2024-08-13 10:43:58

GBDT

GBDT是Gradient Boosting Decision Tree的简称，其形式是决策树的加法模型。
fM(x)=∑m=1MT(x;Θm) f_M(x) = \sum_{m=1}^MT(x;\Theta_m)
其中T(x;Θ)T(x;\Theta)代表树模型，普遍使用的是CART树。

GBDT Regression

求解这个加法模型的方法即是上一节所提到的前向分步算法，于是我们自然要明确每一轮的损失函数的形式。GBDT并不指定损失函数的具体形式，对一般的损失函数L(y,f(xi))L(y,f(x_i))，在前向分步算法中第mm步的优化中，我们要建立回归树去拟合损失函数关于f(x)f(x)的负梯度
rmi=−[∂L(yi;f(x))∂f(x)]f(x)=fm−1(xi)i=1,2,…,Nr_{mi} = -\Bigg[\frac{\partial{L(y_i;f(x))}}{\partial f(x)}\Bigg]_{f(x) = f_{m-1}(x_i)} \quad i = 1,2,\ldots,N

这是梯度提升名称的由来，也是本篇的重点，下面着重解析此处拟合负梯度的动机。

前向分步算法第mm步的本质优化目标可以写为
min⁡f∑i=1NL(yi,f(xi)) \min_{f}\sum_{i=1}^NL(y_i,f(x_i))
将f(x)f(x)拆分为fm−1(x)+T(x,Θm)f_{m-1}(x)+T(x,\Theta_m),优化目标变为
min⁡Θm∑i=1NL(yi,fm−1(xi)+T(xi,Θm)) \min_{\Theta_m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m))
由于L(y,f(x))L(y,f(x))在此处没有明确形式，我们无法像AdaBoost那样直接将fm−1(x)f_{m-1}(x)与T(x,Θm)T(x,\Theta_m)分成独立的两部分，为达成这个目的，考虑L(yi,fm−1(x)+T(x,Θm))L(y_i,f_{m-1}(x)+T(x,\Theta_m))的麦克劳林(Maclaurin)公式
L(yi,fm−1(xi)+T(xi,Θm))≈L(yi,fm−1(xi))+giT(xi,Θm)+12hi[T(xi,Θm)]2 L(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m)) \approx L(y_i,f_{m-1}(x_i))+g_iT(x_i,\Theta_m)+\frac{1}{2}h_i[T(x_i,\Theta_m)]^2
其中gi=[∂L(yi,f(x))∂f(x)]f(x)=fm−1(xi)，g_i = \bigg[\frac{\partial{L(y_i,f(x))}}{\partial{f(x)}}\bigg]_{f(x) = f_{m-1}(x_i)}，\quad hi=[∂2L(yi,f(x))∂(f(x))2]f(x)=fm−1(xi)h_i = \bigg[\frac{\partial^2{L(y_i,f(x))}}{\partial{(f(x))^2}}\bigg]_{f(x) = f_{m-1}(x_i)}

这时候，由于前向分步算法第mm步中，fm−1(xi)f_{m-1}(x_i)是常值，于是优化问题可以做如下转化
argmin⁡Θm∑i=1NL(yi,fm−1(xi)+T(xi,Θm))≈argmin⁡Θm∑i=1NgiT(xi,Θm)+12hi[T(xi,Θm)]2 arg\min_{\Theta_m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m))\approx arg\min_{\Theta_m}\sum_{i=1}^Ng_iT(x_i,\Theta_m)+\frac{1}{2}h_i[T(x_i,\Theta_m)]^2

记L(T(xi,Θ))=giT(xi,Θ)+12hi[T(xi,Θ)]2\mathcal{L}(T(x_i,\Theta)) = g_iT(x_i,\Theta)+\frac{1}{2}h_i[T(x_i,\Theta)]^2,对T(xi,Θ)T(x_i,\Theta)求偏导并使其为00，则有
∂L(T(xi,Θ))∂T(xi,Θ)=gi+hiT(xi,Θ)=0 \frac{\partial{\mathcal{L}(T(x_i,\Theta))}}{\partial{T(x_i,\Theta)}} = g_i + h_iT(x_i,\Theta) = 0
得
T(xi,Θ)=−gihi T(x_i,\Theta) = -\frac{g_i}{h_i}
而我们一般假定L(yi,f(xi))L(y_i,f(x_i))是一个凸函数，此时hi>0h_i>0，通常将hih_i设置成11去扮演梯度下降中学习率的角色，于是我们知道了前向分步算法中第mm步的近似最优解就是能更好的拟合−gi-g_i的那一棵CART回归树，这即是GBDT拟合负梯度的动机。

还可以从另外一个角度去理解，即使L(yi,f(xi))L(y_i,f(x_i))不是一个凸函数，我们将L(yi,fm−1(xi)+T(xi,Θm))L(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m))仅仅展开到一阶，如下式
L(yi,fm−1(xi)+T(xi,Θm))≈L(yi,fm−1(xi))+giT(xi,Θm) L(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m)) \approx L(y_i,f_{m-1}(x_i))+g_iT(x_i,\Theta_m)
移项后，变为
giT(xi,Θm)≈L(yi,fm−1(xi)+T(xi,Θm))−L(yi,fm−1(xi)) g_iT(x_i,\Theta_m) \approx L(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m)) - L(y_i,f_{m-1}(x_i))
我们想要通过每一步优化使训练误差减小，即是想达到L(yi,fm−1(xi)+T(xi,Θm))−L(yi,fm−1(xi))⩽0L(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m)) - L(y_i,f_{m-1}(x_i))\leqslant 0的目的。此时取T(xi,Θm)=−giT(x_i,\Theta_m) = -g_i即可满足要求。从这个角度也可以看出GBDT拟合负梯度的动机。

攻克了这项难关之后，下面的伪代码无非只是每一步用树模型拟合负梯度的前向分步算法
AdaBoost&GBDT（三）
其中关于优化cmjc_{mj}的一步，CART树通常的做法是将落在RmjR_{mj}的所有训练样本的label求平均，作为cmjc_{mj}的值。

GBDT Regression的特例——Boosting Tree

将提升树(Boosting Tree)写在这里，以解决抽象形式的损失函数L(y,f(x))L(y,f(x))所带来的理解困难的问题。
Boosting Tree是特殊的GBDT，其指定了损失函数的具体形式
L(y,f(x))=(y−f(x))2 L(y,f(x)) = (y-f(x))^2
该损失函数是一个凸函数，按照梯度提升树的求法，每一步所训练的树所要拟合的目标为
T(xi,Θ)=−gihi T(x_i,\Theta) = -\frac{g_i}{h_i}
其中gi=[∂L(yi,f(x))∂f(x)]f(x)=fm−1(xi)=−2(yi−fm−1(xi))，g_i = \bigg[\frac{\partial{L(y_i,f(x))}}{\partial{f(x)}}\bigg]_{f(x) = f_{m-1}(x_i)} = -2(y_i-f_{m-1}(x_i))，\quad hi=[∂2L(yi,f(x))∂(f(x))2]f(x)=fm−1(xi)=2h_i = \bigg[\frac{\partial^2{L(y_i,f(x))}}{\partial{(f(x))^2}}\bigg]_{f(x) = f_{m-1}(x_i)} = 2

代入后，有
−gihi=yi−fm−1(xi) -\frac{g_i}{h_i} = y_i-f_{m-1}(x_i)

于是提升树是GBDT的特例，每一步优化的负梯度为当前模型拟合数据的残差(residual)。

GBDT Classification

而当我们想要用GBDT解决分类问题时(以二分类问题为例，多分类问题仅仅是将sigmoid函数更换为softmax函数)，与Logistic Regression类似，用GBDT去拟合对数几率logp1−plog\frac{p}{1-p}.即
logp1−p=f(x)=∑m=1Mfm(x) log\frac{p}{1-p} = f(x) = \sum_{m=1}^M{f_m(x)}
得分类模型
P(y=1∣x)=11+e−f(x)=11+e−∑m=1Mfm(x) P(y=1|x) = \frac{1}{1+e^{-f(x)}} = \frac{1}{1+e^{-\sum_{m=1}^M{f_m(x)}}}
损失函数即与Logistic Regression相同，使用交叉熵(cross entropy)衡量分布的相似程度
L(xi,yi∣f(x))=−yilog11+e−f(xi)−(1−yi)log(1−11+e−f(xi))=yilog(1+e−f(xi))+(1−yi)log(1+e−f(xi)e−f(xi))=yilog(1+e−f(xi))+(1−yi)[log(1+e−f(xi))+f(xi)] \begin{aligned} L(x_i,y_i|f(x)) &= -y_ilog\frac{1}{1+e^{-f(x_i)}}-(1-y_i)log(1-\frac{1}{1+e^{-f(x_i)}}) \\ & = y_ilog(1+e^{-f(x_i)})+(1-y_i)log(\frac{1+e^{-f(x_i)}}{e^{-f(x_i)}}) \\ & = y_ilog(1+e^{-f(x_i)})+(1-y_i)[log(1+e^{-f(x_i)})+f(x_i)] \end{aligned}

损失函数在当前模型的负梯度为
−[∂L(yi∣f(x))f(x)]f(x)=fm−1(xi)=yi−11+e−fm−1(xi)=yi−y^m−1,i -\bigg[\frac{\partial L(y_i|f(x))}{f(x)}\bigg]_{f(x) = f_{m-1}(x_i)} = y_i - \frac{1}{1+e^{-f_{m-1}(x_i)}} = y_i - \hat{y}_{m-1,i}

于是分类任务的GBDT每一轮的训练任务与提升树相同，都是拟合当前模型的残差。

相关推荐