从提高树出发,——》回归提高树、二元分类、多元分类三个GBDT常见算法。html
在说GBDT以前,先说说提高树(boosting tree)。说到提高(boosting),老是绕不过AdaBoost。git
AdaBoost是利用前一轮迭代的偏差率来更新训练集的权重,校订前一轮迭代被错误分类的样本,通俗一点的理解就是将重心放在分错的样本上。提高树也是boosting家族的成员,意味着提高树也采用加法模型(基学习器线性组合)和前向分步算法。github
下面一个一个进行解释,提高树的基学习器是什么,加法模型和前向分步算法又是怎么用的。面试
提高树一般以决策树做为基学习器,对分类问题决策树是二叉分类树,回归问题就是二叉回归树。算法
加法模型,就是说提高树能够表示为如下形式:这里咱们约定 $ T(x;Θ_m ) $表示第m棵决策树;$ Θ_m $表示决策树的参数;$ M $为树的个数。强分类器$f_M (x)$能够由多个弱分类器$T(x;Θ_m )$线性相加而成。app
$$f_M (x)=\sum_{m=1}^MT(x;Θ_m ) $$函数
提高树的前向分步算法。第m步的模型能够写成:学习
$$f_m (x)=f_{m-1} (x)+ T(x;Θ_m )$$优化
而后获得损失函数ui
$$L(f_m (x),y)=L(f_{m-1} (x)+ T(x;Θ_m ),y)$$
迭代的目的是构建$T(x;Θ_m )$,使得本轮损失$L(f_m (x),y)$最小。思想其实并不复杂,可是问题也很明显,对于不一样的任务会有不一样的损失函数,当损失函数是平方损失和指数损失函数时,每一步的优化仍是简单的。可是对于通常损失函数而言,每一步的优化并不容易。
下面关于GBDT的理解来自论文greedy function approximation: a gradient boosting machine
最关键的点在于损失函数的数值优化能够当作是在函数空间而不是参数空间。怎么理解呢?
首先,咱们已经知道强分类器是由多个弱分类器线性相加而成,那么能够写成以下形式:
$$F(x;\{β_m,a_m \}_1^M )=\sum_{m=1}^Mβ_m h(x;a_m )$$
这里的$h(x;a_m )$指代回归树,例如CART。$a_m$是模型参数,这里指代每一个节点的分裂特征(变量),最佳分割点,节点的预测值。$M$就是有多少个弱分类器。
而后,咱们来回顾一下参数空间的数值优化。假设预测函数为$F(x;P)$,那么损失函数就能够写成:
$$ ϕ(P)=L(y,F(x,P))$$
优化之后获得的参数最优解为:
$$P^~=argmin_P ϕ(P) $$
回想一下SGD(随机梯度降低)的优化方式,从山顶上选择梯度降低最快的方向挪动最优步长。咱们是否是能够把最优参数表达成这个形式?
$$P^~=\sum_{m=0}^Mp_m $$
$$p_m=-ρ_m g_m$$
从初始值$p_0$开始,$m$对应每一步更新迭代,负梯度$-g_m$就是最速降低方向,$ρ_m$就是在这个最速降低方向上进行线搜索获得的最优步长。
好了,如今咱们说说函数空间的优化方法。
将预测函数$F(x)$对应参数$P$,最优解变成了:
$$F(x)=\sum_{m=0}^Mf_m (x)$$
至关于在函数空间上做梯度降低。每一步梯度降低:
$$f_m(x)=-ρ_m g_m(x)$$
$$g_m (x)=[\frac{-∂ϕ(F(x))}{∂F(x)} ]_{F(x)=F_{m-1} (x) }$$
$$F_{m-1}(x)=\sum_{i=0}^{m-1}f_i(x)$$
如今把这个思想代入到gradient boosting,咱们以前已经获得预测函数为:
$$F(x;\{β_m,a_m \}_1^M )=\sum_{m=1}^Mβ_m h(x;a_m ) $$
须要作的事情是获得预测函数的最优解,就是:
$$\{\textbf{β}_m, \textbf{a}_m \}_1^M= argmin_{\{β_m,a_m\}_1^M} L(y,\sum_{m=1}^Mβ_m h(x;a_m ))= argmin_{β_m,a_m} L(y,F_{m-1} (x)+β_mh_m (x;a_m))$$
已知最速梯度降低方向为$g_m (x)=[\frac{-∂ϕ(F(x))}{∂F(x) }]_{F(x)=F_{m-1} (x) }$,每个$h_m (x;a_m)$都创建在最速梯度降低的方向,咱们能够获得:
$$\textbf{a}_m=argmin_{β_m,a_m} [-g_m (x)-β_mh_m (x;a_m) ]^2$$
能够认为是用$h_m (x;a)$去拟合伪标签$\tilde{y}=-g_m (x)$。这里为何用最小二乘,个人理解是GBDT构造的树全是回归树,所以用最小二乘。
而后进行线搜索肯定最优步长$ρ_m$:
$$\textbf{ρ}_m= argmin_{ρ_m} L(y,F_{m-1}(x)+ρ_mh_m (x;\textbf{a}_m))$$
$$F_m (x)=F_{m-1} (x)+ \textbf{ρ}_m h_m (x;\textbf{a}_m) $$
ok,如今来整理整个算法流程:
当基学习器$h(x;a)$是一个包含J个节点的回归树时,能够写成:
$$h(x;a)=h(x;\{c_j,R_j\}_1^J)=\sum_{j=1}^Jc_jI(X∈R_j)$$
写完公式发现原来能够写的这么复杂,简单点说就是,对于回归树$h$,若是$x$被归到某个叶子节点$R_j$,那么$x$在这个$h$中获得的预测值就是叶子节点$R_j$的值$c_j$。通常用叶子节点上 $\{x_i∈R_j \}_1^J$的$\{\tilde{y}_i\}_1^J$平均值近似节点$R_j$的值
$$c_j=ave_{x_i∈R_j}\tilde{y}_i $$
$\{R_j\}_1^J$是不相交的区域,集合覆盖预测值的空间。$\{c_j\}_1^J$能够认为是回归树$h$的系数。什么意思?咱们回想一下线性回归,预测函数是$θ^T x$,这个$θ$就是模型系数。一样的,也能够这么理解$\{c_j\}_1^J$,是回归树$h$的系数。
ok,如今咱们已经获得了回归提高树的预测函数:
$$F_m (x)=F_{m-1} (x)+ρ_m \sum_{j=1}^Jc_{m,j}I(x∈R_j)$$
令$γ_{m,j}=ρ_mc_{m,j}$,这个值是叶子节点的最理想的常数更新值,也能够认为兼顾了降低方向和降低步长。
综上,整理一下回归提高树的整个算法流程:
$$\tilde{y}=-[\frac{∂ϕ(F(x))}{∂F(x)}]_{F(x)=F_{m-1}(x) }=y_i-F_{m-1}(x_i),i=1,2,……,N$$
$$h_m(x;a)=\sum_{j=1}^Jγ_{m,j}I(x∈R_{m,j})$$
$$F_m(x)=F_{m-1}(x)+\sum_{j=1}^Jγ_{m,j}I(x∈R_{m,j})$$
$$F_M(x)=\sum_{m=1}^M\sum_{j=1}^Jγ_{m,j}I(x∈R_{m,j})$$
当当当~看到第3点,咱们发现损失函数在当前模型$F_{m-1}(x)$的负梯度值刚恰好是$y-F_{m-1}(x)$,也就是咱们常说的残差!看到这里有没有很激动?这不就是咱们常说的GBDT是在拟合前几轮迭代的残差吗?
下面给出证实:
令当前的预测函数模型为$F_{m-1}(x)$,下一棵要学习的回归树为$h_m (x;a)$,则下一步要学习的预测函数为:
$$F_m(x)=F_{m-1}(x)+h_m(x;a_m)$$
回归提高树的损失函数为平方损失:
$$Loss=L(F_m(x),y)=\frac{1}{2}(F_m(x)-y)^2$$
对$F_m (x)$求关于$a_m$的偏导:
$$\frac{∂Loss}{∂a_m}=(F_m(x)-y)=F_{m-1}(x)+h_m(x;a_m)-y$$
咱们要使经验风险极小化,令偏导为0:
$$h_m(x;a_m)=y-F_{m-1}(x)$$
也就是说,构建的回归树要去拟合前面的残差,得证。能够这么理解,GBDT是在函数空间的梯度降低求最优值,当损失函数为平方损失时,刚好去拟合了残差。
下面给一个简单的例子方便理解,如今要经过购物金额和上网时长来预测年龄。假设有5个训练样本,标签分别14,17,13,25,27。第m轮迭代,经过前几轮的残差构建决策树,获得预测函数$F_m (x)$的预测年龄分别为16,15,12,19,29,计算残差-2,2,1,6,-2。第m+1轮迭代,就去学习这个残差,通俗一点说就是以残差做为第i+1轮迭代构建决策树的标签。
咱们使用负二项对数似然做为损失函数:
$$L(y,F)=log(1+exp(-2yF)),y∈\{1,1\}$$
其中,$F(x)=\frac{1}{2}log[\frac{P(y=1|x)}{P(y=-1|x)}]$
看这个公式有没有很熟悉?是的,这个负二项对数似然能够推到逻辑回归的损失函数。
咱们知道逻辑回归的预测函数为:
$$P(y=1|x)=\frac{1}{1+exp(-θ^Tx)},y∈\{0,1\}$$
咱们知道这里的负样本y=-1对应于逻辑回归里的负样本y=0,因此有:
$$F(x)=\frac{1}{2}log[\frac{P(y=1|x)}{P(y=-1|x)}]=\frac{1}{2}log[\frac{P(y=1|x)}{P(y=0|x)}]=\frac{1}{2}θ^Tx$$
将上式代入$L(y,F)$,可得$L(y,F)=log(1+exp(-2yF))=log(1+exp(-yθ^Tx)),y∈\{-1,1\}$
当y=1时,$L(y,F)= log(1+exp(-θ^T x))=y log(1+exp(-θ^T x) )=ylog(P(y=1|x))$
当y=-1时,$L(y,F)=log(1+exp(θ^T x) )=log(1-P(y=1|x))$
令$y$←0,$L(y,F)=(1-y)log(1-P(y=1|x))$
结合在一块儿,能够写成:
$$L(y,F)=ylog(P(y=1|x))+(1-y)log(1-P(y=1|x)),y∈\{0,1\}$$
与逻辑回归损失函数一致,得证。
预测函数$F_{m-1} (x)$的当前负梯度值,也能够说是伪响应$\tilde{y}$为:
$$\tilde{y}=-[\frac{∂L(F(x),y)}{∂F(x)}]_{F(x)=F_{m-1}(x)}=\frac{2y}{1+exp(2yF_{m-1}(x))}$$
咱们仍然将回归树做为基学习器,进行线搜索获得最优叶子节点值:
$$γ_{m,j}=argmin_y\sum_{x∈R_{m,j}}log(1+(-2y(F_{m-1}(x)+γ)))$$
一看这个公式就知道计算量不是通常的大,咱们用[Newton-Raphson近似][2],获得:
$$γ_{m,j}=\frac{\sum_{x∈R_{m,j}}\tilde{y}_i}{\sum_{x∈R_{m,j}}|\tilde{y}_i|(2-|\tilde{y}|)}$$
总结一下算法流程以下:
最后,咱们获得了预测函数$F_M(x)$,用来进行几率估计:
$$P(y=1|x)=p=\frac{e^{2F(x)}}{1+e^{2F(x)}}=\frac{1}{1+e^{-2F(x)}}$$
$$P(y=-1|x)=1-p=\frac{1}{1+e^{2F(x)}}$$
有了几率以后,咱们能够对样本进行分类。
咱们使用多分类log损失做为损失函数:
$$L(y,F)=-\sum_{k=1}^{K}y_klogp_k(x)$$
对应的几率$p_k(x)$为(就是softmax):
$$p_k (x)=\frac{e^{F_k (x)}}{\sum_{l=1}^Ke^{F_l (x)}}$$
对于多分类问题,在构建基学习器时,咱们要为每一个类别k建立一棵回归树$F_k (x),k=1,2,……,K$
$$\tilde{y}_{i,k}=y_{i,k}-p_{k,m-1} (x_i)$$
所以,每次迭代m,以几率角度来计算当前残差。
叶子节点值近似为:
$$γ_{m,j}=\frac{K-1}{K}\frac{\sum_{x∈R_{m,j}}\tilde{y}_i}{\sum_{x∈R_{m,j}}|\tilde{y}_i|(2-|\tilde{y}|)}$$
做者 Scorpio.Lu转载请注明出处!