XgBoost详解
Tree Ensemble
参数对应树的结构,以及每个叶子节点上的预测分数
如何学习参数
- 定义合理的目标函数,然后尝试优化目标函数
- 我们可以把模型定义成
yi^=∑Kk=1fk(xi) fk∈F - 因此目标函数可以写为
Obj(Θ)=∑ni=1l(yi^,yi)+∑Kk=1Ω(fk)
- 我们可以把模型定义成
模型学习:Additive Trainning
那么问题来了,第t论应该选取什么模型呢?答案很明显:
选取使目标函数最小的模型 对于一般的平方误差损失,还可以写为一下二次函数
很明显,上面的二次函数的最优解为yi−yi^(t−1) ,也就是残差的定义- 不失一般性,对于更加general的情况
-
到了这里,我们可以看到,这样一个形式可以包含所有可以求导的目标函数。因此可以求解回归,分类,排序问题。
树的复杂度定义
首先我们先把树拆成两部分,结构函数
q(x) 和权重函数w(x) -
下面我们给出复杂度的一种定义,当然这不唯一。但下面给出的定义学习出来的效果往往还不错
求解目标函数,建立决策树
-
首先整理一下目标函数
定义Gj=∑i∈Ijgi Hj=∑i∈Ijhi 上式可以整理为
Obj(t)=∑j=1T[Gjwj+12(Hj+λ)w2j]+γT
不难看出,关于这个二次函数的最小值即为wj=−GjHj+λ ,此时目标函数的最小值为Obj(t)=−12∑j=1T[G2jHj+λ]+γT 有了上面的理论推导,我们可以把建立决策树的过程分为两部分
-
建立决策树结构
与ID3算法类似,也是利用贪心法建立树的结构,每一次尝试对已有的叶子进行分割,只不过这里的分割标准不再是信息增益,而是以下公式
对于每次扩展,我们要枚举所有的分割方案,如何高效的枚举所有的分割呢?下面是x<a 的分割
不难看出,对于所有的a,我们只要从左到右扫描一遍,就可以枚举所有的分割方案,然后通过上述公式计算每种分割的分数,选出最优分割。引入分割不一定会使得情况变好,因为我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝,当引入的分割带来的增益小于一个阀值的时候,我们可以剪掉这个分割。大家可以发现,当我们正式地推导目标的时候,像计算分数和剪枝这样的策略都会自然地出现,而不再是一种因为heuristic而进行的操作了。 -
确定叶子节点的权值
一旦树的结构确定了,权值可以利用公式来确定wj=−GjHj+λ 最后一点思考
XgBoost如何处理带权重的样本呢?
算法流程示意图