xgboost 算法总结

xgboost有一篇博客写的很清楚,但是现在网址已经失效了,之前转载过,可以搜索XGBoost 与 Boosted Tree。

现在参考这篇文章,并自己对其进行总结。

[En]

Now refer to this article and make a summary of it by yourself.

xgboost是GBDT的后继算法,也是采用boost算法的cart 树集合。

一、基学习器:分类和回归树(CART)

cart树既可以 进行分类,也可以进行回归,但是两种情况下,采用的切分变量选择方式不同。

CART在进行回归的时候,选择最优切分变量和切分点采用的是如下的标准

xgboost 算法总结

其中,c1 和c2满足下式,即为该段变量取值的均值

CART采用暴力的遍历方式来确定最优切分变量和切分点,具体算法如下:

xgboost 算法总结

CART分类树的算法类似,由于分类无法计算均值,CART分类树采用的是计算基尼指数,通过遍历所有特征和他们的可能切分点,选择基尼指数最小的特征及切分点作为最优特征和最优切分点,并重复调用,直到生成CART分类树。

二、 Tree Ensemble

如果单棵树的过于简单无法有效地预测,因此一个更加强力的模型叫做tree ensemble,也就是分类树的集成算法。如果采用boost集成,也就是加法集成,可以写成如下

xgboost 算法总结

xgboost 算法总结

目标函数如下:

[En]

The objective function is as follows:

xgboost 算法总结

第一部分是误差函数,第二部分是正则化项。

[En]

The first part is the error function and the second part is the regularization term.

三、 模型学习 additive training

因为现在我们的参数可以认为是在一个函数空间里面,我们不能采用传统的如SGD之类的算法来学习我们的模型,因此我们会采用一种叫做additive training的方式。。每一次保留原来的模型不变,加入一个新的函数f f到我们的模型中。

现在还剩下一个问题,我们如何选择每一轮加入什么f呢?答案是非常直接的,选取一个f来使得我们的目标函数尽量最大地降低

xgboost 算法总结

这个公式可能有些过于抽象,我们可以考虑当ll是平方误差的情况。这个时候我们的目标可以被写成下面这样的二次函数

xgboost 算法总结

更一般地,在非平方误差的情况下,我们将使用下面的泰勒展开近似来定义一个近似目标函数,这便于我们在这一步中计算。

[En]

More generally, in the case of non-square error, we will use the following Taylor expansion approximation to define an approximate objective function, which is convenient for us to calculate in this step.

xgboost 算法总结

当我们去掉常量项时,我们会发现一个更统一的目标函数,如下所示。该目标函数具有一个非常明显的特征,即它只依赖于每个数据点的误差函数的一阶和二阶导数。

[En]

When we remove the constant term, we will find a more unified objective function as follows. This objective function has a very obvious characteristic that it only depends on the first and second derivatives of the error function of each data point.

xgboost 算法总结

四、 树的复杂度

到目前为止我们讨论了目标函数中训练误差的部分。接下来我们讨论如何定义树的复杂度。我们先对于f的定义做一下细化,把树拆分成结构部分q和叶子权重部分w。下图是一个具体的例子。结构函数q把输入映射到叶子的索引号上面去,而w给定了每个索引号对应的叶子分数是什么

xgboost 算法总结

当我们给定了如上定义之后,我们可以定义一棵树的复杂度如下。这个复杂度包含了一棵树里面节点的个数,以及每个树叶子节点上面输出分数的L 2 模平方。当然这不是唯一的一种定义方式,不过这一定义方式学习出的树效果一般都比较不错。

xgboost 算法总结

五、 关键步骤

xgboost 算法总结

xgboost 算法总结

以这种方式,可以如下改变目标函数,使用步骤4中的方式来表示误差函数和复杂性,如下

[En]

In this way, the objective function can be changed as follows, using the way in step 4 to represent the error function and complexity, as follows

xgboost 算法总结

这一个目标包含了T个相互独立的单变量二次函数。我们可以定义

xgboost 算法总结

xgboost 算法总结

xgboost 算法总结

xgboost 算法总结

六、打分函数计算举例

最后是算法的简化。

[En]

The last part is the simplification of the algorithm.

第五部分中提到的Obj代表了当我们指定一个树的结构的时候,我们在目标上面最多减少多少。我们可以把它叫做结构分数(structure score)。你可以认为这个就是类似吉尼系数一样更加一般的对于树结构进行打分的函数。下面是一个具体的打分函数计算的例子

xgboost 算法总结

七、 枚举所有不同树结构的贪心法

xgboost算法不断地枚举不同树的结构,利用这个打分函数来寻找出一个最优结构的树,加入到我们的模型中,再重复这样的操作。不过枚举所有树结构这个操作不太可行,所以常用的方法是贪心法,每一次尝试去对已有的叶子加入一个分割。对于一个具体的分割方案,我们可以获得的增益可以由如下公式计算

xgboost 算法总结

对于每次扩展,我们还是要枚举所有可能的分割方案,如何高效地枚举所有的分割呢?我假设我们要枚举所有 x小于a 这样的条件,对于某个特定的分割a我们要计算a左边和右边的导数和。

xgboost 算法总结

我们可以发现对于所有的a,我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL和GR。然后用上面的公式计算每个分割方案的分数就可以了。

观察这个目标函数,大家会发现第二个值得注意的事情就是引入分割不一定会使得情况变好,因为我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝, 当引入的分割带来的增益小于一个阀值的时候,我们可以剪掉这个分割。大家可以发现,当我们正式地推导目标的时候,像计算分数和剪枝这样的策略都会自然地出现,而不再是一种因为heuristic而进行的操作了。

八、最后:

xgboost的github地址: https://github.com/dmlc/xgboost 。xgboost是大规模并行boosted tree的工具,它是目前最快最好的开源boosted tree工具包,比常见的工具包快10倍以上。

Original: https://www.cnblogs.com/bnuvincent/p/11223200.html
Author: Alexander
Title: xgboost 算法总结

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/7607/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

最近整理资源【免费获取】:   👉 程序员最新必读书单  | 👏 互联网各方向面试题下载 | ✌️计算机核心资源汇总