写了小半年（速度真的是够慢的），终于出结果了。
目前只写了 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 的矩阵。这里的 m 是 number of training examples,k 是 number 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_gradient 和 LossFunction_update_terminal_regions。不同的 LossFunction 适用范围不同，得到的效果也不同。（但是我没怎么看懂这些 LossFunction 是如何工作的…… 数学公式有点看不懂）
比如，有些用于分类的 LossFunction，得到的 residual 可能会是这样的结果（就比如下面带数据的那个例子，使用的是 deviance 这种 LossFunction）：如果你属于第 k 个分类，那么你在第 k 个分类上的得分会非常高（比如，3 个分类，得分是几十分），在其他分类上的得分会非常低（比如，3 个分类，得分是负数）。这样能把分类间的差距加大，应该会更有利吧。
真的是这样么？
我们来让数据说话吧。这也是我做调试的时候用的……
首先，某个数据集，有 5 个样本（做例子嘛……），每个样本有 7 个特征，总共有 3 个类型。现在要训练 4 轮。
也就是，n_classes=3，n_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 的原版
参考资料
- [^sk_learn]: sk-learn, https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/ensemble/gradient_boosting.py , 2015
- [^Greedy_Function_Approximation]: J. Friedman, Greedy Function Approximation: A Gradient Boosting Machine, The Annals of Statistics, Vol. 29, No. 5, 2001.
- J. Friedman, Stochastic Gradient Boosting, 1999
- Breiman, L., J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Boca Raton, FL: CRC Press, 1984.
发表回复