接下来几周的时间,我们将会推出关于《西瓜书》读书笔记的连载文章,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的正则项包含两个部分:
最终表示成下图所示的形式:
05
XGBoost的最终形态
此时第一个括号中表示的内容可以看作是学习率,第二个括号中表示的内容可以看作是反向梯度。
06
XGBoost的最优树结构
有了评判树的结构好坏的标准,我们就可以先求最佳的树结构,这个定出来后,最佳的叶子结点的值实际上在上面已经求出来了。
对于我们最开始的是否喜欢电子游戏的例子,最简单的树结构就是一个结点的树,我们可以计算出这棵单结点树的好坏 假设我们现在想按照年龄将这棵单节点树进行分叉,我们需要知道:
1、按照年龄分是否有效,也就是是否减少了obj的值;
2、如果可分,那么以哪个年龄值来分。
我们按照年龄进行排序,找出所有的切分点,对于每一个切分点我们去衡量切分的好坏。示例图和计算方式如下表示:
07
问题小结
至此,我们的XGBoost的原理就全都说通了,下面再来看几个通常会遇到的问题:
文中我们还留了一个问题没有解决,那就是constant具体是怎么来的,让我们来看一下复杂度(正则项)的迭代过程:
这样就很清晰的可以看出所谓的常数,其实就是我们前t-1棵树的复杂度加和。
XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了xgboost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。简单的说:使用二阶泰勒展开是为了xgboost能够自定义loss function。
XGBoost在训练的过程中给出各个特征的评分,从而表明每个特征对模型训练的重要性。
XGBoost利用梯度优化模型算法, 样本是不放回的,想象一个样本连续重复抽出,梯度来回踏步,这显然不利于收敛。
XGBoost支持子采样, 也就是每轮计算可以不使用全部样本。