面试题:xgboost怎么给特征评分?


解析:

我们知道,在训练的过程中,cart树通过Gini指数选择分离点的特征,一个特征被选中的次数越多,那么该特征评分越高。

但xgboost呢?对于一个叶子节点如何进行分裂,xgboost作者在其原始论文中给出了两种分裂节。

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

现在的情况是只要知道树的结构,就能得到一个该结构下的最好分数,那如何确定树的结构呢?

一个想当然的方法是:不断地枚举不同树的结构,然后利用打分函数来寻找出一个最优结构的树,接着加入到模型中,不断重复这样的操作。而再一想,你会意识到要枚举的状态太多了,基本属于无穷种,那咋办呢?

我们试下贪心法,从树深度0开始,每一节点都遍历所有的特征,比如年龄、性别等等,然后对于某个特征,先按照该特征里的值进行排序,然后线性扫描该特征进而确定最好的分割点,最后对所有特征进行分割后,我们选择所谓的增益Gain最高的那个特征,而Gain如何计算呢?

还记得4.2节最后,我们得到的计算式子
0.png

换句话说,目标函数中的G/(H+λ)部分,表示着每一个叶子节点对当前模型损失的贡献程度,融合一下,得到Gain的计算表达式,如下所示:
1.png

第一个值得注意的事情是“对于某个特征,先按照该特征里的值进行排序”,这里举个例子。

比如设置一个值a,然后枚举所有x < a、a < x这样的条件(x代表某个特征比如年龄age,把age从小到大排序:假定从左至右依次增大,则比a小的放在左边,比a大的放在右边),对于某个特定的分割a,我们要计算a左边和右边的导数和。

比如总共五个人,按年龄排好序后,一开始我们总共有如下4种划分方法:
①把第一个人和后面四个人划分开
②把前两个人和后面三个人划分开
③把前三个人和后面两个人划分开
④把前面四个人和后面一个人划分开

接下来,把上面4种划分方法全都各自计算一下Gain,看哪种划分方法得到的Gain值最大则选取哪种划分方法,经过计算,发现把第2种划分方法“前面两个人和后面三个人划分开”得到的Gain值最大,意味着在一分为二这个第一层层面上这种划分方法是最合适的。
2.png

换句话说,对于所有的特征x,我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL和GR。然后用计算Gain的公式计算每个分割方案的分数就可以了。

然后后续则依然按照这种划分方法继续第二层、第三层、第四层、第N层的分裂。

第二个值得注意的事情就是引入分割不一定会使得情况变好,所以我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝, 当引入的分割带来的增益小于一个阀值γ的时候,则忽略这个分割。

换句话说,当引入某项分割,结果分割之后得到的分数 - 不分割得到的分数得到的值太小(比如小于我们的最低期望阀值γ),但却因此得到的复杂度过高,则相当于得不偿失,不如不分割。

即做某个动作带来的好处比因此带来的坏处大不了太多,则为避免复杂 多一事不如少一事的态度,不如不做。
相当于在我们发现“分”还不如“不分”的情况下后(得到的增益太小,小到小于阈值γ),会有2个叶子节点存在同一棵子树上的情况。

下面是论文中的算法

3.png


近似算法

4.png

就职于Google的读者crab6789点评:

把样本从根分配到叶子结点,就是个排列组合。不同的组合对应的cost不同。求最好的组合你就要try,一味穷举是不可能的,所以才

出来贪婪法。

不看从头到尾 就看当下节点怎么分配最好。这才有了那个greddy exact 方法,后来还想加速才有了histogram的做法。
已邀请:

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~