tiny XGBoost以及集成算法回顾

XGBoost是GBDT的一个超级加强版,用了很久,一直没细看原理。围观了一波人家的实现,自己也来弄一遍。以后面试上来一句,要不要我现场写个XGBoost,听上去是不是很霸气。

在开源代码的基础上进行了一点修改,大概跑通了,但是有些地方感觉有点诡异。后面会讲。

回顾一下ensemble算法

之前也写了一篇笔记,台大李宏毅机器学习——集成算法,最近把一些错误做了修改。

bagging

bagging的经典算法就是随机森林了,bagging的思路其实非常非常的简单,就是同时随机抽样本和feature,然后建立n个分类器,接着投票就好了。

bagging的做法本质上不会解决bias太大的问题,所以该过拟合还会过拟合。但是bagging会解决variance太大的问题。这个其实是非常直观的一件事情。

然后我突然开了一个脑洞,RF选择feature这种事情吧,如果用一个weight来表示,把树换成逻辑回归,最后voting的事情也用一个weight来表示,感觉,似乎就是单层神经网络的既视感。anyway,无脑揣测,有待探究。

boosting

boosting跟bagging的套路就不一样,bagging是同时并行很多分类器,但是boosting是串行多个分类器。bagging的分类器之间没有依赖关系,boosting的分类器是有依赖关系的。

boosting算法比较知名的就是GBDT和Adaboost两个。不过其实Adaboost就是一个特殊的GBDT。

GB的一般流程是这样的:

初始化一个函数\(g_0(x) = 0\)
然后按照迭代次数从\(t=1\)\(T\)循环,我们的目标是找到一个函数\(f_t(x)\)和权重\(\alpha_t\)使得我们的函数\(g_{t-1}(x)\)的效果更好,也就是说:
\[g_{t-1}(x) = \sum_{i=1}^{t-1} \alpha_i f_i(x)\] 换个角度来看就是\(g_t(x) = g_{t-1}(x) + \alpha_t f_t(x)\)
而最后我们优化的损失函数\(L(g) = \sum_n l(y_n, g(x_n))\)

那Adaboost就是GB的损失函数\(l\)用exponential表示,也就是\(\exp(-y_n g(x_n))\)。很美妙的一家子。

那实际上我们看\(g_t(x) = g_{t-1}(x) + \alpha_t f_t(x)\)这里,非常像梯度下降,那么如果要做梯度下降的话,其实我们就是对\(g(x)\)做偏导,所以我们得到的是\(g_t(x) = g_{t-1}(x) - \eta \frac{\partial L(g)}{\partial g(x)} \bigg|_{g(x)=g_{t-1}(x)}\)。那其实只要我们想办法让尾巴后面的那一部分是同一个方向的,我们不就达到了梯度下降的目的了吗?!步子的大小是可以用\(\eta\)调的,同样这边也可以调整\(\alpha\)。总之,保证他们的方向一致,就可以做梯度下降了。

Adaboost

现在将Adaboost的损失函数放进来推算一下: \[ \begin{align} L(g) &= \sum_n \exp(-y_n g_t(x_n)) \\ &= \sum_n \exp(-y_n (g_{t-1}(x_n) + \alpha_t f_t(x))) \\ &= \sum_n \exp(-y_n g_{t-1}(x_n)) \exp(-y_n \alpha_t f_t(x_n)) \\ &= \sum_{f_t(x) \ne y} \exp(-y_n g_{t-1}(x_n)) \exp(\alpha_t) + \sum_{f_t(x) = y} \exp(-y_n g_{t-1}(x_n)) \exp(-\alpha_t) \end{align} \]

这样一来,我们需要同时寻找一个\(\alpha\)\(f(x)\)使得我们的损失函数最小。找一个最优的\(f(x)\)这个事情只要让决策树去学习就可以了,那么\(\alpha\)怎么办呢?如果我们对\(\alpha\)求偏导,让偏导数为0,那么理论上,我们在\(\alpha\)这个方向上就是最优的。

具体求偏导这个之前的博客写了,这里就不多搞了。简单说就是刚好会等于\(\ln \sqrt{(1-\varepsilon_t) / \varepsilon_t}\),而这个值刚好是每一轮调整样本权重时候的系数取对数。

GBDT

至于GBDT,实际上跟Adaboost没啥区别,也是一样的搞法,无非是损失函数不一样,优化策略不太一样而已。

GBDT的玩法是用每一棵树去学习上一棵树的残差,通俗的说就是下一棵树学习如何矫正上一棵树的错误。

但是残差这东西也是很妙的一个事情,如果我们损失函数是RMSE,其实我们的残差就是一阶导数。但是呢,如果损失函数是别的函数的时候,其实“残差”这个东西就很难去计算,比如分类的时候,残差究竟是个什么意思?!所以Freidman的梯度提升算法,也就是GBDT前面的GB就是用损失函数对\(f(x)\)的一阶导数来替代残差的。

总体来说,我们想优化的损失函数是: \[ \Theta_t = \arg \min_{\Theta_t} \sum_{t=1}^{T} l(y_n, g_{t-1}(x_n) + \alpha_t f_t(x)) \]

如果我们做回归问题,用RMSE为loss function,那么\(l(y_n, g_t(x_n))=(y_n - g_t(x_n))^2\),而\(y_n - g_t(x_n)\)就是传说中的残差。所以用一阶导数来替代残差真的是神来之笔。这样每次的树直接去学习梯度,而在回归的时候残差跟一阶导数还是一样的,美滋滋。

然后突然有个很不成熟的想法,GBDT是不是很怕one hot的feature呢?!举个例子,如果所有的feature都是one hot的,同时我们每个DT都只有一层,是不是理论上来说,最后有多少feature就有多少树。

XGBoost

嗯,就是一个增强版GBDT。

强在哪呢,boosting是一个加法训练,原来我们用的是一阶导数,而陈天奇则是用了二阶导并加了个正则项。

但是陈天奇做二阶导的目的怎么说呢,我不是非常理解。是inspired by GBDT的RMSE?!这个手算一下,我们的损失函数用RMSE的时候会有一个\((\alpha_t f_t(x))^2\),而这个东西类比泰勒展开的时候就是那个\(\Delta x\),所以怎么说呢,可能大牛是因为看到这个时候灵感乍现,然后尝试用了二阶导。

然后在XGBoost里面的损失函数就可以用二阶泰勒展开来表示: \[ \Theta = \sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f^2_t(x_i)] + \Omega(f_t) \] 其中的\(g_i\)\(h_i\)分别是一阶导数和二阶导数。这样定义的好处是,以后不论用什么损失函数,总体的优化方向仅仅跟一阶导数和二阶导数有关。那么在这个大框架底下,任意可以二阶导的损失函数都可以放进来了。那么我看了XGB的论文关于为什么取二阶导的描述: 直观感受上来说吧,就有点像拟牛顿法是梯度下降的一个功能性提升的样子。

另外就是正则项,这里\(\Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2\)。这里的\(T\)是我们有多少叶节点,\(w\)是叶节点的权重。这两个都在XGB的参数里面可以调整的,我们都知道正则项会改变模型的保守程度,或者说就是variance。而\(w\)在这里就是\(f_t(x)\)。这里要是不理解,可以看陈天奇的这篇中文解释

其他XGB的优化很多是工程上的优化,这个不是CS科班出身就看不懂了。如何并行化什么的,一脸懵逼。具体可以看陈天奇的论文,数学的部分写的非常美妙。

tiny XGB的一些坑

完全自己写太可怕了,在tinygbt的基础上直接修改了一下,原作的代码逻辑非常清晰。anyway,虽然我觉得有些地方貌似是有问题的,做了一点小改动,这个是我的修改版

一个事情就是原作的模型里面learning rate是会越跑越小的,我改成了固定的。另外算split gain的时候我按照论文的公式写的。

还有就是我改了原作的梯度和loss,这样我可以传一些其他损失函数进去,虽然我没试过行不行得通吧。理论上应该OK的吧。XD

然后我觉得原作一个地方我没看懂,就是计算weight的地方,按照论文的公式是\(w_j = -\frac{G_j}{H_j + \lambda}\),但是在这里实现的时候是\(\frac{G_j}{H_j + \lambda}\),就是正负之差。但是很神奇的是我用负号的时候,就不能收敛了。没懂为什么,明明我按照公式求偏导就是负的,实现的时候就不对了。

最后算是一个坑吧,原作数据集用的是LightGBM的测试数据。但是!!!LightGBM的分类和回归用的是同一个数据集,所以,实际上这个回归吧,参考意义也就那样吧。我用的是kaggle上面的pokemon数据集来做回归。

anyway,有人可以发现为什么weight那里会那样的话,给条明路。:)

乞讨码