XGBoost Boosted Trees的介绍
Boosted Trees的介绍
XGBoost是”Extreme Gradient Boosting”的简写,术语”Gradient Boosting”在Friedman的论文” Greedy Function Approximation: A Gradient Boosting Machine”中被提出。XGBoost是基于这个原始模型的。这是篇gradient boosted trees的指导文档,并且大部分内容是基于这些xgboost的作者做的幻灯片的。
GBM(梯度上升树)已经出现了相当一段时间了,有很多关于这个话题的材料。这篇教程尝试用一种独立的方式(使用监督学习的元素)去解释boosted trees。我们认为这个解释是更简洁、正式的并且促进了xgboost相对于GBM的改进。
监督学习的元素
XGBoost是用来解决监督学习的问题的,我们使用训练数据(有多个特征)
模型和参数
监督学习的模型经常引用数学公式来表示怎么通过给定的
这些参数是待定的,我们需要从数据中学习得到。在线性回归问题中,这些参数是系数
目标函数:训练损失+正则化
基于不同对
一个非常重要事实是目标函数通常必须包含两部分:训练损失函数和正则化项。
L代表训练损失函数,
另外一种常用的损失函数是交叉熵,常用在逻辑回归中
正则化项是容易被忘记添加的。正则化项控制模型的复杂度,避免过拟合。这听起来有点抽闲,让我们考虑如下问题如图所示。你在你和一个函数如下所示,后面三种解决方案你认为那种能拟合得最好。
正确答案是标红的那个。想想这个是否看起来是个合理的拟合。通常原则是既要简单又要有较好的预测能力。权衡两者就是在机器学习中权衡偏差和方差的问题。
为什么介绍通常的准则
上面介绍的是监督学习的基本知识,他们自然是机器学习的一部分。举个例子,你应该能描述boosted trees和random forests之间的不同和相同。用形式化来理解这个过程能帮助我们理解目标,我们要学习方法的原因,比如剪枝和平滑。
集成树
现在我们已经介绍完了监督学习的基本知识,让我们开始学习树。首先,让我们学习xgboost的模型:tree ensembles。树的集成模型是分类树和回归树的集合。这里有个简单的CART决策树的例子,来区分某人是否喜欢电脑游戏。
我们讲家庭成员区分到不同的叶子中,并且根据相应的叶子给他们打分。一个CART树和决策树有一点区别,CART树叶子只包含决策的值。在一个CART树中,一个真实的分数是和每个叶子关联的,这为后面分类给了一个更好的解释。这也使得统一的优化步骤更加容易,我们将在本教程的后面部分中看到。
通常,单个树是不足以在实践中用到的。在集成树中用到的是对多棵树预测值求和。
这是一个两棵树集成一个集成树的例子。每个单独的树的分数被加在一起作为最后的评分。从图中可得到的一个重要事实,两棵树尝试去互相补全。我们可以写下如下数学公式
现在我们回到这个问题,什么是随机森林?随机森林正是树的集成。所以随机森林和boosted trees在模型类型上没有区别,区别在于我们怎么训练它。这意味着如果你写一个预测集成树来预测,你只需要写他们中的一个,就能正确的运行。
Tree Boosting
在介绍完模型后,我们开始真正的训练部分。我们怎么学习这个树呢?答案是和所有的监督学习一样,定义一个目标函数然后优化它。
假设我们有以下的目标函数(记着它总是需要包含训练损失和正则化项)
Additive Training
第一件事我们想问的是树的参数。你可以发现我们需要学习的是
依旧要问,每次我们要哪棵树?一个自然的事是添加优化到我们的目标函数。
如果我们使用MSE(均方误差)作为损失函数,可以写出如下形式。
MSE的形式很好,一个差和一个平方。别的损失函数(比如交叉熵)不容易获得如此简单的形式。所以通常,我们使用二阶泰勒展开
当中
我们移除常数项后,第t步的目标函数变为
这变成了我们对新的树的优化目标。这个定义有个很大的有点是它仅仅基于
模型的复杂性
我们已经介绍了训练的步骤,但是别忘了正则化。我们需要定义树的复杂性
这里
当然有很多定义复杂度的函数,但是这个函数在实践中表现得很好。正则化是很多树包中很少认真对待或者直接忽略的。这是因为传统的树模型学习仅仅强调提高纯度,复杂度控制留给了启发式。通过形式化地定义正则化项,我们可以得到更好的方法,并且它在实践中表现的很好。
评分结构
这是求导最神奇的部分。再重新定义树模型后,我们可以写出下列的第t棵树的目标值:
这里
在这个等式中
最后这个等式衡量这个树结构
看一张图片来了解怎么计算的。首先对于一个给定的树结构,我们计算
学习树结构
现在我们已经有了衡量树的好坏的方法,理想的我们可以迭代所有可能的树然后选择最好的一个。实际上这个是棘手的,所以我们尝试一次优化一个等级的树。特别地我们尝试分开一个叶子为两个叶子,它的得分为
这个公式可以分解为
* 新的左叶子的得分
* 新的右叶子的得分
* 原始节点的得分
* 对新加的叶子的正则化
如果gain比
对于一个真实的数据,我们通常想找到最好的划分。为了高效的做这个,我们把所有数据排序,如下
左向右扫描就足以计算出所有可能的分裂解的结构分数,我们可以找到最有效的分割方法。