机器学习

本文是笔者在学习XGBoost时，对XGBoost的英文介绍文档进行翻译。

英文原版地址为：http://xgboost.readthedocs.io/en/latest/model.html

         XGBoost是“ExtremeGradient Boosting”的缩写，“Gradient Boosting” 这个术语来源于Friedman的论文《Greedy Function Approximation: A GradientBoosting Machine》。XGBoost基于这个原始的模型。这是一篇梯度提升树的教程，大多数内容都是基于xgboost的作者这篇PPT《Introduction toBoosted Trees》。

         GBM (boosted trees)已经存在一段时间了，而且有很多这方面主题的材料。这个教程尝试使用监督学习原理以独立和原理性性的方法解释提升树。我们认为这样的解释是更清晰、正式和灵活的使用xgboost。

         XGBoost用于监督学习问题，用训练数据（多特征）xi来预测目标变量yi。在进入XGBoost之前，先我们回顾一下监督学习的基本原理。

         监督学习里的模型通常涉及怎样通过给定的xi预测yi这个数学问题。例如，一个常用的模型是线性模型，预测由输入特征线性加权组合得到，即 。预测值根据不同任务有不同的解释。例如在回归或者分类中，它可以在logistic regression（逻辑回归）中得到正样本的概率，也可以用于作为输出的排名分数。

       参数是我们需要从数据中学习的关键内容。线性回归问题中，这个参数是系数θ。通常我们用θ来表示参数（在一个模型中有很多参数，这里只做简单的定义）。

       基于对的不同理解，我们有不同的问题，例如回归、分类和排序等。我们需要发现一种通过给定的训练数据得到最优参数的方法。我们需要定义一个所谓的目标函数来评估指定参数集的模型性能。

       目标函数的一个重点是它们必须包含两个部分：训练损失和正则化。

         其中L是训练损失函数，W是正则化项。训练损失是评估我们的模型在训练集上的预测效果。例如，一个常用的损失函数是均方差：

         另一个通常使用的损失函数是逻辑回归的逻辑损失：

         正则项是人们通常忘记添加的。正则项控制模型的复杂度，他可以帮助我们避免过拟合。这听起来有点抽象，所以让我们思考下面这个图片中的问题。要求从图中左上角给出的输入数据点拟合一个阶梯函数。你认为在这三种解决方案中哪个拟合得最好？

         正确的答案是标记为红色的图案。看看这是否符合你的想法。我们想要的通用原理是一个简单和可预测的模型。这两者之间的折衷也被称为机器学习中的偏差和方差的折衷。

         上面介绍了监督学习的基本原理，它们是机器学习工具包的组成部分。例如，你应该能够形容boosted trees和random forests之间的区别和共性。以形式化的方式理解这个过程也有助于我们理解正在学习的目标和heuristics （启发）背后的原因，例如修剪和平滑。

现在我们已经介绍了监督学习的原理，接下来让我们开始介绍真正的树。首先了解xgboost的模型：tree ensembles。tree ensembles模型是分类和回归树（CART）的集合。下面一个简单的CART例子，用于分类一个人是否喜欢电脑游戏。

我们将家庭成员分类成不同的叶，然后在相应的叶上给他们分配分数。CART和决策树有一些不同，决策树的树叶只包含判断的数值。在CART中，实际的分数与每片叶都相关，这给了我们不只是分类的更丰富的解释。

通常，在实际应用中单棵树不够强壮。实际使用的是称为树集成的模型，它是多棵树预测的和。

         这是一个集成两棵树的例子。加上每棵单独的树的预测分数得到最后的分数。观察这个例子会发现一个重要的事实是两棵树尝试相互补充。在数学上，我们可以写出这个模型的公式：

         其中K是树的数量，是函数空间F中的一个函数，F是所有可能的CARTs的集合。因此我们优化的目标可以写为：

         现在有一个问题， randomforests（随机森林）的模型是什么？这就是tree ensembles！所以随机森林和提升树在模型上并没有什么区别，不同在于我们是怎样训练它们的。这意味着如果写一个tree ensembles的预测程序，你只要实现其中一个，就可以直接用于随机森林和提升树。

         介绍这些模型后，让我们开始真正训练的部分。我们应该怎样训练一棵树？答案是跟所有的监督学习模型一样：定义一个目标函数然后优化它！

         假设我们有一个目标函数（记住它总包含训练损失和正则化）：

         首先我们需要知道的是树的参数是什么？你可以发现我们需要学习的是它们的函数，它包含树的结构和树叶的分数。这比通过梯度完成的传统优化问题要困难得多。因为很难一次训练完所有的树。取而代之的是使用加法策略：固定我们已经学习的，然后一次添加一棵新的树。记第t步的预测值为，得到：

         还有一个问题，哪棵树是在每一步都需要的？显然是添加一个优化我们的目标。

         如果我们考虑使用MSE作为我们的损失函数，可以得到下面的公式：

         这个关于MSE的公式很友好，它包括一阶项（通常称为残差）和二次项。其他损失函数（例如逻辑损失）很难得到一个这么好的公式。所以通常的情况是，对二次项使用泰勒公式展开：

         其中和被定义为：

         移除所有常数后，步骤t的具体目标变为：

         这就得到了我们所优化目标的新树。这个定义的一个重要优势是它只取决于和。这是这就是XGBoost如何支持自定义损失函数的方法。我们可以使用完全相同的方法获得和作为输入来优化每个损失函数，包括逻辑回归和带权重的逻辑回归。

         我们已经介绍了训练步骤，但是别忘了还有一件重要的事是正则化！我们需要定义树Ω(f)的复杂度。首先重定义树f(x)为：

         这里w是树叶分数的向量，q是给每个相关树叶分配数据的函数，T是树叶的数量。在XGBoost中，定义复杂度为：

         当然定义复杂度的方法不止一种，但这是在实际中表现出色的一种专用的方法。正则化在大多数树工具包中粗略处理或者简单地忽略掉。这是因为传统的树学习方法只强调改善纯度，而复杂的控制留给启发式算法。通过正式的定义，我们可以更好地学习，并且这在实际中也很有用。

         这是推导的神奇所在。在重新公式化树模型后，我们可以写出第t步树的目标值为：

         其中是分配给第j步树叶的数据集。注意到我们在第二行改变了和的索引，因为在所有同样的树叶上的分数相同。可以通过定义和来进一步化简表达式：

         在这个等式中是相互独立的，公式是二次项，以及最佳的q(x)，我们可以得到最佳的化简目标：

         最后一个等式用于评估结构q(x)的好坏程度。

         如果这些听起来有些复杂，那么来看一下这幅图，并且看看分数是如何计算的。基本上，对于一个给定的树结构，我们把统计量gi和hi放到它们所属的树叶上，然后对数据求和，最后使用公式来计算这棵树的好坏。除了需要将模型复杂度带入计算，这个分数类似于决策树中测量的纯度。

         现在我们有了评估树好坏的方法，理想情况下我们会列举所有可能的树和选择最好的一棵。实际上这是难以实现的，所以我们尝试一次优化一个树的等级。具体来说，我们尝试把一片叶子分成两片，分数增益为：

         这个公式可以被分解为（1）左边新叶的分数（2）右边新叶的分数（3）原始树叶的分数（4）增加树叶的正则化。这里我们可以看到一个重要的事实：如果增益小于γ，我们最好不要增加那个分支。这正是基于树模型中的修剪技术！通过使用这些监督学习的原理，我们可以自然而然地想到这样做的原因。

         对于实值数据，我们通常要搜索一个最优分割。为了更有效地实现这个方法，我们将所有实例按顺序排列，就像下面的图片。

         从左到右的扫描足够满足计算所有分解情况的结构分数，我们可以寻找最佳的分割。

         现在你已经明白了什么是boostedtrees，你可能会问在哪里介绍了XGBoost？XGBoost就是一个该教程介绍的原理所实现的工具。更重要的是，它是在系统优化和机器学习原理的基础上发展起来的。这个库的目标是追求机器的计算极限，提供一个可扩展的、可移植的、精确的库。进行你的尝试，更重要的是贡献你的智慧（代码，例子，教程）到论坛！

原文链接：http://xgboost.readthedocs.io/en/latest/model.html

xgboost作者的PPT：https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf