论文总结：XGBoost - A Scalable Tree Boosting System
Published On 2020/04/05 Sunday, Singapore
提升树算法（Gradient Tree Boosting）是机器学习中处理分类问题十分有效的方法，常被应用于广告点击率的预测和机器学习类比赛。
2014年，在传统提升树算法模型上，作者提出了XGBoost，并发布了相应的工具包。XGBoost因其计算速度快和模型表示好而广泛被应用在各类数据竞赛中，这些比赛包括：门店销售额预测，网页文本分类，点击率，产品分类等。该论文发表于两年后的2016KDD会议。
文章链接：XGBoost: A Scalable Tree Boosting System
XGboost 数学过程
目标函数
假设数据集样本个数为$n$，特征变量个数为$m$。其特征可表示为 \(D= \{(\mathbf{x}_i,y_i)\}\)。其中，$\lvert D \rvert = n, \mathbf{x}_i \in \mathbb{R}^m, y_i \in \mathbb{R}$。 一个包含$K$颗树的提升树模型，则其预测结果为所有树预测结果之和, 表示为：
\[\hat{y_i} = \phi(\mathbf{x}_i) = \sum_{k=1}^K f_k(\mathbf{x}_i ), f_k \in \mathbb{F} \tag{1}\]其中，\(\mathbb{F}: \{f(\mathbf{\mathbf{x}})= w_{q(\mathbf{x})}\} (q:\mathbb{R}^m \to T, w \in \mathbb{R}^T )\) 代表所有可能的树结构集合。$q(\mathbf{x})$代表样本$\mathbf{x}$所在的叶节点的位置，$T$代表叶节点个数，$w$代表每个节点的值。
已知模型的预测值$\hat{y}_i$，则损失函数可表示为：
\[\mathbf{L}(\phi) = \sum^n_{i=1}L(y_i,\hat{y}_i) \tag{2}\]相比传统的提升树模型，作者在损失函数中加入正则项$\sum_{k=1}^K\Omega(f_k)$用以惩罚模型复杂度过高,来避免过度拟合。新的损失函数为：
\[\mathbf{L}(\phi) = {\sum^n_{i=1} L(y_i,\hat{y_i})} + {\sum_{k=1}^K \Omega (f_k)} \tag{3}\]其中，$\Omega(f_k) = \gamma T+\frac{1}{2}\lambda \lVert w \rVert^2$
Gradient Boosting
由于公式（3）的目标函数包含函数模型为参数，无法使用传统的最优化方法求解最优值。换一个角度来思考这个问题，假设已经训练了 $t-1$ 棵树，现在需要训练第 $t$ 棵树。第 $t$ 棵树的模型的预测值可表示为：
\[\hat{y}_i^{(t)} = \hat{y}_i^{（t-1）} +f_t(\mathbf{x}_i) \tag{4}\]与此同时，加入第 $t$ 棵树后的损失函数可表示为：
\[\mathbf{L}^{(t)} =\sum^n_{i=1}L(y_i, \hat{y}_i^{(t-1)} +f_t(\mathbf{x}_i))+\Omega(f_t) \tag{5}\]现在用二阶泰勒展来近似目标函数：
\[\begin{align} \mathbf{L}^{(t)}&\simeq\sum^n_{i=1}[L(y_i, \hat{y}_i^{(t-1)}） + \frac{\partial L(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}*f_t(\mathbf{x}_i)+ \frac{1}{2}\frac{\partial^2 L(y_i, \hat{y}_i^{(t-1)})}{\partial^2 \hat{y}_i^{(t-1)}}*f^2_t(\mathbf{x}_i)]+\Omega(f_t) \\\\ &=\sum^n_{i=1}[L(y_i, \hat{y}_i^{(t-1)}) + g_i *f_t(\mathbf{x}_i)+ \frac{1}{2}h_i*f^2_t(\mathbf{x}_i)]+\Omega(f_t) \end{align}\]由于 $L(y_i, \hat{y}_i^{(t-1)})$ 为常数，目标函数可进一步转化为：
\[\tilde{\mathbf{L}}^{(t)} =\sum^n_{i=1}[g_i *f_t(\mathbf{x}_i)+\frac{1}{2} h_i*f^2_t(\mathbf{x}_i)]+\Omega(f_t) \tag{6}\]现在把 $f_t(\mathbf{x}_i)$ 和 $\Omega(f_t)$ 带入到公式（6）中
\[\begin{align} \tilde{\mathbf{L}}^{(t)} &=\sum^n_{i=1}[g_i *w_{q(\mathbf{x}_i)}+ \frac{1}{2} h_i*w^2_{q(\mathbf{x}_i)}]+\gamma T+\frac{1}{2}\lambda \lVert w \rVert^2 \tag{7} \end{align}\]定义 \(I_j = \{i \lvert q(\mathbf{x}_i) = j \}\) 为在叶节点 $j$ 上的所有样本, $w_j$ 为叶节点 $j$ 的值。由于在同一叶节点的样本值 $w_{q(\mathbf{x}_i)}$ 相同，现对每个叶节点进行计算，然后对所有叶节点进行加总。具体表示为如下：
\[\sum^n_{i=1}g_i *w_{q(\mathbf{x}_i)} = \sum^T_{j=1}(\sum_{i\in I_j}g_i)*w_j\] \[\sum^n_{i=1}h_i*w^2_{q(\mathbf{x}_i)} = \sum^T_{j=1}(\sum_{i\in I_j}h_i)*w^2_j\]带入公式（7）得到
\[\begin{align} \tilde{\mathbf{L}}^{(t)} &= \sum^T_{j=1}[(\sum_{i\in I_j}g_i)*w_j+\frac{1}{2}（\sum_{i\in I_j}h_i)*w^2_j]+\gamma T+\frac{1}{2}\lambda \sum^T_{j=1} w^2_j \\\\ &= \sum^T_{j=1}[(\sum_{i\in I_j}g_i)*w_j+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)*w^2_j]+\gamma T \tag{8} \end{align}\]对于给定的树结构 $q(\mathbf{x})$ ，我们可以通过最小化公式（7）找到叶子节点$j$的最优值 $w^{*}_j$ 为
\[w^{*}_j= \frac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j}h_i+\lambda}\tag{9}\]以及此时对应的目标函数的最小值：
\[\tilde{\mathbf{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 \tag{10}\]到目前为止，对于给定的树结构 $q$，都可以计算该树结构的目标函数的最小值 $\tilde{\mathbf{L}}^{(t)}(q)$ 。如果可以把所有可能的树结构罗列出来，便可找出 $\tilde{\mathbf{L}}^{(t)}(q)$ 最小对应的树结构，将其作为第 $t$ 棵树加入。
实际情况下，由于所有可能的树结构的数量随特征个数的增加而呈现指数级增长，算法复杂度太高，所以这里采用贪心算法：从单个叶子节点开始，迭代式加入新的特征。选择新的特征作为分裂点，使得分裂后的新的树结构相比加入特征之前的树结构，损失函数减少更多。损失函数的减少可表示为：
\[\tilde{\mathbf{L}}^{(t)}(q_{old}) - \tilde{\mathbf{L}}^{(t)}(q_{new})= \frac{1}{2} \big[ \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_j}g_i)^2}{\sum_{i\in I_j}h_i+\lambda} \big] - \gamma \tag{11}\]其他优化
为避免过拟合，除去前面的的正则项之外，还加入了shrinkage和列采样。
采用上述贪心算法去寻找分裂点时，对于每个当前节点去遍历所有特征，对每个特征遍历所有可能分裂点。当样本数量太大时或者特征为连续值时，计算量会得非常大。 为了提算法效率，文章提出了近似算法。近似算法的核心在于通过分位数采样得到分隔点的候选集合。