论文学习笔记 CatBoost: unbiased boosting with categorical features

CatBoost和XGBoost、LightGBM并称为GBDT的三大主流神器,都是在GBDT算法框架下的一种改进实现。今天分享一篇论文,CatBoost: unbiased boosting with categorical features
摘要
摘要里指出CatBoost比其他基于GBDT算法的优势在于ordered boosting和一个创新性的处理类别型特征的方法。这两个创新点可以解决由目标泄露(target leakage)造成的决策偏移(prediction shift)问题,而决策偏移存在于目前所有基于GBDT的算法实现中。

除了摘要中提到的最重要的两个创新点,本文还会提到CatBoost基于贪心策略的特征组合方法和使用对称二叉树作为基模型这两个特点。

  • 对类别型特征进行 Ordered TS 编码

对于类别特征,普遍会使用Onehot编码。但如果类别数量很多,使用onehot编码会导致特征数量变得很多。这时候一般会使用Target Statistics的办法将类别型特征转化为数值型特征。

以风控领域的预测信贷用户是否会逾期为例,假设其中一个类别特征是用户所在城市。全国有几百个城市,转化为onehot编码并不合适。这时候最直觉的方法就是我们可以用某个城市用户的平均逾期率来作为该城市的数值特征编码。这就是最简单的的 Target Statistics 编码方法。
Target Statistics
Target Statistics
但是考虑到有一些小城市,比如我的老家安徽宿州,可能在训练样本中数量很少甚至没有,这时候用训练样本中宿州市的用户平均逾期率就会很不靠谱。比如说宿州市只有1个样本,并且这个样本是逾期的,那么逾期率100%,数值编码为1,显然不合理。所以在此基础上我们一般会加入先验值来抑制这种小样本的波动。
加入先验
假设全部训练样本中用户的逾期率为 p = 0.1, 我们可以在分子分母上分别加入 a = 100个逾期率为p的先验样本。这样的编码就合理多了。

这种数值编码方式虽然好,但是会造成训练集中label的泄露,因为对于某个样本来说,其数值编码计算过程中已经把这个样本的label值纳入了计算过程中,这就是文中提到的target leakage。一种解决方式是我们可以拿出一部分数据来Target Statistics,用另外一部分数据来训练。但是这样会造成可用数据的减少。

CatBoost受在线学习的启发,给出了一种创新的Target Statistics方式,即Ordered Target Statistics。基于排序原则,作者人为构造了”时间“,对于每个样本的TS编码计算只依赖于当前“时间”之前的可观测样本。具体步骤如下:

(1) 随机打乱训练集,获取一个随机排列顺序σ。

(2) 在训练集中,用”历史“样本去计算样本类别型特征的TS,即
历史样本
Ordered TS
(注:这张图中右边第五行计算第二个D的TS的式子应该为(0+αp)/(1+α),因为“历史”样本中出现了1次D,且该样本的值为0。)

(3) 在测试集中,用全测试集数据去计算类别型特征的TS。

该方法既充分利用了数据集,又避免了目标泄露。不过这种方式会造成排在前面的样本的类别特征的数值编码估计不是很准,为了减少这个影响,CatBoost会设计多个(默认4个)样本随机排列,在每次建树前从中随机取一个排列。

  • 避免预测偏移的 Ordered Boosting 方法

使用XGBoost或者LightGBM做模型时,我们可能经常会发现模型在训练集上拟合的很好,但是在验证集上却差了一些。这当然有可能是因为模型过于复杂导致的过拟合。按照论文中的说法,这也可能是XGBoost和LightGBM自身算法的缺陷造成的,即预测偏移。LightGBM在训练下一棵tree的时候,需要计算前面这些tree构成的加法模型在所有样本上的一阶梯度和二阶梯度,然后用这些梯度来决定下一棵树的结构和叶子节点取值。但是我们计算的这些一阶梯度和二阶梯度值是问题的。前面的这些tree都是在这些样本上训练的,现在我们又在这些样本上估计模型预测结果的一阶和二阶梯度。(这段纯属人云亦云,我并不太了解LGBM,如有问题请指正。)我们应该换一些新的样本才更合理。

CatBoost 的作者故技重施。先将样本随机打乱,然后每个样本只使用排序在它前面的样本来训练模型。(论文中在前面的Odered TS当中对于类别型特征的处理有介绍到:针对每一个随机排列,计算得到其梯度,为了与Ordered TS保持一致,这里的排列与用于计算Ordered TS时的排列相同。)用这样的模型来估计这个样本预测结果的一阶和二阶梯度。然后用这些梯度构建一棵tree的结构,最终tree的每个叶子节点的取值,是使用全体样本进行计算的。这就是Ordered Boosting的主要思想。可以有效地减少梯度估计的误差,缓解预测偏移。但是会增加较多的计算量,影响训练速度。

models
ordered boosting
举个例子,假设我们要计算x5的负梯度,则我们使用x1,x2,x3,x4训练一棵树,用这棵树预测出x5的预测值然后和真实值带入负梯度计算公式算出负梯度,从而作为x5的负梯度g作为下一轮的标签。 如果要计算x6的负梯度,则使用x1,x2,x3,x4,x5按照上面的方法如法炮制。显然,这种计算方式将导致非常大的计算量,因此CatBoost内部做了一些改进,默认情况下,CatBoost只训练log(num_of_datapoints)个模型,而不是为每个数据点训练不同的模型,节省计算量。大概意思就是:
在第一个数据点上训练的模型用于计算第2个数据点的残差。
在前两个数据点上经过训练的另一个模型用于计算第3,4个数据点的残差。
在前四个数据点上经过训练的另一个模型用于计算第5,6,7,8个数据点的残差。
依次类推……

在定义CatBoost模型时,我们可以用’boosting_type’这个参数来设置是使用Ordered Boosting 还是 LightGBM那样的 Plain Boosting。如果不显式设置,CatBoost会根据样本和特征数量自己决定。
boosting_type

根据CatBoost官网介绍,一般在GPU上训练,训练集数量小于等于5万,且非MultiClass或MultiClassOneVsAll场景时,会自动使用Ordered Boosting。

  • 基于贪心策略的特征交叉方法

类别型特征交叉也是特征工程中一个重要的步骤,例如颜色和种类组合起来,可以构成类似于blue dog这样的特征。使用Ordered Target Statistics 方法将类别特征转化成为数值特征以后,会影响到特征交叉,因为数值特征无法有效地进行交叉。为了有效地利用特征交叉,CatBoost在将类别特征转换为数值编码的同时,会自动生成交叉特征。如果让全部的类别特征之间都进行交叉,两两交叉,三三交叉,四四交叉,这个复杂度是指数级的,特征维度一定会爆炸。

CatBoost使用一种贪心的策略来进行特征交叉。生成tree的第一次分裂,CatBoost不使用任何交叉特征。在后面的分裂中,CatBoost会使用生成tree所用到的全部原始特征和交叉特征跟数据集中的全部类别特征进行交叉。在定义CatBoost模型时,我们可以用’max_ctr_complexity’ 来控制允许的特征交叉的最大特征数量,如果设置为3,那么生成tree时所用到的交叉特征最多只会来自3个特征的交叉。

  • 使用对称二叉树作为基模型

大多数的GBM中使用的都是普通的决策树,比如下面的这个树:
决策树
上面这棵树中,第二层中左右两个节点的判断条件不同。如果一个样本进入了左面的节点,下一个问题是是否关注了“机器会学习”,如果进入了右面的节点,下一个问题则是“喜欢tensorflow”还是“pytorch”。

而对称树是这样的:
对称树
对称树中,每一层的每一个节点判断条件都是一样的。假如如果我们只训练一棵树,那么显然对称树的拟合能力会比普通的决策树弱。但是在GBM中,我们通常训练很多的树,所以拟合能力不必担心。

对称树主要有两个优势:

  • 拟合模式相对简单,结构比普通决策树自由度小,可以看作是加入了penalty,不容易过拟合。

  • 可以提高预测速度。
    传统的决策树对每一个样本进行预测时都要从根节点遍历这棵树,但是应用CatBoost中的对称树我们可以并行地计算每一层的判断条件,组成一个二进制索引,根据索引得到最终的预测结果。下面的模型预测速度对比结果来自CatBoost的官网(40万样本,2000个特征),可见对称树在预测速度上的优异表现。
    预测速度

  • 实战效果

阅读论文后暂时没有时间系统地在几个常用训练集上测评GBDT的三大主流神器的准确率和训练速度,先用一张网上的表格做一个对比。
三大神器
(注:其中CatBoost并不是不支持缺失值的处理,在默认情况下,会将缺失值变成最小值。)

读研时候数据挖掘课的导师组织过一次新加坡房价预测的Kaggle比赛。比赛前半段时间我们组用XGBoost实现,经过Target Statistics、GPLearn等特征工程、以及各种模型调参和ensemble之后,排名大概稳定在10/64左右。后来尝试使用了CatBoost,在未调参的情况下,RMSE直接干到第一名。我在其中主要负责特征工程,后期发现GPLearn和CatBoost并不契合,加了不如不加,对于类别型特征的基于期望的Target Statistics也属于画蛇添足,不如直接将类别型特征交给CatBoost来进行Ordered Target Statistics。所以我后期主要工作就是尽可能创造更多的特征,比如获取新加坡所有中小学的经纬度,了解新加坡学区房政策,从而创建一系列学区房特征,比如获取所有食阁、商圈、公交车站、地铁站等公共设施的经纬度信息,创建“与最近的xx的距离”,“0.5km范围内有几个xx“,“1km范围内有几个xx“,“2km范围内有几个xx“等特征。最终成绩Public Leaderboard 1/64,Private Leaderboard 2/64。
public leaderboard
private leaderboard
这次kaggle比赛中前几名用的都是CatBoost。

  • 总结

CatBoost受在线学习影响,通过给数据随机排序,人为引入了数据的时间顺序,在Target Statistics和Boosting时,只根据“历史“数据进行计算,解决了预测偏移的问题。从而使预测结果更加精准。

CatBoost的基模型为对称二叉树,减小过拟合的同时预测速度极快,在模型部署后,可以更快的响应,我认为在日常工作场景中也非常有用。

预测偏移的概念我是在这篇文章中第一次听说,网上查了不少资料,最终也都指向CatBoost相关的几篇论文。阅读了一些帖子,造成预测偏移的原因是训练集的条件分布和测试集的条件分布不一致,这让我有些困惑,因为在我认知中,过拟合的本质也是训练集的条件分布和测试集的条件分布不一致,正是因为不一致,所以过于复杂的模型过度了拟合了训练集的数据,才会在测试集上表现比较差。那我是否可以认为预测偏移就是一种过拟合呢?欢迎了解预测偏移的兄弟们给我解惑。

  • 参考文献

CatBoost: unbiased boosting with categorical features

catboost完全指南-马东什么

30分钟学会CatBoost-吃货本货

【务实基础】CatBoost-艾宏峰

oblivious tree在机器学习中有什么用?-李大猫

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
上一篇 2022年6月8日 上午11:58
下一篇 2022年6月8日 下午12:01

相关推荐

本站注重文章个人版权,不会主动收集付费或者带有商业版权的文章,如果出现侵权情况只可能是作者后期更改了版权声明,如果出现这种情况请主动联系我们,我们看到会在第一时间删除!本站专注于人工智能高质量优质文章收集,方便各位学者快速找到学习资源,本站收集的文章都会附上文章出处,如果不愿意分享到本平台,我们会第一时间删除!