精华内容
下载资源
问答
  • 梯度提升决策树

    2021-04-13 12:05:58
    待完成

    待完成

    展开全文
  • 文章目录梯度提升决策树(GBDT)算法流程xgboost算法 梯度提升决策树(GBDT)   梯度提升决策树(GBDT)算法是梯度提升(GB)算法限定基学习器是回归决策树时的模型,尤其是CART回归树,关于梯度提升(GB)可以看我的blog...

    梯度提升决策树(GBDT)

      梯度提升决策树(GBDT)算法是梯度提升(GB)算法限定基学习器是回归决策树时的模型,尤其是CART回归树,关于梯度提升(GB)可以看我的blog中对应的部分。

      这里根据GB算法,改写成使用CART回归树的GBDT算法。

    算法流程

    输入:训练集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) … ( x N , y N ) } T=\{(x_{1},y_{1}),(x_{2},y_{2}) \dots (x_{N},y_{N})\} T={(x1,y1),(x2,y2)(xN,yN)};回归树个数M;
    输出:梯度提升决策树
    执行流程:

    1. 初始化 f 0 ( x ) = a r g min ⁡ c ∑ i = 1 N L ( y i , c ) f_{0}(x)=arg\min\limits_{c} \sum\limits_{i=1}^{N}L(y_{i},c) f0(x)=argcmini=1NL(yi,c)这里初始化和传统的前向分步算法令 f 0 ( x ) = 0 f_{0}(x)=0 f0(x)=0不同,这里这样做应该是保证后面求偏导过程不是在零点。
    2. 对第m个基回归树,求其残差近似 r m i = − [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x ) r_{mi}=-[\frac{\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}]_{f(x)=f_{m-1}(x)} rmi=[f(xi)L(yi,f(xi))]f(x)=fm1(x)
    3. 利用残差 r m i r_{mi} rmi学习第m个基回归树,确定第m个基回归树的区域划分 R m j , j = 1 , 2 … J R_{mj},j=1,2\dots J Rmj,j=1,2J
    4. R m j R_{mj} Rmj的最终取值 c m j c_{mj} cmj c m j = a r g min ⁡ c ∑ x i ∈ R m j L ( y i , f m − 1 ( x ) + c ) c_{mj}=arg\min\limits_{c} \sum\limits_{x_{i}\in R_{mj}}L(y_{i},f_{m-1}(x)+c) cmj=argcminxiRmjL(yi,fm1(x)+c)
    5. 更新回归树 f m ( x ) = f m − 1 ( x ) + ∑ j = 1 J c m j I ( x ∈ R m j ) f_{m}(x)=f_{m-1}(x)+\sum\limits_{j=1}^{J}c_{mj}I(x\in R_{mj}) fm(x)=fm1(x)+j=1JcmjI(xRmj)若m<M,递归执行步骤2-5。
    6. 得到最终的回归树 F ( x ) = ∑ m = 1 M ∑ j = 1 J c m j I ( x ∈ R m j ) F(x)=\sum\limits_{m=1}^{M}\sum\limits_{j=1}^{J}c_{mj}I(x \in R_{mj}) F(x)=m=1Mj=1JcmjI(xRmj)

      在《统计学习方法》中,梯度提升没有基学习器的权值,但在有些文献中,会在上面的步骤4后,加一步求权值的操作,这一步定义成4.1.步骤。

    4.1. 计算权值 γ \gamma γ a r g min ⁡ γ m L ( y i , f m − 1 ( x ) + γ m ∑ j = 1 J c m j I ( x ∈ R m j ) ) arg \min \limits_{\gamma_{m}} L(y_{i}, f_{m-1}(x)+\gamma_{m} \sum\limits_{j=1}^{J}c_{mj}I(x\in R_{mj})) argγmminL(yi,fm1(x)+γmj=1JcmjI(xRmj))

    对应的步骤5中,更新的模型变成 f m ( x ) = f m − 1 ( x ) + γ m ∑ j = 1 J c m j I ( x ∈ R m j ) ) f_{m}(x)=f_{m-1}(x)+\gamma_{m} \sum\limits_{j=1}^{J}c_{mj}I(x\in R_{mj})) fm(x)=fm1(x)+γmj=1JcmjI(xRmj))


    极端梯度提升(xgboost)算法

      极端梯度提升(eXtreme Gradient Boosting,xgboost)可以看成改进版本的GBDT算法,xgboost限定了基学习器一定要是CART回归树(在python的xgboost模块中,基学习器还可以是线性模型或dart,但这篇blog仅推导CART回归树情况),输出一个分数而不是类别,这样有助于我们整合所有的基CART回归树的输出结果(简单相加),xgboost引入了并行化,所以其速度更快,同时xgboost引入了损失函数的二阶偏导,一般效果也更好。

      xgboost归根到底属于boost集成学习方法,所以其基学习器的学习是串行的,即当我们要学习第 k k k个学习器时,学习的目标是前 k − 1 k-1 k1个学习器与目标输出的残差,最终的学习器表示如下: y ^ ( K ) = ∑ k = 1 K f k ( x ) , k = 1 , 2 … K \hat{y}^{(K)}=\sum\limits_{k=1}^{K}f_{k}(x),k=1,2\dots K y^(K)=k=1Kfk(x),k=1,2K

    其中, f k ( ⋅ ) f_{k}(·) fk()代表编号是 k k k的基CART回归树,因此,对于输入 { ( x 1 , y 1 ) , ( x 2 , y 2 ) … ( x n , y n ) } \{(x_{1},y_{1}),(x_{2},y_{2})\dots (x_{n},y_{n})\} {(x1,y1),(x2,y2)(xn,yn)},学习第 k k k个基学习器时,我们学习的目标函数表示如下: min ⁡ f k ( x ) ∑ i = 1 n l ( y i , y ^ i ( k − 1 ) + f k ( x i ) ) \min_{f_{k}(x)}\sum\limits_{i=1}^{n}l(y_{i}, \hat{y}^{(k-1)}_{i}+f_{k}(x_{i})) fk(x)mini=1nl(yi,y^i(k1)+fk(xi))

    其中, y i y_{i} yi是第 i i i条数据的真实输出, y ^ i ( k − 1 ) \hat{y}^{(k-1)}_{i} y^i(k1)是已经学习的前 k − 1 k-1 k1个学习器对第 i i i条数据的集成输出, f k ( ⋅ ) f_{k}(·) fk()是待学习的第 k k k个学习器。下面主要说明xgboost如何确定第 k k k个基CART回归树的结构和叶子节点的值。

    xgboost的目标函数

      我们先假设我们已经知道了第 k k k个基CART回归树的结构,下面会推导xgboost对第 k k k个基CART回归树的目标函数。

      xgboost比较GBDT,第一个大的改进是,为了防止过拟合,xgboost的目标函数会加入正则化项,这在CART决策树中是没有的,CART决策树会在后期进行决策树剪枝来防止过拟合,加入正则化项后的目标函数如下: min ⁡ f k ( x ) , Ω ( f j ) ( ∑ i = 1 n l ( y i , y ^ i ( k − 1 ) + f k ( x i ) ) + ∑ j = 1 k Ω ( f j ) ) \min_{f_{k}(x), \Omega(f_{j})}\Big(\sum\limits_{i=1}^{n}l(y_{i}, \hat{y}^{(k-1)}_{i}+f_{k}(x_{i})) + \sum\limits_{j=1}^{k}\Omega(f_{j})\Big) fk(x),Ω(fj)min(i=1nl(yi,y^i(k1)+fk(xi))+j=1kΩ(fj))

    这里的正则化项,我们考虑树的结构(叶子节点数量),以及树的叶子节点的输出分数 w w w,表示如下 Ω ( f ) = γ T + 1 2 λ ∑ t = 1 T w t 2 \Omega(f) = \gamma T+\frac{1}{2}\lambda \sum\limits_{t=1}^{T}w_{t}^{2} Ω(f)=γT+21λt=1Twt2

    其中, T T T是基CART回归树的叶子节点总数, w t , t = 1 , 2 … T w_{t},t=1,2\dots T wt,t=1,2T是基CART回归树的第 t t t个叶子节点的输出值, γ 、 λ \gamma、\lambda γλ是正则化项的系数,属于超参数, γ \gamma γ λ \lambda λ越大,我们越希望获得结构简单的决策树。

    当训练第 k k k个基CART回归树时,不难看出前 k − 1 k-1 k1个基CART回归树的正则化项是一个常数,我们单独把它们提取到 C o n s t a n t Constant Constant(常数)中,目标函数变成 min ⁡ f k ( x ) , Ω ( f k ) ∑ i = 1 n l ( y i , y ^ i ( k − 1 ) + f k ( x i ) ) + Ω ( f k ) + C o n s t a n t = min ⁡ f k ( x ) , w t ∑ i = 1 n l ( y i , y ^ i ( k − 1 ) + f k ( x i ) ) + γ T + 1 2 λ ∑ t = 1 T w t 2 + C o n s t a n t \min_{f_{k}(x), \Omega(f_{k})}\sum\limits_{i=1}^{n}l(y_{i}, \hat{y}^{(k-1)}_{i}+f_{k}(x_{i})) +\Omega(f_{k})+Constant \\ =\min_{f_{k}(x), w_{t}}\sum\limits_{i=1}^{n}l(y_{i}, \hat{y}^{(k-1)}_{i}+f_{k}(x_{i})) +\gamma T+\frac{1}{2}\lambda \sum\limits_{t=1}^{T}w_{t}^{2}+Constant fk(x),Ω(fk)mini=1nl(yi,y^i(k1)+fk(xi))+Ω(fk)+Constant=fk(x),wtmini=1nl(yi,y^i(k1)+fk(xi))+γT+21λt=1Twt2+Constant

      值得一提的是,我们待优化的目标中并没有 T T T,因为我们在求解上面的损失函数时,已经假设确定了第 k k k个基CART回归树的结构

      xgboost比较GBDT,第二个大的改进是,xgboost改进了利用损失函数求残差的过程,对于更一般的损失函数表示 l ( y i , y ^ i ( k − 1 ) + f k ( x i ) ) l(y_{i}, \hat{y}^{(k-1)}_{i}+f_{k}(x_{i})) l(yi,y^i(k1)+fk(xi))

    我们知道 y i y_{i} yi y ^ i ( k − 1 ) \hat{y}^{(k-1)}_{i} y^i(k1)是常量,所以我们的损失函数是关于 f k ( x i ) f_{k}(x_{i}) fk(xi)的函数,我们对 f k ( x i ) = 0 f_{k}(x_{i})=0 fk(xi)=0求损失函数的二阶泰勒展开式子如下 l ( y i , y ^ i ( k − 1 ) + f k ( x i ) ) = l ( y i , y ^ i ( k − 1 ) + 0 ) + ∂ l ∂ f k ( x i ) ∣ f k ( x i ) = 0 ⋅ ( f k ( x i ) − 0 ) + 1 2 ∂ 2 l ∂ f k ( x i ) 2 ∣ f k ( x i ) = 0 ⋅ ( f k ( x i ) − 0 ) 2 = l ( y i , y ^ i ( k − 1 ) ) + ∂ l ∂ ( y ^ i ( k − 1 ) + f k ( x i ) ) ∂ ( y ^ i ( k − 1 ) + f k ( x i ) ) ∂ f k ( x i ) ∣ f k ( x i ) = 0 ⋅ f k ( x i )     + 1 2 ∂ ∂ f k ( x i ) ( ∂ l ∂ ( y ^ i ( k − 1 ) + f k ( x i ) ) ∂ ( y ^ i ( k − 1 ) + f k ( x i ) ) ∂ f k ( x i ) ) ∣ f k ( x i ) = 0 ⋅ f k ( x i ) 2 = l ( y i , y ^ i ( k − 1 ) ) + ∂ l ( y i , y ^ i ( k − 1 ) ) ∂ y ^ i ( k − 1 ) f k ( x i )     + 1 2 ∂ ( ∂ l ∂ ( y ^ i ( k − 1 ) + f k ( x i ) ) ) ∂ ( y ^ i ( k − 1 ) + f k ( x i ) ) ∂ ( y ^ i ( k − 1 ) + f k ( x i ) ) ∂ f k ( x i ) ∣ f k ( x i ) = 0 ⋅ f k ( x i ) 2 = l ( y i , y ^ i ( k − 1 ) ) + ∂ l ( y i , y ^ i ( k − 1 ) ) ∂ y ^ i ( k − 1 ) ⋅ f k ( x i ) + 1 2 ∂ 2 l ( y i , y ^ i ( k − 1 ) ) ∂ ( y ^ i ( k − 1 ) ) 2 ⋅ f k ( x i ) 2 = l ( y i , y ^ i ( k − 1 ) ) + g i f k ( x i ) + 1 2 h i f k ( x i ) 2 \begin{aligned} &amp; l(y_{i}, \hat{y}^{(k-1)}_{i}+f_{k}(x_{i})) \\ &amp;= l(y_{i}, \hat{y}^{(k-1)}_{i}+0)+\frac{\partial l}{\partial f_{k}(x_{i})} \Bigg |_{f_{k}(x_{i})=0} ·(f_{k}(x_{i})-0)+\frac{1}{2}\frac{\partial^{2} l}{\partial f_{k}(x_{i})^{2}} \Bigg |_{f_{k}(x_{i})=0} ·(f_{k}(x_{i})-0)^{2} \\ &amp;= l(y_{i}, \hat{y}^{(k-1)}_{i})+\frac{\partial l}{\partial (\hat{y}^{(k-1)}_{i}+f_{k}(x_{i}))}\frac{\partial (\hat{y}^{(k-1)}_{i}+f_{k}(x_{i}))}{\partial f_{k}(x_{i})} \Bigg |_{f_{k}(x_{i})=0} ·f_{k}(x_{i}) \\ &amp; ~~~+\frac{1}{2}\frac{\partial}{\partial f_{k}(x_{i})}\Big (\frac{\partial l}{\partial (\hat{y}^{(k-1)}_{i}+f_{k}(x_{i}))}\frac{\partial (\hat{y}^{(k-1)}_{i}+f_{k}(x_{i}))}{\partial f_{k}(x_{i})}\Big ) \Bigg |_{f_{k}(x_{i})=0} ·f_{k}(x_{i})^{2} \\ &amp;= l(y_{i}, \hat{y}^{(k-1)}_{i})+\frac{\partial l(y_{i}, \hat{y}^{(k-1)}_{i})}{\partial \hat{y}^{(k-1)}_{i}}f_{k}(x_{i}) \\ &amp; ~~~+\frac{1}{2}\frac{\partial ({\frac{\partial l}{\partial (\hat{y}^{(k-1)}_{i}+f_{k}(x_{i}))})}}{\partial (\hat{y}^{(k-1)}_{i}+f_{k}(x_{i}))} \frac{\partial (\hat{y}^{(k-1)}_{i}+f_{k}(x_{i}))}{\partial f_{k}(x_{i})}\Bigg |_{f_{k}(x_{i})=0} ·f_{k}(x_{i})^{2} \\ &amp;= l(y_{i}, \hat{y}^{(k-1)}_{i})+\frac{\partial l(y_{i}, \hat{y}^{(k-1)}_{i})}{\partial \hat{y}^{(k-1)}_{i}} ·f_{k}(x_{i})+\frac{1}{2}\frac{\partial^{2} l(y_{i}, \hat{y}^{(k-1)}_{i})}{\partial (\hat{y}^{(k-1)}_{i})^{2}} ·f_{k}(x_{i})^{2} \\ &amp; = l(y_{i}, \hat{y}^{(k-1)}_{i})+g_{i}f_{k}(x_{i})+\frac{1}{2}h_{i}f_{k}(x_{i})^{2} \\ \end{aligned} l(yi,y^i(k1)+fk(xi))=l(yi,y^i(k1)+0)+fk(xi)lfk(xi)=0(fk(xi)0)+21fk(xi)22lfk(xi)=0(fk(xi)0)2=l(yi,y^i(k1))+(y^i(k1)+fk(xi))lfk(xi)(y^i(k1)+fk(xi))fk(xi)=0fk(xi)   +21fk(xi)((y^i(k1)+fk(xi))lfk(xi)(y^i(k1)+fk(xi)))fk(xi)=0fk(xi)2=l(yi,y^i(k1))+y^i(k1)l(yi,y^i(k1))fk(xi)   +21(y^i(k1)+fk(xi))((y^i(k1)+fk(xi))l)fk(xi)(y^i(k1)+fk(xi))fk(xi)=0fk(xi)2=l(yi,y^i(k1))+y^i(k1)l(yi,y^i(k1))fk(xi)+21(y^i(k1))22l(yi,y^i(k1))fk(xi)2=l(yi,y^i(k1))+gifk(xi)+21hifk(xi)2
    其中
    g i = ∂ l ( y i , y ^ i ( k − 1 ) ) ∂ y ^ i ( k − 1 ) = ∂ y i ^ ( k − 1 ) l ( y i , y ^ i ( k − 1 ) ) g_{i} = \frac{\partial l(y_{i}, \hat{y}^{(k-1)}_{i})}{\partial \hat{y}^{(k-1)}_{i}}=\partial_{\hat{y_{i}}^{(k-1)}}l(y_{i}, \hat{y}^{(k-1)}_{i}) gi=y^i(k1)l(yi,y^i(k1))=yi^(k1)l(yi,y^i(k1))

    h i = ∂ 2 l ( y i , y ^ i ( k − 1 ) ) ∂ ( y ^ i ( k − 1 ) ) 2 = ∂ y i ^ ( k − 1 ) 2 l ( y i , y ^ i ( k − 1 ) ) h_{i} = \frac{\partial^{2} l(y_{i}, \hat{y}^{(k-1)}_{i})}{\partial (\hat{y}^{(k-1)}_{i})^{2}}=\partial_{\hat{y_{i}}^{(k-1)}}^{2} l(y_{i}, \hat{y}^{(k-1)}_{i}) hi=(y^i(k1))22l(yi,y^i(k1))=yi^(k1)2l(yi,y^i(k1))

    为何要用二阶泰勒展开来替代原损失函数?因为这样我们就构造出了关于 f k ( x i ) f_{k}(x_{i}) fk(xi)的二次函数,我们直接利用二次函数就可以求解损失函数最小值,简化了运算。所以,这里的损失函数要选择可以进行二阶泰勒展开的函数

    我们将上面推出来的损失函数带回到目标函数,化简得到 min ⁡ f k ( x ) , w t ∑ i = 1 n l ( y i , y ^ i ( k − 1 ) + f k ( x i ) ) + γ T + 1 2 λ ∑ t = 1 T w t 2 + C o n s t a n t = min ⁡ f k ( x ) , w t ∑ i = 1 n ( l ( y i , y ^ i ( k − 1 ) ) + g i f k ( x i ) + 1 2 h i f k ( x i ) 2 ) + γ T + 1 2 λ ∑ t = 1 T w t 2 + C o n s t a n t \min_{f_{k}(x), w_{t}}\sum\limits_{i=1}^{n}l(y_{i}, \hat{y}^{(k-1)}_{i}+f_{k}(x_{i})) +\gamma T+\frac{1}{2}\lambda \sum\limits_{t=1}^{T}w_{t}^{2}+Constant \\ =\min_{f_{k}(x),w_{t}}\sum\limits_{i=1}^{n}\Big( l(y_{i}, \hat{y}^{(k-1)}_{i})+g_{i}f_{k}(x_{i})+\frac{1}{2}h_{i}f_{k}(x_{i})^{2}\Big)+\gamma T+\frac{1}{2}\lambda \sum\limits_{t=1}^{T}w_{t}^{2}+Constant fk(x),wtmini=1nl(yi,y^i(k1)+fk(xi))+γT+21λt=1Twt2+Constant=fk(x),wtmini=1n(l(yi,y^i(k1))+gifk(xi)+21hifk(xi)2)+γT+21λt=1Twt2+Constant

    由于 l ( y i , y ^ i ( k − 1 ) ) l(y_{i}, \hat{y}^{(k-1)}_{i}) l(yi,y^i(k1))是常数,我们把它融入 C o n s t a n t Constant Constant后,删去常数 C o n s t a n t Constant Constant,得到 min ⁡ f k ( x ) , w t ∑ i = 1 n ( g i f k ( x i ) + 1 2 h i f k ( x i ) 2 ) + γ T + 1 2 λ ∑ t = 1 T w t 2 \min_{f_{k}(x), w_{t}}\sum\limits_{i=1}^{n}(g_{i}f_{k}(x_{i})+\frac{1}{2}h_{i}f_{k}(x_{i})^{2})+\gamma T+\frac{1}{2}\lambda \sum\limits_{t=1}^{T}w_{t}^{2} fk(x),wtmini=1n(gifk(xi)+21hifk(xi)2)+γT+21λt=1Twt2

    根据上面关于 g i g_{i} gi h i h_{i} hi的定义,我们不难知道 g i g_{i} gi h i h_{i} hi同样是常数,同时考虑到 f k ( x i ) = w f_{k}(x_{i})=w fk(xi)=w,所以我们改变一下求和的顺序,并合并 f k ( x ) f_{k}(x) fk(x) w w w,得到新的目标函数如下 min ⁡ w t ∑ t = 1 T ( ( ∑ f k ( x j ) = w t g j ) w t + 1 2 ( ∑ f k ( x j ) = w t h j + λ ) w t 2 ) + γ T \min_{w_{t}}\sum\limits_{t=1}^{T}\Big((\sum\limits_{f_{k}(x_{j})=w_{t}}g_{j})w_{t}+\frac{1}{2}(\sum\limits_{f_{k}(x_{j})=w_{t}}h_{j}+\lambda)w_{t}^{2}\Big)+\gamma T wtmint=1T((fk(xj)=wtgj)wt+21(fk(xj)=wthj+λ)wt2)+γT

    我们进一步定义 G t = ∑ f k ( x j ) = w t g j G_{t}=\sum\limits_{f_{k}(x_{j})=w_{t}}g_{j} Gt=fk(xj)=wtgj

    H t = ∑ f k ( x j ) = w t h j H_{t}=\sum\limits_{f_{k}(x_{j})=w_{t}}h_{j} Ht=fk(xj)=wthj

    则目标函数进一步变成 min ⁡ w t ∑ t = 1 T ( G t w t + 1 2 ( H t + λ ) w t 2 ) + γ T \min_{w_{t}}\sum\limits_{t=1}^{T}\Big(G_{t}w_{t}+\frac{1}{2}(H_{t}+\lambda)w_{t}^{2}\Big)+\gamma T wtmint=1T(Gtwt+21(Ht+λ)wt2)+γT

    确定基CART树的叶子节点输出

      不难看出来,这是 T T T个关于 w t w_{t} wt独立的二次函数,我们只需让每一个二次函数取最小值即可,也就是 w t = − G t H t + λ w_{t} = -\frac{G_{t}}{H_{t}+\lambda} wt=Ht+λGt

    在其它很多blog中没有提及的是,二次函数只在二次项系数大于0时,才有最小值,所以我们要求 H t + λ &gt; 0 H_{t}+\lambda &gt; 0 Ht+λ>0

    H t H_{t} Ht是很多损失函数关于 f k ( x i ) f_{k}(x_{i}) fk(xi)的二阶偏导数的和,所以我们的损失函数选择时要考虑这一点,损失函数既要满足有二阶导数(二阶泰勒展开的需要)同时损失函数要满足 H t + λ &gt; 0 H_{t}+\lambda &gt; 0 Ht+λ>0,目前来看,平方损失函数和指数损失函数是满足的。

      同时我们也得到了目标函数的相对值(相对值意思是,目标函数中其实没有考虑上面省去的 C o n s t a n t Constant Constant) ∑ t = 1 T ( − G t 2 2 ( H t + λ ) ) + γ T \sum\limits_{t=1}^{T}\Big(-\frac{G_{t}^{2}}{2(H_{t}+\lambda)}\Big)+\gamma T t=1T(2(Ht+λ)Gt2)+γT

      值得一提的是,上面的 G t 、 H t 、 λ 、 γ G_{t}、H_{t}、\lambda、\gamma GtHtλγ和真实输出 y i y_{i} yi没有关系,所以基CART树的叶子节点输出和真实输出 y i y_{i} yi没有关系,只和残差有关。

    确定基CART树的结构

      确定基CART树的结构的方法主要是,递归的确定叶节点是否适合被分割(延伸)。根据上面目标函数的最后取值,我们不难推出基CART回归树的延伸条件,对于某个我们想要延伸的叶子节点 t x t_{x} tx,我们计算其延伸前的目标函数值 o b j 1 = ∑ t = 1 T ( − G t 2 2 ( H t + λ ) ) + γ T obj_{1} = \sum\limits_{t=1}^{T}\Big(-\frac{G_{t}^{2}}{2(H_{t}+\lambda)}\Big)+\gamma T obj1=t=1T(2(Ht+λ)Gt2)+γT

    遍历所有特征的所有可能取值,按照每个取值延伸后,计算延伸后的目标函数值, t x t_{x} tx分割出两个新的叶子节点 t 1 t_{1} t1 t 2 t_{2} t2 o b j 2 = ∑ t = 1 T + 1 ( − G t 2 2 ( H t + λ ) ) + γ ( T + 1 ) obj_{2} = \sum\limits_{t=1}^{T+1}\Big(-\frac{G_{t}^{2}}{2(H_{t}+\lambda)}\Big)+\gamma (T+1) obj2=t=1T+1(2(Ht+λ)Gt2)+γ(T+1)

    两者求差 o b j 1 − o b j 2 = ( G t 1 2 2 ( H t 1 + λ ) + G t 2 2 2 ( H t 2 + λ ) − G t x 2 2 ( H t x + λ ) ) − γ obj_{1}-obj_{2} =(\frac{G_{t_{1}}^{2}}{2(H_{t_{1}}+\lambda)}+\frac{G_{t_{2}}^{2}}{2(H_{t_{2}}+\lambda)}-\frac{G_{t_{x}}^{2}}{2(H_{t_{x}}+\lambda)})-\gamma obj1obj2=(2(Ht1+λ)Gt12+2(Ht2+λ)Gt222(Htx+λ)Gtx2)γ

    我们利用取得最大值的特征及其取值,来分割叶子节点 t x t_{x} tx,当然这个最大差值至少要大于零,或者大于某个设定的阈值。

    xgboost的并行计算

      虽然xgboost中基CART树之间是串行的,但是单个基CART树的生成可以利用并行计算,例如某一节点的延伸,需要遍历诸多特征和特征取值,这一遍历的过程,我们可以利用多线程并行计算,同时不同记录的一阶偏导 g i g_{i} gi、二阶偏导 h i h_{i} hi相互直接也是独立的,我们可以利用并行化完成。

    xgboost的过拟合处理

      xgboost除了可以给目标函数添加正则化项来缓解过拟合外,还有限制树的最大深度,收缩(Shrinkage)以及特征子采样(Column Subsampling)等方法。

      限制树的最大深度好理解,收缩(Shrinkage)主要是指给新生成的基CART回归树的叶子结点的输出乘一个收缩系数 η \eta η,防止某个基CART回归树影响过大,留更多的学习空间,给后面迭代生成的基CART回归树。

      特征子采样(Column Subsampling)是指随机选取部分特征来学习,不遍历整个特征集合,主要有两种实现方式,一种是按层随机采样,对于要学习的基CART回归树的某一层,我们随机选出部分特征,该层的节点的延伸只考虑这些特征;另一种是先采样出部分特征,在按这些特征生成整个基CART回归树。一般第一种效果更好。


    参考文献:
    一步一步理解GB、GBDT、xgboost:https://www.cnblogs.com/wxquare/p/5541414.html
    xgboost的原理没你想像的那么难:https://www.jianshu.com/p/7467e616f227
    XGBoost——机器学习(理论+图解+安装方法+python代码):https://blog.csdn.net/huacha__/article/details/81029680
    一文读懂机器学习大杀器XGBoost原理 :http://blog.itpub.net/31542119/viewspace-2199549/
    xgboost原理及应用–转(有一些可下载的百度云盘文件):https://www.cnblogs.com/zhouxiaohui888/p/6008368.html
    陈天奇做的XGBoost为什么能横扫机器学习竞赛平台?https://mp.weixin.qq.com/s/lSlRpSD9KWPcSuJbH0LYBg

    展开全文
  • 梯度提升决策树算法(GBDT)作者:江尘([受电子邮件保护])GBDT是Jerome H. Friedman的梯度提升决策树算法的高性能且功能齐全的C ++实现。 ([受电子邮件保护])GBDT是Jerome H. Friedman的“梯度增强决策树算法”...
  • 基于梯度提升决策树的情境感知推荐模型.pdf
  • 原理: 决策树生成算法: 是递归地生成决策树,它往往分类精细,对训练数据集分类准确,但是对未知数据集却没有那么准确,有比较...梯度提升决策树按照一定的次序搭建多个分类模型。模型之间彼此存在依赖关系。后续加入
  • 梯度提升决策树-GBDT(Gradient Boosting Decision Tree).pdf
  • 从决策树到GBDT(Gradient Boosting Decision Tree)梯度提升决策树和XGBoost的一些学习笔记 决策树 决策树可以转换成if-then规则的集合,也可以看作是定义在特征空间划分类的条件概率分布。决策树学习算法包括三...

    从决策树到GBDT(Gradient Boosting Decision Tree)梯度提升决策树和XGBoost的一些学习笔记

    决策树

    决策树可以转换成if-then规则的集合,也可以看作是定义在特征空间划分类的条件概率分布。决策树学习算法包括三部分:特征选择,数的生成和数的剪枝。最大优点: 可以自学习。在学习的过程中,不需要使用者了解过多背景知识,只需要对训练实例进行较好的标注,就能够进行学习。显然,属于有监督学习。
    常用有一下三种算法:

    • ID3 — 信息增益 最大的准则
    • C4.5 — 信息增益比 最大的准则
    • CART(Classification and Regression tree, 分类与回归树)
      回归树: 平方误差 最小 的准则
      分类树: 基尼系数 最小的准则

    回归树 Regression Decision Tree

    回归树总体流程类似于分类树,区别在于,回归树的每一个节点都会得一个预测值。

    使用平方误差最小准则
    训练集为:D={(x1,y1), (x2,y2), …, (xn,yn)}。
    输出Y为连续变量,将输入划分为M个区域,分别为R1,R2,…,RM,每个区域的输出值分别为:c1,c2,…,cm则回归树模型可表示为:

    f(x)=m=1McmI(xRm) f ( x ) = ∑ m = 1 M c m I ( x ∈ R m )

    接下来可以使用平方误差 xiRm(yif(xi)) ∑ x i ∈ R m ( y i − f ( x i ) ) 来表示训练数据的预测误差,用最小平方误差的准则来求解每个单元的最优输出值。
    c^m=ave(yi|xiRm) c ^ m = a v e ( y i | x i ∈ R m )

    假如使用特征j的取值s来将输入空间划分为两个区域,分别为:
    R1(j,s)={x|x(j)<=s}R2(j,s)={x|x(j)>s} R 1 ( j , s ) = { x | x ( j ) <= s } 和 R 2 ( j , s ) = { x | x ( j ) > s }

    选择最优切分变量j与切分点s,求解
    minj,s[minc1xiR1(j,s)(yic1)2+minc2xiR2(j,s)(yic2)2] min j , s [ min c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ]

    并可以得出
    c^1=ave(yi|xiR1(j,s)) c ^ 1 = a v e ( y i | x i ∈ R 1 ( j , s ) )

    c^2=ave(yi|xiR2(j,s)) c ^ 2 = a v e ( y i | x i ∈ R 2 ( j , s ) )

    最小二叉回归树生成算法:

    从以上可以归纳出在最小二叉回归树生成算法。训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域并决定每个子区域上输出值,构建二叉决策树。
    1. 选择最优切分变量j与切分点s,求解

    minj,s[minc1xiR1(j,s)(yic1)2+minc2xiR2(j,s)(yic2)2] min j , s [ min c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ]

    遍历变量j,对固定的切分变量j扫描切分点s,选择使上式最小值的对(j,s)。其中Rm是被划分的输入空间,cm是空间Rm对应的固定输出值。
    2. 用选定的对(j,s)划分区域并决定相应的输出值:
    R1(j.s)={xx(j)s},R2(j,s)={xx(j)>sc^m=1NmxiRm(j,s)yi,xRm,m=1,2 R 1 ( j . s ) = { x ∣ x ( j ) ≤ s } , R 2 ( j , s ) = { x ∣ x ( j ) > s c ^ m = 1 N m ∑ x i ∈ R m ( j , s ) y i , x ∈ R m , m = 1 , 2

    3. 继续对两个子区域调用步骤(1),(2),直至满足停止条件。
    4. 将输入空间划分为M个区域R1,R2,…,RM,生成决策树:
    f(x)=m=1Mc^mI(xR) f ( x ) = ∑ m = 1 M c ^ m I ( x ∈ R )

    提升树 Boosting Decision Tree

    提升树是迭代多棵回归树来共同决策。当采用平方误差损失函数时,每一棵回归树学习的是之前所有树的结论和残差,拟合得到一个当前的残差回归树,残差的意义如公式:残差 = 真实值 - 预测值 。提升树即是整个迭代过程生成的回归树的累加。

    提升树的核心就在于,每一棵树学的是之前所有树结论和的残差,这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁,但第一棵树的预测年龄是12岁,差了6岁,即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习,如果第二棵树真的能把A分到6岁的叶子节点,那累加两棵树的结论就是A的真实年龄;如果第二棵树的结论是5岁,则A仍然存在1岁的残差,第三棵树里A的年龄就变成1岁,继续学。这就是Boosting的意义。

    提升树/GBDT的常用损失函数如图,如何选择损失函数决定了算法的最终效果,包括用平方误差损失函数的回归问题,指数损失函数的分类问题,以及用一般损失函数的一般决策问题。

    对于二分类问题,提升树算法只需将AdaBoost算法中的基本分类器限制为二类分类树即可,可以说此时提升树算法是AdaBoost的特殊情况。这里简单叙述一下回归问题的提升树算法。

    提升树算法

    {D={(x(1),y(1)),(x(2),y(2)),,(x(M),y(M))},x(i)XRn,y(i)Y;fK(x).:(1).f0(x)=0(2).Kk=1,2,,K(a).rki=y(i)fk1(x(i)),i=1,2,,M(b).rkiT(x;Θk)(c).fk(x)=fk1(x)+T(x;Θk)(3).fK(x)=Kk=1T(x;Θk)} { 输 入 : 训 练 数 据 集 D = { ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , ⋯ , ( x ( M ) , y ( M ) ) } , x ( i ) ∈ X ⊆ R n , y ( i ) ∈ Y ; 输 出 : 提 升 树 f K ( x ) . 过 程 : ( 1 ) . 初 始 化 模 型 f 0 ( x ) = 0 ; ( 2 ) . 循 环 训 练 K 个 模 型 k = 1 , 2 , ⋯ , K ( a ) . 计 算 残 差 : r k i = y ( i ) − f k − 1 ( x ( i ) ) , i = 1 , 2 , ⋯ , M ( b ) . 拟 合 残 差 r k i 学 习 一 个 回 归 树 , 得 到 T ( x ; Θ k ) ( c ) . 更 新 f k ( x ) = f k − 1 ( x ) + T ( x ; Θ k ) ( 3 ) . 得 到 回 归 提 升 树 f K ( x ) = ∑ k = 1 K T ( x ; Θ k ) }

    梯度提升决策树 Gradient Boosting Decision Tree (GBDT)

    提升树利用加法模型和前向分步算法实现学习的优化过程。当损失函数时平方损失和指数损失函数时,每一步的优化很简单,如平方损失函数学习残差回归树。但对于一般的损失函数,往往每一步优化没那么容易,如下图中的绝对值损失函数和Huber损失函数。针对这一问题,Freidman提出了梯度提升算法:利用最速下降的近似方法,即利用损失函数的负梯度在当前模型的值,作为回归问题中提升树算法的残差的近似值,拟合一个回归树

    步骤:

    1. 求出损失函数的负梯度, 当做残差的近似值。
    2. 然后让一棵树去拟合每个样本的残差。
      • 回归树和决策树很类似,只是回归树把落入叶子节点的样本,对于他们的标签求了个平均值输出,注意,这里的标签,对于GBDT来说,是每一个样本的残差。
    3. 然后再去求这棵树的占的比重。估计回归树叶节点区域,以拟合残差的近似值。
    4. 线性搜索求系数, 也就是每棵树的系数,使损失函数极小化
    5. 最后的模型用这些树融合

    梯度提升GBDT算法:

    {D={(x(1),y(1)),(x(2),y(2)),,(x(M),y(M))},x(i)XRn,y(i)Y;L(y,f(x));f^(x).:(1).f0(x)=argmincMi=1L(y(i),c)(2).Kk=1,2,,K(a).i=1,2,,Mrki=[L(y(i),f(x(i)))f(x(i))]f(x)=fk1(x)(b).rkikRkjj=1,2,,J(c).j=1,2,,J,ckj=argmincx(i)RkjL(y(i),fk1(x(i))+c)(d).fk(x)=fk1(x)+Jj=1ckjI(xRkj)(3).f^(x)=fK(x)=Kk=1Jj=1ckjI(xRkj)} { 输 入 : 训 练 数 据 集 D = { ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , ⋯ , ( x ( M ) , y ( M ) ) } , x ( i ) ∈ X ⊆ R n , y ( i ) ∈ Y ; 损 失 函 数 L ( y , f ( x ) ) ; 输 出 : 提 升 树 f ^ ( x ) . 过 程 : ( 1 ) . 初 始 化 模 型 f 0 ( x ) = arg ⁡ min c ∑ i = 1 M L ( y ( i ) , c ) ; ( 2 ) . 循 环 训 练 K 个 模 型 k = 1 , 2 , ⋯ , K ( a ) . 计 算 残 差 : 对 于 i = 1 , 2 , ⋯ , M r k i = − [ ∂ L ( y ( i ) , f ( x ( i ) ) ) ∂ f ( x ( i ) ) ] f ( x ) = f k − 1 ( x ) ( b ) . 拟 合 残 差 r k i 学 习 一 个 回 归 树 , 得 到 第 k 颗 树 的 叶 结 点 区 域 R k j , j = 1 , 2 , ⋯ , J ( c ) . 对 j = 1 , 2 , ⋯ , J , 计 算 : c k j = arg ⁡ min c ∑ x ( i ) ∈ R k j L ( y ( i ) , f k − 1 ( x ( i ) ) + c ) ( d ) . 更 新 模 型 : f k ( x ) = f k − 1 ( x ) + ∑ j = 1 J c k j I ( x ∈ R k j ) ( 3 ) . 得 到 回 归 提 升 树 f ^ ( x ) = f K ( x ) = ∑ k = 1 K ∑ j = 1 J c k j I ( x ∈ R k j ) }

    使用scikit-learn中的GBDT

    在scikit-learn中对GBDT算法有了很好的封装,对于分类可以选择的损失函数有逻辑回归和指数函数,对于回归的损失函数相对比较多,有最小二乘法、最小绝对偏差函数、huber以及分位数等。具体损失函数的描述可以参考下面的图片:

    下面是sklearn中的一个分类原例:

    >>> from sklearn.datasets import make_hastie_10_2
    >>> from sklearn.ensemble import GradientBoostingClassifier
    >>> X, y = make_hastie_10_2(random_state=0)
    >>> X_train, X_test = X[:2000], X[2000:]
    >>> y_train, y_test = y[:2000], y[2000:]
    >>> clf = GradientBoostingClassifier(n_estimators=100, learning_rate=1.0,
    ...     max_depth=1, random_state=0).fit(X_train, y_train)
    >>> clf.score(X_test, y_test)                 
    0.913...

    推荐GBDT树的深度:6
    (横向比较:DecisionTree/RandomForest需要把树的深度调到15或更高)

    GBDT与XGBOOST差别

    XGBoost,在计算速度和准确率上,较GBDT有明显的提升。XGBoost的全称是eXtreme Gradient Boosting
    1. 传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项(可以看前面的博文)的Logistics回归(分类问题)或者线性回归(回归问题)。

    1. 传统GBDT在优化时只用到一阶导数信息,xgboost则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便提一下,xgboost工具支持自定义代价函数,只要函数可一阶和二阶求导。

    2. Xgboost在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲,正则项降低了模型的variance,使学习出来的模型更加简单,防止过拟合,这也是xgboost优于传统GBDT的一个特性。

    3. Shrinkage(缩减),相当于学习速率(xgboost中的eta)。xgboost在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间。实际应用中,一般把eta设置得小一点,然后迭代次数设置得大一点。(补充:传统GBDT的实现也有学习速率)

    4. 列抽样(column subsampling)。xgboost借鉴了随机森林的做法,支持列抽样,不仅能降低过拟合,还能减少计算,这也是xgboost异于传统gbdt的一个特性。

    5. 缺失值的处理。对于特征的值有缺失的样本,xgboost可以自动学习出它的分裂方向。

    6. xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的?注意xgboost的并行不是tree粒度的并行,xgboost也是一次迭代完才能进行下一次迭代的(第t次迭代的代价函数里包含了前面t-1次迭代的预测值)。xgboost的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),xgboost在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。

    7. 可并行的近似直方图算法。树节点在进行分裂时,我们需要计算每个特征的每个分割点对应的增益,即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下,贪心算法效率就会变得很低,所以xgboost还提出了一种可并行的近似直方图算法,用于高效地生成候选的分割点。

    参考文献

    1. https://zhuanlan.zhihu.com/p/30316845
    2. Why Does XGBoost Win “Every” Machine Learning Competition?
      https://brage.bibsys.no/xmlui/bitstream/handle/11250/2433761/16128_FULLTEXT.pdf
    3. https://mp.weixin.qq.com/s?__biz=MzA3MzI4MjgzMw==&mid=2650732958&idx=1&sn=234f0aa7992d2435a266bab96c9f4a2a&chksm=871b3de0b06cb4f6dea8b742469df89878a583688ee6c9c138f08a498f756198d17164c0881f&mpshare=1&scene=1&srcid=1108hWgjeMRAV0p7GFI0KQxx#rd
    4. http://www.cnblogs.com/wxquare/p/5541414.html
    5. 统计学习方法,李航
    6. http://www.jianshu.com/p/005a4e6ac775
    7. https://www.jianshu.com/p/7467e616f227
    8. http://scikit-learn.org/stable/modules/ensemble.html#gradient-boosting
    展开全文
  • 梯度提升决策树(Gradient Boosting Decision Tree,GBDT) 集成学习的系列博客: 集成学习(ensemble learning)基础知识 随机森林(random forest) AdaBoost算法(一)——基础知识篇 AdaBoost算法(二)——...

    梯度提升决策树(Gradient Boosting Decision Tree,GBDT)

    集成学习的系列博客:

    今天来讲一讲GBDT,GBDT的名声如雷贯耳,早在深度学习没火之前,集成学习大行其道的时候,GBDT无论是在机器学习比赛中,还是在工业界(尤其CTR预估)都被广泛使用,因为其优秀的性能。GBDT的改进如陈天奇的XGBoost和微软的LightGBM不仅性能优秀,尤其计算速度相比较原始的GBDT有巨大的提升,这两个算法都有现成的python库提供,当我们使用的时候可以调用,sklearn中也封装了基本的GBDT模型,想用也可以直接调用。

    这篇博客想粗浅的讲下GBDT,只讲回归,虽然GBDT也可以用于分类,但貌似工业界回归用的多一些。首先GBDT是boosting算法中的一种,因此学习GBDT需要的前验知识有:

    • Boosting这一类算法思想
    • 分类与回归树(CART)回归部分
    • 提升树

    1、关于Boosting这一类算法思想倒也简单,因为博客集成学习(ensemble learning)基础知识已经讲得很清楚了,这里不再累述,不清楚的请移步这篇博客。
    2、分类与回归树(CART)回归部分,我的博客分类与回归树(classification and regression tree,CART)之回归也有详细的讲解,因此,这里也不太讲解,不清楚的请移步。因为GBDT中的决策树通常都是CART。

    实际上GBDT和AdaBoost的主要区别就在于AdaBoost是在每一次迭代中修改样本权重来使得后一次的树模型更加关注被分错的样本,而GBDT则是后一次树模型直接去拟合残差。这篇博客主要讲解的内容有:

    • 提升树算法
    • 梯度提升树算法
    • GBDT的优缺点
    • GBDT的改进算法

    一、提升树算法

    在前面介绍AdaBoost的时候,讲了提升方法实际上就是加法模型和前向分布法。提升树算法那也采用前向分步法,首先初始提升树 f 0 ( x ) = 0 f_0(x) = 0 f0(x)=0,第m步的模型是
    (1) f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) f_m(x) = f_{m-1}(x) + T(x; \Theta_m) \tag{1} fm(x)=fm1(x)+T(x;Θm)(1)
    其中, f m − 1 ( x ) f_{m-1}(x) fm1(x)表示当前模型,目标是通过经验风险极小化确定下一颗决策树的参数 Θ m \Theta_m Θm
    (2) Θ ^ m = arg ⁡ min ⁡ Θ m ∑ i = 1 N L ( y i , f m − 1 ( x i ) + T ( x i ; Θ m ) ) \hat{\Theta}_m = \arg\min_{\Theta_m}\sum_{i=1}^{N}L(y_i, f_{m-1}(x_i) + T(x_i;\Theta_m))\tag{2} Θ^m=argΘmmini=1NL(yi,fm1(xi)+T(xi;Θm))(2)
    对于提升树而言,分类问题使用的损失函数是指数函数,回归问题使用的是均方误差。我们这里主要回归问题。
    对于一个训练集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,((x_N,y_N)\} T={(x1,y1),(x2,y2),...,((xN,yN)},如果将输入空间划分为 J J J个互不相交的区域 R 1 , R 2 , . . . , R J R_1,R_2,...,R_J R1,R2,...,RJ,并且在每个区域上确定输出的常量 c j c_j cj(看了CART的博客我们知道这个其实就是结点分裂后某个分支包含的样本的真实值的平均值),则树可表示为:
    (3) T ( x ; Θ ) = ∑ j = 1 J c j I ( x ∈ R j ) T(x;\Theta)=\sum_{j=1}^{J}c_jI(x \in R_j)\tag{3} T(x;Θ)=j=1JcjI(xRj)(3)
    其中,参数 Θ = { ( R 1 , c 1 ) , ( R 2 , c 2 ) , . . . . , ( R J , c J ) } \Theta=\{(R_1,c_1),(R_2,c_2),....,(R_J,c_J)\} Θ={(R1,c1),(R2,c2),....,(RJ,cJ)},表示空间划分和各区域上的常数(预测值), J J J是叶结点的个数。
    对于回归问题,当损失函数为均方误差时,
    (4) L ( y , f ( x ) ) = ( y − f ( x ) ) 2 L(y, f(x)) = (y - f(x))^2\tag{4} L(y,f(x))=(yf(x))2(4)
    即,
    (5) L ( y , f m − 1 ( x ) + T ( x ; Θ m ) ) = [ y − f m − 1 ( x ) − T ( x ; Θ m ) ] 2 = [ r − T ( x ; Θ m ) ] 2 \begin{aligned} L(y, f_{m-1}(x) + T(x;\Theta_m)) &amp;= [y-f_{m-1}(x) - T(x;\Theta_m)]^2 \\ &amp;= [r - T(x;\Theta_m)]^2 \tag{5} \end{aligned} L(y,fm1(x)+T(x;Θm))=[yfm1(x)T(x;Θm)]2=[rT(x;Θm)]2(5)
    其中, r = y − f m − 1 ( x ) r=y-f_{m-1}(x) r=yfm1(x) 为当前模型拟合数据的残差,也就是说对回归问题的提升树而言,下一次迭代中模型只需要拟合当前模型的残差即可。上面说了这么一堆,直接来看提升树的算法吧,可能更清晰点。
    提升树
    下面直接上例子,一直觉得举例子是最容易让人懂得,文字描述太扯淡,又不是写论文,搞这些形式化的文字意义不大。
    数据集为(摘自李航《统计学习方法》,注,李航的书并未给出特征,只给出了x的取值范围,我这里把它给的切分点设置成了特征,这样最后结果保持不变):

    样本编号12345678910
    x i ( 1 ) x_i^{(1)} xi(1)1.52.53.54.55.56.57.58.59.510.5
    y i y_i yi5.565.705.916.406.807.058.908.709.009.05

    假设我们采用提升树模型去学习这个回归问题,ps:由于这个数据集共10个样本,每个样本只有一个特征,但是实际上显然数据集不可能特征是一维的,因此寻找最优特征和最优切分点双重for循环即可。我们这里由于特征是一维的,因此只要找到最优切分点即可。因此提升树里的基分类器实际上就是个CART,因此查找最优特征和最优切分点过程就是CART的过程。下面是计算过程:
    第一步, m = 1 m=1 m=1时:

    1. 当切分点为 s = 1.5 s=1.5 s=1.5时, R 1 = { 1 } R_1=\{1\} R1={1} R 2 = { 2 , 3 , . . . , 10 } R_2=\{2,3,...,10\} R2={2,3,...,10},此时 c 1 = 5.56 c_1=5.56 c1=5.56 c 2 = 7.5 c_2=7.5 c2=7.5,此时误差 m ( 1.5 ) = 15.72 m(1.5)=15.72 m(1.5)=15.72
    2. 当切分点为 s = 2.5 s=2.5 s=2.5时, R 1 = { 1 , 2 } R_1=\{1,2\} R1={1,2} R 2 = { 3 , . . . , 10 } R_2=\{3,...,10\} R2={3,...,10},此时 c 1 = 5.63 c_1=5.63 c1=5.63 c 2 = 7.73 c_2=7.73 c2=7.73,此时误差 m ( 2.5 ) = 12.08 m(2.5)=12.08 m(2.5)=12.08
    3. 当切分点为 s = 3.5 s=3.5 s=3.5时, R 1 = { 1 , 2 , 3 } R_1=\{1,2,3\} R1={1,2,3} R 2 = { 4 , . . . , 10 } R_2=\{4,...,10\} R2={4,...,10},此时 c 1 = 5.72 c_1=5.72 c1=5.72 c 2 = 7.98 c_2=7.98 c2=7.98,此时误差 m ( 3.5 ) = 8.36 m(3.5)=8.36 m(3.5)=8.36
    4. 当切分点为 s = 4.5 s=4.5 s=4.5时, R 1 = { 1 , . . . , 4 } R_1=\{1,...,4\} R1={1,...,4} R 2 = { 5 , . . . , 10 } R_2=\{5,...,10\} R2={5,...,10},此时 c 1 = 5.89 c_1=5.89 c1=5.89 c 2 = 8.25 c_2=8.25 c2=8.25,此时误差 m ( 4.5 ) = 5.78 m(4.5)=5.78 m(4.5)=5.78
    5. 当切分点为 s = 5.5 s=5.5 s=5.5时, R 1 = { 1 , . . . , 5 } R_1=\{1,...,5\} R1={1,...,5} R 2 = { 6 , . . . , 10 } R_2=\{6,...,10\} R2={6,...,10},此时 c 1 = 6.07 c_1=6.07 c1=6.07 c 2 = 8.54 c_2=8.54 c2=8.54,此时误差 m ( 5.5 ) = 3.91 m(5.5)=3.91 m(5.5)=3.91
    6. 当切分点为 s = 6.5 s=6.5 s=6.5时, R 1 = { 1 , . . . . , 6 } R_1=\{1,....,6\} R1={1,....,6} R 2 = { 7 , . . . , 10 } R_2=\{7,...,10\} R2={7,...,10},此时 c 1 = 6.24 c_1=6.24 c1=6.24 c 2 = 8.91 c_2=8.91 c2=8.91,此时误差 m ( 6.5 ) = 1.93 m(6.5)=1.93 m(6.5)=1.93
    7. 当切分点为 s = 7.5 s=7.5 s=7.5时, R 1 = { 1 , . . . . , 7 } R_1=\{1,....,7\} R1={1,....,7} R 2 = { 8 , 9 , 10 } R_2=\{8,9,10\} R2={8,9,10},此时 c 1 = 6.62 c_1=6.62 c1=6.62 c 2 = 8.92 c_2=8.92 c2=8.92,此时误差 m ( 7.5 ) = 8.01 m(7.5)=8.01 m(7.5)=8.01
    8. 当切分点为 s = 8.5 s=8.5 s=8.5时, R 1 = { 1 , . . . . , 8 } R_1=\{1,....,8\} R1={1,....,8} R 2 = { 9 , 10 } R_2=\{9,10\} R2={9,10},此时 c 1 = 6.88 c_1=6.88 c1=6.88 c 2 = 9.03 c_2=9.03 c2=9.03,此时误差 m ( 8.5 ) = 11.74 m(8.5)=11.74 m(8.5)=11.74
    9. 当切分点为 s = 9.5 s=9.5 s=9.5时, R 1 = { 1 , . . . . , 9 } R_1=\{1,....,9\} R1={1,....,9} R 2 = { 10 } R_2=\{10\} R2={10},此时 c 1 = 7.11 c_1=7.11 c1=7.11 c 2 = 9.05 c_2=9.05 c2=9.05,此时误差 m ( 9.5 ) = 15.74 m(9.5)=15.74 m(9.5)=15.74

    把上面的误差放到一张表里,看的更清晰点。

    切分点1.52.53.54.55.56.57.58.59.5
    误差(均方差)15.7212.088.365.783.911.938.0111.7415.74

    能够看出当切分点为6.5时,误差最小,所以6.5为最优切分点。此时 c 1 = 6.24 c_1=6.24 c1=6.24 c 2 = 8.91 c_2=8.91 c2=8.91,所以回归树 T 1 ( x ) T_1(x) T1(x)为:
    T 1 ( x ) = { 6.24 x ≤ 6.5 8.91 x &gt; 6.5 T_1(x)=\left\{\begin{matrix} 6.24 &amp; x\leq6.5\\ 8.91 &amp; x&gt;6.5 \end{matrix}\right. T1(x)={6.248.91x6.5x>6.5
    所以,提升树模型 f 1 ( x ) = T 1 ( x ) f_1(x) = T_1(x) f1(x)=T1(x),那么用这个模型去拟合训练样本,我们能够算出预测值与真实值之间的误差也就是残差,如下表所示:

    样本编号12345678910
    真实值 y i y_i yi5.565.705.916.406.807.058.908.709.009.05
    残差-0.68-0.54-0.330.160.560.81-0.01-0.210.090.14

    此时,损失(均方误差)为:
    L ( y , f 1 ( x ) ) = ∑ i = 1 10 ( y i − f 1 ( x ) ) 2 = 1.93 L(y,f_1(x)) = \sum_{i=1}^{10}(y_i-f_1(x))^2 = 1.93 L(y,f1(x))=i=110(yif1(x))2=1.93
    第二步,即 m = 2 m=2 m=2时,求 T 2 ( x ) T_2(x) T2(x)求得方法与求 T 1 ( x ) T_1(x) T1(x)一样,只不过 T 1 ( x ) T_1(x) T1(x)拟合的是 y i y_i yi,而 T 2 ( x ) T_2(x) T2(x)拟合的是上表中的残差,求最后划分点的过程我这里就省略了,最优划分点为 s = 3.5 s=3.5 s=3.5,即
    T 2 ( x ) = { − 0.52 x ≤ 3.5 0.22 x &gt; 3.5 T_2(x)=\left\{\begin{matrix} -0.52 &amp; x\leq3.5\\ 0.22 &amp; x&gt;3.5 \end{matrix}\right. T2(x)={0.520.22x3.5x>3.5
    则,树模型 f 2 ( x ) f_2(x) f2(x)为:
    f 2 ( x ) = f 1 ( x ) + T 2 ( x ) = { 5.72 x ≤ 3.5 6.46 3.5 &lt; x ≤ 6.5 9.13 x &gt; 6.5 f_2(x) = f_1(x) + T_2(x)=\left\{\begin{matrix} 5.72 &amp; x\leq3.5\\ 6.46 &amp; 3.5 &lt; x \leq 6.5 \\ 9.13 &amp; x &gt; 6.5 \end{matrix}\right. f2(x)=f1(x)+T2(x)=5.726.469.13x3.53.5<x6.5x>6.5
    注意看下分段函数的相加。
    f 2 ( x ) f_2(x) f2(x)拟合训练样本loss为:
    L ( y , f 2 ( x ) ) = ∑ i = 1 10 ( y i − f 2 ( x ) ) 2 = 0.79 L(y,f_2(x)) = \sum_{i=1}^{10}(y_i-f_2(x))^2 = 0.79 L(y,f2(x))=i=110(yif2(x))2=0.79

    第三步,即 m = 3 m=3 m=3 时,有
    T 3 ( x ) = { 0.15 x ≤ 6.5 − 0.22 x &gt; 6.5 T_3(x)=\left\{\begin{matrix} 0.15 &amp; x\leq6.5\\ -0.22 &amp; x&gt;6.5 \end{matrix}\right. T3(x)={0.150.22x6.5x>6.5
    f 3 ( x ) = f 2 ( x ) + T 3 ( x ) = { 5.87 x ≤ 3.5 6.61 3.5 &lt; x ≤ 6.5 8.91 x &gt; 6.5 f_3(x) = f_2(x) + T_3(x)=\left\{\begin{matrix} 5.87 &amp; x\leq3.5\\ 6.61 &amp; 3.5 &lt; x \leq 6.5 \\ 8.91 &amp; x &gt; 6.5 \end{matrix}\right. f3(x)=f2(x)+T3(x)=5.876.618.91x3.53.5<x6.5x>6.5
    loss为: L ( y , f 3 ( x ) ) = 0.47 L(y,f_3(x)) = 0.47 L(y,f3(x))=0.47

    第四步,即 m = 4 m=4 m=4 时,有
    T 4 ( x ) = { − 0.16 x ≤ 4.5 0.11 x &gt; 4.5 T_4(x)=\left\{\begin{matrix} -0.16 &amp; x\leq4.5\\ 0.11 &amp; x&gt;4.5 \end{matrix}\right. T4(x)={0.160.11x4.5x>4.5
    f 4 ( x ) = f 3 ( x ) + T 4 ( x ) = { 5.71 x ≤ 3.5 6.45 3.5 &lt; x ≤ 4.5 6.72 4.5 &lt; x ≤ 6.5 9.02 x &gt; 6.5 f_4(x) = f_3(x) + T_4(x)=\left\{\begin{matrix} 5.71 &amp; x\leq3.5\\ 6.45 &amp; 3.5 &lt; x \leq 4.5 \\ 6.72 &amp; 4.5 &lt; x \leq 6.5 \\ 9.0