Practical Lessons from Predictin

本文是Facebook 2014年发表的一篇经典论文，文中提出使用GBDT + LR来构建模型是一个亮点。同时，论文还对数据新颖度（Data freshness），下采样方法，学习率，特征构建进行了研究。

1、特征构建

为了提升线性分类器的效果，一般使用两种方式对特征进行转换：

• 对于连续型特征，一般先分箱离散化，每个区间作为一个单独的特征。线性模型可以学习到一个非线性的映射；
• 对于非连续型特征，一般可以使用笛卡尔积的方式得到特征组合。但是这种方式得到的组合结果是非常稀疏的，难以训练。

在本文中，作者使用GBDT中的树来对特征进行转换。

如上图，一个样本特征输入后样本会经过最上层的决策树，最后落入树的某个叶子节点。我们将这个叶子节点的index作为转换后的特征，也即后续LR模型的输入。

具体地，如上图有2棵树，假如一个样本输入后在两棵树中分别掉入了第一棵树的第二个叶子节点和第二棵树的第一个叶子节点，则转换后的特征为[0,1,0,1,0]，其中的1分别代表样本落入的叶子节点的索引。因此，无论是离散还是连续型特征，经此方式后都能转换为离散型特征作为LR的输入。

作者认为，（1）这种特征转换将一个实值得向量转化为了一个紧凑的二进制向量，（2）且每一个从树根节点到叶子节点的组合都代表了一个特征组合，叶子节点表示组合情况（3）使用线性分类器来对这些特征进行学习就是学习得到这些组合的权重。

2、数据新颖度（Data freshness）

作者取了一周的数据进行研究。其中第一天数据作为训练集训练模型，然后分别对后面的数据进行预测，结果发现，时间越靠后的数据预测结果越差。说明及时更新训练模型非常有必要。文中给出：

• 提升树可以一天或几天训练一次；
• LR则可以使用在线学习来进行实时更新。

3、学习率设置

最终的实验结果是：Per-coordinate learning rate效果最好。这个跟Adagrad的做法几乎一样，分母上使用梯度的平方进行累加，然后开根号。使得不同的参数具有不同的学习速率。

对于global learning rate失败主要是由于训练样本在特征上分布不平衡造成。对于一些在很多样本都存在的特征，能很好地学习。但是对于某些仅存在于少数样本中的特征，则会由于学习率下降过快而学习不充分。

而对于per-weight learning rate策略本身是用于解决样本在特征上分布不平衡问题的，这里依旧失败的原因是对于所有特征，学习率下降太快，训练在模型收敛到次优点的情况下过早终止。

4、在线学习

这部分主要是说明 online data joiner。前面我们研究过 data freshness 对于模型的训练是非常重要的。那么新的训练数据是怎么产生的呢？online data joiner 将用户的点击结果作为特征添加到训练数据中去。

有一个问题是，在页面上没有 not click按钮，如何设定not click是一个问题。作者提出设置一个时间阈值，当一个作者展示给用户足够长的时间但用户没有点击后，则记为 not click。这个等待的时间阈值是一个非常关键的参数，太短了，用户来不及点击，会降低点击覆盖率（click coverage），太长了会增加缓存影响数据产生。所以在线学习系统必须要做出一个在资源和点击覆盖率上的权衡。

如果点击覆盖比较低，意味着很多用户的点击不但没有记录下来，而是变成了没有点击。造成数据分布发生偏差，结果就是：模型学习到的CTR值要比真实值低很多。不过实际情况中，问题比较好解决：增大等待时间窗口，只要内存消耗还可以接受就行。

对于系统异常造成的点击率过低问题，可以通过异常检测来识别，如当发现实时的训练数据分布发生比较大变化的时候，就把 online trainer 和 online joiner 自动断开，防止Trainer学习到坏的数据分布。

5、GBDT树和特征的研究

作者分别采用了1-2000棵树，结果显示500棵树已经足够，再添加树对于模型结果的提升几乎低于0.1%

而对于特征的研究表明，少量（top 10）重要特征占据了主导地位，而那些不重要特征（last 300）贡献的重要性不足1%。

输入特征可以分为两类：上下文特征（contextual features）和历史特征（historical features）。上下文特征包括用户使用的设备、当前页面、时间、一周第几天等；而历史特征则主要是指用户或者广告之前的一些信息，比如：该广告上周的CTR值、该用户的历史平均CTR值等。

对这两类特征的研究结果表明，历史特征在重要性上占主导地位。但上下文特征在用户冷启动问题解决上非常重要。

6、 下采样研究

很多的计算广告领域的训练数据量都是非常巨大的，那么如何有效的控制训练带来的开销就非常重要。常用的办法是采样，分为平均下采样（Uniform subsampling）和负下采样（ Negative down sampling）。

平均下采样简单易实现，而且不改变数据分布，训练出来的模型可以直接在测试集上用。一般而言，使用更多的数据结果往往更好，但在本研究中使用10%的数据，相比于使用100%的数据，仅仅造成了1%的性能降低，是非常小的。

数据不均衡是非常常见的一个问题，一个解决此问题的方法就是负下采样。负采样的一个问题是会改变数据分布，因此在最后需要对模型进行校正。研究结果表明采样率不同，对模型性能影响很大，采样率为0.025的时候取得最好结果。

上式中，p为未校正前的预测概率，w为采样率。

一些问题总结（摘自https://blog.csdn.net/lilyth_lilyth/article/details/48032119
）：

（1）、为什么建树采用ensemble决策树？

一棵树的表达能力很弱，不足以表达多个有区分性的特征组合，多棵树的表达能力更强一些。GBDT每棵树都在学习前面棵树尚存的不足，迭代多少次就会生成多少颗树。按paper以及Kaggle竞赛中的GBDT+LR融合方式，多棵树正好满足LR每条训练样本可以通过GBDT映射成多个特征的需求。

（2）、为什么建树采用GBDT而非RF？

RF也是多棵树，但从效果上有实践证明不如GBDT。且GBDT前面的树，特征分裂主要体现对多数样本有区分度的特征；后面的树，主要体现的是经过前N颗树，残差仍然较大的少数样本。优先选用在整体上有区分度的特征，再选用针对少数样本有区分度的特征，思路更加合理，这应该也是用GBDT的原因。

然而，Facebook和Kaggle竞赛的思路是否能直接满足现在CTR预估场景呢？

按照Facebook、Kaggle竞赛的思路，不加入广告侧的ADID特征？但是现CTR预估中，AD ID类特征是很重要的特征，故建树时需要考虑AD ID。直接将AD ID加入到建树的feature中？但是AD ID过多，直接将AD ID作为feature进行建树不可行。下面第三部分将介绍针对现有CTR预估场景GBDT+LR的融合方案。

（3）、GBDT与LR融合方案

AD ID类特征在CTR预估中是非常重要的特征，直接将AD ID作为feature进行建树不可行，顾考虑为每个AD ID建GBDT树。但互联网时代长尾数据现象非常显著，广告也存在长尾现象，为了提升广告整体投放效果，不得不考虑长尾广告[12]。在GBDT建树方案中，对于曝光充分训练样本充足的广告，可以单独建树，发掘对单个广告有区分度的特征，但对于曝光不充分样本不充足的长尾广告，无法单独建树，需要一种方案来解决长尾广告的问题。

综合考虑方案如下，使用GBDT建两类树，非ID建一类树，ID建一类树。1）非ID类树：不以细粒度的ID建树，此类树作为base，即便曝光少的广告、广告主，仍可以通过此类树得到有区分性的特征、特征组合。2）ID类树：以细粒度的ID建一类树，用于发现曝光充分的ID对应有区分性的特征、特征组合。

如何根据GBDT建的两类树，对原始特征进行映射？以如下图3为例，当一条样本x进来之后，遍历两类树到叶子节点，得到的特征作为LR的输入。当AD曝光不充分不足以训练树时，其它树恰好作为补充。

通过GBDT 映射得到的特征空间维度如何？GBDT树有多少个叶子节点，通过GBDT得到的特征空间就有多大。如下图4一颗树，一个叶子节点对应一种有区分性的特征、特征组合，对应LR的一维特征。这颗树有8个叶子节点，即对应LR 的8维特征。估算一下，通过GBDT转换得到的特征空间较低，Base树、ID树各N颗，特征空间维度最高为（N+N广告数+N广告主数+ N广告类目数）叶子节点个数。其中广告数、广告主数、广告类目数都是有限的，同时参考Kaggle竞赛中树的数目N最多为30，叶子节点个数小于10，则估算通过GBDT 映射得到的特征空间维度并不高，且并不是每个ID训练样本都足以训练多颗树，实际上通过GBDT 映射得到的特征空间维度更低。

（4）如何使用GBDT 映射得到的特征？

通过GBDT生成的特征，可直接作为LR的特征使用，省去人工处理分析特征的环节，LR的输入特征完全依赖于通过GBDT得到的特征。此思路已尝试，通过实验发现GBDT+LR在曝光充分的广告上确实有效果，但整体效果需要权衡优化各类树的使用。同时，也可考虑将GBDT生成特征与LR原有特征结合起来使用，待尝试。

小结

这篇文章发表时间较早，对于特征组合现在已经可以使用FM、FFM来实现了。而ID类特征的处理则可以使用embedding的方式将其转换为稠密特征。但是文章中的一些思路想法依然值得借鉴。

参考：
Practical Lessons from Predicting Clicks on Ads at Facebook
CTR预估 论文精读(五)--Practical Lessons from Predicting Clicks on Ads at Facebook
CTR预估中GBDT与LR融合方案