从原理和数据说 Gradient Boosting Tree


发布于

|

分类

写了小半年(速度真的是够慢的),终于出结果了。

目前只写了 Gradient Boosting Classifier 部分。现在除了速度很慢很慢很慢之外其他还好。

来说说细节吧。

思想

思想不难:一棵树解决不了的问题,用多棵树来解决。

这好像也是 “集成学习” 的总思想吧。自己解决不了的问题,让一大群同伙一起来解决。

后人解决的是前人的“遗留问题”。

这个算法很有意思,虽然是分类问题,但它使用的却是回归树。

核心版

刚才说到“使用多棵树”,用多少呢?

这个问题,你说的算。也就是说,我们需要定义一个 n_estimators,作为“训练的轮数”。因为每一轮会产生一棵树,所以就会产生 n_estimators 棵树。

怎么训练这些树呢?

首先,进行进行预预测,得到预测结果 y_pred。关于预预测,后面会说到。

然后开始我们的大循环,以下过程循环 n_estimators 次:

把预测结果 y_pred 和我们的标签 Label 做减法,得到一个差值,他们都叫这个差值为“残差”(Residual)。

接下来, 使用 (x,residual) 进行训练得到一棵新的小树。

再接下来,用这棵小树对 X 做预测,得到对于 x 的预测结果 y_pred_partial

然后 y_pred+=y_pred_partial

大循环结束。

什么是预预测?

初始化用的,别太在意。

比如,我说(预测),对于这一批数据,你们都属于第一个分类~

反正是预测…… 看看天气预报你就知道它们准不准了。

做完训练,我们得到了什么?

得到了 n_estimators 棵树。木有了。

那么,如何进行预测呢?

回看一下 “训练” 的过程:训练、用小树预测、结果相加。最后我们得到一个中间变量 y_pred, 对吧。但是训练结束后这个 y_pred 就没有用了。

但是在做预测的时候,这个 y_pred 就是我们需要的预测结果。

所以,预测就是这样的:

对于那 n_estimaters 棵树:我们让这些树对测试数据 x 分别进行预测,取预测结果之和。

就结束啦~

增强版

使用多少棵树?

首先,我们要人为规定一个 n_estimators 参数,作为“训练的轮数”。对于分类问题(因为我还没有看回归问题),假设现在有 n_classes 个分类,那么每一轮就新产生 n_classes 棵树。也就是说,总共产生 n_estimators * n_classes 棵树。比如,100 轮,3 个分类,那么最后会得到 100 轮 ×3 棵 = 300 棵树。

对于第 i 轮中的第 k 棵树,它的作用是“判断对于数据 x,属于分类 k 的可能性有多大”。

怎么训练这些树呢?

在 “核心版” 中,我们得到的是一个向量 y_pred,因为我们只是说“x 属于那一类”。现在呢,我们得到一个矩阵,m*k 的矩阵。这里的 mnumber of training examples,knumber of classes。我这样说你是不是能猜到下面要做什么了呢?

第一步,预预测,得到 y_pred

然后,开始大循环:对于每一轮(假设为第 i 轮):

刚才不是说有 n_classes 个分类么,那就再套一个循环:对于每一个分类(假设为第 k 个分类):(现在这是两重循环了啊~)

首先把我们的 Target,或者叫 Label 变一下:原来拿到的 Label 是“这个样本属于第几类”,现在变成一个二值向量,“这个样本是不是属于第 k 个分类”。掩模一下就可以得到了是吧。

然后得到 “残差”:将现在的 y_pred(:,k) 与“变一下” 的 y 做减法,即 redidual=y_pred(:,k)-y(y==k)

下面,将得到的残差作为 第 i 轮第 k 个 树的 y,进行训练。

然后,用这颗刚刚生成的新树,对所有样本再做一次预测,得到的结果叠加到 y_pred 里面去。

将这棵树保存起来备用。

So,做完训练,我们得到了什么?

得到了一大堆树。更确切一点,我们得到了 n_estimators 棵 “看看你是不是属于第 k 个分类” 的树。

换句话说,经过 100 轮训练,得到了 200 棵树。每一轮的第一棵树的作用是判断你有多大的可能性是人,第二棵树判断你有多大的可能性是鱼。

然后呢?如何开始真正的预测呢?

对于一组新的测试数据,我们也需要做 n_estimators 轮、每轮经过 n_classes 棵树的预测,叠加预测结果。

然后,刚才说什么来着,“预测结果”是 “这个样本属于第 x 个分类的可能性的大小” 是吧?

OK,选出预测结果中数值最大的,作为预测结果。输出即可。

继续增强版

“核心版”就是这篇文章 [^Greedy_Function_Approximation] 里面的 Algorithm 2: LS Boost。好像用它来做回归问题也是蛮适合的…… 但是做分类效果也不错啊~

“增强版”可以说是 Sk-learn[^sk_learn]代码的核心。

我们可以在这个基础上加上各种变化,只要改变 “如何得到 residual” 和“如何把预测结果加到 y_pred”。对于这个,sk-learn 把它归结为 LossFunction_negative_gradientLossFunction_update_terminal_regions。不同的 LossFunction 适用范围不同,得到的效果也不同。(但是我没怎么看懂这些 LossFunction 是如何工作的…… 数学公式有点看不懂)

比如,有些用于分类的 LossFunction,得到的 residual 可能会是这样的结果(就比如下面带数据的那个例子,使用的是 deviance 这种 LossFunction):如果你属于第 k 个分类,那么你在第 k 个分类上的得分会非常高(比如,3 个分类,得分是几十分),在其他分类上的得分会非常低(比如,3 个分类,得分是负数)。这样能把分类间的差距加大,应该会更有利吧。

真的是这样么?

我们来让数据说话吧。这也是我做调试的时候用的……

首先,某个数据集,有 5 个样本(做例子嘛……),每个样本有 7 个特征,总共有 3 个类型。现在要训练 4 轮。

也就是,n_classes=3n_estimators=4。使用的是 deviance,对应的 LossFunction 是 MultinomialDeviance(这个变化更明显一点,但是我没有理解公式)。Loss 体现在残差的计算和 y_pred 与当前结果相加的时候所用的策略。

(为什么不用最简单的?因为今天测试的时候突然出状况了怎么都出不来结果……tree 就一个节点死活都不给分裂…… 只能用以前的调试结果了,过几天把 demo 的更直观更简单一点的调试结果给贴出来)

下面是每一步的 预测结果(y_pred),可以保存到记事本里面看:

y_pred =
0.4000    0.4000    0.2000
0.4000    0.4000    0.2000
0.4000    0.4000    0.2000
0.4000    0.4000    0.2000
0.4000    0.4000    0.2000
====================

i:1 k:1 (只有第 1 列变化了)
0.2967    0.4000    0.2000
0.2967    0.4000    0.2000
0.2967    0.4000    0.2000
0.5879    0.4000    0.2000
0.5879    0.4000    0.2000

i:1 k:2 (只有第 2 列变化了)
0.2967    0.5814    0.2000
0.2967    0.5814    0.2000
0.2967    0.2946    0.2000
0.5879    0.3004    0.2000
0.5879    0.3004    0.2000

i:1 k:3 (只有第 3 列变化了)
0.2967    0.5814    0.1074
0.2967    0.5814    0.1074
0.2967    0.2946    0.4134
0.5879    0.3004    0.1075
0.5879    0.3004    0.1075
==================== 第一轮训练结束

i:2 k:1 (只有第 1 列变化了)
0.1991    0.5814    0.1074
0.1991    0.5814    0.1074
0.1986    0.2946    0.4134
0.7458    0.3004    0.1075
0.7458    0.3004    0.1075

i:2 k:2 (只有第 2 列变化了)
0.1991    0.7350    0.1074
0.1991    0.7350    0.1074
0.1986    0.1952    0.4134
0.7458    0.2058    0.1075
0.7458    0.2058    0.1075

i:2 k:3 (只有第 3 列变化了)
0.1991    0.7350    0.0182
0.1991    0.7350    0.0182
0.1986    0.1952    0.5874
0.7458    0.2058    0.0186
0.7458    0.2058    0.0186
==================== 第二轮训练结束

i:3 k:1
0.1062    0.7350    0.0182
0.1062    0.7350    0.0182
0.1050    0.1952    0.5874
0.8836    0.2058    0.0186
0.8836    0.2058    0.0186

i:3 k:2
0.1062    0.8698    0.0182
0.1062    0.8698    0.0182
0.1050    0.1006    0.5874
0.8836    0.1153    0.0186
0.8836    0.1153    0.0186

i:3 k:3
0.1062    0.8698   -0.0678
0.1062    0.8698   -0.0678
0.1050    0.1006    0.7362
0.8836    0.1153   -0.0673
0.8836    0.1153   -0.0673
====================

i:4 k:1
0.0172    0.8698   -0.0678
0.0172    0.8698   -0.0678
0.0151    0.1006    0.7362
1.0069    0.1153   -0.0673
1.0069    0.1153   -0.0673

i:4 k:2
0.0172    0.9910   -0.0678
0.0172    0.9910   -0.0678
0.0151    0.0102    0.7362
1.0069    0.0283   -0.0673
1.0069    0.0283   -0.0673

i:4 k:3
0.0172    0.9910   -0.1513
0.0172    0.9910   -0.1513
0.0151    0.0102    0.8676
1.0069    0.0283   -0.1505
1.0069    0.0283   -0.1505

你会发现有些值一直在增大,有些值一直在减小,而且每次只变化第 k 列,即只更新“你属于第 k 个分类的可能性”。

好的,然后如果我告诉你,前四个样本的 Target 分别是 2 2 3 1 ,现在你推测一下最后一行数据的 target 是多少?

OK,下面是预测。

y_pred = 0.4000    0.4000    0.2000
i:1 k:1  0.4645    0.4000    0.2000
i:1 k:2  0.4645    0.3669    0.2000
i:1 k:3  0.4645    0.3669    0.1721
i:2 k:1  0.5223    0.3669    0.1721
i:2 k:2  0.5223    0.3374    0.1721
i:2 k:3  0.5223    0.3374    0.1470
i:3 k:1  0.5739    0.3374    0.1470
i:3 k:2  0.5739    0.3111    0.1470
i:3 k:3  0.5739    0.3111    0.1247
i:4 k:1  0.6199    0.3111    0.1247
i:4 k:2  0.6199    0.2877    0.1247
i:4 k:3  0.6199    0.2877    0.1048

所以呢,它属于第一个分类。

So,测试精度呢?

在几个小规模样本集上做了简单测试。

Mine_Transtale
Mine_Simple
Mine_Simple_Enhanced

========== Dataset_index_fixed

seeds
Max: 0.9524  Min: 0.8571     Avg: 0.8905
Max: 1.0000  Min: 0.8571     Avg: 0.9286
Max: 0.9524  Min: 0.8571     Avg: 0.9048

thyroid
Max: 0.9863  Min: 0.9726     Avg: 0.9834
Max: 1.0000  Min: 0.9589     Avg: 0.9820
Max: 0.9863  Min: 0.9589     Avg: 0.9779

wine
Max: 1.0000  Min: 0.7647     Avg: 0.9100
Max: 1.0000  Min: 0.7647     Avg: 0.9319
Max: 1.0000  Min: 0.7895     Avg: 0.9272

========== Dataset

Data_Set_pima
Max: 0.8182  Min: 0.5065     Avg: 0.6909
Max: 0.7662  Min: 0.5974     Avg: 0.6948
Max: 0.7662  Min: 0.6753     Avg: 0.7299

Data_Set_eeg_eye_state
Max: 0.8478  Min: 0.8164     Avg: 0.8370
Max: 0.9246  Min: 0.8919     Avg: 0.9065
Max: 0.9085  Min: 0.8939     Avg: 0.9013

Data_Set_dermatology
Max: 1.0000  Min: 0.8649     Avg: 0.9405
Max: 1.0000  Min: 0.8919     Avg: 0.9459
Max: 1.0000  Min: 0.8649     Avg: 0.9432

效果不是特别稳定,但整体还算可以吧。

参数的调整

树的最大高度

“回归树特别容易出现过拟合”,这是 sk-learn 源代码中的注释…… 好吧,为了防止过拟合,那就让你欠拟合一点。反正最后的精度可以通过增加训练轮数来解决。

如何让欠拟合一点呢?减少树的高度。带来的 “副作用” 好处是,减少训练时间。(对于大规模数据……100000 多个样本,1000 多个分类,我在可怜的 Dell 5420 上面跑了一晚上都没跑完…… 我的显卡也不能被调用…… 哭)

这可能也是最最重要的一个参数了。一般来说可以取默认值 4 或者 5 就好了。有时候高度太高,精度反而下降。

有一个对比是,在某一组测试数据上,控制树最大高度 5,得到精度 0.7416;最大树高 2147463847(相当于不控制最大树高),得到精度 0.6909。

训练轮数

这个倒是没有做太多的对比。一些简单的数据集用 5 轮足矣。默认 100 轮。反正轮数太大了不好调试…… 至于对精度的影响我到没有做对比测试。

Loss Function 的选择

唔…… 这个比较关键。对于不同的问题,不同的数据,选用不同的 Loss Function 可能效果不太一样。

就比如说,二分类问题。完全可以当作表标准准的二分类问题去做,每一轮产生两棵树。同时,也可以使用一个叫做 “BinomialDeviance” 的 Loss Function 去做,每轮产生一棵树。在某个数据集上,前者精度 0.7299, 后者精度 0.6909。

Loss 体现在 residual 的获取、y_pred 的更新过程、对 y_pred 的理解(y_pred 的含义、最后选谁做预测结果)。这三个过程是配套的。

目前存在的问题

OK,不得不说,训练速度真的很慢!完全不能忍啊!树多一点、分类数多一点、样本大一点,照这个速度训练,孙子都会打酱油了啊!

原因呢…… 在 Matlab 中,自带的回归树不能直接控制树的的高度。

然后,Matlab R2015a 在 R2014a 的基础上增加了一个还是两个比较有用的参数,可以加上去使用。

最后给出项目地址

我的 Matlab 翻译版 & scikit-learn 的原版

参考资料

  1. [^sk_learn]: sk-learn, https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/ensemble/gradient_boosting.py , 2015
  2. [^Greedy_Function_Approximation]: J. Friedman, Greedy Function Approximation: A Gradient Boosting Machine, The Annals of Statistics, Vol. 29, No. 5, 2001.
  3. J. Friedman, Stochastic Gradient Boosting, 1999
  4. Breiman, L., J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Boca Raton, FL: CRC Press, 1984.

评论

  1. sunny 的头像
    sunny

    看不懂,why let me look there

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注