我们对Boosting家族的Adaboost算法做了总结，本文就对Boosting家族中另一个重要的算法梯度提升树(Gradient Boosting Decison Tree, 以下简称GBDT)做一个总结。GBDT有很多简称，有GBT（Gradient Boosting Tree）, GTB（Gradient Tree Boosting ）， GBRT（Gradient Boosting Regression Tree）, MART(Multiple Additive Regression Tree)，其实都是指的同一种算法，本文统一简称GBDT。GBDT在BAT大厂中也有广泛的应用，假如要选择3个最重要的机器学习算法的话，个人认为GBDT应该占一席之地。
我们先来看看提升树：
提升树模型实际是将多个决策树简单的叠加起来，用数学模型可表示为

$\( f_M(x) = sum_{m=1}^M T(x;Theta_m) \)\(</p><p>其中，\)T(x;Theta_m)\(表示决策树，\)Theta_m\( 表示决策树的参数；\)M\( 为树的个数。<br>针对样本\)D={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}\(，提升树模型的训练就是，选择决策树的参数\)Theta={Theta_1,Theta_2,…,Theta_M}\(以最小化损失函数 \)sum L(y_i,f_M(x_i))\(，即</p><p>\)\( arg min_Theta sum_{i=1}^N L(y_i,f_M(x_i)) = arg min_Theta sum_{i=1}^N Lleft(y_i, sum_{m=1}^M T(x;Theta_m) ight) \)\(</p><p>这里，损失函数用来反应“样本标签 \)y_i\( ”与提升树的输出 \)f_M(x_i)\( 之间的差别，这里可以选择平方误差损失函数：</p><p>\)\( L(y, f(x))=left( y-f(x) ight)^2 \)\(</p><p>提升树模型也可以表示为迭代过程</p><p>\)\( f_m(x)=f_{m-1}(x)+T(x;Theta_m),~ m=1,2,...,M \)\(</p><p>因此，提升树的训练也可以按照迭代的过程来完成，在 \)m\(次迭代中，生成一个新的决策树\)T(x;Theta_m)\(<br>具体而言，首先初始化提升树 \)f_0(x)=0\(，第 \)m\( 步确定第 \)m\( 个决策树\)T(x;Theta_m)\(，即选择合适的决策树参数 \)Theta_m\(，使损失函数最小，即</p><p>\)\( hat{Theta}_m = arg min_{Theta_m} sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i;Theta_m)) \)\(</p><p>对于上式的求解，即为提升树的关键所在。如果采用平方损失函数，则有</p><p>\)\( begin{eqnarray*} L(y_i,f_{m-1}(x_i)+T(x_i;Theta_m)) &amp;=&amp; left[,y_i - f_{m-1}(x_i) - T(x_i;Theta_m) ight]^2 \ &amp;=&amp; left[,r_{m,i} - T(x_i;Theta_m) ight]^2 end{eqnarray*} \)\(</p><p>这里， \)r_{m,i}=yi-f{m-1}(xi)\( 表示模型\)f{m-1}(x)\(拟合数据 \)(x_i,y_i)\( 的残差。<br>就变成了选择合适的决策树参数\)Theta_m\(，使得决策树的输出 \)T(x_i;Thetam)\(与 残差 \)r{m,i}\( 的误差尽可能小。因此，可以使用 \){(xi,r{m,i})}_{i=1,2,…,N}\(来作为决策树\)T(x;Theta_m)\(的样本集，按照常规的决策树生成过程获得参数的最优值\)hat{Theta}_m\(。<br>综上，我们可以得到提升树算法如下：</p><p style="text-align:center;"><img src='https://s2.51cto.com/images/blog//_658b54d2f112e24196.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184' alt='梯度提升树与神经网络结合matlab代码 梯度提升树优缺点_决策树' title="image" style="width: 866px; visibility: visible;"></p><p> <br></p><p> <br></p><p>上面我们讲了提升树，在某些时候不方便求残差，梯度提升树则是用损失函数的负梯度方向值来近似拟合残差，下面来看看具体细节： <br></p><p> <br></p><p style="text-align:center;"><img src='https://s2.51cto.com/images/blog//_658b54d32ae.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184' alt='梯度提升树与神经网络结合matlab代码 梯度提升树优缺点_决策树_02' title="image" style="width: 864px; visibility: visible;"></p><p><br></p><p style="text-align:center;"><img src='https://s2.51cto.com/images/blog//_658b54d351ef.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184' alt='梯度提升树与神经网络结合matlab代码 梯度提升树优缺点_r语言_03' title="image" style="width: 867px; visibility: visible;"></p><p><strong>二元GBDT分类算法</strong><br>对于二分类问题，比较常用的损失函数为</p><p>\)\( L(y,f(x))=log (1+exp (-y cdot f(x))) ag{12} \)\(</p><p>其中 \)y∈{−1,+1}\(，此时的负梯度误差为</p><p>\)\( r_{m,i} = -left[ frac{partial L(y_i,f(x_i))}{partial f(x_i)} ight]_{f(x)=f_{m-1}(x)} = frac{y_i}{1+exp (y_i f_{m-1}(x_i))} \)\(</p><p>对于生成决策树，其叶子节点的输出值为</p><p>\)\( c_{m,j} = arg min_c sum_{x_iin R_{m,j}} log (1+exp (-y_i (f_{m-1}(x_i) + c))) \)\(</p><p>由于上式比较难优化，我们一般使用近似值代替</p><p>\)\( c_{m,j} =left. sum_{x_iin R_{m,j}} r_{m,i} middle / sum_{x_iin R_{m,j}} |r_{m,i}|(1-|r_{m,i}|) ight. \)\(</p><p><strong>多元GBDT分类算法</strong><br>对于多分类问题，假设类别为\) K\(，一般采用的损失函数为</p><p>\)\( L(y,f(x)) = - sum_{k=1}^K y_k log p_k(x) \)\(</p><p>其中，如果样本输出类别为 \)k\( ，则 \)y_k=1\( ；\)p_k(x)\( 表示模型 \)f(x)\(判定 \)x\(属于第\)k\( 类的概率，其表达式为</p><p>\)\( p_k(x) = frac{exp (f_k(x))}{ sum_{l=1}^K exp(f_l(x))} \)\(</p><p>注意此处，对于多分类问题，回归树训练时，会为每一个类别训练一个决策树。<br>由此，我们可以计算出第 \)m\( 轮的第\)i\(个样本对应类别\) l\(的负梯度误差为</p><p>\)\( r_{m,i,l} = -left[ frac{partial L(y_i,f(x_i))}{partial f(x_i)} ight]_{f(x)=f_{m-1,l}(x)} = y_{i,l} - p_{m,l}(x_i) \)\(</p><p>观察上式可以看出，其实这里的误差就是样本\)i\(对应类别\)l\( 的真实概率和\)m−1\( 轮预测概率的差值。<br>对于生成的决策树，对应第\)l\(类别的决策树的叶节点输出为</p><p>\)\( c_{m,l,j} = arg min_c sum_{x_i in R_{m,l,j}} L(y_{i,l}, f_{m-1,l}(x_i) + c) \)\(</p><p>类似的，我们用近似值代替</p><p>\)\( c_{m,l,j} = frac{K-1}{K} frac{sumlimits_{x_i in R_{m,l,j}}r_{m,i,l}}{ sumlimits_{x_i in R_{m,l,j}} |r_{m,i,l}|(1-|r_{m,i,l}|) } \)\(</p><p><strong>GBDT 的正则化</strong></p><ul><li>第一种是和Adaboost类似的正则化项，即使用步长(learning rate)，定义为 αα 。常规的提升回归树的迭代为</li></ul><p>\)\( f_m(x) = f_{m-1}(x) + T(x;Theta_m) \)\(</p><p>引入正则化后，其迭代过程为</p><p>\)\( f_m(x) = f_{m-1}(x) + alpha T(x;Theta_m) \)\(</p><p>其中，\)0&lt;α≤1\(。对于同样的训练集学习效果，较小的 αα 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。</p><ul><li>第二种正则化的方式是通过子采样比例（subsample）。取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。<br>使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。</li><li>第三种称为 Regularized Learning Objective，将树模型的复杂度作为正则项显式地加进优化目标里，这也是XGBoost实现的独到之处。其具体实现可以参考文献[7]，在这里列出其加入正则化后的优化目标</li></ul><p>\)\( L_{r}(y,f(x)) = L(y,f(x)) + sum_{m} Omega(T(x;Theta_m)) \ mathrm{where} ~~ Omega(T(x;Theta_m)) = gamma T_{leaf} + frac12 lambda | w |^2 \)\(</p><p>其中，\)L(y,f(x))\( 为常规的损失函数；\)Omega(T(x;Thetam))\(表示决策树的复杂度，\)T{leaf}\(为树叶节点个数，\)w\( 为叶节点的固定输出值\)c_m\(组成的向量；\)γ,λ$为相应的系数。

讯享网

• 最后还有一种就是类 似DeepLearning 的 Dropout ，其具体可以参考文献[8]。通俗地讲，每次新加一棵树，这棵树要拟合的并不是之前全部树ensemble后的残差，而是随机抽取的一些树ensemble。