GBDT是一个很常用的算法,在很多地方的效果都很好,而且它和AdaBoost还有密切的关系。

From Random Forest to AdaBoost-D Tree

Random Forest本身就有不少好用的性质,它利用boostrapping的方式,获取更多的样本交给决策树来处理,然后加入一些随机化的因子(比如删减一些特征)等方式,来减少模型过拟合的可能,最后用等权投票的方式来获取最终的结果。

其实很直接的一个想法就是把boostrapping改成adaboost,然后交给决策树来处理,但是还有一些小问题要处理,因为adaboost得到的数据是带权的,而一般来说决策树是没有权值这种说法的。所以,只能在数据处理上做文章,即按照权重将数据进行抽样,这样得到数据应该也是符合权重的比例的。

不过,由于最终需要给学出来的树计算投票权重,\(\alpha_t = ln \sqrt{\frac{1 - \epsilon_t}{\epsilon_t}}\),如果一个树在fully grown时,他的\(\epsilon_t\)会变成0,这样的话权值就变成\(\infty\),这显然是不合理的,所以我们要限制单棵树的高度,防止单棵树的过拟合。

Optimization View of AdaBoost

回到AdaBoost中核心的调解样本权值的部分, 对于每一次的迭代,当问题是二分类输出的时候可以简化成

\[u_{n}^{t + 1} = u_{n}^{t} * \exp(-y_n\alpha_tg_t(x_n))\]

其实最后可以看成

\[\begin{split} u_{n}^{t+1} & = u_n^{1}* \prod_{t = 1}^Texp(-y_n\alpha_tg_t(x_n)) \\ &= 1/ N * exp(-y_n\sum_{t = 1}^T \alpha_tg_t(x_n)) \end{split}\]

但是其实,指数上面那一项\(\sum_{t = 1}^T \alpha_tg_t(x_n)\)本来就是最终投票时得到的分数的部分。这表明了,其实最终样本的权值是和指数项有简单的正比的关系。

换个角度看这个问题的话,对于linear blending可以看成是通过学习每一个\(g_t\)的过程看做进行特征转换,然后其实\(\alpha_t\)就是特征的权重,那\(\sum_{t = 1}^T \alpha_tg_t(x_n))\)这一项就可以看成用\(w^T\phi(x_n)\),这其实就和SVM中用来求margin\(\frac{y_n(w^T\phi(x_n) + b)}{||w||}\)很像,只是少了\(||w||\),所以我们可以把这个看成是对margin的一种描述。

所以,我们希望间隔大其实就是等价于\(exp(-y_n\sum_{t = 1}^T \alpha_tg_t(x_n))\)尽可能的小,也就等价于\(u_n^{N+1}\)尽可能的小,也就是AdaBoost要减小\(\sum_{n=1}^{N}u_n^{t}\)

Gradient Descent on AdaBoost Error Function

之前,已经得到了AdaBoost的Error Function,即

\[E_{ADA} = 1/ N * \sum_{n - 1}^Nexp(-y_n\sum_{t = 1}^T \alpha_tg_t(x_n))\]

然后,每一次迭代的时候,我们想要优化这个函数,但是方式不太一样,是找一个好的\(g_t\)来进行优化,即加入一个参数\(h(x)\)代表待优化的函数,\(\eta\)为其系数。

\[\begin{split} E_{ADA} &= \frac{1}{N} \sum_{n - 1}^N exp (-y_n(\sum_{\tau = 1}^{t - 1}\alpha_\tau g_\tau(x_n) + \eta h(x_n))) \\ & = \sum_{n = 1}^N u_n^t exp(-y_n\eta h(x_n)) \\ & \sim \sum_{n = 1}^N u_n^t (1 - y_n \eta h(x_n)) \\ & = \sum_{n = 1}^t u_n^t - \eta \sum_{n - 1}^N u_n^t y_n h(x_n) \end{split}\]

对于第t+1次迭代,先将第t次迭代所得的那一项取出来,然后对这个式子进行泰勒展开,最后得到最后一项,即我们想要优化的部分是\(\sum_{n = 1}^N u_n^t(-y_nh(x_n))\)

继续向下看,对于这一项,我们考虑二元分类的情况下简单的变形即分类标签为\(\{+1, -1\}\)

\[\begin{split} \sum_{n = 1}^N u_n^t(-y_nh(x_n)) & = -\sum_{n = 1}^N u_n^t + 2E_{in}^{u^t}(h) \end{split}\]

所以,我们想要优化的话,就靠优化每一个的\(E_{in}\),而这正是在AdaBoost里面使用的分类器做的事情。

接下来,再进一步,方向\(h(x)\)有了,那对应的\(\eta\)不是也能继续优化嘛,找一个最合适的\(\eta\)可以提高目标函数收敛的速度,回到刚才那个式子 其实式子$_{n = 1}^N u_n^t(-y_nh(x_n)) $完全可以看成 \[(\sum_{n = 1}^N u_n^t)(\sum_{correct}u_n^t exp(-\eta) + \sum_{incorrect}u_n^t exp(\eta))\]

然后对这个式子求偏导,解出来就是\(\eta_t = \ln \sqrt{\frac{1 - \epsilon_t}{\epsilon}}\),这个就是\(\alpha_t\)

其实到这里,AdaBoost 优化的方法就展示出来了,它每一步其实都是在找一个函数的方向,然后向那个方向走\(\alpha\)大小的距离,这个就是最后的结果。

Gradient Boosting Decision Tree

如果我们把之前的AdaBoost的方法扩展一下,不做二元分类的假设,

\[\underset{\eta}{min} \underset{h}{min}\frac{1}{N}\sum_{n = 1}^N err \big (\sum_{\tau}^{t- 1}\alpha_\tau g_\tau(x_n) + \eta h(x_n), y_n\big) \]

不对error函数做假设,每一步计算梯度的\(h(x)\)以及距离的\(\eta\)

Gradient Boosting on Regression

下面看一个把这个思路用在Regression的例子。 显然,Regression的时候,使用的error function一般是是\(err(s, y) = (s - y)^2\)

在极小化h的时候, \[\underset{h}{min} \ \ constants + \frac{\eta}{N} \sum_{n = 1}^{N} 2h(x_n)(s_n - y_n)\]

前面是每次迭代的开始位置,我们不关心,因为理论上,只要我们每一步走的没错,不论在哪里开始都能最终走到一个好的解,之后那一项就是\(h(x)\)与error function对s的偏导。如果我们想要减少这个目标函数的话,只要让\(h(x_n)\)\((s_n - y_n)\),由于我们只想要方向而不关心\(h(x_n)\)的大小,所以,我们加\((h(x))^2\)作为惩罚项到目标函数里,这样完全满足我们的假设。

则上式变成

\[\underset{h}{min} \ \ \ constants + \frac{\eta}{N} \sum_{n = 1}^N (2h(x_n)(s_n - y_n)+ (h(x_n))^2)\]

整理一下就变成了

\[constants + \frac{n}{N} \sum_{n = 1}^N(constants + (h(x_n) - (y_n - s_n))^2)\]

也就是我们希望\(h(x_n)\)和残差尽可能的接近,那只要让\(h(x_n)\)称为一个\(x_n\)\((y_n - s_n)\)的一个线性映射就可以了。也就是再解一个平方误差的回归问题就行了。

找到了好的\(h(x)\)之后,下一步就是搞定\(\eta\)

\[\begin{split} \underset{\eta}{min} & \frac{1}{N}(s_n + \eta g_t(x_n) - y_n)^2 \\ &= \frac{1}{N} \sum_{n = 1}^{N}((y_n - s_n) - \eta g(x_n))^2 \end{split}\]

最后这一项又称为了一个一元的线性回归项。

GBDT

最终终于到了GBDT这个重点,与之前的方法相似。

初始化 \(s_1 = s_2 = s_3 = ... = s_N = 0\) 对于第t次循环

  1. 先求解一种算法求解\(g_t\),使其满足\(x_n\)\(y_n - s_n\)的回归。这里就可以使用决策树。 由于一开始\(s_n\)都是0,所以一起开始其实就是求解一个原始的regression。

  2. 做一个单变量的线性回归来拟合\((\{(g_t(x_n),y_n - s_n )\})\),求解\(\alpha\)

  3. 更新\(G(x) = \sum_{t = 1}^T \alpha_tg_t(x)\)

最终得到 \(G(x) = \sum_{t = 1}^T \alpha_t g_t(x)\)

反思

GBDT其实是GB这种方法在决策树上的应用,对于RF这种基于Boosting的算法来说,依靠每个决策树学习算法(一般来说分类器越强越好)来减少模型的bias,然后依靠Boosting以及其他随机因子来减小模型的variance。而像AdaBoost这种算法,一方面依靠每个分类器学习模型在泛函空间上的梯度方向,然后靠Adaptive的方法学习在这些方向上的距离,由于每个分类器只提供方向(而且应该尽可能的只提供方向),所以即使是弱分类器效果也会不错,而且反而还会避免overfitting。(这一段都是我瞎编的)

不过,我倒是我发现,我对一些基础理论的学习还是不够,接下来还是看一些相关的东西吧。




X