梯度提升决策树(GBDT)与极端梯度提升(xgboost)算法

梯度提升决策树(GBDT)与极端梯度提升(xgboost)算法"/>

梯度提升决策树(GBDT)与极端梯度提升(xgboost)算法

文章目录

• 梯度提升决策树(GBDT)
• • 算法流程
• 极端梯度提升(xgboost)算法
• • xgboost的目标函数
  • 确定基CART树的叶子节点输出
  • 确定基CART树的结构
  • xgboost的并行计算
  • xgboost的过拟合处理

梯度提升决策树(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)=argcmin​i=1∑N​L(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)=fm−1​(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,2…J。
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​=argcmin​xi​∈Rmj​∑​L(yi​,fm−1​(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)=fm−1​(x)+j=1∑J​cmj​I(x∈Rmj​)若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=1∑M​j=1∑J​cmj​I(x∈Rmj​)

  在《统计学习方法》中，梯度提升没有基学习器的权值，但在有些文献中，会在上面的步骤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γm​min​L(yi​,fm−1​(x)+γm​j=1∑J​cmj​I(x∈Rmj​))

对应的步骤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)=fm−1​(x)+γm​j=1∑J​cmj​I(x∈Rmj​))

---

极端梯度提升(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 k−1个学习器与目标输出的残差，最终的学习器表示如下： 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=1∑K​fk​(x),k=1,2…K

其中， 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)min​i=1∑n​l(yi​,y^​i(k−1)​+fk​(xi​))

其中， y i y_{i} yi​是第 i i i条数据的真实输出， y ^ i ( k − 1 ) \hat{y}^{(k-1)}_{i} y^​i(k−1)​是已经学习的前 k − 1 k-1 k−1个学习器对第 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=1∑n​l(yi​,y^​i(k−1)​+fk​(xi​))+j=1∑k​Ω(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=1∑T​wt2​

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

当训练第 k k k个基CART回归树时，不难看出前 k − 1 k-1 k−1个基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​)min​i=1∑n​l(yi​,y^​i(k−1)​+fk​(xi​))+Ω(fk​)+Constant=fk​(x),wt​min​i=1∑n​l(yi​,y^​i(k−1)​+fk​(xi​))+γT+21​λt=1∑T​wt2​+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(k−1)​+fk​(xi​))

我们知道 y i y_{i} yi​与 y ^ i ( k − 1 ) \hat{y}^{(k-1)}_{i} y^​i(k−1)​是常量，所以我们的损失函数是关于 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(k−1)​+fk​(xi​))=l(yi​,y^​i(k−1)​+0)+∂fk​(xi​)∂l​∣∣∣∣∣​fk​(xi​)=0​⋅(fk​(xi​)−0)+21​∂fk​(xi​)2∂2l​∣∣∣∣∣​fk​(xi​)=0​⋅(fk​(xi​)−0)2=l(yi​,y^​i(k−1)​)+∂(y^​i(k−1)​+fk​(xi​))∂l​∂fk​(xi​)∂(y^​i(k−1)​+fk​(xi​))​∣∣∣∣∣​fk​(xi​)=0​⋅fk​(xi​)   +21​∂fk​(xi​)∂​(∂(y^​i(k−1)​+fk​(xi​))∂l​∂fk​(xi​)∂(y^​i(k−1)​+fk​(xi​))​)∣∣∣∣∣​fk​(xi​)=0​⋅fk​(xi​)2=l(yi​,y^​i(k−1)​)+∂y^​i(k−1)​∂l(yi​,y^​i(k−1)​)​fk​(xi​)   +21​∂(y^​i(k−1)​+fk​(xi​))∂(∂(y^​i(k−1)​+fk​(xi​))∂l​)​∂fk​(xi​)∂(y^​i(k−1)​+fk​(xi​))​∣∣∣∣∣​fk​(xi​)=0​⋅fk​(xi​)2=l(yi​,y^​i(k−1)​)+∂y^​i(k−1)​∂l(yi​,y^​i(k−1)​)​⋅fk​(xi​)+21​∂(y^​i(k−1)​)2∂2l(yi​,y^​i(k−1)​)​⋅fk​(xi​)2=l(yi​,y^​i(k−1)​)+gi​fk​(xi​)+21​hi​fk​(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(k−1)​∂l(yi​,y^​i(k−1)​)​=∂yi​^​(k−1)​l(yi​,y^​i(k−1)​)

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(k−1)​)2∂2l(yi​,y^​i(k−1)​)​=∂yi​^​(k−1)2​l(yi​,y^​i(k−1)​)

为何要用二阶泰勒展开来替代原损失函数？因为这样我们就构造出了关于 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),wt​min​i=1∑n​l(yi​,y^​i(k−1)​+fk​(xi​))+γT+21​λt=1∑T​wt2​+Constant=fk​(x),wt​min​i=1∑n​(l(yi​,y^​i(k−1)​)+gi​fk​(xi​)+21​hi​fk​(xi​)2)+γT+21​λt=1∑T​wt2​+Constant

由于 l ( y i , y ^ i ( k − 1 ) ) l(y_{i}, \hat{y}^{(k-1)}_{i}) l(yi​,y^​i(k−1)​)是常数，我们把它融入 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),wt​min​i=1∑n​(gi​fk​(xi​)+21​hi​fk​(xi​)2)+γT+21​λt=1∑T​wt2​

根据上面关于 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 wt​min​t=1∑T​((fk​(xj​)=wt​∑​gj​)wt​+21​(fk​(xj​)=wt​∑​hj​+λ)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​)=wt​∑​gj​

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​)=wt​∑​hj​

则目标函数进一步变成 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 wt​min​t=1∑T​(Gt​wt​+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=1∑T​(−2(Ht​+λ)Gt2​​)+γT

  值得一提的是，上面的 G t 、 H t 、 λ 、 γ G_{t}、H_{t}、\lambda、\gamma Gt​、Ht​、λ、γ和真实输出 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=1∑T​(−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=1∑T+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 obj1​−obj2​=(2(Ht1​​+λ)Gt1​2​​+2(Ht2​​+λ)Gt2​2​​−2(Htx​​+λ)Gtx​2​​)−γ

我们利用取得最大值的特征及其取值，来分割叶子节点 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：.html
xgboost的原理没你想像的那么难：
XGBoost——机器学习（理论+图解+安装方法+python代码）：
一文读懂机器学习大杀器XGBoost原理 ：/
xgboost原理及应用–转(有一些可下载的百度云盘文件)：.html
陈天奇做的XGBoost为什么能横扫机器学习竞赛平台？