之前一篇写了关于基于权重的 Boosting 方法 Adaboost，本文主要讲述 Boosting 的另一种形式 Gradient Boosting ，在 Adaboost 中样本权重随着分类正确与否而在下一次迭代中动态发生改变；Gradient Boosting 并没有样本权重的概念，它也采用 Additive Model ，每次迭代时，用损失函数刻画目标值与当前模型输出的差异，损失函数的负梯度则可以近似代表目标值与当前输出的残差，本次迭代产生的模型拟合该残差建立基学习器，然后加到整体模型即可。这便是 Gradient Boosting 的思想。这里先对Gradient Boosting 进行介绍，之后就是关于 Gradient Boosting 的热门方法 Gradient Boosting Regression Tree 即 GBDT。
Gradient Boosting
Gradient Boosting 采用的也是 Additive Model 与前向分部算法，其模型可以表示为：
\[f_M(x) = \sum_m \gamma_m T(x; \theta_m)\]
首先确定初始模型，定义初始基学习器 $f_0(x)$ ，当模型迭代到第 $m$ 步时：
\[f_m(x) = f_{m-1}(x) + \gamma_mT(x; \theta_m)\]
通过最小化损以下损失来确定参数 $\theta_m$ 的值：
\[arg \min_{\theta_m} \sum_iL(y_i,f_{m-1}(x_i) + \gamma_mT(x; \theta_m))\]
这里以回归为例来说明 Gradient Boosting 的思想，对于样本 $(x_i,y_i)$ , 目标是使得模型输出值 $f_M(x_i)$ 与 $y_i$ 尽可能接近，当模型迭代到第 $m$ 步时，已经得到 $f_{m-1}(x)$ 的值，待估计的是基学习器 $T(x; \theta_m)$ 的参数$(\gamma_m,\theta_m)$，如何得到一个较优的参数来使得 $f_{m-1}(x) + \gamma_{m}T(x; \theta_m)$ 与 $y_i$ 的差异进一步较小呢？这里可以引入损失函数来衡量当前模型输出值与目标值的差异，损失函数越越小，则 $y_i$ 与模型输出越接近，所以迭代过程中需要使得损失不断减小，满足的条件为：
\[L(y_i,f_m(x_i)) < L(y_i,f_{m-1}(x_i))\]
每次迭代都使得损失函数减小，不断迭代求解损失函数的极小值，这正好就是 Gradient Descent 的思想，回忆 Gradient Descent ，对于给定的关于 $\theta$ 的损失函数 $L( \theta)$ :
\[ \theta ^{new} = \theta ^{old} - \frac{\partial L(\theta)}{ \partial \theta^{old}}\]
不断迭代，最终会找到一个最优的 $\theta^*$ ，满足：
\[\theta^* = arg\min_{\theta} L(\theta)\]
在 Gradient Boosting 的第 $m$ 次迭代，把 $L(y_i,f_{m-1}(x_i))$ 看做 $f_{m-1}(x_i)$ 的函数，则该损失在沿 $f_{m-1}(x_i)$ 梯度下降的方向上不但使得损失函数减小，而且损失函数减小的最快：
\[f_{m}(x_i) = f_{m-1}(x_i) – \frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}\]
很明显，满足上述等式即可使得损失减小 ，模型的输出值更加接近真实值，$f_m(x)$ 与 $f_{m-1}(x)$ 的差 $– \frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}$ 为两次迭代中基学习器 $\gamma_mT(x ; \theta_m)$ 需要拟合的 $residual$ ，拟合这个 $residual$ 便能使得损失函数下降的最快，所以每次迭代把当前的训练数据替换为 $(x_i,r_{mi})_{i=1}^N$ 来训练基学习器 $T(x ; \theta_m)$ 即可，拟合该残差后使得模型进一步朝梯度下降的方向前进，不断迭代得到便可得到使得损失最小的模型 $f_M(x)$。综上给出 Gradient Boosting 的代码：
输入： 训练集 $\left \{ (x_i,y_i)\right \}^N_{i=1}$ , 损失函数 $L(y,f(x))$.
1. 用常数 $c$ 初始化模型：
\[f_0(x) = arg \min_c \sum_iL(y_i,c)\]
2. $for$ $m = 1,…,M$ $do$:
a）计算近似残差:
\[r_{mi} = \left [ -\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right ]_{f(x_i) = f_{m-1}(x)} \ \ \ ,\left \{1,2,…,N \right \} \]
b）用近似残差来拟合基学习器 $T(x; \theta_m)$，训练集为 $\left \{ (x_i,r_{mi})\right \}^N_{i=1}$
c）计算基学习器的权重 $\gamma_m$：
\[ \gamma_m = arg \min_{\gamma}\sum_iL(y_i,f_{m-1}(x_i) + \gamma T(x; \theta_m)) \]
d）更新模型：$f_{m}(x) = f_{m-1}(x) + \gamma_m T(x; \theta_m)$
3. 输出最终模型$f_M(x)$.
Gradient Boosting 的目标是不断减小模型的 Bias ，并没有关注 Variance ，所以需要注意 Bias 与 Varance 之间的权衡，因为一味的减小 Bias ，可能导致 Variance 可能过大，进而导致模型过拟合，失去了模型的泛化能力，需要考虑一些避免过拟合的方法：
- 增大 M ， M 增大会使得 Variance 会减小，但泛化能力会很差，M 可以通过 Cross Validation 的方式选取；
- 在损失函数中加入正则，正则其实就是在当前迭代中把当前基学习器的复杂度也考虑进去，不要让当前模型太复杂；
- Shrinkage（收缩）方法，Shrinkage 是在迭代过程中对模型进行更新时乘以一个参数 $v$ 满足 $0<v<1$ ，实践中设置很小的 Shrinkage 参数 $v$ 比如 $v < 0.1$ ，会比 $v = 1$ 产生非常好的泛化性能。但 $v$ 设置很小 需要的迭代次数 M 大一些：
\[f_{m}(x) = f_{m-1}(x) + v \cdot \gamma_m T(x; \theta_m)\]
xgboost 对 GBDT 的优化
补充一下 xgboost 对于GBDT 的优化，来自知乎 wepon 的回答（侵删）：
1）传统 GBDT 以 CART 作为基分类器，xgboost 还支持线性分类器，这个时候 xgboost 相当于带 L1 和 L2 正则化项的Logistic 回归（分类问题）或者线性回归（回归问题）。
2）传统 GBDT 在优化时只用到一阶导数信息，xgboost 则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost 工具支持自定义代价函数，只要函数可一阶和二阶求导。
3）xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的 L2 模的平方和。从 Bias-variance tradeoff 角度来讲，正则项降低了模型的 variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
\[\gamma_m = arg \min_{\gamma}\left \{ \sum_iL(y_i,f_{m-1}(x_i) + \gamma T(x; \theta_m)) + \Omega (T) \right \}\]
这里 $\Omega (T)$ 即为引入的正则损失：
\[\Omega (T) = \alpha T + \frac{1}{2}\beta \sum_{j=1}^Tw_j^2\]
4）Shrinkage（缩减），相当于学习速率（ xgboost 中的 $\eta$）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把 $\eta$ 设置得小一点，然后迭代次数设置得大一点。
5）列抽样（column subsampling）。xgboost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是 xgboost 异于传统 gbdt 的一个特性。
6）对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
7）xgboost 工具支持并行。boosting 不是一种串行的结构吗?怎么并行的？注意 xgboost 的并行不是 tree 粒度的并行， xgboost 也是一次迭代完才能进行下一次迭代的（第 t 次迭代的代价函数里包含了前面 t-1 次迭代的预测值）。 xgboost 的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点）， xgboost 在训练之前，预先对数据进行了排序，然后保存为 block 结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个 block 结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
8）可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。
Gradient Boosting Decision Tree
Gradient Boosting Decision Tree 即为强大的 GBDT ，其实就是基学习器采用的 Decision Tree 的 Gradient Boosting 方法，常用的就是 CART 了，既可用于分类，也可用于回归。GBDT 可以用作分类与回归，或者是特征组合，最后是关于 GBDT 并行化的问题，GBDT是工业生产与各种竞赛中的热门方法，值得好好研究一下，接下来一一讨论。
（1）GBDT 用作回归。当基学习器采用 Regression Tree 结合 Gradient Boosting 的方法来做回归，算法是迭代进行的，初始时给出一个最优的偏置常数 $c$ ，然后每次迭代分别计算出一颗回归树，注意这里设置回归树最多有固定的 $J$ 个叶节点，叶节点数目达到 $J$ 后便不会再增多，迭代中每颗树都会拟合上一次损失函数的负梯度，最终通过加权的方式将 M 颗树组合起来，最终共同作出决策。GBDT回归算法如下：
输入： 训练集 $\left \{ (x_i,y_i)\right \}^N_{i=1}$ , $x_i \in \mathbb{R}^n,y \in \mathbb{R}$ ，损失函数 $L(y,f(x))$.
1. 初始化偏置常量 $c$ :
\[ f_0(x) = arg\min_c \sum_i L(y_i , c)\]
2. $for$ $m = 1,…,M$ :
a) 计算残差项 $r_{mi}$ ：\[r_{mi} = \left [ -\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right ]_{f(x_i) = f_{m-1}(x_i)} \ \ \ ,i= \left \{1,2,…,N \right \} \].
b) 使用数据 $\left \{ (x_i,r_{mi})\right \}^N_{i=1}$ 拟合回归树，产生 $J$ 个决策区间 $R_{mj},j = 1,2,…,J$
c) $for$ $j = 1,2,…,J$ :
\[ \gamma_{mj} = arg \min_{\gamma}\sum_{x_i \in R_{mj}}L(y_i,f_{m-1}(x_i) + \gamma) \]
d) 更新模型: $f_m(x) = f_{m-1}(x) + \sum_j \gamma_{mj}I(x \in R_{mj}) $.
3. 输出最终的累加结果： $f_M(x) = \sum_m\sum_j\gamma_{mj}I(x \in R_{mj})$.
这里每棵树的每个决策区间都有一个权值，最终通过加权的方式共同作出决策。
（2）GBDT用作分类。这里讨论 K 分类问题，每个样本 $(x_i,y_i)$ 都会对应一个类别 $k$ ，其中 $y_i \in\mathbb{R}^K$ 为一个 K 维向量，类别为 $k$ 时，对应的 $y_{ik}$ 为 1 。假设样本 $(x_i,y_i)$ 的类别为 $k$ ，在第 $m$ 次迭代中，模型当前的输出为向量 $f_{m-1}(x) \in \mathbb{R}^K$，第 $k$ 维的值是 $f_{m-1,k}(x)$ ，对输出做一个 Softmax 归一化，可以得到类别 $k$ 的概率 $p_{m-1,k}(x)$ ，且概率和为 $\sum_k p_{m-1,k}(x) = 1$ ，这模型的输出作为 Softmax 层来处理：
\[p_{m-1,k}(x) = \frac{exp(f_{m-1,k}(x))}{\sum^K_{l = 1}exp(f_{m-1,l}(x))}, \ \ \ k=1,…,K\]
对应的所需极小化的损失函数便为 Cross Entropy：
\[L(y_i,f_{m-1}(x_i)) = -\prod_{k=1}^K [f_{m-1,k}(x_i)]^{y_{ik}}\]
对损失函数取 $log$ 之后得到等价的损失为：
\[ L(y_i,f_{m-1}(x_i)) = -\sum_{k=1}^K y_{ik}log f_{m-1,k}(x_i)\]
由于是 K 分类问题，求解第 $m$ 个基分类器时模型的输出为 K 维向量 $f_{m-1}(x)$ ，负梯度方向也为一个向量，第 $m$ 个基学习器需要拟合 residual 向量的每一维：
\[r_{i} = -\frac{\partial L(y_i,f_{m-1}(x_i))}{ \partial f_{m-1,k}(x_i)} = y_{i} –p_{m-1}(x_i) \]
以上的计算参考 之前的文章多层感知机及其BP算法（Multi-Layer Perception），文章中关于 Softmax 损失函数求导的部分跟这个计算完全一样。
这里用一个例子来说明，对于 $K=5$ 的分类问题， $y_i = (0,0,1,0,0)$ ，模型的估计值为 $f(x_i) = (0, 0.3, 0.6, 0, 0)$，则经过 Softmax 归一化之后得到 $p(x_i) = (0.16,0.21,0.29,0.16,0.16)$，residual 为负梯度 $y_i – p(x_i)$ ,进而可得到近似残差 $r_i：(-0.16, -0.21, 0.71, -0.16, -0.16)$ , 接下来用 $\left \{ (x_i,r_i)\right \}^N_{i=1}$ 继续构建基学习器去拟合残差向量 $r_i$ ，需要现在学习器需要在第 3 个维度增大，其余维度减小来进一步接近 $y_i$ 的取值接下来用训练数据拟合残差即可，综上，用于 K 分类的 GBDT 算法过程如下：
输入： 训练集 $\left \{ (x_i,y_i)\right \}^N_{i=1}$ , $x_i \in \mathbb{R}^n,y \in\mathbb{R}^K$ ，损失函数 $L(y,f(x))$.
1. 初始化 $f_{0，k} = 0 , \ \ \ k = 1,2,…K$
2. $for$ $m=1,2,…,M$ $do$:
3. 进行 Softmax 归一化：
\[p_{m-1,k}(x) = \frac{exp(f_{m-1,k}(x))}{\sum^K_{l = 1}exp(f_{m-1,l}((x))}, \ \ \ k=1,…,K\]
4. $for$ $k = 1,2,…,K$ $do$:
a) 计算 residual :
\[ r_{ik} = \frac{\partial L(y_i,f_{m-1}(x_i))}{ \partial f_{m-1,k}(x_i)} = y_{ik} –p_{m-1,k}(x_i), \ \ i = 1,2,…N \]
b) 用 $\left \{ (x_i,r_{ik})\right \}^N_{i=1}$ 拟合 $J$ 个节点的分类树 $\left \{R_{mkj} \right \}_{j=1}^J$
c) 计算权重参数：
\[\gamma_{mkj} = \frac{K-1}{K} \frac{ \sum_{x_i \in R_{mkj}} r_{ik} }{\sum_{x_i \in R_{mkj}} |r_{ik}|(1-|r_{ik}|)} , \ \ \ j = 1,2,...,J\]
d)更新模型 $f_{m,k}(x) = f_{m-1,k}(x) + \sum_j\gamma_{mkj}I(x \in R_{mkj})$
把最终的分类模型写为向量形式可以得到 : $f_M(x) = \left \{ f_{M,1}(x),f_{M,2}(x),...,f_{M,K}(x) \right \}$，模型求解时，共迭代 M 次，每次建立 K 颗树，共建立 M $\times$ K 颗树，每个类别下为 M 颗树的加权，对数据 $x$ 进行预测时，得到的向量 $f_M(x)$ 中最大的一个维度即为其类别。关于GBDT 的工业实现，可以参考 xgboost ，这个以后有时间再看。
（3）GBDT用做作特征组合，在一些算法中，特征扩展能有效提升模型精度，特征组合便是有效的特征扩展手段，比如在 Logistic Regression 模型中的特征组合扩展特征十分关键，通过笛卡尔积可以扩展特征，比如特征$A$ 取值为 $a, b$，特征 $B$ 取值为$0, 1, 2$，则 $A,B$ 的笛卡尔积为$\left \{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2) \right \}$，瞬间多出 $N_A \times N_B$ 个特征。但是对哪些特征进行笛卡尔积只能依靠人工经验，耗时耗力同时并不一定会带来效果提升。如何自动发现有效的特征、特征组合，弥补人工经验不足，缩短 LR 特征实验周期，是亟需解决的问题。Facebook 2014年的文章介绍了通过GBDT 解决LR的特征组合问题。
GBDT 的思想在特征组合方面具有天然优势，可以发现多种有区分性的特征以及特征的组合，决策树的路径可以直接作为LR输入特征使用，省去了人工寻找特征、特征组合的步骤。这种通过 GBDT 生成 LR 特征的方式（GBDT+LR），业界已有实践（Facebook，Kaggle-2014），且效果不错，是非常值得尝试的思路。GBDT前面的树，特征分裂主要体现对多数样本有区分度的特征；后面的树，主要体现的是经过前N颗树，残差仍然较大的少数样本。优先选用在整体上有区分度的特征，再选用针对少数样本有区分度的特征，思路更加合理，所以用 GBDT 来做特征组合会有意想不到的效果。GBDT 与 LR的融合方式，Facebook的paper有个例子如下图2所示，图中Tree1、Tree2为通过 GBDT 模型学出来的两颗树，$x$ 为一条训练样本，遍历两棵树后，$x$ 分别落到两颗树的叶子节点上，每个叶子节点对应 LR 的一维组合特征，那么通过遍历树，就得到了该样本对应的所有 LR 特征。由于树的每条路径，是通过最小化均方差等方法最终分割出来的有区分性路径，根据该路径得到的特征、特征组合都相对有区分性，效果理论上不会亚于人工经验的处理方式。4）GBDT的并行化。由于 Gradient Boosting 本质上还是串行算法，并行化主要包括了数据并行与建树时寻找最优切分特征时并行计算的；其中耗时部分仍然是遍历所有可能的特征值，并按照相应的增益公式寻找增益最大的分裂点的过程；（增益公式并不是指 Information Gain）；其中 Boosting 的阶段还是串行的。并行时用一个 $master$ 节点来进行同步控制，具体的并行方法如下：
——————————————————————————————————————————
1. 将样本按行分成 $n$ 份，分别在 $n$ 个节点上做计算；
2. 并行建立一棵的过程：
a) 在 master 节点上对特征随机采样，生成建立一棵树需要用到的特征，并分发到 $n$ 个节点上；
b) 在 master 结点上维护每一维采样特征所有可能的特征值；
c) 将每一维特征的每一个可能的特征值分发到 $n$ 个节点上；
d) 根据分发得到的特征值的，各个子节点上的样本分割成左右子树，计算增益 IG ；
e) 归并所有节点的增益，在 master 结点得到每一个特征在每一个特征值的增益 (feature，val，IG)；
f) 在 master 结点上找出最大的 (feature，val，IG)，作为本次的最佳裂点，分发到 n 个节点上；
g) n 个节点将样本按照 (feature，val，IG) 分割成左右子树；
h) 对左右子树继续上面过程，直到叶子节点数目满足要求；
3. 回到 2 并行建立第二棵树.
———————————————————————————————————————————
需要注意，这里的随机采样是对 Gradient Boosting 的一种优化方式，类似于 Random Forest，随机选取一些特征来进行计算，即列抽样，不仅能降低过拟合，还能较少计算。
参考： http://blog.csdn.net/w28971023/article/details/43704775
https://en.wikipedia.org/wiki/Gradient_boosting
http://blog.csdn.net/w28971023/article/details/43704775
https://www.zhihu.com/search?type=content&q=xgboost
http://www.cnblogs.com/LeftNotEasy/archive/2011/03/07/1976562.html
《统计学习方法》