提升树模型

提升树

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

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

加法模型

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

f(x)=∑m=1Mβmb(x;γm)f(x) = \sum_{m=1}^{M} \beta_{m} b(x;\gamma_{m})

前向分布算法

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

min⁡(βm,γm)∑i=1NL(yi,∑m=1Mβmb(xi;γm))\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⁡(β,γ)∑i=1NL(yi,βb(xi;γ))\min _{(\beta, \gamma)} \sum_{i=1}^{N} L\left(y_{i}, \beta b\left(x_{i} ; \gamma\right)\right)

给定训练集T={(x1,y1),(x2,y2),…,(xN,yN)},xi∈X⊆Rn,yi∈Y={−1,+1}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))L(Y, f(x)), 基函数的集合为{b(X;γ)}\{b(X;\gamma)\}, 学习加法模型f(x)f(x)的前向分布算法步骤如下:

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

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

    • 极小化损失函数: (βm,γm)=argmin⁡β,γ∑i=1NL(yi,fm−1(xi)+βb(xi;γ))\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), 得到参数βm\beta_{m}和γm\gamma_{m}

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

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

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

提升树模型

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

fM(x)=∑m=1MT(x;Θm)f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right)

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

Θ^m=argmin⁡(Θm)∑i=1NL(yi,fm−1(xi)+T(xi;Θ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))2L(y,f(x))=(y-f(x))^2时, 损失函数变为:

L(y,fm−1(x)+T(x;Θm))=[y−fm−1(x)−T(x;Θm)]2=[r−T(x;Θm)]2L\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−fm−1(x)r=y-f_{m-1}(x), 是当前模型拟合结果的残差(residual). 因此, 当前基模型只需要拟合之前累积得到的加法模型预测的残差, 就可以最小化损失函数.

对于分类问题

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

Θm=arg⁡min⁡Θm∑i=1Ne−yi(fm−1(xi)+T(xi;Θm)))=arg⁡min⁡Θm∑i=1Nwmie−yiT(xi;Θm)\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}

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

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

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

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

参考资料

上一页Boosting Model下一页梯度提升

最后更新于

这有帮助吗？