机器学习基础---集成学习---GBDT梯度提升树

GBDT 梯度提升树（Gradient Boosting Decision Tree）

方法概述

提出背景

• Adaboost方法采用指数损失函数，其对噪声点较为敏感
• 因此需要一个可以应用不同损失函数函数的提升方法

核心思想

• 仍然是基于决策树的加法模型
• 与Adaboost不同，不考虑样本的分布，单纯考虑最小化损失函数
• 采用前向分步方法，分步训练基学习器，每步训练的模型都是对先前累加模型的负梯度拟合

模型表示

• 模型
  $$f_M(x)=\sum _{m=1}^{M}T(x,{\theta }_m)$$

• 优化目标

$$\underset{\theta }{argmin}L(y,f_M(x))$$

相关概念

• 梯度提升

  • 向量空间

    • 对函数$f(\theta )$，将$f({\theta }^t)$在${\theta }^{t-1}$处一阶泰勒展开
      $$f({\theta }^t)\approx f({\theta }^{t-1})+f^{\prime }({\theta }^{t-1})\Delta \theta$$

    • 要使$f({\theta }^t)>f({\theta }^{t-1})$，可以取
      $$\Delta \theta =-\alpha f^{\prime }({\theta }^{t-1})$$
      则有：
      $${\theta }^t={\theta }^{t-1}-\alpha f^{\prime }({\theta }^{t-1})$$
      此处$\alpha$为步长

    • 若以上式对${\theta }^{t-1}$进行更新，可以令$f({\theta }^t)>f({\theta }^{t-1})$，即函数值提升

    • 此处的$\theta$若为标量，直接求导更新；若为向量，进行向量求导并更新

  • 函数空间与负梯度拟合

    • 对函数$g(f(\theta ))$，同样有梯度提升更新
      $$f({\theta }^t)=f({\theta }^{t-1})-\alpha g^{\prime }(f({\theta }^{t-1}))$$

    • 此处不同处在于对函数负梯度${\nabla }_{f(\theta )}g(f(\theta ))$的求解，难以通过解析方式求解，因此考虑通过数值方法求解

    • 已知$(f(\theta ),g(f(x)))$对，使用数值方法求得对应点处梯度，构成$(\theta ,{\nabla }_{f(\theta )}g(f(\theta )))$点对

    • 要求的负梯度应该是一个函数，其可以根据任意$\theta$求得对应的梯度，而上一步只是得到有限点处的数值梯度

    • 因此还需要引入一个用于回归的学习器，以$(\theta ,{\nabla }_{f(\theta )}g(f(\theta )))$点对学习$\theta$到梯度的映射关系

• CART回归树学习过程

  • GBDT方法使用的基分类器为CART回归树而非分类树，
    • 其具有以下优点
      • 可解释性强；有特征组合、特征选择的作用；对异常点鲁棒；容易并行；可处理混合类型特征；具有伸缩不变性；可自然处理缺失值
    • 但同时也有**缺乏平滑性（输出数值种类有限）**的缺点
  • 对$d$维样本集$X$训练回归树的过程大致如下：
    • 遍历当前可选特征维度，每个维度上遍历切分点，对每个切分分别计算切分之后$D_1,D_2$两部分的误差平方和
    • 选择对应误差平方和最小的特征及切分点进行切分，接着递归对$D_1,D_2$两部分进行切分直到满足约束
    • 每个子节点（不可再分样本集）对应输出值是其内部样本均值、
  • 回归树的训练过程实际上就是对样本空间各维度进行划分的过程，在划分完成后再为每个空间确定一个输出值

方法推导

• 依照前向分步算法的过程逐一学习基学习器，假设已经经过$m-1$轮迭代，得到累加模型$f_{m-1}(x)$

• 在当前步骤下（第m步），优化目标为：
  $$\underset{f_m}{argmin}L(f_m(x),y_i)$$

  • 根据梯度提升思想，展开损失函数

  $$L(f_m(x),y_i)=L(f_{m-1}(x),y_i)+{\nabla }_{f_{m-1}(x)}L(f_{m-1}(x),y_i)$$

  ​ $f_m(x)$更新：
  $$f_m(x)=f_{m-1}(x)-\alpha {\nabla }_{f_{m-1}(x)}L(f_{m-1}(x),y_i)$$
  ​ 有：
  $$T_m(x,{\theta }_m)=f_m(x)-f_{m-1}(x)=-{\nabla }_{f_{m-1}(x)}L(f_{m-1}(x),y_i)$$

  • 故，第m步时建立的回归树，其目的是对损失函数对上一步累加模型的负梯度进行拟合
  • 当损失函数是平方损失函数时，负梯度正好为残差

方法步骤

• 初始化：
  $$f_0(x)=\underset{c}{\mathrm{argmin}}\sum _{i=1}^{n}L(y_i,c)$$

• 对$m=1,2,\dots ,M$

  • 对$i=1,2,\dots ,N$分别计算样本点处负梯度
    $$-[\frac{\partial L(y_i,f(x))}{\partial f(x)}]{|}_{f(x)=f_{m-1}(x)}$$

  • 对负梯度点对使用回归树进行拟合，得到树$T(x,{\theta }_m)$，及回归树对区域的划分

  • 对各区域，计算
    $$c_{mj}=\underset{c}{argmin}\sum _{x_i\in R_{mj}}L(y_i,c_{mj})$$

  • 更新$f_m(x)=f_{m-1}(x)+{\sum }_{j=1}^J{c}_{mj}I(x\in R_{m}j)$

• 得到最终提升树$f_M(x)$

参考资料

【1】《集成学习》周志华