机器学习技法笔记 – Gradient Boosted Decision Tree(GBDT)

Adaptive Boosted Decision Tree

一言以概之,Gradient Boosted Decision Tree简称GBDT,即AdaBoost与Decision Tree的Aggregation:

如果说Random Forest是在数据集上通过Bagging的方式,以数据集的随机性获得训练出决策树\(g_t\)的差异性。

那么对对于GBDT,则是通过Re-weighted的数据集,来训练出差异化的决策树\(g_t(t)\),最后将他们做Blending,来得到\(G(x)\):

接下来我们介绍一种被称之为Weighted Decision Tree Algorithm的算法,用于训练GBDT。

对于Re-weighted权重的最佳化问题,我们需要最小化下式:

接下来训练出\(u^t_n\)权重对应的\(g_t\),然后计算出Blending时该\(g_t\)的权重:

然后重复上述步骤\(T\)次,最后做Blending,得到\(G(x)\)。

但是这样做存在一些问题,对于一颗未经剪枝的决策树,它的\(E_{in}=0\),这非常可怕,这会导致错误率\(\epsilon_t=0\),这会导致\(\alpha_t=∞\),那么Blending也就显得毫无意义了,这样显然是不行的:

所以剪枝是必要的,在训练GBDT时,我们通常采用的决策树剪枝方法称之为Extremely-Pruned Tree,这种特殊的决策树的高度只有\(1\),是一种非常弱的决策树:

这种决策树又被称之为AdaBoost-Stump。

Optimization View of AdaBoost

接下来的内容,是对AdaBoost的一些数学上的理论分析,这一小节的理论分析,将会对\(\alpha_t=ln(\sqrt{\frac{1-\epsilon_t}{\epsilon_t}})\)这一结论做详细的解释。

对于AdaBoost的Re-weighted,其\(u^{(T+1)}_n\)有以下计算方式:

以分类问题为例,在上式中,无论是乘以或者除以\(♦︎_t\),都可以简化为\(♦︎^{-y_ng_t(x_n)}_t\),然后添加\(exp(x)\),在指数中补一个\(\alpha_t\),从而进一步整理上式如下:

上式将连乘替换为连加,值得注意的是,\(\sum^{T}_{t=1} \alpha_tg_t(x_n)\)即是\(G(x)\),所以我们有以下结论:

值得注意的是,对于下式:

与SVM中的Margin:

具有一些联系,可以看出,\(\sum^{T}_{t=1} \alpha_tg_t(x_n)\)即是为正规化的\(margin\),在SVM中,我们希望\(margin\)越大越好,在AdaBoost中也恰恰反映为如果\(\sum^{T}_{t=1} \alpha_tg_t(x)\)足够大,就会使得\(u^{(T+1)}_n\)足够小,从而达到Re-weighted的目的。

接下来我们介绍AdaBoost Error Function,对于AdaBoost,我们总希望\(u^{(T+1)}_n\)越小越好,所以我们希望\(\sum^{N}_{n=1} u^{(t)}_n\)越小越好,故AdaBoost Error Function具有以下形式:

对比\(err_{0/1}\)与\(err_{ada}\),我们可以发现\(err_{ada}\)是\(err_{0/1}\)上界:

接下来我们通过Gradient Descent(梯度下降)最小化\(\sum^{N}_{n=1} u^{(t)}_n\),注意\(h(x_n)\)是自变量:

通过观察,可以发现\(\frac{1}{N}exp(-y_n\sum^{t-1}_{\tau} \alpha_{\tau}g_{\tau}(x_n))\)可以进一步改写为\(u^{(t)}_n\),因此可以将原始进一步改写为以下形式:

上式是一个指数函数,回忆指数函数的麦克劳林泰勒展开:

$$e^x = \sum^{∞}_{n=0} \frac{x^n}{n!}$$

对上式做一阶泰勒展开:

由于:

$$\sum^{N}_{n=1} u^{(t)}_n = E_{in}$$

到此为止,回忆梯度下降的基本形式:

所以有:

$$v^T▽E_{in}(w_t) = \sum^{N}_{n=1} u^{(t)}_ny_nh(x_n)$$

需要注意的是,由于\(h(x_n)\)是函数,这里没有办法像在解Linear Regression或者Logistics Regression时,先对Error Function求梯度,再将\(x_n\)带入梯度函数后求值,同时乘以\(\eta\),然后迭代\(T\)次或者直到梯度值收敛到\(0\),所以进行了不同的处理。

回到原问题,最后问题转化为最小化下式:

以分类问题为例,上式的取值具有以下可能:

将等式右边进行如下改写:

回忆\(E_{in} · N = u^{(t)}_n\),所以上式可以继续改写:

那么谁来最小化\(E^{u^{(t)}}_{in}\)呢?回忆AdaBoost的工作过程,很容易发现是每一次根据\(u^{(t)}_n\)来训练\(g_t\)的过程。

那么最有步长\(\eta\)又该如何确定呢?这里同样与解Linear Regression或者Logistics Regression时不同,无法通过经验直接给定一个例如值为\(0.001\)的步长。

在AdaBoost每次根据当前权重训练出\(g_t\)时,回顾Error Function:

我们可以发现,除了\(\eta\),其他参数都是已知的,所以原问题转化为了一个最小化\(\eta\)的问题。

对于分类问题:

\(exp(-y_n{\eta}g_t(x_n))\)的取值可能有如下情况:

所以将原始进行一下改写:

最后令\(\frac{\partial{\widehat{E}_{ADA}}}{\partial{\eta}}=0\),最后求解得出\(\eta=ln(\sqrt{\frac{1-\epsilon_t}{\epsilon}})=\alpha_t\),即最佳步长。

小结一下上述推导:通过理论分析,我们证明了在使用AdaBoost时,通过梯度下降最小化\(u^{(t)}_n\)时,其最速下降方向\(h(x)\)即是每一次根据\(u^{(t)}_n\)来训练出\(g_t\),而最佳步长则是在训练出\(g_t\)后,令\(\frac{\partial{\widehat{E}_{ADA}}}{\partial{\eta}}=0\)后求解得出。

以上数学的推导即是AdaBoost在最佳化理论上的支撑。

Gradient Boosting

对于AdaBoost,其Error Function具有如下形式:

而所谓Gradient Boosting,它的Error Function则不再需要具体的形如指数函数这样的某一函数,它可以是任意函数:

如果将Gradient Boosting用于Regression问题,则可以使用平方误差函数:

对上式进行一阶泰勒展开:

与AdaBoost的情况类似,Regression问题在最小化\(h(x)\)时,最后经过化简,最终变成了最小化\(\sum^{N}_{n=1} h(x_n) · 2(s_n-y_n)\)的问题。

但是没有约束的\(h(x_n)\)有可能会使得\(h(x_n)=-∞\),如果是一个\(-∞\)的\(h(x_n)\),则步长\(\eta\)将无法约束下降步长,梯度下降也就无从谈起了。

所以Regularization是必要的,我们通过添加\(h(x_n)\)的平方项,再通过配方,将原式做以下改写:

我们可以发现,在\(y_n, s_n\)已知的情况下,求解\(h(x_n)\)即是求解一个Linear Regression问题。

最后确定最佳步长\(\eta\):

在各项已知的情况下,易求出\(\eta\)。

最后对Gradient Boosting做一下小结:

首先根据Gradient Boosting Error Function最小化\(g_t\),然后求出最佳化步长\(\eta\),也即Blending时的\(\alpha\),然后更新\(s_n\),重复\(T\)次,最后Blending,得出\(G(x)\)。

Summary of Aggregation Models

最后对所有的Aggregation方法做一个总结。

对于在训练完差异化的\(g_t\)后再进行Blending的方式:

对于一边训练出差异化的\(g_t\),一边进行Blending的方式:

以上是对Gradient Boosted Decision Tree在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Neural Network。