@TOC
论文名称：Practical Lessons from Predicting Clicks on Ads at Facebook
原文地址：Facebook
⚡本系列历史文章⚡
【推荐系统论文精读系列】(一)--Amazon.com Recommendations
【推荐系统论文精读系列】(二)--Factorization Machines
【推荐系统论文精读系列】(三)--Matrix Factorization Techniques For Recommender Systems
【推荐系统论文精读系列】(四)--Practical Lessons from Predicting Clicks on Ads at Facebook
【推荐系统论文精读系列】(五)--Neural Collaborative Filtering
【推荐系统论文精读系列】(六)--Field-aware Factorization Machines for CTR Prediction
【推荐系统论文精读系列】(七)--AutoRec Autoencoders Meet Collaborative Filtering
【推荐系统论文精读系列】(八)--Deep Crossing：Web-Scale Modeling without Manually Crafted Combinatorial Features
【推荐系统论文精读系列】(九)--Product-based Neural Networks for User Response Prediction
【推荐系统论文精读系列】(十)--Wide&Deep Learning for Recommender Systems
【推荐系统论文精读系列】(十一)--DeepFM A Factorization-Machine based Neural Network for CTR Prediction
【推荐系统论文精读系列】(十二)--Neural Factorization Machines for Sparse Predictive Analytics
一、摘要
点击预测系统大多是以在线广告系统维中心，每天7亿的日常活跃用户和超过1百万的活跃广告，因此预测FaceBook上的广告点击率是一项具有挑战的机器学习任务。本片论文中我们介绍了一个模型采用决策树和逻辑回归结合的模式，融合模型的表现胜过它们自己单独建模的效果3%，这个一个重大的影响对于整个系统的表现。
我们然后探索了一些基本参数对我们真个系统的预测表现进行了探索，不足为奇，我们获得来了一个重要的结论就是：使系统整体表现提高最重要的就是拥有正确的特征（那么捕捉了用户或者广告的历史信息），这些特征在所有的特征中占据着主导地位，一旦我们拥有了正确的特征和正确的模型（决策树+逻辑回归），其它的特征几乎发挥很小的作用（尽管小的提升在整个业务范围内也是很重要的）。挑选一些最优的数据处理方式，例如数据新鲜度、学习率模式、数据采样，这些都会轻微的提升模型的性能，但是提升的幅度仍会小于拥有高效的特征组合或者是使用正确的模型。
二、简介
数字广告使一个几十亿美元的工业并且每年都在急剧地增加。在众多互联网广告平台，支配广告是动态的，居于观察到的用户返回合理为它们调整用户的兴趣。机器学习发挥了重要的作用在计算预测效用和一个用户对于一个广告的点击率，并且这种方式会增加整个市场的效率。
在2007年Varian和Edelman发表了一篇开创性的论文，描述了出家和每次的点击拍卖。同年，微软基于相同的拍卖模型构建了一个赞助搜索市场，这个广告拍卖的有效性依赖于点击率预测的精度和校准。点击率预测系统需要健壮性和适应性，并且有能力从海量数据中进行学习。这篇论文的目标就是分享来自实验的观点，这些实验考虑了这些需求并且在真实世界中的数据进行的执行。
在赞助的搜索广告，用户搜索被用于去检索候选的广告，这些广告可以隐式或者显示的进行匹配用户的搜索，说白了就是可以从用户每次的搜索匹配对应的广告，但是FaceBook与微软不同，它的用户搜索较少，广告和搜索几乎没什么关联，它们只和特定的人口特征和兴趣目标相关。因此，当一个用户访问Facebook时符合条件被展示的广告要远大于基于搜索的模型。
为了解决每次请求的候选广告非常多的问题，当一个用户访问Facebook时，这时请求广告就会被触发，我们首先建立了一个不断增加成本的级联分类器。本篇论文中，主要研究级联分类器的最后阶段的点击预测模型，即对最终候选广告集进行预测的模型。
我们发现了一种混合模型（决策树+逻辑回归），这种模型比这两种方法各自的性能都要好3%以上。这种提升在整个系统的表现能力上是有重大意义的。大量的基本参数会影响最终的预测系统的表现。正如预期的那样，最重要的就是拥有好的特征组合，这些特征会捕捉用户或者广告的历史信息并且还会占据主导地位在所有的特征中。一旦我们有了这些特征并且使用了我们的混合模型，其它的特征因子将起到很小的作用。挑选一些最优的数据处理方式，例如数据新鲜度、学习率模式、数据采样，这些都会轻微的提升模型的性能，但是提升的幅度仍会小于拥有高效的特征组合或者是使用正确的模型。
三、实验设置
为了实现严格的控制实验，我们准备了线下数据通过挑选出任意一周的数据。为了保持相同的训练和测试集数据分布在不同的条件下，我们准备的线下数据是与线上观测到的数据是相似的。我们将线下数据分成了训练集和测试集，并且使用它们去模型数据流，对于线上训练和预测。
3.1 评估指标
因为我们最关心的是特征对整个模型的影响，所以我们使用了预测准确率作为衡量指标而不是以和利益或者收入相关的指标。我们使用Normalized Entropy(NE)和Calibration作为我们主要的评估指标。
NE的评估公式为：
Calibration评估指标：Calibration是平均估计CTR和经验CTR之比，换句话说，它是预测点击次数与实际观察到的点击次数之比，它是个非常重要的指标，准确预测CTR是在线招标和拍卖成功的关键。
注意到，AUC也是一个非常好的评估指标对于衡量排序质量如果不考虑Calibration。在真实的环境中，我们期望的是准确的预测而不是仅仅得到最优的排序。
四、预测模型结构
4.1 决策树特征变换
由于线性模型过于简单，它只能够捕捉线性特征，对于非线性是无能为力的，这就会导致如果使用逻辑回归进行建模会导致丢失很多数据信息，虽然现在很多模型都可以捕捉非线性关系，但是它们的计算复杂度大，线性回归算法简单，容易实现并行，对于海量数据能大幅提高计算效率，那么我们就希望有没有一种方法可以转化特征，变成线性回归可以拟合的数据。
两种转化特征的方法分别是：
- 连续型：将特征进行分箱，然后将每个箱的索引作为类别特征
- 类别型：对所有类别特征做笛卡尔积，产生组合特征
对于类别特征做笛卡尔积产生的新特征，不是所有的特征都是有用的，那么怎样才能组合出高效的特征呢。
我们发现梯度提升树是一个强有力而且很方面去实现非线性和成对特征组合。我们将每个独立的树作为一个分类特征。然后使用OneHot编码将其转化成特征。例如，如果一个梯度提升树有两个子树，第一颗子树有3个叶子节点，第二颗子树有两个节点，假如样本x分别落在了第一个子树的第二个叶子节点，落在了第二颗子树的第1个叶子节点，那么我们就可以为其进行编码为【0，1，0，1，0】。在每次学习迭代的过程中，一个新的树会拟合前一棵树的残差。我们能够理解梯度提升树基于转化作为一个有监督的特征编码，会将一个真值向量转化成一个稠密的二值化向量。从根节点进行遍历到叶子节点，这时就会呈现一个规则对于某种特征，可以理解为这个样本可以按照这个路径的特征来进行区分。梯度提升树是以一个批次的方式进行训练。
我们执行了这个实验去展示将提升树产生的特征输入到线性模型的效果。在这个实验中，我们对比了逻辑回归模型，一个是带有融合特征，另外一个是原始特征，我们也使用了一个梯度提升树模型仅仅用于对比。
提升树产生的特征帮助我们的模型减少3.4%的损失使用NE熵，这是一个重大的提升。
4.2 数据新鲜度
点击预测系统通常被部署在一个动态的环境下，这个数据的分布会随着时间而改变。我们研究了训练数据新鲜度对于预测表现的影响。为了验证这个，我们训练了一个模型根据某一特定天的数据，然后进行验证测试使用之后连续几天的数据，我们进行这个实验使用的是梯度提升树和逻辑回归的模型带有融合获得的特征。
在这个实验中，我们训练了一天的数据，然后对改天接下来的六天的数据进行了评估并且计算了NE。
结果表明，预测精度随着每天的推移，训练集和测试集的精度都有所下降，很容易看出，如果我们从每周训练一次到每天训练一次，我们的模型的表现几乎可以提高1%。
这些发现表明，我们是很值得每天进行重新训练模型的。一个选择就是我们每天将会有一个重复的工作就是重新训练模型，可能是以批次进行训练。重新训练梯度提升树模型的时间可能依赖不同的因素，例如：训练集的规模大小、树的数目、每棵树叶子节点的个数、CPU、内存大小等。如果我们采用单核CPU进行训练百万级别的数据，使用几百棵树的模型进行训练，那么我们的训练时间可能超过24个小时。但实际情况是，如果我们采用多核并行训练，训练时间可能缩小到几个小时内，原因是多核并行可以将整个训练集加载到内存中进行计算。
梯度提升树需要每天重新训练或者每两天训练一次，但是我们的线性分类器需要通过在线学习进行实时学习。
4.3 在线线性分类器
为了最大化数据的新鲜程度，一个选择就是在线训练线性分类器，也就是说，当推荐广告到达的时候，我们就会为其打标签，然后进行建模。在接下来的章节，我们会描述一个基础架构，能够产生实时的训练数据。在这个部分我们会评估几种设置学习率的方式对于逻辑回归使用SGD进行求解。我们然后对比最好的变体对于在线学习与BOPR模型。
1.Per-coordinate learning rate：
2.Per-weight square root learning rate：
3.Per-weight learning rate：
4.Global learning rate：
5.Constant learning rate：
前三个设置学习率的模式每个特征之间是独立的，而后两个对于所有的特征学习率是相同的。所有可以调节的参数都会使用网格搜索进行优化。
对于持续学习，我们将学习率下界设置为0.00001，我们训练和测试是使用相同的数据，然后使用上述的几种设置学习率的模式然后进行对比。
从上述的结果，我们发现，SGD使用每个可调节的学习率实现了最好的预测精度，大约比使用每个权重的学习模式的NE低了大概5%。使用square root 和constant的学习模式是差不多的。另外两个学习模式比这几个的精度都要差。全局学习率模式失败主要是由于训练集的样本数据对于每个特征的分布不均衡。因为每个训练样例可能包含不同的特征，一些受欢迎的特征将会得到更多的训练相对于其它的特征。在全局学习率的模式下，对于较少的示例将会减小的非常快，并且阻止了算法的收敛。尽管per-weight学习率模式解决了这个问题，但是它仍然失败了，因为它将会减少所有特征的学习率。训练停止太早，会导致模型只收敛到局部最优位置。这也就是为什么，这个学习率模式会是所有选择中表现最差的。
我们执行了一个实验去对比使用per-coordinate SGD和BOPR在同一数据集上的表现。我们给出了相似的定性模型更新方程。结果BOPR和SGD有着非常接近的预测表现使用NE或者是calibration指标。
LR相对于BOPR的一个优点是模型大小为一半，因为每个稀疏特征值只惯量一个权重，而不是均值和方差，在执行过程中，较小的型号可能导致更好的缓存局部性，从而加快缓存查找速度。在预测是的计算费用方面，LR模型只需要在特征向量和权重上求一个内积，而BOPR模型则需要两个内积作为方差向量和带特征向量的均值向量。
与LR相比，BOPR的一个重要优点是它是一个贝叶斯模型，它提供了一个完全的点击概率分布，这可用于计算点击分布的百分位数，可用于探索或者开发新的学习方案。
五、在线数据连接器
之前的部分表明新的数据会导致增加预测精度，它也呈现了一个简单的模型架构，就是线性分类器是在线学习。
这个部分介绍了一个实验系统能够产生实时的训练数据用于训练线性分类器通过在线学习。我们将使用这个系统作为在线连接器，去将标签（用户点击或不点击）与训练数据（推荐广告）连接起来作为新的训练输入数据。
这和Google Advertising System被用于流计算的例子十分相像。在线数据连接器会输出一个实时的训练数据流给一个结构叫做Scribe。我们定义广告被点击为正样本，不点击为负样本，但是对于推荐广告对于用户来说是没有不点击的按钮的，那么我们就无法判断用户是否会点击该广告。对于这个原因我们将考虑使用一个时间停留窗口，如果当一个广告出现后，如果在指定的时间内用户没有点击，我们将视为用户没有点击。关于这个时间窗口的等待时间需要仔细设定。
- 点击时间长：会导致实时数据的延误，增加分配给缓冲的内存用于等待用户点击的信号
- 点击时间短：会导致数据的丢失，如果时间太短，可能一个用户会点击这个广告，由于时间短，在该时间内还没有点击就结束了
所以针对这个现象，就必须时间和点击覆盖取得权衡。
六、包含内存和延迟
6.1 提升树的数目
如果树的棵数越多，模型对一个预测所需要的时间就越长，在这个部分，我们将会研究提升树的数目对于评估精度的影响。
我们改变树的个数从1-2000，并且训练这个模型使用一整天的数据然后进行预测评估使用接下来一天的数据，我们强制约束每棵树的叶子节点个数不超过12个。和之前的实验一样，我们使用NE作为评估准则。
通过结果我们发现随着树的个数越多，模型的NE越来越小，但是当树的个数达到500棵左右，NE的下降趋势越来越小，而且最后增加1000棵树减少的NE少于0.1%。而且我们还看到使用NE submodel2的模型当树的棵数达到1000时，模型的效果反而有点倒退，原因就是随着树的数目增加，模型产生了过拟合效应。这是因为submodel2的数据集的规模相对于模型0和模型1的数据集规模小了近4倍左右。
6.2 增加特征的重要性
特征数目是模型的另外一个特征能够影响均衡评估精度和预测时间。为了更好的了解特征数目的影响，我们首先应用一个特征到每个特征中。
为了衡量一个特征的重要性，我们使用了statistic Boosting Feature Importance，这样的目的是为了捕获计算每个特征减少的损失。在进行构建每个节点的过程中，挑选最好的特征作为分割节点，然后去最大化平方损失，因为一个特征可能用于多棵树的构建，所以每个特征的损失需要计算所有树对于这个特征的损失之和。
结果表明，top10的特征的重要性占据了所有的一半，然而最后300个特征贡献却不足1%。基于这个发现，我们进一步研究了top10、20、50、100和200个特征的影响，并且它们是怎样影响模型的表现的。
6.3 历史特征
在提升树模型中使用的特征主要可以分成两类：上下文特征、历史特征。
- 上下文特征：依赖于当前的上下文信息，比如用户设备的型号、用户当前所在的页面
- 历史特征：依赖于用户和广告先前的交互信息，比如这条广告上周的点击率或者用户的平均点击率
在这个部分，我们将会研究系统依赖这两类特征的表现。首先我们会先查两类特征的的相关的重要性。我们通过重要性将特征进行排序，然后计算每个历史特征的重要性。
通过结果表明，我们可以发现历史特征可以提供更多的解释性比上下文特征。最重要的10个特征都是基于历史特征。在前20个特征中，只有两个特征是上下文特征。为了更好的了解每种类型特征的对比，我们训练了两个提升树模型分别仅仅使用上下文特征和历史特征，然后对比两个模型和全部特征的比较。
从结果我们可以发现历史特征是发挥了更大的作用比上下文特征。
但是上下文特征也有个重要的作用就是能够解决冷启动问题，对于新的用户和新的广告，上下文特征是不依赖于点击率进行预测的。
接下来，我们评估了训练模型只使用上下文特征和历史特征在连续周的训练数据针对于数据新鲜度的问题，我们发现有着上下文的特征是更加依赖于数据新鲜度的相对于历史特征。这符合我们的直觉，因为历史功能描述了长期积累的用户行为，这比上下文功能更稳定。
七、处理海量数据
Facebook每天的广告数据多大几亿的数据量，为了减少训练的消耗，我们通用的做法就是减少训练数据的列数。在这个部分我们会评估两种下采样的方式，分别是：uniform subsampling和negative down sampling。我们会训练两个包含600棵树的模型，然后使用calibration和NE作为评估指标进行评估。
7.1 Uniform subsampling
对训练行进行均匀子抽样是一种很有吸引力的减少数据量的方法，因为它既易于实现，而且生成的模型可以在不修改下采样训练数据和非下采样测试数据的情况下使用。在这一部分，我们评估一组粗略指数增长的子抽样率。对于每个速率，我们训练一个增强的树模型，以该速率从基础数据集采样。我们分别设定了采样率为【0.001，0.01，0.1，0.5，1】
通过结果可以表明，我们仅仅使用总共数据10%的数据，我们的模型表现仅仅下降了1%，可以看到均匀采样是有一定帮助的，在牺牲小的精度换的更高的时间效率。
7.2 Negative down sampling
类别不平衡已经被许多研究者进行研究，并且表明类别不平衡对模型的表现有着重大的影响。在这个部分，我们使用Negative down sampling去解决这个问题。我们使用不同的比率尽心采样，然后去测试模型的精度，我们设定采样率分别为【0.1，0.01，0.001，0.0001】。
从结果发现，我们能够看到negative down sampling采样率有着重大的影响对于模型的表现，最好的表现是我们将这个比率设立在0.025。
八、总结
我们已经呈现了一些来自实验的经验关于Facebook广告数据。这启发了一个很有前途的混合模型体系结构，用于点击预测领域。
- Data freshness matters：我们至少每天都要将模型进行重新训练，本篇论文中我们进一步研究了不同种的在线学习模式。我们也给出了基础架构允许生成实时的训练数据。
- 使用梯度提升树进行转化特征极大的增加了线性分类器的预测精度。这启发了一种混合模型体系结构，该体系结构将增强决策树和稀疏线性分类器连接起来。
- 最优在线学习模式：LR与预协调学习率，最终与BOPR的性能相当，并优于所有正在研究的LR结合SGD的方案
我们已经描述了在大规模机器学习应用程序中保持内存和延迟的技巧
- 我们已经提出了改进决策树的数量和准确性之间的权衡。保持树的数量小有利于保持计算和内存
- 提升树给予了一个方便的方式去做特征选择通过特征的重要性，我们可以大幅减少主动特征的数量，同时适度降低预测精度
- 我们分析了历史特征和上下文特征的影响对于模型效果。对于广告和用户的历史特征，这些特征会提供更有的预测精度比上下文特征。
最后，我们讨论了对训练数据进行子采样的方法，既可以是一致的，更有趣的是，也可以是有偏差的，即只对负样本进行子采样。
Preferences
[1] R. Ananthanarayanan, V. Basker, S. Das, A. Gupta, H. Jiang, T. Qiu, A. Reznichenko, D. Ryabkov, M. Singh, and S. Venkataraman. Photon: Fault-tolerant and scalable joining of continuous data streams. In SIGMOD, 2013.
[2] L. Bottou. Online algorithms and stochastic approximations. In D. Saad, editor, Online Learning and Neural Networks. Cambridge University Press, Cambridge, UK, 1998. revised, oct 2012.
[3] O. Chapelle and L. Li. An empirical evaluation of thompson sampling. In Advances in Neural Information Processing Systems, volume 24, 2012.
[4] B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. In American Economic Review, volume 97, pages 242–259, 2007.
[5] J. H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29:1189–1232, 1999.
[6] L. Golab and M. T. Ozsu. Processing sliding window ¨ multi-joins in continuous queries over data streams. In VLDB, pages 500–511, 2003.
[7] T. Graepel, J. Qui˜nonero Candela, T. Borchert, and R. Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising in Microsoft’s Bing search engine. In ICML, pages 13–20, 2010.
[8] H. B. McMahan, G. Holt, D. Sculley, M. Young, D. Ebner, J. Grady, L. Nie, T. Phillips, E. Davydov, D. Golovin, S. Chikkerur, D. Liu, M. Wattenberg, A. M. Hrafnkelsson, T. Boulos, and J. Kubica. Ad click prediction: a view from the trenches. In KDD, 2013.
[9] M. Richardson, E. Dominowska, and R. Ragno. Predicting clicks: Estimating the click-through rate for new ads. In WWW, pages 521–530, 2007.
[10] A. Thusoo, S. Antony, N. Jain, R. Murthy, Z. Shao, D. Borthakur, J. Sarma, and H. Liu. Data warehousing and analytics infrastructure at facebook. In SIGMOD, pages 1013–1020, 2010.
[11] H. R. Varian. Position auctions. In International Journal of Industrial Organization, volume 25, pages 1163–1178, 2007.
[12] J. Yi, Y. Chen, J. Li, S. Sett, and T. W. Yan. Predictive model performance: Offline and online evaluations. In KDD, pages 1294–1302, 2013
