数据挖掘面试题之：梯度提升树
关于作者：Milter，一名机器学习爱好者、NLP从业者、终生学习者，欢迎志同道合的朋友多多交流
0x00 前言
GBDT是机器学习面试中的常客，但是，要准确地说出它的原理却并不容易，除了掌握DT基本知识外，还要掌握加法模型、前向分步算法、梯度提升思想，本文是对这些知识点的一个简单总结，请各路大神指正。
为了提高写作效率，文中公式都是手写，美观不足，但清晰准确是没问题的。
0x01 从加法模型说开去
首先，我们需要具备一些基本的机器学习知识，这里简单列出，以作为下面讨论的基础：
- 机器学习的大致流程就是确定模型集H、定义经验损失函数（一般是基于单个样本点进行定义）、利用给定的数据集{（x_i,y_i）}，从模型集中寻找最佳的模型（一般就是寻找最佳的模型参数）。
- 决策树是一种模型，它的主要思想是将输入空间划分为不同的子区域，然后给每个子区域确定一个值，如果是分类树，这个值就是类别，如果是回归树，这个树就是一个实值。 如下图所示：
3. GBDT中的DT是回归树，不是分类树，也就是说，只有回归树才有所谓的梯度提升。
所谓加法模型，也是一种模型集H，它的一般形式如下：
f_m(x)叫做基函数，基函数可以有各种各样的形式，自然也会有自己的参数，待会儿我们讨论GBDT时，它就是二叉回归决策树。β_m是基函数的系数，一般假设大于0。
有了模型，还需定义该模型的经验损失函数，如下所示：
现在，我们的问题转变成了通过极小化经验损失函数来确定各个系数β_m和各个基函数f_m(x)。
问题是：How？
此时，我们既不知道基函数的具体形式，也不知道损失函数的具体形式，只有N个样本点，很显然，我们无法往下进行。
0x02 前向分步算法横空出世
这就是前向分步算法一显身手的地方，前向分布算法说：“我可以提供一套框架，不管基函数和损失函数是什么形式，只要你的模型是加法模型，就可以按照我的框架的指导，去求解。”
也就是说，前向分步算法提供了一种学习加法模型的普遍性方法，不同形式的基函数、不同形式的损失函数都可以用这种普遍性方法去求出加法模型的最优化参数，它是一种元算法。
它的思路是：加法模型中一共有M个基函数以及与之相应的M个系数，可以从前往后，每次学习一个基函数及其系数。
其学习步骤如下：
前向分步算法中最核心的就是第2步中的第1小步，即如何求出f_m和β_m？
0x03 梯度提升顺利接盘
梯度提升思想正是为了解决上面的问题。它的主要思想是先求f_m，再求β_m。观察式子：
我们要最小化的式子由N部分相加而成，如果能够最小化每一部分，自然也就最小化了整个式子。考察其中任一部分，并将其进行泰勒一阶展开（这是关键所在！）：
由于β是大于0的，若：
不难得出：
这说明，我们已经成功地降低了在第i个样本点上的预测损失。同理，我们可以降低在每一个样本点上的预测损失。条件就是：
这个条件其实告诉了我们如何去寻找f_m，即能够使得在每一个样本点上上式尽可能成立的f_m就是我们要找的。这是一个回归问题，很容易解决。
我们已经有了f_m，下面优化求解β，很显然，这是一个一维搜索问题，如下：
在上面的泰勒一阶展开时，有一个条件就是βf(x_i)要足够小，显然，执行一维搜索后得到的β会满足这个条件。
0x04 这时才是学习梯度提升树的最佳时机。
以上是加法模型的一般学习方法，对不同的基函数，不同的损失函数，不同的问题（分类还是回归），都可以套用上面的方法来求解，只是具体的表现形式会有所变化。
比如当加法模型解决的问题是二类分类问题，基函数是基本分类器，损失函数为指数损失函数时，按照上面的方法求解，其过程就和AdaBoost是完全一样的。
当用加法模型解决的问题是回归问题，基函数是二叉决策回归树时，加法模型本身会得到简化，基函数前面的系数可以省去，因为对每一个系数，我们都可以把它内化到二叉决策回归树内部去，这时的加法模型变成了这样：
简化了加法模型，消除了β，在求解第2步第1小步时，过程也得到了简化，详情请参考《统计学习方法》P151-152：
在上面的图中，有一点值得注意，就是我们用r_mi拟合出一个回归树之后，进一步用整体损失函数对这棵回归树的值进行了优化。这样的思想在机器学习中很常见，我管它叫做“先局部、后整体”思想，就是先通过逐步的局部优化得出一个结果，然后再从全局的角度来优化这个结果。
举个例子，决策树的生成和剪枝，先通过局部优化（用信息增益等指标选择特征）得出一个决策树，再从降低整体损失的角度，进行剪枝。
Note：注重总结机器学习各种模型中的思想，就可以达到触类旁通的境界。
更进一步，当损失函数是平方误差时，求解过程就更加的简单了，详情请见《统计学习方法》P148。
0x05 总结一下
本文首先介绍了机器学习中一类模型——加法模型，然后介绍了求解优化该类模型的前向分步算法，又进一步介绍了该算法中最核心步骤求解所用的梯度提升思想。然后，从一般到个别，展示了当加法模型运用到不同问题中（分类和回归），当基函数采用不同的具体形式（基本分类器和二叉决策回归树），当损失函数采用不同的具体形式（指数损失函数和平方损失函数）时，其具体化的求解步骤。
可以看出GBDT作为求解回归问题的加法模型，具有形式简单（消除了β），求解便捷（见上面的《统计学习方法》图）的特点，这也是为什么它十分流行的原因
