回归问题(Regression)
考虑一个回归问题，已知n个样本
需要拟合一个函数 ，使得误差最小。
迭代拟合残差
当然，通常很难找到一个非常准确的 F，于是我们先找到一个预测准确性比较弱的 ，其预测值
与实际 y 值之间的差异，也就是残差
现在问题可以变成，尽量找到一个好的 来拟合
。假设我们拟合了一个
，现在总的拟合函数就是
。不幸的是，
虽然比
有提升，但依然存在残差
于是我们再寻找一个 来拟合
，于是
。
这个迭代可以一直进行下去，使函数 F(x) 不断逼近目标值 y。这样迭代拟合残差来构造的模型函数可以写作
即，初始模型 的预测就用所有样本目标值y的均值。第m轮迭代得到的模型函数
，等于上一轮函数
，加上对上一轮函数残差的拟合函数
。
不求一次性找到一个最优的拟合函数 F，而是采用迭代的方法构造出一系列函数，组合起来构成总的拟合函数 F，在迭代过程中不断逼近要拟合的真实函数，这是 Boosting 算法家族的共同特点。
梯度
我们现在要讨论的算法叫 Gradient Boosting，但是上面说了半天就是在拟合残差，好像跟梯度没啥关系啊！那么现在来研究一下误差函数 L 对拟合函数 F 的梯度。
对拟合函数 F，设拟合值
采用平方误差函数
对所有样本，总的误差
样本的目标值 是已知的，误差J 最后算出来的结果就是一个数值标量，总共有n个样本，所以 误差J 是n元变量
的函数。
计算 函数J 的梯度：
即 残差 = 负梯度
说明一下，上面偏导数写法是 ，不过有些文章会写作
。刚开始看到对
求偏导感觉有点疑惑，对函数求偏导怎么理解？仔细想想，其实
就是拟合函数的输出值，对于J来说，它也是一个变量。所以上面设
，这两个偏导是一样的，引入
主要是帮助理解。
在机器学习领域，梯度下降是很常用的算法，通常应用梯度下降是 误差J 对模型 F(x,w)的参数w 计算梯度，也就是说使用梯度下降的目的是 寻找最优的参数，使得模型
的预测值 与目标值y 的误差J 最小。
而这里 Gradient Boosting 是 误差J 对 F的值 计算梯度，即对 计算梯度，而不关心F的参数w。实际上也没法关心，因为在迭代过程中，F的参数在上一轮迭代已经确定好了，F已经是确定的（记得第一个
是先给出的，然后再开始迭代），现在的关注点是残差。
其它误差函数
上面推导出 残差=负梯度，但两者既然一样，好像也没有引出什么新的东西。不过，上面的结论是采用平方误差函数的情况。如果考虑其它误差函数，用梯度计算时我们可以得到一些不同的特性。我们对比看几个例子：
1. 残差
2. 平方误差
负梯度
3. 绝对误差
负梯度
4. Huber 误差
负梯度
可见，平方误差的负梯度=残差，而绝对误差和Huber误差的 负梯度 残差。
这些差异会带来什么不同的特性呢？
公式(1)表明，绝对误差的负梯度是 {-1,1}，每个样本的残差都映射到 {-1,1}，差别大小被忽略了。
公式(2)表明，Huber误差的负梯度，在 误差绝对值 时等于残差，但 误差绝对值
时被限制为
，即“残差”上限是
。
所以，相对原始的残差 ，这两种负梯度都弱化了异常值的影响。如果我们拟合这三种负梯度，会发现平方误差对异常值（outliers）的敏感度较高，Huber 误差、绝对误差对异常值的敏感度较低。
负梯度 / 伪残差
虽然绝对误差和Huber误差的 负梯度 残差，但负梯度也是根据误差 L 计算出来的，从上面的分析也可以看出，不同误差函数得到的负梯度主要是对残差进行了一些限制或调整，所以，我们可以把负梯度理解为一种“伪残差”，或者说，经过调整的残差。
Gradient Boosting 算法步骤
对于回归问题，已知n个样本 ，求拟合函数
，使得误差最小。
首先选取一个可微分的误差函数L。
- 产生一个初始模型，比如
- 进行M次迭代
2.1 计算L对F的负梯度
2.2 构建函数 h 拟合负梯度
2.3 计算h的权重系数，使得F增加h后的总误差
最小。
这里 y、F、h 都已知，可以用一维优化方法计算出
2.3 F 更新为 F+
Gradient Boosting vs AdaBoost
同属 Boosting 家族，Gradient Boosting vs AdaBoost 在大方向上是一致的，都是通过迭代构建弱模型，逐步增强（Boosting）并组合为强模型。
主要的差别集中在，Gradient Boosting 迭代拟合负梯度（“伪残差”），AdaBoost 迭代调整样本的权重。
关于 AdaBoost 可以参考上一篇文章 Boosting/AdaBoost —— 多级火箭助推。
另外，Gradient Boosting 并不只用于回归问题，也可以用在分类和排名问题，本文不再详述。
参考
A Gentle Introduction to Gradient Boosting
维基百科 - Gradient boosting
