GBDT回归算法

GBDT

梯度提升方法, 通过拟合负梯度的方式, 可以配合各种可微损失函数使用. 如果基函数使用决策树, 此时的算法称为梯度提升决策树(Gradient Boosting Decision Tree, GBDT).

理论上梯度提升方法可以配合各种各样的基函数使用, 为何配合决策树称为了最流行的选择呢.

为什么选择决策树

决策树有以下的优点:

  • 相当于IF-ELSE规则的集合, 可解释性强, 预测速度快

  • 相比于其他算法, 需要的特征工程少, 如不需要进行标准化

  • 可以很好的处理特征值缺失的情况

  • 不用担心特征之间的相关性, 抗特征共线性干扰

  • 对异常点鲁棒

  • 并行

  • 可扩展

同时也有以下的缺点:

  • 缺乏平滑性, 回归预测时输出值只能输出有限的若干种数值

  • 不适合处理高维稀疏数据

  • 单独使用决策树算法时容易过拟合

我们可以通过抑制决策树的复杂性, 降低单棵决策树的拟合能力, 再通过梯度提升的方法集成多个决策树, 最终能够很好的解决过拟合的问题. 由此可见, 梯度提升方法和决策树学习算法可以互相取长补短, 是一对完美的搭档.

GBDT回归算法

GBDT算法可以看成是MM棵树组成的加法模型:

F(x,w)=∑m=0Mαmhm(x,wm)=∑m=0Mfm(x,wm)F(x, w)=\sum_{m=0}^{M} \alpha_{m} h_{m}\left(x, w_{m}\right)=\sum_{m=0}^{M} f_{m}\left(x, w_{m}\right)

xx为输入样本, h(x;w)h(x;w)为回归决策树, ww为决策树模型的参数, α\alpha为每棵树的权重.

给定训练集T={(x1,y1),(x2,y2),…,(xN,yN)}T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}, 其中xi∈χ⊆Rnx_{i} \in \chi \subseteq R^{n}, χ\chi为输入控件, yi∈Y⊆Ry_{i} \in Y \subseteq R, YY为输出控件, 损失函数为L(Y,f(x))L(Y, f(x)), 目标是得到最终的GBDT回归模型FMF_{M}.

  • 初始化第一个回归决策树F0(x)=arg⁡min⁡c∑i=1NL(yi,c)F_{0}(x)=\underset{c}{\arg \min } \sum_{i=1}^{N} L\left(y_{i}, c\right)

  • 依次建立m=1,2,⋯ ,Mm=1,2,\cdots,M棵回归决策树

    • 对于所有样本i=1,2,⋯ ,Ni=1,2,\cdots,N, 计算第mm棵树对应的负梯度rm,i=−[∂L(yi,F(xi))∂F(x)]F(x)=Fm−1(x)r_{m, i}=-\left[\frac{\partial L\left(y_{i}, F\left(x_{i}\right)\right)}{\partial F(x)}\right]_{F(x)=F_{m-1}(x)}

    • 使用所有样本(xi,rm,i)(x_i,r_{m,i}), 拟合得到一棵新的回归决策树, 即第mm棵树. 树中叶子结点的数量为JmJ_m, 每个叶子结点j=1,2,⋯ ,Jmj=1,2,\cdots,J_m对应的区域记为Rm,jR_{m,j}

    • 对于每个叶子结点区域, 拟合出这个结点的最佳输出值cm,j=arg⁡min⁡c∑xi∈Rm,jL(yi,Fm−1(xi)+c)c_{m, j}=\underset{c}{\arg \min } \sum_{x_{i} \in R_{m, j}} L\left(y_{i}, F_{m-1}\left(x_{i}\right)+c\right)

    • 更新强学习器Fm(x)=Fm−1(x)+∑j=1Jmcm,jI(x∈Rm,j)F_{m}(x)=F_{m-1}(x)+\sum_{j=1}^{J_{m}} c_{m, j} I\left(x \in R_{m, j}\right)

  • 得到最终的强学习器FM(x)=F0(x)+∑m=1M∑j=1Jmcm,jI(x∈Rm,j)F_{M}(x)=F_{0}(x)+\sum_{m=1}^{M} \sum_{j=1}^{J_{m}} c_{m, j} I\left(x \in R_{m, j}\right)

GBDT回归任务损失函数

均方差

L(y,F(x))=(y−F(x))2L(y,F(x))=(y-F(x))^2

对应的负梯度为:

rm,i=−[∂L(yi,F(xi))∂F(x)]F(x)=Fm−1(x)=yi−F(xi)r_{m, i}=-\left[\frac{\partial L\left(y_{i}, F\left(x_{i}\right)\right)}{\partial F(x)}\right]_{F(x)=F_{m-1}(x)}=y_i-F(x_i)

经过推导, 初始化应为:

F0(x)=yˉF_{0}(x)=\bar{y}

yˉ\bar{y}是所有样本真实值的平均值.

每个叶子节点区域Rm,jR_{m,j}的最佳输出cm,jc_{m, j}为:

cm,j=averagex∈Rm,jrm,ic_{m, j}=\text{average}_{x \in R_{m, j}}r_{m, i}

即这个叶子节点区域中所有样本负梯度的平均值.

在sklearn中loss参数赋值为ls

绝对损失

L(y,F(x))=∣y−F(x)∣L(y,F(x))=|y-F(x)|

负梯度为:

rm,i=−[∂L(yi,F(xi))∂F(x)]F(x)=Fm−1(x)=sign(yi−F(xi))r_{m, i}=-\left[\frac{\partial L\left(y_{i}, F\left(x_{i}\right)\right)}{\partial F(x)}\right]_{F(x)=F_{m-1}(x)}=\text{sign}(y_i-F(x_i))

初始化模型为:

F0(x)=median(y)F_{0}(x)=\text{median}(y)

即所有样本真实值的中位数.

每个叶子节点区域Rm,jR_{m,j}的最佳输出cm,jc_{m, j}为:

cm,j=medianx∈Rm,j(yi−Fm−1(xi))c_{m, j}=\text{median}_{x \in R_{m, j}}(y_i-F_{m-1}(x_i))

在sklearn中的参数赋值为lad.

Huber损失

Huber损失是均方差和绝对损失的折衷产物, 对于远离中心的异常点, 采用绝对损失, 而中心附近的点采用均方差, 这个界限一般用分位数点度量.

L(y,f(x))={12(y−f(x))2∣y−f(x)≤δ∣δ(∣y−f(x)∣−δ2)∣y−f(x)>δ∣L(y, f(x))=\left\{\begin{aligned} \frac{1}{2}(y-f(x))^{2} &|y-f(x) \leq \delta| \\ \delta\left(|y-f(x)|-\frac{\delta}{2}\right) &|y-f(x)>\delta| \end{aligned}\right.

对应的负梯度为:

r(yi,f(xi))={yi−f(xi)∣yi−f(xi)≤δ∣δ⋅sign⁡(yi−f(xi))∣yi−f(xi)>δ∣r\left(y_{i}, f\left(x_{i}\right)\right)=\left\{\begin{aligned} y_{i}-f\left(x_{i}\right) &\left|y_{i}-f\left(x_{i}\right) \leq \delta\right| \\ \delta \cdot \operatorname{sign}\left(y_{i}-f\left(x_{i}\right)\right) &\left|y_{i}-f\left(x_{i}\right)>\delta\right| \end{aligned}\right.

分位数损失

θ\theta为分位数, 是一个超参数.

L(y,f(x))=∑y≥f(x)θ∣y−f(x)∣+∑y<f(x)(1−θ)∣y−f(x)∣L(y, f(x))=\sum_{y \geq f(x)} \theta|y-f(x)|+\sum_{y<f(x)}(1-\theta)|y-f(x)|

对应的负梯度为:

r(yi,f(xi))={θyi≥f(xi)θ−1yi<f(xi)r\left(y_{i}, f\left(x_{i}\right)\right)=\left\{\begin{array}{rl} \theta & y_{i} \geq f\left(x_{i}\right) \\ \theta-1 & y_{i}<f\left(x_{i}\right) \end{array}\right.

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

GBDT的正则化

为了防止过拟合, GBDT有很多正则化的方式.

Shrinkage

为了防止过拟合, 在每次对负梯度估计进行迭代时, 不直接加上当前步所拟合的负梯度, 而是乘以一个系数α\alpha, 也被称为学习率. 它可以对梯度提升的步长进行调整, 较小的α\alpha意味着步幅较小, 需要更多的若学习器, 即更多的迭代次数, 更多的树. 迭代过程变为了:

Fm(x)=Fm−1(x)+αhm(x)F_{m}(x)=F_{m-1}(x)+\alpha h_{m}(x)

Subsample

采样样本的比例, 取值为0到1. 这里是不放回抽样. Subsample可以减小方差, 防止过拟合, 但会增加拟合的偏差, 因此取值不能太低, 推荐[0.5, 0.8]之间

对于回归树进行正则化剪枝

Early Stopping

选择一部分样本作为验证集, 在迭代拟合训练集的过程中, 如果模型在验证集里错误率不再下降, 就停止训练, 控制迭代的轮数, 树的个数.

Dropout

参考DART: Dropouts meet Multiple Additive Regression Trees. GBDT有一个显著的问题, 前面迭代的树对预测值的贡献比较大, 后面的树会集中预测一小部分样本的偏差. 通过Dropout平衡所有树对预测的贡献.

每次新加一棵树, 这棵树要拟合的并不是之前全部树ensemble后的负梯度, 而是随机抽取的一些树ensemble.

调参准则

  • loss选择使用的损失函数, 如果要减少异常点的影响, 使用Huber损失和分位数损失

  • learning_rate参数会强烈影响到参数n_estimators, 一般将learning_rate设置为小于0.1的小常数, 并通过early stopping来控制弱学习器的总数

  • subsample可以减小方差, 防止过拟合, 但会增加拟合的偏差, 因此取值不能太低, 推荐[0.5, 0.8]之间

  • n_iter_no_change控制Early Stopping

参考资料

上一页梯度提升下一页GBDT分类算法

最后更新于