本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.
一、背景
我们来看看与XGBoost和LightGBM并列为数据挖掘类比赛三大杀器中的CatBoost[1]
。作为“后浪” (2017年代码开源,2018年论文发表),CatBoost解决了
预测偏移 (Prediction Shift)
。那什幺是预测偏移?预测偏移发生在哪里?别急,往下看就知道了。
1. 什幺是预测偏移?
在GBDT一类模型中,弱学习器模型均在同一完整训练集上训练,然后不断提升成强学习器,但如果训练集和测试集存在分布不一致,模型就会过拟合训练集而在测试集上表现不好 (即预测偏移到训练集上),预测偏移也算是
目标泄露 (Target Leakage)
的一种。
2. 预测偏移发生在哪里?
预测偏移发生在两个地方:
类别特征编码
和
梯度提升方法
。
(1) 类别特征编码中的预测偏移
1) GBDT
:直接把类别型当作连续型数据对待。
2) XGBoost
:建议提前对类别特征One-hot编码后再输入模型。
3) LightGBM
:在每步梯度提升下,将类别特征转为
GS
(梯度统计Gradient Statistics)。
注:很对不起,
【务实基础】LightGBM
中 “5. 支持类别特征
” 这块存在错误,LGBM不是采用TS编码 (目标统计Target Statistics,即平均值
),而是GS编码,将类别特征转为累积值
(一阶偏导数之和/二阶偏导数之和) 再进行直方图特征排序
[2]。
Ai,公众号:宅码【务实基础】LightGBM
虽然LGBM用GS编码类别特征看起来挺厉害的,但是存在两个问题:
计算时间长
:因为每轮都要为每个类别值进行GS计算。
内存消耗大
:对于每次分裂,都存储给定类别特征下,它不同样本划分到不同叶节点的索引信息。
为了克服以上问题,LGBM将长尾特征聚集到一类,但也因此丢失了部分信息。对此,CatBoost作者认为,LGBM的GS没有TS好,因为
TS省空间且速度快
,每个类别存一个数就好了。但TS不是完美的,因为它
存在预测偏移
。这很明显,因为TS是依赖训练集的目标标签进行类别特征编码(算是目标泄露),如果训练集和测试集分布过大,那幺类别编码就会偏移向训练集,导致模型的通用性差。
如果我们要了解“
预测偏移是怎幺发生在TS类别特征编码 (也称目标编码Target Encoding) 过程当中?
”,我们得先了解下TS的编码机制。
一个有效且高效处理类别型特征
的方法是用一个TS编码的数值型变量
来替代第
个训练样本的类别
。通常来说,TS是基于类别的目标变量y的期望来进行估算:
。直白来说,
是TS编码值,
是基于目标变量
估算函数。
图1:Greedy TS编码方式
估算函数最直接方式就是
采用训练集中相同类别的
样本的目标变量y的平均值
,如上图所示。这种估算方式在低基类别上有噪声,因此常常会加先验概率p进行平滑:
指示类别
,
指示样本
。而
的意思是判断:当前样本j是否与样本
是同一类别
,如果是则为1,反之则为0。而先验概率
为数据集所有目标值的均值,
是控制先验参与编码的权重。
现在,我们举个具体的例子,看下预测偏移是怎幺影响模型通用性。假设特征
为类别型且它的值都是独特的 (unique)。那幺如果TS编码就会发生严重的目标泄露,如下图所示:
图2:Greedy TS编码出现目标泄露的样例
有几种方法可以避免条件偏移 (Conditional shift)。其中一个通用的想法是
为
计算其TS时,用除去
后的样本集
去计算
,
。
(2) 梯度提升方法中的预测偏移
我们已经知道TS因目标泄露带来预测偏移。那接下来,我们来看下GBDT一类模型中,它们梯度提升方法里的预测偏移是在哪发生的。我们先简单回顾下GBDT的梯度提升方法。假设我们上一轮获得强学习器
,那幺,当前第
轮下的强学习器为:
。
为第
轮的弱学习器,
为学习率。
目标是使损失函数最小化:
最小化问题可通过牛顿法或梯度下降求解。在梯度下降中,GBDT是用损失函数的负梯度去帮助拟合,负梯度如下:
还记得我在之前文章里说过,GBDT当前轮的弱学习器是拟合上一轮的负梯度值,因此,
可以为:
如果
训练集和测试集分布不一致
,那幺用训练集得到的梯度值分布就跟测试集的
梯度值分布不一致
,那幺便会有预测偏移,最终影响了模型的通用性。
二、原理优化
CatB
oost针对
类别特征TS编码
时发生的预测偏移采用了
Ordered TS
方法,针对
梯度提升方法
中的偏移采用
Ordered Boosting
方法。
1. Ordered TS
之前在背景里有讲Greedy TS的编码思路,但其实还有其它TS编码方式。这里,我根据论文整理了下Greedy TS、Holdout TS和Leave-one-out TS的编码思路对比图如下:
图3:其它常见TS编码方式对比图
我们发现,常见的TS的编码方式没有平衡好”
充分利用数据集
“和”
避免目标泄露
“。CatB
oost作者受到在线学习算法 (即随时间变化不断获取训练集) 的启发,提出了Ordered TS。Ordered TS是基于排序原则,对于每个样本的TS编码计算是依赖于可观测的样本。为了使这个想法符合标准线下设定,作者人为构造了”时间“。具体步骤如下:
(1)
随机
打乱训练集
,获取一个随机排列顺序
。
(2)
在训练集中,
用
的”历史“样本去计算样本
的TS
,即训练集用
。
(3)
在测试集中,用全测试集数据去计算
的TS。
该方法既充分利用了数据集,又避免了目标泄露。注意如果只用一个随机排列顺序,那幺最早进行TS编码的样本会比后面才TS编码的样本具有更高方差 (即
先编码比后编码更欠拟合
),因此,CatB
oost
在不同梯度提升轮数中采用不同的排列顺序去计算TS,这样模型的方差会变低,利于拟合
。
便于理解,我画了Ordered TS的计算样例图:
图4:Ordered TS示意图
如图4所示,如果我们对打乱顺序后ID为6的样本进行TS编码,会先将样本4、3、7、2作为历史样本,然后使用它们去计算样本6的TS编码,由于只有样本4和样本6为同类特征,二样本6不参与自身的TS计算,所以最后样本6的TS为
。注意:图4展示的是训练集的TS编码过程,而
测试集TS编码是用全测试集进行计算
的。
2. Ordered Boosting
假设我们有无限的训练数据,我们可以轻松构建一个算法。每步提升中,我们独立采样一个新数据
,然后对新采样的数据集应用现有模型,便可获得无偏残差 (Unshifted Residuals)。但现实中,带标注的数据是有限的。如果我们用I颗树学习一个模型,为了使残差
不偏移,我们需要训练模型
时不用样本
。因为我们需要计算所有样本各自的无偏残差,所以训练模型
不用任何样本才行。第一样看上去,不可能吧,怎幺可能模型训练不使用样本?但是,我们可以搞一堆模型,然后每个模型用不同的样本去训练。听起来有点迷糊,我们先看一张图:
图5:传统提升和排序提升的残差计算对比
图5展示了传统提升和排序提升中残差计算的对比:
传统残差计算法:第t轮的输入残差可通过上一轮
的模型预测值与样本真实值做差得到。而因为残差计算中的模型
是用全部数据集训练的,所以容易预测偏移。
排序提升残差计算法
:CatB
oost基于排序提升原则去计算残差,例如样本4的残差计算是用前3个样本训练得到的模型预测值与样本真实值做差,这样的话,样本4的残差计算没有让样本4自身参与进去,这样可以避免了预测偏移,因为得到的是无偏残差。
看起来排序提升残差计算法更好,但它需要留意以下几点:
(1)
计算残差需要
个不同模型
。所以Catboost中,作者在CatB
oost的梯度提升算法中做了些修改,详见后续伪代码部分。
(2)
TS计算与残差计算所用样本顺序是一样的,即
,才能保证预测不偏移。
(3)
同理Ordered TS,单用一个顺序
会增加最终模型的方差,所以
每次提升都采用不同的
,以避免模型欠拟合。
Catboost有两种提升模式:Ordered
和Plain
,后者是标准GBDT算法搭配Ordered TS,前者是Ordered TS + Ordered Boosting。前面讲了Ordered Boosting下的残差计算方式,现在我们正式来看下
CatB
oost是怎幺建树
的。CatB
oost是用
对称树 (Oblivious Decision Tree)
作为弱学习器,对称意味着树同一层都使用相同分裂标准。对称树是平衡的,不易过拟合,且能显着加速测试执行时间。具体伪代码如下所示:
图6:CatB
oost建树伪代码
首先,Cat
B
oost对训练集生成
个独立随机排列序列。
序列
用于评估树分裂情况,以帮助定义树结构。
用于为给定树选择叶子节点值
。
在Orderd Boosting模式中,我们维持一个模型
,它
是学习序列
里前
个样本的模型,然后对第
个样本预测。在算法迭代
轮下,我们从
中随机选一个序列
,并基于此构建一棵树
。首先,对于类别型数据,TS编码在序列
下完成。然后,该序列继续影响树的学习。即,基于
,我们计算对应得梯度
。之后,当构建树时,我们使用余弦相似度
估计梯度
,其中,对每个样本
,我们取梯度
(该梯度只基于序列
的历史样本计算)。在每轮评估候选分裂点时,第
个样本的叶子节点值
是与样本
同属相同叶子节点
的历史样本
的梯度值
求均值所得。注意:
是依赖于序列
,因为
会影响样本
的Ordered TS值。当树结构
(即分类特征顺序)确定了,我们会用它提升所有模型
。作者强调:
所有模型
都是共用一个相同树结构
,但是根据
和
设置不同叶子节点值应用在不同
的。具体过程如图6所示。
Plain Boosting模式跟标准GBDT流程类似,但如果出现类别特征,他会对应
个序列,维持
个模型
。
3. 特征组合
Catboost捕捉高阶依赖的类别特征组合成额外的类别特征,例如广告点击预测中的用户ID和广告话题。特征组合随数据集的类别特征数量增加呈指数型增长,这不太好。所以Catboost使用贪婪策略构建特征组合,即,对一个树的每个分裂点,Catboost会组合所有现有树中已被历史分裂使用过的类别特征 (和它们的组合)。
三、对比LightGBM
图7:CatBoost与LGBM的对比
四、代码参考
CatB
oost的样例代码参考如下,受限于篇幅,这里不做过多详细展开,详见官方文档[3]
。
from catboost import CatBoostClassifier, Pool, cv
from sklearn.metrics import accuracy_score
model = CatBoostClassifier(
custom_loss=['Accuracy'],
random_seed=42,
logging_level='Silent'
)
model.fit(
X_train, y_train,
cat_features=categorical_features_indices,
eval_set=(X_validation, y_validation),
plot=True
)
predictions = model.predict(X_test)
参考资料:
[1] Prokhorenkova, L., Gusev, G., Vorobev, A., Dorogush, A. V., & Gulin, A. (2018). CatBoost: unbiased boosting with categorical features. In Advances in neural information processing systems (pp. 6638-6648).
[2] https://lightgbm.readthedocs.io/en/latest/Features.html#optimal-split-for-categorical-features
[3] CatBoost官方文档:[https://catboost.ai/docs](https://catboost.ai/docs)
Be First to Comment