本文将带领大家，一起来重读一篇经典的 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 的模型结构。
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%。
LR+Trees 模型的 Loss 对比
为了确定最优的 GBDT 子树规模，facebook 绘出了子树规模和 loss 的关系曲线如下：
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）。
模型更新延迟与 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。
该模块最重要的作用是准实时的把来自不同数据流的数据整合起来形成 sample features，并最终与 click 数据进行 join，形成完整的 labeled sample。在整个过程中，我认为最应该注意的有三点：
waiting window 的设定：waiting window 指的是在 impression 发生后，我们要等待多久才能够判定一个 impression 是否有 click。如果 waiting window 过大，数据实时性受影响，如果 waiting window 过小，会有一部分 click 来不及 join 到 impression，导致样本 CTR 与真实值不符。这是一个工程调优的问题，需要有针对性的找到跟实际业务匹配的合适的 waiting window。除此之外，无论怎样我们都会漏掉一部分 click，这就要求我们阶段性的全量 retrain 我们的模型，避免 online learning 误差的积累。
分布式的架构与全局统一的 action id：为了实现分布式架构下 impression 记录和 click 记录的 join，facebook 除了为每个 action 建立全局统一的 request id 外，还建立了 HashQueue 缓存 impressions。hashQueue 缓存的 impression，如果在窗口过期时还没有匹配到 click 就会当作 negative sample，这里说的窗口与上面提到的 waiting window 相匹配。facebook 使用 scribe 实现了这一过程，更多公司使用 Kafka 完成大数据缓存和流处理。
数据流保护机制：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 的比较如下：
可以看到当采样率是 10% 时，相比全量数据训练的模型，仅损失了不到 1% 的效果。
另一种方法 negative down sampling 保留全量正样本，对负样本进行降采样。除了提高训练效率外，负采样还直接解决了正负样本不均衡的问题，facebook 经验性的选择了从 0.0001 到 0.1 的一组负采样频率，试验效果如下：
大家可以看到，当负采样频率在 0.025 时，loss 不仅优于更低的采样频率训练出来的模型，居然也优于负采样频率在 0.1 时训练出的模型，虽然原文没有作出进一步的解释，但推测最可能的原因是解决了数据不均衡问题带来的效果提升。
负采样带来的问题是 CTR 预估值的漂移，比如真实 CTR 是 0.1%，进行 0.01 的负采样之后，CTR 将会攀升到 10% 左右。而为了进行准确的竞价以及 ROI 预估等，CTR 预估模型是要提供准确的有物理意义的 CTR 值的，因此在进行负采样后需要进行 CTR 的校正，使 CTR 模型的预估值的期望回到 0.1%。校正的公式如下：
其中 q 是校正后的 CTR，p 是模型的预估 CTR，w 是负采样频率。大家可以利用简单的转换关系就可以得出上述公式，有兴趣的同学可以手动推导一下。
至此，我们介绍完了 facebook 这篇经典的 CTR 预估论文，可以看到虽然五年过去了，我们仍能从中汲取不少模型改造和工程实现的经验，就我个人来言，最值得学习的有下面三点：
特征工程模型化。五年前在很多从业者还在通过调参经验尝试各种特征组合的时候，利用模型进行特征自动组合和筛选是相当创新的思路，也几乎是从那时起，各种深度学习和 embedding 的思想开始爆发，一脉相承的发扬着特征工程模型化的思路。
模型复杂性和实效性的权衡。对 GBDT 和 LR 采用不同的更新频率是非常工程化和有价值的实践经验，也是对组合模型各部分优点最大化的解决方案。
有想法要用数据去验证。这其实是我读完这批文章最大的感触，在做算法工程师的过程中，我们其实是有很多直觉上的结论，比如 data freshness 的影响有多大，GBDT 应该设置多少颗子树，到底是应该用负采样还是 uniform 采样，针对这些问题，facebook 告诉你的是，用数据说话，无论是多么小的一个选择，都应该用数据去支撑，这才是一位工程师严谨的工作态度。
最后惯例提出两个问题供大家讨论：
如果采用 random forest 替代 GBDT，有哪些优点和缺点？
GBDT+LR 这个模型结构，是否能够有效处理大量 ID 类特征，为什么？如果希望处理大量 ID 类特征，我们应该如何改进这个模型？
参考资料：
Practical Lessons from Predicting Clicks on Ads at Facebook
Computational Advertising Paper List
