XGBoost原理

定义：$x_i \in \Bbb R^d$ 来表示第 $i$ 个训练样本

模型：如何根据给定的 $x_i$ 做出预测 $\hat y_i$，通常有线性模型：$\hat y_i = \sum_j w_j x_{ij} $，常见的有线性回归模型和 $logistic$ 回归，这里的预测 $\hat y_i$ 可以有不同的解释，我们可以用它来作为回归目标的输出，或者进行 $sigmoid$ 变换得到概率，或者作为 排序 的指标等

参数：指我们需要学习的东西，在线性模型中，参数指我们的系数 $w$

目标函数

$\bf{L}$ 表示的是 误差函数 ，即模型对数据的拟合程度，$\bf{\Omega}$ 表示的是 正则项 ，即对模型复杂程度的惩罚。这样目标函数的设计来自于统计学习里面的一个重要概念叫做 $Bias-Variance Tradeoff$，即偏差和方差的权衡。一个比较感性的理解是说，$Bias$ 假设我们有无限多数据，可以训练出最好的模型所得到的误差。而 $Variance$ 有限数据的随机性带来的误差。

直观上讲，目标中误差函数鼓励我们的模型尽量去拟合训练数据，这样相对来说最后的模型会有比较少的 $Bias$。而正则化项则鼓励更加简单的模型，因为当模型简单之后，有限数据拟合出来结果的随机性比较小，不容易过拟合，使得最后模型的预测更加稳定。

回归树

分类和回归树CART

典型的回归树就是 $CART$，回归树其实是决策树的一个扩展，下面就是 $CART$ 的一个例子

$CART$ 会把输入根据输入的属性分配到各个叶子节点，而每个叶子节点上面都会对应一个实数分数。上面的例子是预测一个人是否会喜欢电脑游戏，我们可以把叶子的分数理解为有多可能这个人喜欢电脑游戏。

组合树

一个 $CART$ 往往过于简单无法有效地预测，因此出现了一个更加强力的模型 $Tree\;Ensemble$，即组合树，组合树和集成学习是工业界经常使用的一种方法，例如随机森林等算法就是利用的组合树的思想。

在上面的例子中，我们用两棵树来进行预测，我们对于每个样本的预测结果就是每棵树预测分数的和。

模型和参数

组合树的学习是一种加性模型，假设我们有 $K$ 颗树：

$$ \hat y_i = \sum_{k=1}^Kf_k(x_i)\quad f_k \in \mathcal{F}$$

其中每个 $f$ 是函数空间 $\mathcal{F}$ 内的函数，$\mathcal{F}$ 是一个包含所有回归树的集合，其中每个回归树都可以直观地理解为将属性映射为分数的函数。

参数方面，每颗回归树都有其树的结构和叶子的值，最后的输出值在逻辑上与结构和叶子值有关，在数学上只取决于叶子上值的大小，组合树学习的参数不是对特征空间内直接进行学习，而是通过学习每棵树内的参数来实现整体的预测。

下面是只含有一个属性的回归树的学习过程：

我们要学习的内容包括切分位置和切分后每个片段的值，参数的学习同样需要考虑误差函数和正则项的影响。

遵循前面的设计理念，我们写出回归树的目标函数：

$$ Obj(\Theta) = \sum_i^n l(y_i,\hat y_i) +\sum_{k=1}^K\Omega(f_k) $$

对正则项的定义可以包括树的深度、节点个数、叶子值的各种范数等等，树形结构的学习很多都依赖于一些如下所示的启发式定义和映射：

梯度提升树

提升模型学习

梯度提升的学习方法使用的不是传统的梯度下降或者梯度上升，而是利用加性模型的思想，使用 $Additive Training$ 的方法（也叫 $Boosting$），每一次保留原来的模型不变，加入一个新的函数 $f$ 到我们的模型中：

那么现在的问题是我们如何选择每一轮加入的 $f$ 呢？很显然，我们应该选取能够使得我们的目标函数最大程度上降低的 $f$

如上图所示，目标函数按照加性模型展开后，前 $t-1$ 个正则项的累加 $\sum_{i=1}^{t-1} \Omega(f_i)$ 对本轮学习可以视为常数。同样，如果使用平方误差，下面的式子展开后不含有 $f_t(x_i)$ 的项在本轮学习中都可以视为常数，化简之后，得到的 $(\hat y_i^{t-1} - y_i)$ 就是 $t-1$ 轮迭代后的 残差 。

更加一般地，我们直接可以直接使用二阶泰勒展开式得到一个目标函数的近似值：

同样，$l(y_i, \hat y_i^{t-1})$ 对本轮迭代也是常数项，当我们把所有的常数项移除之后，我们得到了新的目标函数：

这一个目标函数有一个非常明显的特点，它 只依赖于每个数据点的在误差函数上的一阶导数和二阶导数 。

定义正则项

在定义树的复杂度方面，我们把树拆分成结构部分 $q$ 和叶子权重部分 $w$。

当我们给定了如上定义之后，我们可以定义一棵树的复杂度。这个复杂度包含了一棵树里面节点的个数，以及每个树叶子节点上面输出分数的 $L2$ 模平方。当然这不是唯一的一种定义方式，不过这一定义方式学习出的树效果一般都比较不错。

改写目标函数

定义了一个新的变量 $I_j$ 来表示落在叶子节点 $j$ 上的样本集合，从第二行到第三行实际上就是进行了一个集合上的变换，因为 $\sum_{i=1}^n = \sum_{j=1}^T\sum_{i \in I_j}$，即每个数据点落入且仅落入一个叶子节点，所以可以把 $n$ 个数据点按叶子成组，类似于合并同类项，两个数据点同类指的是落入相同的叶子，即这里的指示变量集 $I_j$。

我们定义 $ G_j = \sum_{i \in I_j} g_i \quad H_j = \sum_{i \in I_j} h_i$，那么这个目标函数可以进一步改写成如下的形式，

假设我们已经知道树的结构 $q$，我们可以通过这个目标函数来求解出最好的 $w$，以及最好的 $w$ 对应的目标函数最大的增益

打分函数示例

寻找划分点

贪心法

我们不断地枚举不同树的结构，利用这个打分函数来寻找出一个最优结构的树，加入到我们的模型中，再重复这样的操作。不过枚举所有树结构这个操作不太可行，所以常用的方法是 贪心法 ，每一次尝试去对已有的叶子加入一个分割。

上式中几个部分的意义分别是：左子树分数与右子树分数的和减去不分割情况下的分数以及加入新叶子节点引入的复杂度代价。

对于每次扩展，我们还是要枚举所有可能的分割方案，如何高效地枚举所有的分割呢？假设我们要枚举所有 $x\lt a$ 这样的条件，对于某个特定的分割 $a$ 我们要计算 $a$ 左边和右边的导数和。

我们可以发现对于所有的 $a$，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和 $G_L$ 和 $G_R$。然后用上面的公式计算每个分割方案的分数就可以了。

于是我们就得到了梯度提升树的算法：

时间复杂度：$O(ndK\log n)$，排序的时间复杂度是 $O(n\log n)$，其中 $d$ 是特征数，$K$ 是树的深度。

近似算法

在数据量非常大甚至不能直接读入内存的时候，上面方法就不能够处理，所以就出现了一种近似算法，对每一个特征进行“值”采样，原来需要对每一个特征的每一个可能分割点进行尝试，首先对特征值的分布采样确定候选划分点，然后只对候选划分点进行计算，这种方法很明显可以减少计算量，采样密度越小计算的越快，拟合程度也会越差，所以采样还可以防止过拟合。执行采样的方式有两个，一种是 $global$ 模式，一种是 $local$ 模式。$global$ 模式是在生成树之前采一次样，后面不再更新；$local$ 模式是每次 $split$ 之后都再次进行一次采样。

缺失值处理

有很多种原因可能导致特征的稀疏（缺失），所以当遇到样本某个维度的特征缺失的时候，就不能知道这个样本会落在左孩子还是右孩子。简单的做法就是扔掉或者根据缺失原因设计具体的处理策略，本文的处理策略是落在哪个孩子得分高，就放到哪里（把默认值设置到哪里）。

并行计算

注意到每一次寻找划分点的时候是需要对当前节点中的样本按照特征值进行排序的，其实这个排序可以在初始化的时候进行一次就够了，比如有 $n$ 个样本 $m$ 维特征，只需要预先生成一个 $n\times m$ 的矩阵，第$m$ 列表示的是按照第 $m$ 个特征从小到大对样本的排序索引。通过指针存储，一个指针也就是四个字节，耗费的空间有限，这个排序索引的过程可以并行进行，并且寻找划分点的时候，也可以同时多个维度并发地去寻找得分最高的切分点。

[1] XGBoost: A Scalable Tree Boosting System - Paper in KDD2016

[2] Introduction to Boosted Trees - Slides of Tianqi Chen

[3] XGBoost与Boosted Tree - 我爱计算机