树模型奠基性论文解读GBM：GradientBoostingMachine
1.背景
函数估计(Function Estimation/Approximation)是对函数空间(Function Space)进行数值优化，而不是对参数空间(Paramter Space)进行优化。这篇论文[1]提出的Gradient Boosting Machine算法将stagewise additive expansions(分步加和扩展)和steepest-descent minimization(最速下降极小化，也就是梯度下降法)结合起来实现对函数空间的数值优化，可以适用于回归和分类问题，具有完整性好，鲁棒性强，解释性好等优点。
正则化的回归分析可以避免2.动因
为了理解作者的动因，我们首先从我们熟悉的函数最小值优化问题谈起：
对于该优化问题，可以使用Steepest Gradient Descent，梯度下降法进行求解。这个算法大致过程如下：
∙给定一个起始点
∙对分别作如下迭代：
∙, 其中表示在上的梯度值，是步长，是通过在方向线性搜索来动态调整的。
∙一直到足够小，或者足够小，即函数收敛。
以上过程就是梯度下降法，可以理解为整个过程就是小步走，每小步都往函数值下降最快的方向走。这样的寻优过程得到的结果可以表示为加和形式，即：
我们可以从上面得到启发，这样的过程是否可以推广至函数空间求函数估计问题？求解函数估计问题本身也是一个寻优的过程，只不过我们寻的结果是最优函数估计，而不是最优点估计。优化的目标通常通过最小化损失函数来定义：
类似上面的梯度下降法，我们可以依次迭代得到,可以类比成上述的,则最优的 , 每次迭代求梯度：
其中，是负梯度，是每次迭代需要学习的弱学习器(基函数)，用于拟合负梯度，即。此处前的权重为1，通常会给每次学习的弱学习器分配一个权重，即，，从最终的组成来看，衡量了该弱学习器在所有弱学习器中的重要性。
我们发现上述求解是函数对函数求梯度，由于损失函数对函数的梯度是关于的函数，而只能观测到在离散的训练样本上的取值，因此对的梯度也只能观测到在训练样本上的取值。为了泛化到测试样本，我们需要对训练集上的离散梯度值进行曲线拟合，得到梯度的近似。
我们首先将函数表示成由所有样本点在该函数上的离散值构成。即：
这是一个N维向量，可以计算：
上式是函数对向量的求导，得到的也是一个梯度向量。这里求导过程，首先是求,即每个样本点的F函数值，然后再根据具体的损失函数，来计算损失函数对函数值的导数，而不是对的导数。
但是， 只是描述了 在每个训练样本点上的值，并不足以表达 ，也就是说只是表达了训练集，不能泛化到其它数据上。重点在于，我们可以通过「函数拟合」的方法从 中构造出, 这是一个我们非常熟悉的问题，例如回归曲线拟合问题。这个问题可以当作一个子问题求解，只要损失函数可导即可。这样我们就近似得到了函数对函数的求导结果。
上述过程归纳起来，也就是加和扩展(additive expansion)和梯度下降(steepest-descent mini
mization)的结合。表示成如下形式：
其中是初始估计，是用于拟合负梯度的弱学习器，是最优步长，。
3.主要思想
了解了动因之后，我们从一般化函数估计问题谈起。首先仍然从介绍函数估计开始，函数估计的目标是得到对映射函数(从x映射到y)的估计,使得在所有训练样本的联合分布上，最小化期望损失函数 ：
上式是求联合分布，等于对在x上求边缘分布。
我们需要在函数空间进行数值优化。在函数空间，为了表示一个函数,理想状况下有无数个点，我们可以使用“非参数方法”来求解上述问题，非参数方法可以理解为，我们并没有指定的形式，任意的都有可能。
根据前文（参见动因一节），我们需要解：
是初始估计，是负梯度的拟合函数，是对梯度。是最优步长。
其中：
假设可以交换微分和积分的顺序，则：
乘子沿着步长方向进行线性搜索，代表步长：
然而我们面对的情况是只能用有限的数据集表示x，y的联合分布的时候，上述方法就有点行不通了，因为 不能被数据集上的每个点正确估计，即使可以，也只是针对训练集，不能泛化到其它任意点。
因此我们需要修改解的形式。可以通过限制为一系列带参数的函数集合 是一个有限的参数集合，即首先确定了的形式，然后再在参数空间中搜索的参数值，实际上这是将函数估计问题转化成了参数估计问题。
本文也采用类似的思想，使用“分步加和扩展(Stagewise Additive Expansion)”求解上述函数估计目标。即，我们定义的形式为：
其中，可以理解为基函数,是基函数的参数。对于GBDT而言，为CART树,而对应着这棵小的
CART树的结构，可以认为是基函数的权重。即，我们使用的是基函数乘上某个权重来拟合负梯度。该权重通常为1。
则可将上述优化问题转化为：
上述问题仍然是难以求解的。难以求解的原因是，我们要一次性同时出所有的（注意看min下标），也就是出所有基函数和的一个最优序列，每次有新的分类器加入，还需要调整之前的分类器。
一种贪心算法的思想是采用「Greedy Stagewise」方法，对,
然后更新：
可以看出这是一种分步加和扩展的方式(注意min的下标)，即每次只训练一个弱分类器，当新分类器被加入模型的时候，不调整原来得到的分类器, 实际上是一种贪心策略。
对于给定的损失函数和基分类器。上式求解比较困难。假设，在确定了的前提下，并且是的某个成员，同时也作为步长的方向，那么可以看作是对(1)的最优贪心步长(greedy step),也可以认为是(3)中的最深梯度下降步长。
我们构建样本函数值的负梯度如下：
因此N维空间上的函数负梯度可以表示为.然而这只是对训练集样本而言，不能泛化到其它样本上。也就是说，我们原本的目标是需要损失函数对函数进行求梯度(参考动因一节)，函数对函数的梯度难以求解，现在通过所有样本在处的「取值的梯度」集合来近似替代对函数的梯度。然而这里只是对训练集进行求值替代，为了能够泛化到其他数据集，我们需要「根据训练集在取值的梯度集合拟合出对的梯度」,使得其能够泛化到其它样本上。
具体而言，我们需要从中选择某一个，使得和最接近。这是一个典型的函数拟合问题，可以使用平方误差损失在样本上进行拟合：
注意上述平方误差损失只是用来拟合负梯度用的，和前面的是完全不一样的两个东西。对于GBDT而言，也就是「使用一棵新的回归树CART」，「拟合」损失函数对的「负梯度」。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。