梯度提升树

提升树是分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。

1.1 提升树模型

提升树的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。提升树模型可以表示成决策树的加法模型。

$$f_M(x) = \sum_{m=1}^{M}T(x;\Theta_m)$$

​ 其中，$T(x;\Theta_m)$表示决策树；$\Theta_m$表示决策树的参数；$M$为树的个数.

1.2 提升树算法

提升树算法采取前向分步算法。首先确定初始提升树$f_0(x) = 0$,第$m$步的模型是

$$f_m(x) = f_{m-1}(x)+T(x;\Theta_m)$$

其中$f_{m-1}(x)$为当前模型，通过经验风险极小化确定下一棵决策树的参数$\Theta_m$,

$$\hat{\Theta}_m = \arg \min_{\Theta_m}\sum_{i=1}^{M}L(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$$

由于树的线性组合可以很好的拟合训练数据，即数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。

下面讨论针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括用平方损失函数的回归问题，用指数损失函数的分类问题，以及一般损失函数的一般决策问题。

对于二分类分类问题，提升树算法只需要将$Adaboost$算中基本分类器限制为二类分类树即可，可以说这时的提升树算法是$Adaboost$算法的特殊情况，这里不再详细叙述。下面重点叙述回归问题的提升树。

已知一个训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)},x_{i} \in \chi \subseteq\mathbb{R}^n$,$\chi$为输入空间，$y_i \in \nu \subseteq \mathbb{R} $ ,$\nu$为输出空间。如果将输入空间$\chi$划分成$J$个互不相交的区域$R_1,R_2,…,R_J$，并且在每个区域上确定输出的常量$c_j$,那么树可以表示为

$$T(x;\Theta) = \sum_{j=1}^{J}c_jI(x \in R_j)$$

其中参数$\Theta={(R_1,c_1),(R_2,c_2),…,(R_J,c_J)}$表示树的区域划分和各区域上常数，$J$是回归树的复杂度即叶子节点的个数。

回归问题提升树使用以下前向分布算法：

$$\begin{aligned} f_0(x) &= 0\\ f_m(x) &= f_{m-1}(x) + T(x;\Theta_m),m = 1,2,...,M \\ f_M(x) &= \sum_{m=1}^{M}T(x;\Theta_m) \\ \end{aligned}$$

在前向分布算法的第$m$步，给定当前模型$f_{m-1}(x)$，需求解

$$\hat{\Theta}_m = \arg \min_{\Theta_m}\sum_{i=1}^{M}L(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$$

得到$\hat{\Theta}_m$,即第$m$棵树的参数。

当采用平方损失函数时，

$$L(y,f(x)) = (y - f(x))^{2}$$

其损失变为

$$\begin{aligned} L(y,f_{m-1}(x) - T(x;\Theta_m)) &=(y - f_{m-1}(x) - T(x;\Theta_m))^{m}\\ &= (r - T(x;\Theta_m))^2 \end{aligned}$$

这里,

$$r = y - f_{m-1}(x)$$

是当前模型拟合数据的残差(residual),所以，对回归问题的提升树来说，只需要简单地拟合当前模型的残差。这样，算法是相当简单。

算法1 回归问题的提升树算法

输入：训练数据$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)},x_{i} \in \chi \subseteq\mathbb{R}^n$,$\chi$为输入空间，$y_i \in \nu \subseteq \mathbb{R} $ ,$\nu$为输出空间

输出：提升树$f_M(x)$

(1) 初始化$f_0(x) = 0$

(2) 对$m=1,2,3,…,M$

​ (a) 按照式$r = y - f_{m-1}(x)$计算残差

$$r_{mi} = y_i - f_{m-1}(x_i), i = 1,2,...,N$$

​ (b) 拟合残差$r_{mi}$学习一棵回归树，得到$T(x;\Theta_m)$

​ (c) 更新$f_m(x) = f_{m-1}(x) + T(x;\Theta_m)$

(3) 得到回归问题提升树

$$f_M(x) = \sum_{m=1}^{M}T(x;\Theta_m)$$

1.3 梯度提升

梯度提升(Gradient Boosting）是Boosting中的一大类算法，其基本思想是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中。提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失时，每一步优化是很简单的。对于一般的损失函数而言，往往每一步优化并不是那么容易。针对这一问题，Freidman提出了梯度提升(gradient boosting)算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值：

$$-[\frac{\partial{L(y,f(x_i))}}{\partial{f(x_i)}}]_{f(x) = f_{m-1}(x)}$$

作为回归问题提升树算法中残差的近似值，拟合一个回归树。

当损失函数选用均方损失函数是时，每一次拟合的值就是（真实值 - 当前模型预测的值），即残差。此时的变量是$y_i$，即“当前预测模型的值”，也就是对它求负梯度。

算法2 梯度提升树算法

输入：训练数据$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)},x_{i} \in \chi \subseteq\mathbb{R}^n$,$\chi$为输入空间，$y_i \in \nu \subseteq \mathbb{R} $ ,$\nu$为输出空间

输出: 回归树$\hat{f}(x)$

(1) 初始化$f_0(x) = \arg \min_{c}\sum_{i=1}^{N}L(y_i,c)$

(2) 对$m=1,2,3,…,M$

​ (a) 对$i = 1,2, …,N$计算残差

$$r_{mi} = -[\frac{\partial{L(y_i,f(x_i))}}{\partial{f(x_i)}}]_{f(x) = f_{m-1}(x)}$$

​ (b) 拟合$r_{mi}$学习一棵回归树，得到第$m$棵树的叶节点区域$R_{mj},j = 1,2,…,J$

​ (c) 对于$j = 1,2,…,J$，计算

$$c_{mj} = \arg \min_{c}\sum_{x_i \in R_{mj}}L(y_i,f_{m-1}(x_i) +c)$$

​ (d）更新$f_m(x) = f_{m-1}(x) + \sum_{j=1}^Jc_{mi}I(x \in R_{mj})$

(3) 得到回归问题提升树

$$\hat{f}(x) = f_M(x) = \sum_{m=1}^{M}\sum_{j=1}^{J}c_{mj}I(x\in R_{mj})$$

算法的第一步初始化，估计使损失函数极小化的常数值，它只有一个根节点的树，第2(a)步计算损失函数的负梯度在当前模型的值，将它作为残差的估计，对于平方损失函数来说，它的负梯度其实就是常说的残差，对于一般的损失函数，它就是残差的近似值。第2（b)步，估计回归树叶子节点区域，以拟合残差的近似值。第2(c)步利用线性搜索估计叶子终点区域的值，使损失函数极小化。第2（d）步更新回归树。第3步，得到输出的最终模型。

1.4 提升树主要损失函数

下面我们对提升树所用的损失函数做一个总结：

1) 对于分类算法来说：其损失函数一般有对数损失函数和指数损失函数：

a）指数损失函数

$$L(y_i,f(x_i)) = exp(-y_if(x_i))$$

其负梯度误差为：

$$-y_i.exp(-f(x_i))$$

b）对数损失函数

$$L(y_i,f(x_i)) = ln(1+exp(-y_i.f(x_i)))$$

其负梯度为：

$$\frac{y_i.exp(-y_i.f(x_i))}{1+exp(-y_i.f(x_i))}$$

化简为：

$$\frac{y_i}{(1+exp(y_if(x_i)))}$$

2) 回归算法：常见的有以下四种

1. 均方差损失函数

   $$L(y_i,f(x_i)) = (y_i - f(x_i))^2$$

   其负梯度为：

   $$y_i - f(x_i)$$

   p.s. 损失函数为$L(y,f(x))=(y-f(x))^2$,我们需要最小化$J= \sum_iL(y_i,f(x_i))$通过调整$f(x_1),f(x_2),…,f(x_n)$.我们把$f(x_i)$当成参数并求导

   $$\frac{\partial}{\partial f(x_i)} = \frac{\partial \sum_iL(y_i,f(x_i))}{\partial f(x_i)} = \frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} = f(x_i) - y_i$$

   所以，我们在均方差损失函数下，可以把残差理解成负梯度。

   $$y_i-f(x_i) = - \frac{\partial}{\partial f(x_i)}$$

2. 绝对损失函数：

   $$L(y_i,f(x_i) = |y_i - f(x_i)|$$

   其对应的负梯度为：

   $$sign (y_i - f(x_i))$$

3. Huber损失函数：它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。损失函数如下：

   $$\begin{aligned} L(y_i,f(x_i)) = \begin{cases} \frac{1}{2}(y_i-f(x_i))^2, |y_i - f(x_i)|\leq \delta\\ \delta(|y_i -f(x_i)| - \frac{\delta}{2}), |y_i - f(x_i)|\geq \delta \end{cases} \end{aligned}$$

   其对应的负梯度为：

   $$\begin{aligned} r(y_i,f(x_i)) = \begin{cases} y_i-f(x_i), |y_i - f(x_i)|\leq \delta\\ \delta .sign(y_i -f(x_i)), |y_i - f(x_i)|\geq \delta \end{cases} \end{aligned}$$

4. 分位数损失。它对应的是分位数回归的损失函数，表达式为

   $$L(x_i,f(x_i)) = \sum_{y_i \geq f(x_i)}\theta|y_i - f(x_i)| + \sum_{y_i < f(x_i)}(1-\theta)|y_i - f(x_i)|$$

   其中，$\theta$为分位数，需要在回归钱设置，其对应的负梯度为：

   $$\begin{aligned} r(y_i,f(x_i)) = \begin{cases} \theta, y_i \geq f(x_i)\\ \theta - 1, y_i < f(x_i) \end{cases} \end{aligned}$$

   

1.5 总结及优缺点

本文介绍了boosting族的提升树算法和梯度提升树（GBDT)算法，提升树算法的每轮弱学习器是拟合上一轮的残差生成的，GBDT算法的每轮弱学习器是拟合上一轮损失函数的负梯度生成的。提升树算法和GBDT算法都是用CART回归树作为弱学习器，只要确定模型的损失函数，提升树和GBDT就可以通过前向分布算法进行构建。

梯度提升树主要的优点有：

1） 可以灵活处理各种类型的数据，包括连续值和离散值。

2）在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。

3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

梯度提升树的主要缺点有：

1）由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

1.6. 梯度提升和梯度下降的区别和联系是什么？

下表是梯度提升算法和梯度下降算法的对比情况。可以发现，两者都是在每 一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更 新，只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参 数的更新。而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函 数空间中，从而大大扩展了可以使用的模型种类。

1.7 代码实现

scala代码地址:https://github.com/StringsLi/ml_scratch_scala/blob/master/src/main/scala/com/strings/model/ensemble/GBDT.scala

1.8 参考文献

李航 《统计学习》

偏差和方差

• 偏差指的是由所有采样得到的大小为m的训练数据集训练出的所有模型的输出的平均值和真实模型输出之间的偏差。偏差通常是由于我们对学习算法做了错误的假设所导致的，比如真实模型是某个二次函数，但我们假设模型是一次函数。由偏差带来的误差通常在训练误差上就能体现出来。
• 方差指的是由所有采样得到的大小为m的训练数据集训练出的所有模型的输出的方差。方差通常是由于模型的复杂度相对于训练样本数m过高导致的，比如一共有100个训练样本，而我们假设模型是阶数不大于200的多项式函数。由方差带来的误差通常体现在测试误差相对于训练误差的增量上。

GBDT 和LR

图中共有两棵树，x为一条输入样本，遍历两棵树后，x样本分别落到两颗树的叶子节点上，每个叶子节点对应LR一维特征，那么通过遍历树，就得到了该样本对应的所有LR特征。构造的新特征向量是取值0/1的。举例来说：上图有两棵树，左树有三个叶子节点，右树有两个叶子节点，最终的特征即为五维的向量。对于输入x，假设他落在左树第一个节点，编码[1,0,0]，落在右树第二个节点则编码[0,1]，所以整体的编码为[1,0,0,0,1]，这类编码作为特征，输入到LR中进行分类。

• 为什么建树采用ensemble决策树？

  一棵树的表达能力很弱，不足以表达多个有区分性的特征组合，多棵树的表达能力更强一些。GBDT每棵树都在学习前面棵树尚存的不足，迭代多少次就会生成多少颗树。按paper以及Kaggle竞赛中的GBDT+LR融合方式，多棵树正好满足LR每条训练样本可以通过GBDT映射成多个特征的需求。

• 为什么建树采用GBDT而非RF？

  RF也是多棵树，但从效果上有实践证明不如GBDT。且GBDT前面的树，特征分裂主要体现对多数样本有区分度的特征；后面的树，主要体现的是经过前N颗树，残差仍然较大的少数样本。优先选用在整体上有区分度的特征，再选用针对少数样本有区分度的特征，思路更加合理，这应该也是用GBDT的原因。

• 如何使用GBDT 映射得到的特征？

  通过GBDT生成的特征，可直接作为LR的特征使用，省去人工处理分析特征的环节，LR的输入特征完全依赖于通过GBDT得到的特征。此思路已尝试，通过实验发现GBDT+LR在曝光充分的广告上确实有效果，但整体效果需要权衡优化各类树的使用。