XGboost是一种梯度提升决策树（GBDT）的模型，它的思想是由决策树（CART）到Adaboost，再到GBDT发展起来的，下面开始总结一下学习XGboost原理的一些心得体会。
XGboost原理推导
首先我们来看XGboost的目标函数： \[L(\phi)=\sum_i l(\hat y_i ,y_i)+\sum_k \Omega(f_k) \qquad (1-1)\]
其中
\[\Omega (f)=\gamma T+\frac{1}{2} \lambda \parallel \omega \parallel ^2\]
这里一个个解释，目标函数中的第二项\(\displaystyle \sum_k \Omega(f_k)\)，这是正则项，也称惩罚项，它是控制模型的复杂度，也就是说这一项的目的是为了在模型复杂程度和模型效果之间取一个平衡。\(f_k\)是基分类器（XGboost中的基分类器是CART），是来自于Boosting思想中的加法模型，即 \[\hat y_i =\sum_k f_k(x_i)\]
在\(\Omega (f)\)的表达式中，\(T\)表示树中的叶子节点数，\(\omega\)是叶子节点上的值。目标函数中的第一项是损失函数（Lost function），\(\hat y_i\)是预测值，\(y_i\)是真实值，\(i\)是样本数。
根据这个目标函数，我们要求的就是\(f_k\)，即当前状态下的决策树是什么样子的。求解的方法是向前分步算法： \[L^{(t)}=\sum_i l(y_i,\hat y^{(t-1)}_i + f_t(x_i))+\Omega (f_t) \qquad (1-2)\]
也就是说，在当前状态第\(t\)轮，那么的\(t-1\)轮的结果就是已知的，所以优化上面的式子就能得到\(f_t\)。其实这个式子还有一个常数项\(\displaystyle \sum_{k=1}^{t-1}\Omega(f_k)\)，即前\(t-1\)轮的正则项，由于常数项对于优化结果是没有影响的，所以去掉了。求解式（1-2），这里用到二阶泰勒展开，先回顾一下二阶泰勒展开： > \(\displaystyle f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{1}{2}f''(x_0)(x-x_0)^2\)
换一种写法可能对这个问题更直观一点： > \(\displaystyle f(x_0+\Delta x)=f(x_0)+f'(x_0)\Delta x+\frac{1}{2}f''(x_0)(\Delta x)^2\)
下面我们将式（1-2）中的损失函数二阶展开，把\(\hat y^{(t-1)}_i\)看作是泰勒公式中的\(x_0\)，\(f_t(x_i)\)看作是\(\Delta x\)，展开得到下式： \[L^{(t)}\simeq \sum_i[l(y_i,\hat y^{(t-1)}_i)+g_i f_t(x_i)+\frac{1}{2}h_i f^2_t(x_i)]+\Omega (f_t) \qquad (1-3)\]
其中
\[g_i=\partial _{\hat y^{(t-1)}} l(y_i,\hat y^{(t-1)}) \qquad h_i=\partial ^2_{\hat y^{(t-1)}} l(y_i,\hat y^{(t-1)})\] 即\(g_i\)，\(h_i\)分别是损失函数\(l(y_i,\hat y^{(t-1)})\)对\(\hat y^{(t-1)}\)的一阶导数和二阶导数。
由于式（1-3）中的\(l(y_i,\hat y^{(t-1)})\)为已知项，即为常数项，所以去除后可以得到下式： \[L^{(t)}\simeq \sum_i[g_i f_t(x_i)+\frac{1}{2}h_i f^2_t(x_i)]+\Omega (f_t) \qquad (1-4)\]
接下来将式（1-4）中的正则项\(\Omega (f_t)\)的具体内容代入式子中，得到下式： \[L^{(t)}\simeq \sum_i[g_i f_t(x_i)+\frac{1}{2}h_i f^2_t(x_i)]+\gamma T+\frac{1}{2}\lambda \sum^T_{j=1} \omega^2_j \qquad (1-5)\]
式中的\(\omega _j\)是叶子节点\(j\)上的值。接下来需要做一个求和下标的转换，式（1-5）中的求和是对所有的样本点求和，那么我们可以这样想，因为每一个样本点最终都会落到一个叶子节点上，所以对于每一个叶子节点，至少有一个样本点。这样一来，对所有的样本点求和就可以转换成对所有的叶子节点求和，可以得到下式： \[L^{(t)}\simeq \sum^T_{j=1}[ (\sum _{i\in I_j} g_i)\omega _j +\frac{1}{2}(\sum _{i\in I_j} h_i+\lambda)\omega ^2_j]+\gamma T \qquad (1-6)\]
式（1-6）中的\(I_j\)是一个集合，表示所有落到叶子节点\(j\)的样本点。对于某棵决策树结构，式（1-6）的未知量就只有\(\omega _j\)，并且整个式子（1-6）是关于\(\omega _j\)的一元二次方程，求最值时，令\(\displaystyle \frac{\partial {L^{(t)}}}{\partial \omega _j}=0\)即可求得\(\omega ^*_j\)： \[\omega ^*_j =-\frac{\sum _{i\in I_j} g_i}{\sum _{i\in I_j} h_i+\lambda}\]
将\(\omega ^*_j\)的值代入式（1-6）得到下式： \[L^{(t)} (q)=-\frac{1}{2} \sum ^T_{j=1} \frac{(\sum _{i\in I_j} g_i)^2}{\sum _{i\in I_j} h_i+\lambda}+\gamma T\]
这里便得到了评价树结构好坏的score function，根据这个score function就可以得到划分节点的依据，即某节点分开后的score function减去这个节点未分开的score function： \[L_{split}=\frac{1}{2} [\frac{(\sum _{i\in I_L} g_i)^2}{\sum _{i\in I_L} h_i+\lambda}+\frac{(\sum _{i\in I_R} g_i)^2}{\sum _{i\in I_R} h_i+\lambda}-\frac{(\sum _{i\in I} g_i)^2}{\sum _{i\in I} h_i+\lambda}]-\gamma\]
式子中的\(I_L,I_R\)分别表示某节点分裂后落到左边节点的所有样本点和落到右边节点的所有样本点。
(未完待续)
参考文献
- Chen, Tianqi, and Carlos Guestrin. "Xgboost: A scalable tree boosting system." Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. ACM, 2016.
- 《统计学习方法》 李航 著
- 深入理解网红算法XGBoost
- 对xgboost的理解
- 一文理解GBDT的原理
