Skip to content

10.10 Gradient Boosting的数值优化

原文 The Elements of Statistical Learning
翻译 szcf-weiya
时间 2017-08-27
更新 2018-03-01
状态 Done

Recall

采用任意可导损失准则的 (10.29) 的快速近似算法可以类比数值优化导出.在训练数据上用 $f(x)$ 来预测 $y$ 的损失为

目标是最小化关于 $f$ 的函数 $L(f)$,其中 $f(x)$ 限定为树的和 (10.28),

Recall

忽略这个限定,最小化 (10.33) 可以看成数值优化

其中参数 $\mathbf f\in \IR^N$ 是在 $N$ 个数据点 $x_i$ 的近似的函数值 $f(x_i)$:

数值优化过程是将 (10.34) 看成向量的和来求解

其中 $\mathbf f_0=\mathbf h_0$ 是初识化的猜测,并且每个接下来的 $\mathbf f_m$ 基于当前的参数向量 $\mathbf f_{m-1}$来导出.数值优化方法的区别在于它们采用不同的方法来计算每个增长向量 $\mathbf h_m$.

最速下降

最速下降 (steepest descent) 选择 $\mathbf h_m=-\rho_m \mathbf g_m$,其中 $\rho_m$ 为标量值,$\mathbf g_m\in \IR^N$ 是在 $\mathbf f=\mathbf f_{m-1}$ 取值的 $L(\mathbf f)$ 的梯度.$\mathbf g_m$ 的组分为

步长 (step length) $\rho_m$ 是下式的解 当前的解则更新为

这个过程一直重复直到下一次迭代.最速下降可以看成是非常贪婪的策略,因为 $-\mathbf g_m$ 是 $\IR^N$ 空间中 $L(\mathbf f)$ 在 $\mathbf f= \mathbf f_{m-1}$ 处最速下降的局部方向.

gradient boosting

Forward stagewise boosting(算法 10.2)也是非常贪婪的策略.每一步中,在给定当前模型 $f_{m-1}$ 以及其拟合值 $f_{m-1}(x_i)$ 下,得到的解是在最大程度上降低 (10.29) 的树.

Recall

因此,树的预测值$T(x_i;\Theta_m)$与负梯度(10.35)的组分类似.本质区别在于树的组分$\mathbf t_m=\{T(x_1;\Theta_m),\ldots,T(x_N;\Theta_m)\}$ 不是独立的.它们限定为终止结点个数为$J_m$的树的预测值,然而负梯度是没有任何限制的最速下降方向.

Recall

向前逐步方法中 (10.30) 的解类似于在最速下降方向对 (10.36) 进行 线搜索(line search).区别在于 (10.30) 中对 $\mathbf t_m$ 的组分进行单独的线搜索,这里的组分是对应每个单独的终止结点 $\{T(x_i;\Theta_m)\}_{x_i\in R_{jm}}$,换句话说,就是对每个终止结点应用一次线搜索.

如果在训练数据上最小化损失(10.33)是唯一的目标,则最速下降是更好的策略.梯度 (10.35) 对于任意可导的损失函数 $L(y,f(x))$ 是很容易计算的,然而对于10.6节中讨论的鲁棒的准则来求解 (10.29) 是很困难的.很不幸的是梯度 (10.35) 仅仅在训练数据点 $x_i$ 处有定义,然而最终的目标是将 $f_M(x)$ 一般化到新数据,而不是仅仅是出现在训练集中的数据.

解决这个困境的一种可能方案是在第 $m$ 次迭代中构造 $T(x;\Theta_m)$,其预测值 $\mathbf t_m$ 与负梯度尽可能接近.采用平方误差来衡量近似程度,则有

也就是,用最小二乘对负梯度值 (10.35) 进行拟合.如 10.9 节提到的,对于最小二乘决策树生长(induction)存在快速算法.尽管(10.37)的解$\hat R_{jm}$会与求解(10.29)得到的 $R_{jm}$ 不同,但一般而言它们已经足够近似来实现同样的目的.在任何情形下,向前逐步boosting过程,自上而下决策树生长(induction),都是近似过程.当构造完树(10.37),对应的每个区域的常数值由(10.30)给出.

表10.2总结了通常使用的损失函数的梯度.对于平方误差损失,负梯度恰恰是普通的残差$-g_{im}=y_i-f_{m-1}(x_i)$,所以(10.37)等价于标准的最小二乘boosting.在绝对值损失下,负梯度为残差的符号,所以在每次迭代,(10.37)利用最小二乘对当前的残差的符号进行拟合.对于Huber M-回归,负梯度是这两者的综合(详见表10.2).

对于分类,损失函数是多项偏差

并且在每次迭代过程中构造$K$个最小二乘树.每个树$T_{km}$是对各自负梯度向量$g_{km}$的拟合,

其中 $p_k(x)$ 由 (10.21) 给出.尽管在每次迭代时,构造 $K$ 个独立的树,但是它们通过式(10.21)关联起来.

对于二值分类($K=2$),仅仅需要一棵树.

weiya注

对于二值分类,多项式偏差简单化为logit损失函数 考虑 我们有$p=\frac{1}{1+e^{-z}}$,则二项分布似然函数为 其负对数似然为 也称为logit损失函数. logit损失函数的负梯度为

Info

笔记损失函数的梯度总结及Julia实现用Julia表达了表10.2中的各个损失函数及其梯度.

gradient boosting的实现

上图中的算法10.3展示了用于回归的gradient tree-boosting的通用算法.特定的算法可以通过插入不同的损失准则$L(y, f(x))$得到.算法第一行初始化为最优的常数模型,也就是单终止结点的树.第2(a)行的负梯度计算的组分被称为广义残差或伪残差(pseudo residuals),$r$.通常使用的损失函数的梯度已经总结在表10.2中.

用于分类的算法是类似的.第2(a)-(d)行每次迭代时重复$K$次,每次对每个类用(10.38)计算负梯度.第3行的结果是$K$个不同的树的展开$f_{kM}(x), k=1,2,\ldots, K$.这通过(10.21)得到概率或者像(10.20)一样做分类.细节在练习10.9中给出,两个基本的调整参数为迭代次数$M$和每个组分树的大小$J_m,m=1,2\ldots,M$.

这个算法原始实现称为MART,指的是“多重可加回归树(multiple additive regression trees)”.这章中很多图是用MART得到的.这里描述的gradient boostingR语言的gbm包中有实现(Ridgeway, 19991, “Gradient Boosted Models”),可以免费使用.10.14.2节中用了gbm包,在第16章和第15章有详细介绍.另外,还有个boosting算法的R语言实现是mboost(Hothorn and Bühlmann, 20062).有个gradient boosting/MART的商业实现称为TreeNet (Salford Systems, Inc.)


  1. Ridgeway, G. (1999). The state of boosting, Computing Science and Statistics 31: 172–181. 

  2. Hothorn, T. and B¨uhlmann, P. (2006). Model-based boosting in high dimensions, Bioinformatics 22(22): 2828–2829. 

Comments