机器学习｜XGBoost

接下来几周的时间，我们将会推出关于《西瓜书》读书笔记的连载文章，updating~

频频在各大比赛中大放异彩的算法XGBoost究竟是怎么回事？

（看懂了就动动小手点个赞吧）

01

XGBoost的定义

和GBDT一样，XGBoost也是一种基于CART树的Boosting算法，让我们来看一下如何通俗的去理解XGBoost。

先简单的回想一下，在我们之前提到过的GBDT中是怎样用很多棵树去做预测的？很简单，我们给了每棵树不同的训练数据，得到多种不同的结果，最终我们把这些结果相加作为最终的预测值就可以了。

举一个简单的例子，我们要预测一家人对电子游戏的喜好程度，考虑到年轻和年老相比，年轻更可能喜欢电子游戏，以及男性和女性相比，男性更喜欢电子游戏，故先根据年龄大小区分小孩和大人，然后再通过性别区分开是男是女，最终给每个人在电子游戏上的喜爱程度进行打分，如下图所示：

我们把上图中得到的树记为tree1，同样我们可以根据日常是否使用电脑来进行新一次的打分，如下图所示：

这样我们就训练好的两棵树tree1和tree2，我们把两棵树的评分结果相加就是最终的结果，如上图中，男孩的得分是2+0.9=2.9，爷爷的得分是-1-0.9=-1.9。

看完了这个例子，你可能会疑惑，这个过程和GBDT不是一样的吗？其实在本质上XGBoost和GBDT的差异就在于目标函数的定义上，别急，继续往下看。

02

XGBoost的目标函数

看懂了上节中的例子，不难说出XGBoost的核心就是不断的添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。用数学来表示这个模型，如下所示：

03

XGBoost的训练

04

XGBoost的正则项

这里我们所说的正则项，也可以看作是树的复杂度。

我们先对CART做一个新的定义，式子及结构表示如下：

对于图中的式子的解释：一棵树有T个叶子结点，这T个叶子节点的值组成了一个T维向量w，q(x)是一个映射，用来将样本映射成1到T的某个值，也就是把它分到某个叶子节点，q(x)其实就代表了CART树的结构。 自然就是这棵树对样本x的预测值了（得分）。

根据上面的定义，我们可以设定XGBoost的正则项包含两个部分：

1. 一个是树里面叶子节点的个数T
2. 一个是树上叶子节点的得分w的L2模平方（对w进行L2正则化，相当于针对每个叶结点的得分增加L2平滑，目的是为了避免过拟合）

最终表示成下图所示的形式：

05

XGBoost的最终形态

此时第一个括号中表示的内容可以看作是学习率，第二个括号中表示的内容可以看作是反向梯度。

06

XGBoost的最优树结构

有了评判树的结构好坏的标准，我们就可以先求最佳的树结构，这个定出来后，最佳的叶子结点的值实际上在上面已经求出来了。

对于我们最开始的是否喜欢电子游戏的例子，最简单的树结构就是一个结点的树，我们可以计算出这棵单结点树的好坏 假设我们现在想按照年龄将这棵单节点树进行分叉，我们需要知道：

1、按照年龄分是否有效，也就是是否减少了obj的值；

2、如果可分，那么以哪个年龄值来分。

我们按照年龄进行排序，找出所有的切分点，对于每一个切分点我们去衡量切分的好坏。示例图和计算方式如下表示：

07

问题小结

至此，我们的XGBoost的原理就全都说通了，下面再来看几个通常会遇到的问题：

1. obj中的constant是怎么来的？

文中我们还留了一个问题没有解决，那就是constant具体是怎么来的，让我们来看一下复杂度（正则项）的迭代过程：

这样就很清晰的可以看出所谓的常数，其实就是我们前t-1棵树的复杂度加和。

1. XGBoost为什么用泰勒展开？

XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了xgboost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。简单的说：使用二阶泰勒展开是为了xgboost能够自定义loss function。

1. XGBoost如何寻找最优特征？是有放回还是无放回的呢？

XGBoost在训练的过程中给出各个特征的评分，从而表明每个特征对模型训练的重要性。

XGBoost利用梯度优化模型算法, 样本是不放回的，想象一个样本连续重复抽出,梯度来回踏步，这显然不利于收敛。

XGBoost支持子采样, 也就是每轮计算可以不使用全部样本。