提升树模型

提升树

在介绍梯度提升模型之前, 首先引入提升树模型. 顾名思义, 提升树模型就是以分类树或回归树为基本分类器的提升方法.

具体来说, 采用加法模型(即基函数的线性组合)与前向分步算法作为提升手段, 以决策树为基函数的提升方法称为提升树.

加法模型

加法模型(Additive Model)即基函数的线性组合, 假设$b(x;\gamma_{m})$为基函数, $\gamma_{m}$为基函数的参数, $\beta_{m}$为基函数的加权系数, 加法模型表达如下:

$f(x) = \sum_{m=1}^{M} \beta_{m} b(x;\gamma_{m})$

前向分布算法

给定训练数据和损失函数$L(Y, f(x))$, 学习加法模型$f(x)$, 就是一个损失函数极小化的问题:

$\min _{\left(\beta_{m}, \gamma_{m}\right)} \sum_{i=1}^{N} L\left(y_{i}, \sum_{m=1}^{M} \beta_{m} b\left(x_{i} ; \gamma_{m}\right)\right)$

使用前向分布算法求解这一优化问题. 思路是: 由于学习的是加法模型, 如果能够从前向后, 每步只学习一个基函数及其系数, 逐步减小损失函数的大小, 解决优化问题. 即每步只需要优化如下的损失函数:

$\min _{(\beta, \gamma)} \sum_{i=1}^{N} L\left(y_{i}, \beta b\left(x_{i} ; \gamma\right)\right)$

给定训练集$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}, x_{i} \in X \subseteq R^{n}, y_{i} \in Y=\{-1,+1\}$, 损失函数为$L(Y, f(x))$, 基函数的集合为$\{b(X;\gamma)\}$, 学习加法模型$f(x)$的前向分布算法步骤如下:

• 初始化加法模型$f_{0}(x)$

• 依次生成$M$个基函数, 对$m=1,2,\cdots,M$

  • 极小化损失函数: $\left(\beta_{m}, \gamma_{m}\right)=\operatorname{argmin}_{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+\beta b\left(x_{i} ; \gamma\right)\right)$, 得到参数$\beta_{m}$和$\gamma_{m}$

  • 更新加法模型: $f_{m}(x)=f_{m-1}(x)+\beta_{m} b\left(x ; \gamma_{m}\right)$

• 得到最终的加法模型: $f(x)=f_{M}(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)$

因此, 前向分布算法, 将寻找整体的加法模型, 拆分为依次寻找每个基模型参数$\gamma_{m}$和其加权参数$\beta_{m}$的问题. 而前向分布算法的关键点在于如何极小化损失函数, 从而得到一个新的基函数这一步.

提升树模型

以决策树为基函数加法模型称为提升树. 记决策树为$T\left(x ; \Theta_{m}\right)$, 提升树记为:

$f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right)$

在前向分布算法的第$m$步, 给定当前模型$f_{m-1}(x)$, 需求解第$m$棵树的参数$\hat{\Theta}_{m}$:

$\hat{\Theta}_{m}=\operatorname{argmin}_{\left(\Theta_{m}\right)} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+T\left(x_{i} ; \Theta_{m}\right)\right)$

对于回归问题:

如果使用的损失函数是平方误差函数$L(y,f(x))=(y-f(x))^2$时, 损失函数变为:

$L\left(y, f_{m-1}(x)+T\left(x ; \Theta_{m}\right)\right)=\left[y-f_{m-1}(x)-T\left(x ; \Theta_{m}\right)\right]^{2}=\left[r-T\left(x ; \Theta_{m}\right)\right]^{2}$

其中的$r=y-f_{m-1}(x)$, 是当前模型拟合结果的残差(residual). 因此, 当前基模型只需要拟合之前累积得到的加法模型预测的残差, 就可以最小化损失函数.

对于分类问题

如果使用的损失函数是指数损失函数$L(y,f(x))=e^{-yf(x)}$. 那么损失函数就变为:

$$\begin{aligned} \Theta_{m} &= \arg \min _{\Theta_{m}} \sum_{i=1}^{N} e^{\left.-y_{i}\left(f_{m-1}\left(x_{i}\right)+T\left(x_i ; \Theta_{m}\right)\right)\right)} \\ &= \arg \min _{\Theta_{m}} \sum_{i=1}^{N} w_{mi} e^{-y_{i}T\left(x_i ; \Theta_{m}\right)} \end{aligned}$$

在求最小对应的参数过程中, 将常数部分化为$w_{mi}=e^{-y_{i}f_{m-1}(x_i)}$.

在$\sum_{i=1}^{N} w_{mi} e^{-y_{i}T\left(x_i ; \Theta_{m}\right)}$中, $T\left(x_i ; \Theta_{m}\right)$此时是分类树, 因此有$y_i$与$T\left(x_i ; \Theta_{m}\right)$的值域都为$\{-1,+1\}$, 只要两者同号相等, 损失就越小.

因此根据上式, 第$m$步的基函数, 就是以$w_{mi}$为每个样本的权重, 拟合一个分类决策树.

而如果给这里的分类提升树中, 每个基函数都加上一个系数$\alpha_{m}$, 这就是Adaboost算法. 因此可以说Adaboost算法就是以指数损失函数为目标损失函数的提升树.

参考资料

• 深入理解提升树（Boosting tree）算法
• 一文弄懂AdaBoost、提升树、残差树、GDBT