浅谈决策树、GBDT、LightGBM


从决策树说起

决策树是我们后面一系列树方法的基础,因此不能不提。在我看来,它的精要只在一点,即如何衡量一个划分(split)的好坏。ID3用的是信息增益,C4.5用的是信息增益率,而CART用的是Gini系数。无论用的哪种metric,有一点是很有意思的,即做一次划分后的impurity一定是减少的(至少不会增加)。

更进一步讲,某一类sample总的impurity贡献在一次划分后是减少的。设某个node的样本数为n,其中某一类的样本数为a,记为(n, a),经过某一划分后,左右子节点分别为(n1, a2)、(n2, a2)。上述性质用数学公式可以表述为:
impurity(n, a) >= n1/n * impurity(n1, a1) + n2/n * impurity(n2, a2)
通过Jensen不等式可以证明(略)。
对于分类问题,impurity函数可以是熵或者Gini系数;对于回归问题,impurity函数一般采用方差。
(方差的来历:对连续值,一般让平方损失最小,因此节点的预测值取的是节点内均值,代入即为方差)

而将多个CART组合起来即可以产生一个ensemble模型,如RF。RF是决策树的组合,通过样本随机和特征集随机来提升模型的鲁棒性。这个模型的优势在于它很难过拟合,可以放心大胆的迭代下去。不好的地方则是随机的可解释性,你的效果比别人好,到底是模型好呢还是因为运气好。

Boosted-Tree

很多讲gbdt的blog用的是残差的概念,即每添加一个新的树,学习的是之前剩下的残差。这么讲当然没有错,但是突然扔出这样一个概念还是略显生硬。另一类blog则用的是泛函的概念,摘抄了论文中比较复杂的公式,看了有点眼花缭乱。我个人觉得这里要说清楚,从boosted-tree的角度来讲更加自然。

假设我们想构造含有t颗树的模型,可以用下面的过程来表示:

gbdt1.jpg


每一轮迭代以后的输出,是当前所有树的求和。那么每一轮迭代我们如何去构造新的树呢?可以用下式来表示第t轮我们的目标函数,其中n是sample数,等式右边前一项是损失函数,第二项是正则项(可以忽略)。

gbdt2.jpg


我们将其前半部分使用Taylor展开,可以得到:

gbdt3.jpg


其中

gbdt4.jpg


如果我们只看一阶导数,那么ft(x)取-gi时梯度下降最快(回想梯度下降算法),如果恰好损失函数用的是平方误差,那么 L=1/2*(y'-y)^2 ,即 g(y, y’) = y’-y,那么ft(x)的更新方向应为 -g(y, y’) = y-y’,这就是残差的由来;又因为这里的f是一个函数,因此又和泛函扯上了关系,求解这个泛函的过程实际上就是建树的过程。
而如果我们把二阶导数也考虑进去呢,那就得到了xgboost,陈天奇大神有非常详细的介绍,这里就不再细说。

计算split的比较

对于连续值得feature,我们在求split时,一般是先做排序,然后顺序选择分割点并计算结构分数。
这里Boosted-Tree中的tree,相比于CART有一个很大的好处,那就是每一个sample的结构分是固定不变的,因此计算分数时只需要在上一次迭代后的分数的基础上算增量即可;而CART的impurity则无法计算增量,无论是熵还是gini系数,当增减sample时,需要全部重新算一次,这无疑是很大一部分的计算量。

关于LightGBM

微软亚研最近开源了他们的LightGBM,我大致看了下,和xgboost一样用到了二阶导数。主要的特点如下:
- 使用直方图简化计算,计算split时只考虑直方图的bin做划分点,而不细化到每个sample。
- 使用leaf-wise替代level-wise,每次选择delta-loss最大的节点做分割。
- 计算直方图时,两个子节点只用计算其中一个,另一个通过root和前一个做差可得。
- 基于histogram的算法,在寻找最佳split时,可以先顺序访问data的gradient,填入对应bin中,提高cache hit。
- 对于category类型的feature,可以直接作为特征输入,不需要转化成one-hot之类的编码,据说在准确度差不多的情况下速度能快8倍以上。

有几个地方还有疑问
- 直方图中桶的个数和宽度如何确定?
- 如果要通过直方图做差节约计算,那么父节点和子节点的直方图分桶必须一致,难道一棵树所有节点的分桶都一致?
- 对于category类型的feature是如何做到支持直接输入的呢?

扫了一下源码,建直方图的过程如下:

- 首先对原数据排序;
- 然后统计出distinct value 以及对应的 count;
- 如果distinct value数目小于max bin数,则正好每个value放入一个bin;
- 如果distinct value大于max bin,计算bin大小的均值,按一定规则将sample放入bin,保证相同value的放入同一bin,bin包含的sample数尽量平均。
- 注:max bin的默认值是256。

对于category类型的feature,则是每一种取值放入一个bin,且当取值的个数大于max bin数时,会忽略那些很少出现的category值。
在求split时,对于category类型的feature,算的是"按是否属于某个category值划分"的gain,这和数值型feature是完全不同的,它的实际效果就是类似one-hot的编码方法。

欢迎有兴趣的同学一起讨论~
已邀请:

会飞的猩猩

赞同来自:


gbdt的cart树不是回归树,分类树才用gini系数。Lightgbm也用二阶导吗?我在论文里面好像没看见

要回复问题请先登录注册

返回顶部