[翻译] 提升树算法的介绍（Introduction to Boosted Trees）
1. 有监督学习的要素
XGBoost 适用于有监督学习问题。在此类问题中，我们使用多特征的训练数据集 \(x_i\) 去预测一个目标变量 \(y_i\) 。在专门学习树模型前，我们先回顾一下有监督学习的基本要素。
1.1 模型和参数
有监督学习的模型通常指这样的数学结构：预测值 \(y_i\) 是由给定输入值 \(x_i\) 决定的。一个常见的例子是线性模型，其中预测值 \(\hat{y}_i=\sum_j \theta_jx_{ij}\) 是一个对输入特征值的加权线性组合。这个预测值可以有不同的解释，这取决于任务是回归还是分类。例如，在逻辑回归中，可通过预测值的逻辑变换获得样本被归为正面类别的概率；当我们需要将输出进行排序时，预测值也可作为一个排序得分值。
参数是我们需要从数据中学习得到的非确定部分。在线性回归问题中，参数就是系数 \(\theta\)。我们通常用 \(\theta\) 代表参数（事实上模型中有许多参数，这里只是粗浅的定义一下）。
1.2 目标函数：训练损失+正则项
通过谨慎地选则 \(y_i\)，我们可以表达各种各样的任务，比如回归、分类、排序。训练模型意味着要寻求最佳参数 \(\theta\) 使得能够最好地拟合训练数据 \(x_i\) 和标签 \(y_i\)。为了训练模型，我们需要定义目标函数来衡量这个模型拟合数据的效果有多好。
目标函数的一个显著特征是，它由训练损失和正则项两个部分组成：
\[obj(\theta)=L(\theta)+\Omega(\theta)\]
式中 \(L\) 是训练损失函数，\(\Omega\) 是正则项。训练损失函数衡量的是模型在该训练数据集上的预测能力。\(L\) 通常选择均方误差，公式如下：
\[L(\theta) = \sum_i (y_i - \hat y_i)^2\]
另一个常用的损失函数是逻辑损失（logistic loss），被用于逻辑回归问题：
\[L(\theta)=\sum_i[y_i\ln(1+e^{-\hat y_i})+(1-y_i)ln(1+e^{\hat y_i})]\]
人们通常会忘记加正则项。实际上，正则项能够控制模型的复杂度，这有助于避免过拟合问题。这听起来有点抽象。让我们考虑下图中的这个问题：对于左上角图片中给出的输入数据，要求直观地给出一个阶梯函数的拟合结果，三个图中哪个方案的拟合效果最好？
正确答案已用红色标出了。你是否能够直观地感觉出这是一个合理的拟合结果？一般性的原则就是，我们希望得到一个既简单又具备预测能力的模型。在机器学习领域，这两者之间的折衷也被称为偏差-方差权衡（bias-variance tradeoff）。
1.3 为什么介绍一般原则
上面介绍的内容是有监督学习的基本要素，它们自然而然地成为了机器学习工具包的基本组成部分。例如，你应该能够描述梯度提升树和随机森林的相同点和不同点。以形式化方法理解这一过程，有助于我们理解正在学习的对象以及启发式算法背后的原因，例如剪枝和平滑。
2 决策树集成
介绍完有监督学习的要素，现在开始进入真正的树模型。首先，了解一下XGBoost所选择的模型是：决策树集成（decision tree ensemble）。树集成模型包含了一组分类和回归树（CART）。下图展示了一个CART用于对“某人是否会喜欢电脑游戏”分类的简单例子。
我们将一个家庭的成员划分入不同的叶子节点，并且给他们分配所在叶子节点相对应的分数。与叶子节点仅包含了决策值的决策树不同，在CART中，一个实数分值是与每个叶节点相关联的，这点比起分类器能让我们对结果有更深的理解。正如我们将在接下来的章节会看到的那样，这也使得能够从原理上、以更统一的方式去做优化。
通常而言，单棵树的能力是不够直接被应用在实践中的，实践中运用的是集成模型，即将多棵树的预测值求和。
这是一个由两棵树构成的树集成示例，最终得分由单棵树的预测分值求和得到。一个关键点是，这两个树所做的是试图互相补充。形式上我们可以用以下公式来表示模型：
\[\hat y_i=\sum_{k=1}^Kf_k(x_i),\ f_k\in F\]
式中\(K\)是树的总数，\(f\)是属于函数空间\(F\)的函数，\(F\)是所有可能的CART的集合。待优化的目标函数如下：
\[obj(\theta)=\sum_i^nl(y_i,\hat y_i)+\sum_{k=1}^K\Omega(f_k)\]
现在有个巧妙的问题：随机森林使用的是什么模型？是树集成！所以随机森林和提升树其实是同样的模型，不同之处在于我们如何训练它们。这就意味着，如果你想用树集成来写一个预测服务，只需要写一个就好了，它既能用随机森林又能用梯度提升树（参见Treelite的实例），一个说明为什么有监督学习的元素会抖动的例子。
3 树提升
已经介绍完了模型，接下来我们把目光聚焦在训练上：我们要如何学习出这些树呢？答案是，正如所有有监督学习模型一直做的事：定义一个目标函数然后做优化。
现在假设下面这个函数是我们的目标函数（记得它始终需要含有训练损失和正则项）：
\[obj=\sum_{i=1}^nl(y_i,\hat y_i^{(t)})+\sum_{k=1}^t\Omega(f_i)\]
3.1 累加训练
我们会想询问的第一个问题是：树的参数有哪些？你会发现我们需要学习得到的就是那些函数\(f_i\)，每个都包含了树结构及叶节点分数。学习树结构比传统的最优化问题难多了，在传统最优化问题中只需要简单地取梯度就好。一次性地学习出所有的树是很难解决的。作为替代，我们使用累加策略：保持已经得到的训练结果不变，仅仅在每次训练时增加一棵新的树。设第\(t\)步中得到的预测值是\(\hat y_i^{(t)}\)。那么我们有：
\[
\begin{split}
\hat y_i^{(0)}&=0\\
\hat y_i^{(1)}&=f_1(x_i)=\hat y_i^{(0)}+f_1(x_i)\\
\hat y_i^{(2)}&=f_1(x_i)+f_2(x_i)=\hat y_i^{(1)}+f_2(x_i)\\
&...\\
\hat y_i^{(t)}&=\sum_{k=1}^tf_k(x_i)=\hat y_i^{(t-1)}+f_t(x_i)
\end{split}
\]
还有一个问题：在每步中加入的树要怎么选？一个很自然的想法就是加入那棵能够最优化我们的目标函数的树。
\[
\begin{split}
obj^{(t)}&=\sum_{i=1}^nl(y_i,\hat y_i^{(t)})+\sum_{k=1}^t\Omega(f_i)\\
&=\sum_{i=1}^nl(y_i,\hat y_i^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant
\end{split}
\]
如果考虑使用均方差（MSE）作为损失函数，那么目标就变为：
\[
\begin{split}
obj^{(t)}&=\sum_{i=1}^n(y_i-(\hat y_i^{(t-1)}+f_t(x_i)))^2+\sum_{i=1}^t\Omega(f_i)\\
&=\sum_{i=1}^n[2(\hat y_i^{(t-1)}-y_i)f_t(x_i)+f_t(x_i)^2]+\Omega(f_t)+constant
\end{split}
\]
MSE的公式非常友好，有一个一次性（通常称为残差）和一个二次项。如果使用其他损失函数（比如逻辑损失），就很难得到这么漂亮的公式了。因此在这个一般情况下，我们对损失函数进行二次泰勒展开：
\[obj^{(t)}=\sum_{i=1}^n[l(y_i,\hat y_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)+constant\]
式中\(g_i\)和\(h_i\)的定义是：
\[
g_i=\partial_{\hat y_i^{(t-1)}} l(y_i,\hat y_i^{(t-1)})\\
h_i=\partial_{\hat y_i^{(t-1)}}^2 l(y_i,\hat y_i^{(t-1)})
\]
移除所有常数项后，在第\(t\)步中的特定目标即为：
\[\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\]
这就是我们构造新树的最优化目标。这一定义带来的一个重要优势是，目标函数值仅取决于\(g_i\)和\(h_i\)，这就是XGBoost能够支持自定义目标函数的原因。我们能够优化所有损失函数，包括逻辑回归和pairwise排序，对于不同的输入值\(g_i\)和\(h_i\)使用的是完全一致的解决方案。
3.2 模型复杂度
介绍完了训练步骤，但是稍等，还有一件很重要的事情，那就是正则项！我们需要为树定义复杂度\(\Omega(f)\)。为了做这件事，让我们改进一下对于树\(f(x)\)的定义：
\[f_t(x)=\omega_{q(x)},\ \omega \in R^T,\ q:R^d
\rightarrow \{1,2,...,T\}\]
这里 \(\omega\) 是叶节点分值向量，\(q\)是将每个数据点分配到相对应的叶节点中去的函数，\(T\)是叶子数量。在XGBoost中，我们定义复杂度如下：
\[\Omega (f)=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^T\omega_j^2\]
当然，还有其他多种方式来定义复杂度，但是上式的定义在实践中效果最好。正则项是被大多数树算法的包粗略对待甚至直接忽视的一部分内容。这是因为传统对于树的学习只重视改善不纯度，而对复杂度的控制就留给了启发式算法。通过形式化地定义正则项，我们能够对正在学习的东西有更好的认识，并得到一个更加泛化的模型。
3.3 结构分数
导数中有一个神奇的部分。在重构树模型后，我们可以将第\(t\)棵树的目标值写作：
\[
\begin{split}
obj^{(t)}&\approx \sum_{i=1}^n[g_i\omega_{q(x_i)}+\frac{1}{2}h_i\omega_{q(x_i)}^2]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^T\omega_j^2\\
&=\sum_{j=1}^T[(\sum_{i \in I_j}g_i)\omega_j+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)\omega_j^2]+\gamma T
\end{split}
\]
式中 \(I_j=\{i \mid q(x_i)=j\}\) 是被分配到第\(j\)个叶子的数据点的下标集合。注意到在第二行中，我们变换了求和函数的下标，因为位于同个叶子中的所有数据点得到的分值是相同的。更近一步化简表达式，定义\(G_j=\sum_{i \in I_j}g_i\)，\(H_j=\sum_{i \in I_j}h_i\)，得到：
\[obj^{(t)}=\sum_{j=1}^T[G_j\omega_j+\frac{1}{2}(H_j+\lambda)\omega_j^2]+\gamma T\]
在这一等式中，\(w_j\)是互相独立的，式子\(G_j\omega_j+\frac{1}{2}(H_j+\lambda)\omega_j^2\)是一个二次项。对于给定的结构\(q(x)\)，使目标函数的最小化的\(\omega_j\)的取值、及最小化的目标函数为：
\[
\begin{split}
\omega_j^*&=-\frac{G_j}{H_j+\lambda}\\
obj^*&=-\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T
\end{split}
\]
后一个等式衡量了树结构\(q(x)\)有多好。
如果所有这些听起来有点复杂，让我们看看在这张图片中，分数是怎样计算得出的。总的来说，对于一个给定的树结构，我们将定值\(g_i\)和\(h_i\)放到它们对应的叶节点中，将这些值求和，然后运用公式计算出这棵树有多好。这个得分很像决策树中的不纯度，只是它将模型复杂度也考虑进去了。
3.4 学习树结构
既然我们已有了衡量一棵树有多好的方法，理论上我们可以枚举所有可能的树然后挑出最好的，但在实际中这是很难做到的，所以我们将尝试每次优化树的一层。
特别地，若我们试图将一个叶节点划分为两个叶节点，此时分数增益为：
\[Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]-\gamma\]
这个公式可被拆分为 1)左子树得分 2）右子树得分 3) 原叶节点得分 4）对新增添的叶子的正则化项。显而易见的是，如果增益值比\(\gamma\)值小，我们就最好不要添加这个分支。这也正是所有基于树的模型的剪枝技术。通过运用有监督学习的原则，我们自然能想到这些技术能够起效果的原因 : )
对于实数值的数据，我们通常想要找到最优的切分点。为了高效地做这件事，我们先将所有样本排序好，像下图所示：
只要从左到右扫描，就足够用于计算所有可能的切分方案的结构分数，然后我们就能高效地找到最佳切分点。
关于公式推导中常数项的解释：在第t步时，前t-1步的运算结果都可视作已知（常数）。
原文：Introduction to Boosted Trees
相关概念阅读参考：
Understanding the Bias-Variance Tradeoff
分类与回归树（Classification and Regression Trees, CART）
L1, L2 Regularization – Why needed/What it does/How it helps?
感谢南大薛恺丰同学帮忙校对~