Gradient Boosting Decision Tree梯

作者: ColleenKuang | 来源:发表于2019-04-07 21:51 被阅读0次

Content

Introduction & Motivation
Additive model
Forward Stagewise Algorithm
Boosting Tree
4.1 Pseudo-Residuals
4.2 Cost Function

1. Introduction & Motivation

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。

GBDT = Gradient Boosting + Decision Tree

先从Decision Tree开始讲，单个决策树容易过拟合，但我们可以通过各种方法，抑制决策树的复杂性，降低单颗决策树的拟合能力，然后通过其他手段来集成多个决策树，最终能够很好的解决过拟合的问题。

GBDT中的树都是回归树，不是分类树!!!
GBDT中的树都是回归树，不是分类树!!!
GBDT中的树都是回归树，不是分类树!!!

GBDT的核心在于累加所有树的结果作为最终结果，而分类树的结果显然是没办法累加的，这点对理解GBDT相当重要（PS: 尽管GBDT调整后也可用于分类但不代表GBDT的树是分类树）。

上面说的手段就是Boosting。Boosting 是一族可将弱学习器提升为强学习器的算法，属于集成学习（ensemble learning）的范畴。

基于梯度提升算法的学习器叫做 GBM(Gradient Boosting Machine)。理论上，GBM 可以选择各种不同的学习算法作为基学习器。GBDT 实际上是 GBM 的一种情况。

为什么梯度提升方法倾向于选择决策树作为基学习器呢？

决策树可以认为是 if-then 规则的集合，易于理解，可解释性强，预测速度快。同时，决策树算法相比于其他的算法需要更少的特征工程，比如可以不用做特征标准化，可以很好的处理字段缺失的数据，也可以不用关心特征间是否相互依赖等。

弱决策树们通过梯度提升（Gradient Boosting）的方法，提升模型准确度。由此可见，梯度提升方法和决策树学习算法是一对完美的搭档。

2. Additive model - 加法模型

GBDT 算法可以看成是由 K 棵树组成的加法模型。加法模型的通常表达：
$f(x) = \sum_{m=1}^{M} \beta_mb(x;\gamma_m)$

其中， $b(x;\gamma_m)$ 为基函数， $\gamma_m$ 为基函数的参数， $\beta_m$ 为基函数的系数。

在给定训练数据以及损失函数 $L(y,f(x))$ 的条件下，学习加法模型 $f(x)$ 成为经验风险极小化即损失函数极小化问题:
$\min_{\beta_m, \gamma_m}\sum_{n=1}^{N} L(y_i, \sum_{m=1}^{M}\beta_mb(x;\gamma_m))$

3. Forward Stagewise Algorithm - 前向分步算法

解决加法模型的优化问题，可以用前向分布算法（forward stagewise algorithm）因为学习的是加法模型，如果能够从前往后，每一步只学习一个基函数及其系数（结构），逐步逼近优化目标函数，那么就可以简化复杂度。具体地，每步只需要优化如下损失函数：
$\min_{\beta, \gamma}\sum_{n=1}^{N} L(y_i, \beta b(x_i;\gamma))$

更加具体的流程

$\begin{aligned} Input:&\text{训练数据集} T = {(x_1, y_1), (x_2, y_2), ..., (x_N, y _N)} \\ &\text{损失函数} L(y,f(x)) \\ &\text{基函数集合}b(x;\gamma) \\ Output&: \text{学习加法模型}f(x)\\ \end{aligned} \\$

初始化 $f_0(x) = 0$
对 $m = 1, 2, ... ,M$
(a) 极小化损失函数
$(\beta_m, \gamma_m) = \arg\min_{\beta, \gamma} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + \beta b(x_i;\gamma))$
得到参数 $\beta_m, \gamma_m$
(b) 更新
$f_m(x) = f_{m-1}(x) + \beta_m b(x;\gamma_m)$
得到加法模型
$f(x) = f_M(x) = \sum_{m=1}^{M}\beta_m b(x;\gamma_m)$
这样，前向分步算法将同时求解从 $m=1$ 到 $M$ 所有参数 $\beta_m, \gamma_m$ 的优化问题简化为逐次求解各个 $\beta_m, \gamma_m$ 的优化问题。

4. Boosting Tree - 提升树

提升树算法采用前向分步算法。首先确定初始提升树 $f_0(x) = 0$ ，第m步的模型是：
$f_m(x) = f_{m-1}(x) + T(x; \gamma)$
其中， $f_{m-1}(x)$ 为当前模型，通过经验风险极小化确定下一棵决策树的参数 $\gamma$
$\gamma = \arg\min_{\gamma} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + T(x; \gamma))$
针对不同问题的提升树学习算法，损失函数的选择也不同。

4.1 负梯度拟合

在梯度提升算法中负梯度也被称为伪残差(pseudo-residuals)。

提升树用加法模型与前向分布算法实现学习的优化过程。当损失函数为平方损失和指数损失函数时，每一步优化是很简单的。但对于一般损失函数而言，往往每一步都不那么容易。对于这问题，Freidman提出了梯度提升算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值：
$-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x) = f_{m-1}(x)}$
作为回归问题在当前模型的残差的近似值，拟合一个回归树。
为什么要拟合负梯度呢？这就涉及到泰勒公式和梯度下降法了。

泰勒公式

定义：泰勒公式是一个用函数在某点的信息描述其附近取值的公式。

公式： $f(x) = \sum_{n=0}^{∞}\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n$

一阶泰勒展开式： $f(x) = f(x_0) +f'(x_0)(x - x_0) + Error$

梯度下降法

在机器学习任务中，需要最小化损失函数 $L(\theta)$ ，其中 $\theta$ 是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法：选择初值 $\theta_0$ ，不断迭代更新 $\theta$ ，进行损失函数极小化。

迭代公式: $\theta^{t} = \theta^{t - 1} + \Delta \theta$

将 $L(\theta^t)$ 在 $\theta_{t - 1}$ 处进行一阶泰勒展开： $L(\theta^t) = L(\theta^{t-1} + \Delta \theta) \approx L(\theta^{t-1}) + L'(\theta^{t-1})\Delta \theta$
要使得 $L(\theta_t) < L(\theta_{t-1})$ ，可取： $\Delta \theta = - \alpha L'(\theta^{t-1})$ ，则 $\theta^t = \theta^{t-1} - \alpha L'(\theta^{t-1})$ ，这里 $\alpha$ 是步长，一般直接赋值一个小的数。

相对的，在函数空间里，有 $f^t(x) = f^{t-1}(x) + f_t(x)$
此处把 $L(f^t(x))$ 看成提升树算法的第t步损失函数的值， $L(f^{t - 1}(x))$ 为第t-1步损失函数值，要使 $L(f^{t}(x)) < L(f^{t - 1}(x))$ ，则需要 $f_t(x) = -\alpha g_t(x)$ ，此处 $-g_t(x)$ 为当前模型的负梯度值，即第t步的回归树需要拟合的值。

4.2 损失函数

对于分类算法，其损失函数一般由对数损失函数和指数损失函数两种
(a)指数损失函数表达式：
$L(y,f(x)) = e^{(-yf(x))}$
(b)对数损失函数可分为二分类和多分类两种。
对于回归算法，常用损失函数有如下4种
(a) 平法损失函数
$L(y,f(x)) = (y- f(x))^2$
(b) 绝对损失函数
$L(y,f(x)) = |y = f(x)|$
(c) Huber损失，它是均方差和绝对损失的折中产物，对于远离中心的异常点，采用绝对损失误差，而对于靠近中心的点则采用平方损失。这个界限一般用分位数点度量。损失函数如下：
$L(y,f(x))=\left\{ \begin{aligned} &\frac{1}{2}(y-f(x))^2 & |y-f(x)| \leq \delta \\ &\delta(|y-f(x)| = frac{\delta}{2}) & |y - f(x)| > \delta \end{aligned} \right.$
对应的负梯度误差为：
$r(y_i,f(x))=\left\{ \begin{aligned} &y_i-f(x_i) & |y-f(x)| \leq \delta \\ &\delta sign(y_i-f(x_i)) & |y - f(x)| > \delta \end{aligned} \right.$
(d) 分位数损失。它对应的是分位数回归的损失函数，表达式为：
$L(y,f(x)) = \sum_{y ≥ f(x)} \theta|y - f(x)| + \sum_{y < f(x)} (1-\theta)|y - f(x)|$
对应的负梯度误差为：
$r(y_i,f(x))=\left\{ \begin{aligned} &\theta & y_i \geq f(x_i) \\ &\theta - 1 & y_i < f(x_i) \end{aligned} \right.$

对于Huber损失和分位数损失，主要用于健壮回归，也就是减少异常点对损失函数的影响。

Summary

总结一下 GBDT 的学习算法：

算法步骤解释：

初始化，估计使损失函数极小化的常数值，它是只有一个根节点的树，即 $\gamma$ 是一个常数值。
对每个弱分类器
（a）计算损失函数的负梯度在当前模型的值，将它作为残差的估计
（b）估计回归树叶节点区域，以拟合残差的近似值
（c）利用线性搜索估计叶节点区域的值，使损失函数极小化
（d）更新回归树
得到输出的最终模型 $f(x)$

Gradient Boosting Decision Tree梯

Content

1. Introduction & Motivation

为什么梯度提升方法倾向于选择决策树作为基学习器呢？

2. Additive model - 加法模型

3. Forward Stagewise Algorithm - 前向分步算法

4. Boosting Tree - 提升树

4.1 负梯度拟合

泰勒公式

梯度下降法

4.2 损失函数

Summary

Reference

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读