前文介绍了gbrank和logisticRank，顺着logisticRank思路，我们可以接触到gradient boosting框架以及经典的gradient boosting decision tree(GBDT)。
后续的介绍主要回答下面三个问题：

  1. gradient boosting是什么框架 [上篇]
  2. 最小绝对值误差LAD， 最小均方差LST， HUBER-M函数，三者有什么区别[下篇]
  3. gbdt怎么处理分类问题[下篇]

本篇学习路径较深，建议先看引文[2]决策树之CART算法和[3] GBDT(MART)迭代决策树入门教程。
计划按提出者Jerome H. Friedman论文[1]思路介绍gbdt，希望通过总结这篇笔记，得到对算法更具体的认识，又能更抽象地记忆。

级联函数的介绍

给定${\bf{x}} = \left\{ {{x_1},...,{x_n}} \right\}$和对应的输出$y$，进行学习预测。根据样本集$\left\{ {{y_i},{{\bf{x}}_i}} \right\}_1^N$估计（逼近）函数$\hat F\left( x \right)$。在样本集上得到最小化 loss function 得到的函数，记为 ${F^*}\left( x \right)$。
$$\begin{equation}{F^*}\left( x \right) = \arg \mathop {\min }\limits_F {E_{y,{\bf{x}}}}L\left( {y,F\left( {\bf{x}} \right)} \right) = \arg \mathop {\min }\limits_F {E_{\bf{x}}}\left[ {{E_y}\left( {L\left( {y,F\left( x \right)} \right)} \right)|x} \right]\end{equation}$$
对于回归问题，loss function最常用最小均方误差$(y-F)^2$和$|y-F|$最小绝对值误差。分类问题常用二元负log似然loss function，$log(1+e^{-2yF})$，其中 $y \in \left\{ { - 1,1} \right\}$，后面还会介绍多元log似然loss function。
通常做法是将$F(\bf x)$限制为带参函数族$F(x; \bf{P})$。其中${\bf{P}} = \{ {p_1},{p_2},...\}$ ，$p_i$选定以后就可以得到$F(x)$中的每个组成函数。GBDT采用如下级联形式的公式：$$\begin{equation}F\left( {{\bf{x}};\left\{ {{\beta _m},{{\bf{a}}_m}} \right\}_1^M} \right) = \sum\limits_{m = 1}^M {{\beta _m}h\left( {{\bf{x}};{{\bf{a}}_m}} \right)} \end{equation}$$
公式$(2)$中的通用式$h\left( {{\bf{x}};{{\bf{a}}_m}} \right)$是关于$x$的带参函数，参数空间为$a={a_1, a_2, ...}$。通过选定不同的$a_m$，得到不同的级联函数子项。函数子项如果使用$CART$[2]作为回归树进行学习，那么参数$a_m$包含选择作为分裂点的变量（用何项分裂）、分裂点的分裂值（用何值进行分裂）、每棵树叶结点的均值（何时终止分裂），这就是GBDT的构造思路。

作者介绍了初始目标函数$(1)$的两种优化方法，数值优化和函数空间的数值优化，再引入GBDT的解法。前者适合辅助理解GBDT的构造，后者可以在原文中找到描述。

带参函数在数值空间的优化

引入参数表达后，我们把目标优化函数$(1)$式改造为
$$\begin{equation}{F^*}\left( x \right) = F\left( {x;{{\bf{P}}^*}} \right) = \arg \mathop {\min }\limits_p {E_{y,{\bf{x}}}}L\left( {y,F\left( {x;{\bf{P}}} \right)} \right)\end{equation}$$
对于大多数$F(x;\bf{P})$和loss function $L$，可以用数值优化算法进行求解。通常解的形式如下：$${{\bf{P}}^*} = \sum\limits_{m = 0}^M {{{\bf{p}}_m}} $$
其中$\bf{p_0}$随机初始化，$\left\{ {{{\bf{p}}_m}} \right\}_1^M$为随后每一步的增量，其值由优化算法决定。

梯度下降法

梯度下降法是最常用的数值最小化方法，记能量函数为$\Phi (x) = {E_{y,{\bf{x}}}}L\left( {y,F\left( {x;{\bf{P}}} \right)} \right)$，通过梯度下降法可以按如下套路进行求解：

  1. 计算梯度$g_m$为$${g_m} = \left\{ {{g_{jm}}} \right\} = \left\{ {{{\left[ {{{\partial \Phi (x)} \over {\partial {P_j}}}} \right]}_{{\bf{P}} = {{\bf{P}}_{m - 1}}}}} \right\}$$这里${{\bf{P}}_{m - 1}} = \sum\limits_{i = 0}^{m - 1} {{{\bf{P}}_i}} $
  2. 得到下降梯度方向，通过线搜索算法确定步长：
    $${{\bf{p}}_m} = - {\rho _m}{{\bf{g}}_m}$$，其中${\rho _m} = \arg \mathop {\min }\limits_\rho \Phi ({{\bf{P}}_{m - 1}} - \rho {{\bf{g}}_m})$。

有限集合的求解

如果我们在一个有限集合$\left\{ {{y_i},{{\bf{x}}_i}} \right\}_1^N$估计$\left( {y,{\bf{x}}} \right)$的联合分布，在这个集合上不能得到确定的解${E_y}\left[ { \cdot |{\bf{x}}} \right]$。我们需要学习这些训练样本得到最优函数表达$F^*({\bf x})$，进而去估计新的点${\bf x}$。样本点通过影响最终的函数对测试样本点的值施加约束。（按，同样是约束，我理解GBDT是判别形式，而高斯过程是产生形式，通过训练样本点和测试样本点的关系去施加约束，先估计联合高斯分布。）我们前面介绍过参数估计和优化的方法，可以写成如下形式：
$$\begin{equation}\left\{ {{\beta _m},{{\bf{a}}_m}} \right\}_1^M = \arg \mathop {\min }\limits_{\left\{ {\beta {'_m},a{'_m}} \right\}_1^M} \sum\limits_{i = 1}^N {L\left( {{y_i},{F_{m - 1}}\left( {{{\bf{x}}_i}} \right) + \beta 'h\left( {{{\bf{x}}_i};{\bf{a}}'} \right)} \right)} \end{equation}$$
这个解可以尝试进行贪心的梯度下降方法，通过每一级的逼近，对于$m=1,2,...M$，每一级参数估计如下：$$\begin{equation}\left\{ {{\beta _m},{{\bf{a}}_m}} \right\} = \arg \mathop {\min }\limits_{\beta ,{\bf{a}}} \sum\limits_{i = 1}^N {L\left( {{y_i},{F_{m - 1}}\left( {{{\bf{x}}_i}} \right) + \beta h\left( {{{\bf{x}}_i};{\bf{a}}} \right)} \right)} \end{equation}$$
最后得到解函数的形式为：
$${F_m}\left( {\bf{x}} \right) = {F_{m - 1}}\left( {{{\bf{x}}_i}} \right) + \beta 'h\left( {{{\bf{x}}_i};{\bf{a}}'} \right)$$
在每一级的增加过程，逐级策略和数值优化介绍的逐步累加的方式有所区别。这种方法也叫boosting，$h(x;a)$为弱分类器，通常为分类树，如果不引发歧义，可以理解为子函数。

下面介绍GB的一般套路

假设给定了前$m-1$级的逼近函数$F_{m-1}({\bf x})$，当前的子函数$\beta_mh({\bf x;a})$可以视为最优解函数$F^*(x)$在梯度方向贪心策略的一步最佳逼近，这时子函数$h({\bf x;a})$视为参数化函数类$h({\bf x;a})$的成员，每一个级联过程就等同于最速下降法的每一步，我们可以通过梯度得到子函数的参数估计。
$$ - {g_m}\left( {{{\bf{x}}_i}} \right) = - {\left[ {{{\partial L\left( {{y_i},F\left( {{{\bf{x}}_i}} \right)} \right)} \over {\partial F\left( {{{\bf{x}}_i}} \right)}}} \right]_{F\left( {\bf{x}} \right) = {F_{m - 1}}\left( {\bf{x}} \right)}}$$
我们可以得到第$M$步在训练集上关于$F_{m-1}(x)$的最佳梯度$-{\bf g}_m=\{-g_m({\bf x}_i) \} _1^N$。这些得到的梯度是从训练样本集中获取，并不能泛化到其他未知样本点。我们通过约束子函数$h({\bf x;a})$，使它满足在训练样本上的值${\bf h}_m=\{h({\bf x_i;a_m})\}_1^N$与$-{\bf g}_m \in R^N$平行。根据上面的论述，子函数$h({\bf x;a})$和$-{\bf g}_m(x)$强相关，可以从下面式子中解出来：$$\begin{equation} {{\bf{a}}_m} = \arg \mathop {\min }\limits_{{\bf{a}},\beta } {\sum\limits_{i = 1}^N {\left[ { - {g_m}\left( {{{\bf{x}}_i}} \right) - \beta h\left( {{{\bf{x}}_i};{\bf{a}}} \right)} \right]} ^2} \end{equation}$$
负梯度$\{h({\bf x_i;a_m})\}_1^N$替换$-{\bf g}_m \in R^N$，前面说过，有了梯度方向，我们还需要通过线搜索得到最佳步长
$$\begin{equation} {\rho _m} = \arg \mathop {\min }\limits_\rho \sum\limits_{i = 1}^N {L\left( {{y_i},{F_{m - 1}}\left( {{{\bf{x}}_i}} \right) + \rho h\left( {{{\bf{x}}_i};{{\bf{a}}_m}} \right)} \right)} \end{equation}$$
那么第$m$级的函数逼近为：$${F_m}\left( {\bf{x}} \right) = {F_{m - 1}}\left( {\bf{x}} \right) + {\rho _m}h\left( {{\bf{x}};{{\bf{a}}_m}} \right)$$

将公式$(5)$中的解替换为$(6)(7)$带来的变化 ，作者描述为：”Basically, instead ofobtaining the solution under a smoothness constraint, the constraint is applied to the unconstrained (rough) solution”，需要后续琢磨下

通过$h({\bf x;a})$拟合pseudo-responses：$\left\{ {{{\tilde y}_i} = - {g_m}\left( {{x_i}} \right)} \right\}_{i = 1}^N$，在前面博客引用的wiki页中也称为pseudo -residuals，是一个概念。这样的变化把公式$(5)$难优化的问题转为了$(6)$中较容易优化的最小均方误差和$(7)$中较为简单的单参数优化。我们可以通过逐级的方式最小化任何可导的loss function$L(y,F)$。在每一级中，用最小均方误差从公式$(6)$中解出$h({\bf x;a})$。所以导出下面的通用GB流程：

  1. ${F_0}\left( {\bf{x}} \right) = \arg {\min _\rho }\sum\nolimits_{i = 1}^N {L\left( {{y_i},\rho } \right)} $
  2. $For\;m = 1\;to\;M\;do:$
  3. ${{\tilde y}_i} = - {\left[ {{{\partial L\left( {{y_i},F\left( {{{\bf{x}}_i}} \right)} \right)} \over {\partial F\left( {{{\bf{x}}_i}} \right)}}} \right]_{F\left( {\bf{x}} \right) = {F_{m - 1}}\left( {\bf{x}} \right)}},i = 1,N$
  4. ${{\bf{a}}_m} = \arg {\min _{{\bf{a}},\beta }}{\sum\nolimits_{i = 1}^N {\left[ {{{\tilde y}_i} - \beta h\left( {{{\bf{x}}_i};{\bf{a}}} \right)} \right]} ^2}$
  5. ${\rho _m} = \arg \mathop {\min }\limits_\rho \sum\nolimits_{i = 1}^N {L\left( {{y_i},{F_{m - 1}}\left( {{{\bf{x}}_i}} \right) + \rho h\left( {{{\bf{x}}_i};{{\bf{a}}_m}} \right)} \right)} $
  6. ${F_m}\left( {\bf{x}} \right) = {F_{m - 1}}\left( {\bf{x}} \right) + {\rho _m}h\left( {{\bf{x}};{{\bf{a}}_m}} \right)$
  7. $end For$

根据不同的loss函数，第4行的负梯度计算也不同，其他计算条件期望的拟合方法也可以用，例如最小绝对值误差(LAD)，Huber(M)。这里使用最小均方差(LS)表示只是因为比较自然，分类问题中还可以有$L(y,F)=L(yF)$。

下一篇介绍，最小绝对值误差LAD， 最小均方差LST， HUBER-M函数这三个不同loss function对应的方法，以及 gbdt怎么处理分类和回归问题

参考

[1] Friedman J H. Greedy Function Approximation: A Gradient Boosting Machine[J]. Annals of Statistics, 2000, 29(5):1189–1232.
[2] 决策树之CART算法
[3] GBDT（MART）迭代决策树入门教程

ShawnXiao@baidu