回顾Facebook经典CTR预估模型

这里是「王喆的机器学习笔记」的第九篇文章，今天我们重读一篇经典的CTR预估领域的论文，Facebook在2014发表的“Practical Lessons from Predicting Clicks on Ads at Facebook”。

在这篇文章中，Facebook提出了经典的GBDT（Gradient Boosting Decision Trees）+LR(Logistics Regression)的CTR模型结构，可以说开启了特征工程模型化、自动化的新阶段。此外其在五年前就采用的online learning，online data joiner，negative down sampling等技术时至今日也有极强的工程意义。下面我们就一起回顾一下这篇当时红极一时，现在仍常看常新的论文吧。

用户场景

文章的用户场景是一个标准的点击率预估的场景，需要强调的只有一点，因为我们需要利用CTR计算精准的出价、ROI等重要的后续预估值，因此CTR模型的预估值需要是一个具有物理意义的精准的CTR，而不是仅仅输出广告排序的高低关系。所以文中不仅把CTR calibration作为重要的评价指标，更是在最后介绍了模型校正的相关方法。

模型结构

计算广告方向的同学应该都对GBDT+LR这个模型有所了解，这一点也无益是这篇文章最大的贡献。虽然文章其他部分的价值丝毫不逊于该模型，但再次回顾该模型，清楚知道其技术细节还是必要的。

简而言之，文章提出了一种利用GBDT自动进行特征筛选和组合，进而生成新的feature vector，再把该feature vector当作logistic regression的模型输入，预测CTR的模型结构。

回顾Facebook经典CTR预估模型

                                GBDT+LR模型结构

这里需要强调的是，用GBDT构建特征工程，和利用LR预测CTR两步是独立训练的。所以自然不存在如何将LR的梯度回传到GBDT这类复杂的问题，而利用LR预测CTR的过程是显然的，在此不再赘述，我们着重讲一讲如何利用GBDT构建新的特征向量。

大家知道，GBDT是由多棵回归树组成的树林，后一棵树利用前面树林的结果与真实结果的残差做为拟合目标。每棵树生成的过程是一棵标准的回归树生成过程，因此每个节点的分裂是一个自然的特征选择的过程，而多层节点的结构自然进行了有效的特征组合，也就非常高效的解决了过去非常棘手的特征选择和特征组合的问题。

我们利用训练集训练好GBDT模型，之后就可以利用该模型构建特征工程。具体过程是这样的，一个样本在输入GBDT的某一子树后，会根据每个节点的规则最终落入某一叶子节点，那么我们把该叶子节点置为1，其他叶子节点置为0，所有叶子节点组成的向量即形成了该棵树的特征向量，把GBDT所有子树的特征向量concatenate起来，即形成了后续LR输入的特征向量。

举例来说，比如GBDT由三颗子树构成，每个子树有4个叶子节点，一个训练样本进来后，先后落到了“子树1”的第3个叶节点中，那么特征向量就是[0,0,1,0]，“子树2”的第1个叶节点，特征向量为[1,0,0,0]，“子树3”的第4个叶节点，特征向量为[0,0,0,1]，最后concatenate所有特征向量，形成的最终的特征向量为[0,0,1,0,1,0,0,0,0,0,0,1]，我们再把该向量作为LR的输入，预测CTR。

引入了GBDT+LR的模型后，相比单纯的LR和GBDT，提升效果是非常显著的。从下表中可以看到，混合模型比单纯的LR或Trees模型在loss上减少了3%。

回顾Facebook经典CTR预估模型

                        LR+Trees模型的Loss对比

为了确定最优的GBDT子树规模，facebook绘出了子树规模和loss的关系曲线如下：

回顾Facebook经典CTR预估模型

                    GBDT子树数量与loss的关系

可以看到，在规模超过500棵子树后，增加子树规模对于loss下降的贡献就微乎其微了。特别是最后1000棵子树仅贡献了0.1%的loss下降，最终facebook选择了600作为其子树规模。

该模型的优势我们上面已经提到，即可以自动进行特征组合和特征筛选，但在实践过程中，模型的缺陷也比较明显，相比FTRL，FM，NN等能够通过梯度下降训练的模型来说，GBDT缺乏online learning的能力，因此我们往往只能相隔一天甚至几天才能够update GBDT模型，势必影响模型的实效性，那么Facebook是如何解决模型更新的问题的呢？

模型的实效性问题和更新策略

虽然我们的直觉是模型的训练时间和serving时间之间的间隔越短，模型的效果越好，但为了证明这一点，facebook的工程师还是做了一组实效性的实验，在结束模型的训练之后，观察了其后6天的模型loss（这里采用normalized entropy作为loss）           

回顾Facebook经典CTR预估模型

                                模型更新延迟与loss的关系

可以看出，模型的loss在第0天之后有所上升，特别是第2天过后显著上升。因此daily update的模型相比weekly update的模型效果肯定是有大幅提升的。

但囿于facebook巨大的数据量以及GBDT较难实施并行化的原因，GBDT的更新时间往往超过24小时，所以为了兼顾data freshness和客观的工程要求，facebook采取了下面的模型更新方法：

The boosted decision trees can be trained daily or every couple of days, but the linear classifier can be trained in near real-time by using some flavor of online learning.

就是说GBDT的部分几天更新一次，而LR的部分进行准实时的更新，这无疑是很好的工程实践经验。时至今日，我们已经开始使用大量不同的embedding方法进行特征编码，facebook当时的做法也对我们现在的工程实践有重要的参考价值。因为大量深度学习embedding方法的更新计算开销也非常大，但对实效性要求并不高，我们也完全可以低频更新embedding，高频或实时更新基于embedding特征的LR，NN等预测模型。

facebook的实时数据流架构

为了实现模型的准实时训练，facebook专门介绍了其基于Scribe的数据流架构，文中称其为online data joiner。

回顾Facebook经典CTR预估模型

该模块最重要的作用是准实时的把来自不同数据流的数据整合起来形成sample features，并最终与click数据进行join，形成完整的labeled sample。在整个过程中，我认为最应该注意的有三点：

1.waiting window的设定：waiting window指的是在impression发生后，我们要等待多久才能够判定一个impression是否有click。如果waiting window过大，数据实时性受影响，如果waiting window过小，会有一部分click来不及join到impression，导致样本CTR与真实值不符。这是一个工程调优的问题，需要有针对性的找到跟实际业务匹配的合适的waiting window。除此之外，无论怎样我们都会漏掉一部分click，这就要求我们阶段性的全量retrain我们的模型，避免online learning误差的积累。

2.分布式的架构与全局统一的action id：为了实现分布式架构下impression记录和click记录的join，facebook除了为每个action建立全局统一的request id外，还建立了HashQueue缓存impressions。hashQueue缓存的impression，如果在窗口过期时还没有匹配到click就会当作negative sample，这里说的窗口与上面提到的waiting window相匹配。facebook使用scribe实现了这一过程，更多公司使用Kafka完成大数据缓存和流处理。

3.数据流保护机制：facebook专门提到了online data joiner的保护机制，因为一旦data joiner失效，比如click stream无法join impression stream，那么所有的样本都会成为负样本，由于模型实时进行online learning和serving，模型准确度将立刻受到错误样本数据的影响，进而直接影响广告投放和公司利润，后果是非常严重的。为此，facebook专门设立了异常检测机制，一旦发现实时样本数据流的分布发生变化，将立即切断online learning的过程，防止预测模型受到影响。

降采样和模型校正

对于巨型互联网公司来说，为了控制数据规模，降低训练开销，降采样几乎是通用的手段，facebook实践了两种降采样的方法，uniform subsampling和 negative down sampling

uniform subsampling是对所有样本进行无差别的随机抽样，为选取最优的采样频率，facebook试验了0.001，0.01， 0.1， 0.5 和1五个采样频率，loss的比较如下：

回顾Facebook经典CTR预估模型

可以看到当采样率是10%时，相比全量数据训练的模型，仅损失了不到1%的效果。

另一种方法 negative down sampling 保留全量正样本，对负样本进行降采样。除了提高训练效率外，负采样还直接解决了正负样本不均衡的问题，facebook经验性的选择了从0.0001到0.1的一组负采样频率，试验效果如下：

回顾Facebook经典CTR预估模型

大家可以看到，当负采样频率在0.025时，loss不仅优于更低的采样频率训练出来的模型，居然也优于负采样频率在0.1时训练出的模型，虽然原文没有作出进一步的解释，但推测最可能的原因是解决了数据不均衡问题带来的效果提升。

负采样带来的问题是CTR预估值的漂移，比如真实CTR是0.1%，进行0.01的负采样之后，CTR将会攀升到10%左右。而为了进行准确的竞价以及ROI预估等，CTR预估模型是要提供准确的有物理意义的CTR值的，因此在进行负采样后需要进行CTR的校正，使CTR模型的预估值的期望回到0.1%。校正的公式如下：

回顾Facebook经典CTR预估模型

其中q是校正后的CTR，p是模型的预估CTR，w是负采样频率。大家可以利用简单的转换关系就可以得出上述公式，有兴趣的同学可以手动推导一下。

至此，我们介绍完了facebook这篇经典的CTR预估论文，可以看到虽然五年过去了，我们仍能从中汲取不少模型改造和工程实现的经验，就我个人来言，最值得学习的有下面三点：

1.特征工程模型化。五年前在很多从业者还在通过调参经验尝试各种特征组合的时候，利用模型进行特征自动组合和筛选是相当创新的思路，也几乎是从那时起，各种深度学习和embedding的思想开始爆发，一脉相承的发扬着特征工程模型化的思路。

2.模型复杂性和实效性的权衡。对GBDT和LR采用不同的更新频率是非常工程化和有价值的实践经验，也是对组合模型各部分优点最大化的解决方案。

3.有想法要用数据去验证。这其实是我读完这批文章最大的感触，在做算法工程师的过程中，我们其实是有很多直觉上的结论，比如data freshness的影响有多大，GBDT应该设置多少颗子树，到底是应该用负采样还是uniform采样，针对这些问题，facebook告诉你的是，用数据说话，无论是多么小的一个选择，都应该用数据去支撑，这才是一位工程师严谨的工作态度。

最后惯例提出两个问题供大家讨论：

1.如果采用random forest替代GBDT，有哪些优点和缺点？

2.GBDT+LR这个模型结构，是否能够有效处理大量ID类特征，为什么？如果希望处理大量ID类特征，我们应该如何改进这个模型？

欢迎大家关注我的 王喆的机器学习笔记（wangzhenotes）一起交流，水平有限，欢迎大家拍砖、吐槽、讨论。感觉文章有价值的同学也欢迎点赞鼓励，谢谢。

参考资料：

1.Practical Lessons from Predicting Clicks on Ads at Facebook

2.Computational Advertising Paper List

—END—

回顾Facebook经典CTR预估模型

每周关注计算广告、推荐系统和其他机器学习前沿文章，欢迎关注王喆的机器学习笔记