ML——GBDT-梯度提升树-推导过程

Posted on

本文介绍梯度提升树(族)的推导过程,包括传统的GBDT,XGBoost等

参数空间的优化

  • 参数空间中我们使用梯度下降法(一阶导数)和牛顿迭代法(二阶导数)来优化
  • 关于无约束参数优化方法参考无约束参数优化方法

从参数空间优化到函数空间的优化

  • 函数空间中我们使用GBDT(一阶导数)和XGBoost(二阶导数)来优化
  • 函数空间的优化完全类比参数空间的优化

Boosting是一种加法模型

加法模型：additive training
$$
\begin{align}
F(x) = \sum_{t=0}^{T}f_{t}(x)
\end{align}
$$

  • 上式中\(f_{t}(x)\)为基分类器, 我们通常采用回归树[Friedman 1999] 和逻辑回归
    [Friedman 2000]
  • 树模型的优缺点可以参考ML——DT-决策树

GBDT算法原理

这里只原论文中的Gradient Boosting Tree算法
Friedman于论文”GreedyFunctionApproximation…”中最早 出GBDT

模型\(F\)的加法定义：

$$
\begin{align}
F(x) &= \sum_{t=0}^{T}\alpha_{t} h_{t}(x;w_{t}) \\
&= \sum_{t=0}^{T} f_{t}(x;w_{t})
\end{align}
$$

  • 其中, \(x\)为输入样本, \(h_{t}\)为分类回归树, \(w_{t}\)是树\(h_{t}\)的参数, \(\alpha_{t}\)是树\(h_{t}\)的权重

损失函数的定义

$$
\begin{align}
F^{\star} = \arg\max_{F}\sum_{i=1}^{N}L(y_{i}, F(x_{i};w))
\end{align}
$$

  • 其中，\(N\)为样本数量，所有样本的损失总和为总的损失函数
  • 最小化损失函数即可得到最优模型

最优模型的求解

  • 直接列举所有可能的树——NP难问题
  • 所以GBDT算法使用贪心法, 迭代求局部最优解
  • 详细的Gradient Boosting Tree迭代过程如下
  • 上面的推导中
    • 2.1中：\(\tilde{y}_{i}\)是当前的损失函数\(L(y_{i}, F(x_{i})\)关于当前函数\(F(x)\)(模型)在\(F(x)=F_{t-1}(x)\)处的负梯度(每个样本都有一个负梯度)
      • 这个损失函数在使用不同回归方法时时定义各不相同
      • 原始论文中提到两个损失函数定义,根据损失函数的不同,对应的归回方法不同: 最小二乘归回或者最小绝对误差回归
    • 2.2中：\(w^{\star}\)是指能够拟合当前负梯度的树\(h_{t}(x;w^{\star})\)的最佳参数，这里我们认为最佳参数就是最小二乘的最佳参数，实际上这个地方可以使用其他测拟合标准(这个标准是拟合当前负梯度的拟合标准，与后面的损失函数\(L(y, F(x;w))\)无关)，只是这里最小二乘是最简单也是最自然的选择
      • 原始论文中这里使用的基函数是\(\beta h(x;w)\)，其中\(\beta\)是当前基函数\(h(x;w)\)的权重，这里我认为直接使用\(h(x;w)\)作为基函数即可,权重\(\beta\)会自动被基函数学到的(可能原始论文中\(h(x;w)\)指的是简单的基函数，是不含权重学习功能的)
      • 但是需要注意的是,如果我们使用的基分类器是逻辑回归,那么这里每个基分类器的结果都是在[0-1]之间的数,是需要前面的\(\beta\)的
      • 这里我们推导的时候假定了基分类器是回归树,所以不需要使用 \(\beta\)
    • 2.3中：由于\(w^{\star}\)只能保证当前树\(h_{t}(x;w^{\star})\)是能拟合负梯度的，不能保证把当前这棵树添加到模型中时模型的损失函数是最小的，所以我们加了一个步长参数\(\rho\)，用来表示得到当前树的最优权重
      • 损失函数是平方损失函数时，这里的参数为\(\rho\)就是1，无需计算
    • 2.4中：将当前树的最优树(包括权重)一起加入到模型中

不同损失函数和基函数对应不同的算法

上述式子中推导用到的基函数为树模型，实际使用中也可以使用逻辑回归模型[Friedman 2000]等基函数
本小节将介绍不同损失函数或者基函数带来的不同算法

  • 注意:包括Adaboost和GBDT在内Boosting框架中，基函数(基分类器)都不能使用线性模型
    • 理解: Boosting框架本质上是一个加法模型，是对多个基函数的线性组合，得到更优的分类器，可以证明线性模型的线性组合还是线性模型，如果Boosting框架中使用线性模型，那么我们最终得到的分类器也是线性模型，这就局限了我们的整体模型的表达能力
最小二乘回归(损失函数)

Least-Squares Regression

损失函数定义
  • 此时损失函数定义为
    $$
    \begin{align}
    L(y,F(x)) = \frac{1}{2}(y-F(x))^{2}
    \end{align}
    $$
进一步理解推导过程
  • 2.1中\(\tilde{y}_{i}=y_{i}-F_{t-1}(x_{i})\)，这里直接对损失函数求导即可的到
    $$
    \begin{align}
    \tilde{y_{i}} &= -\left [\frac{\partial L(y,F(x_{i}))}{\partial F(x_{i})}\right ]_{F(x) = F_{t-1}(x)} \\
    &= -\left [\frac{\partial L(y,F_{t-1}(x_{i}))}{\partial F_{t-1}(x_{i})}\right ] \\
    &= -\left [\frac{\partial \frac{1}{2}(y_{i}-F_{t-1}(x_{i}))^{2}}{\partial F_{t-1}(x_{i})}\right ] \\
    &= 2 \cdot -\frac{1}{2}(y_{i}-F_{t-1}(x_{i})) \cdot -1 \\
    &= y_{i}-F_{t-1}(x_{i})
    \end{align}
    $$
  • 2.2中正常拟合(使用线性回归和CART回归树均可)
  • 2.3中基函数的权重\(\rho^{\star}\)是常数1，推导如下
    $$
    \begin{align}
    L(y,F_{t}(x)) &= \sum_{i=1}^{N}L(y_{i}, F_{t}(x_{i})) \\
    &= \frac{1}{2}\sum_{i=1}^{N}((y_{i}-F_{t}(x_{i}))^{2}) \\
    &= \frac{1}{2}\sum_{i=1}^{N}((y_{i}-F_{t-1}(x_{i}) - h_{t}(x_{i};w))^{2}) \\
    &= \frac{1}{2}\sum_{i=1}^{N}((\tilde{y}_{i}-h_{t}(x_{i};w))^{2}) \\
    \end{align}
    $$
  • 显然，这个式子和2.2中拟合目标完全相同(只差着2倍常数权重)，所以2.2中得到的最优基函数\(h_{t}(x;w^{\star})\)就是2.3中使得模型损失函数\(L(y,F_{t}(x))\)最小的最优基函数，无需添加任何的权重系数
最小绝对偏差回归(损失函数)

Least Absolute Deviation Regression, LAD

损失函数定义
  • 此时损失函数定义为
    $$
    \begin{align}
    L(y,F(x)) = |y-F(x)|
    \end{align}
    $$
进一步理解推导过程
  • 2.1中\(\tilde{y}_{i}=sign(y_{i}-F_{t-1}(x_{i}))\)
    • 绝对值的导数就是1或者-1,当
      $$y_{i}-F_{t-1}(x_{i}) > 0$$
    • 对损失函数求导得到-1,负梯度为1
    • 同理得到，当
      $$y_{i}-F_{t-1}(x_{i}) > 0$$
    • 对损失函数求导得到1,负梯度为-1
    • 总结得到负梯度为
      $$\tilde{y}_{i}=sign(y_{i}-F_{t-1}(x_{i}))$$
  • 2.2中正常拟合(使用线性回归和CART回归树均可)
  • 2.3中基函数的权重\(\rho^{\star}\)不再是常数，推导如下
  • 待更新*
    $$
    \begin{align}
    待更新
    \end{align}
    $$
回归树(基函数)

Regression Trees

  • 传统GBDT中原始论文使用树回归,论文见Firedman 1999,后来作者提出可以使用逻辑回归,论文见Friedman 2000
  • 回归树和逻辑回归的优缺点比较
    • 树模型优点:
      • 可解释性强
      • 可处理混合类型特征(混合类型特征指的是数值型和类别型均可处理)
      • 具有伸缩不变性(无需特征归一化: 神经网络和逻辑回归都需要,逻辑回归中是为了保证随机梯度下降的方向正确,速度快)
      • 可自然的处理缺失值, C4.5树处理缺失值默认使用的方法是先用未缺失样本计算信息增益确定分裂结点,然后将缺失值的每个样本按照权重(当前叶子节点未缺失样本数量 / 未缺失样本总数)分配到各个结点
      • 对异常点鲁棒(不用去除异常点,LR不具有这个优点)
      • 有特征选择的作用
      • 可扩展性强,容易并行(并行是最好的,用来解释为什么XGBoost等都用树模型)
    • 树模型缺点:
      • 缺乏平滑性(回归预测时输出值只能输出若干种数值,而不是连续的数值,所以不平滑[不平滑即离散])
      • 不适合处理高维稀疏数据(当数据量太少时,非常容易过拟合,树的深度太深,从而模型变得太复杂)

传统GDBT与XGBoost的比较