点击率预测综述 ( 下篇）

接《 点击率预测综述 ( 上篇）》

4. 几种常用点击率模型介绍

4.1 BOPR

[2]是微软内部竞赛出来的一个算法，也被后续很多算法作为对比的 baseline。

这个算法的细节可以直接去看原文，这里只对优劣做一个简单介绍。该算法的基本思想是参数 w 是一个先验分布为正态分布的分布，参数为 u、ó；在贝叶斯框架下，每一个样本都是在修正对应的分布参数 u、ó；对应的更新公式为

该模型的优点是基于贝叶斯模型，因此可以做到在线学习，每个样本都可以对参数进行微调，同时 online learning 带来了在线学习的能力，可以及时应对用户兴趣的变化。

不足之处在于每个 feature 对应权重都需要两个参数来描述，模型的尺寸是 lr 的两倍，在复杂模型场景下这个成本可能比较难接受。

从文末的评测来看，bopr 和朴素贝叶斯相比，bopr 能在比较宽的 pctr 维度很好的拟合经验点击率的情况。

4.2 GBDT+LR

[3]是 14 年 facebook 出的一篇 ctr 领域非常经典的论文，15 年去北京参加qcon 大会时，机器学习方向的演讲几乎都提到了这篇论文，可见该方法的成功。

前文提到，随着特征的增加，特征组合这件事将变得尤为困难，人力很难应付。假如一个点击率预测的系统涉及到 100 个特征，则熟悉二项式定理的同学可以心算出来所有可能的组合特征接近 2100；这个数据有多恐怖呢？一张纸对着 50 次对应 250，出来的高度是 1125899906 米，大约是几十万个珠穆朗玛峰那么高。而特征组合是在特征离散化以后做的，稍微几个特征分桶可能就不止 100 了，再组合，特征就会爆炸掉。

特征爆炸带来两个问题，一是不太可能再用人力的方式去做特征组合的事，这简直就是太平洋里捞一个水分子了。另一个问题是维度灾难，这个可以参考我 km 另一篇文章。

[3]就是尝试提出一种解决特征组合问题的方案，基本思路是利用树模型的组合特性来自动做特征组合，具体一点是使用了 GBDT 的特征组合能力。整体架构如下：

先在样本集上训练一个 GBDT 的树模型，然后使用这个树模型对特征进行编码，将原始特征 x 对应的叶子节点按照 01 编码，作为新的特征，叠加到 lr 模型里再训练一个 lr 模型。预测的时候也是类似的流程，先对原始特征 x 通过 GBDT 计算一遍，得到叶子节点情况，以途中为例，如果 x 落到第一棵树的第二个节点，第二棵树的第一个节点，则转换后的输入特征为(0、1、0、1、0)；

GBDT+LR 模型确实明显优于单独的 LR 模型，我们在浏览器多个场景做了测试，auc 都有非常明显的提升，接近 10 个百分点。从训练来看，GBDT 也确实像 [4]所说那样，很容易过拟合，但叠加 lr 以后却能去的很不错的性能。GBDT 因为是在函数空间对残差进行连续的逼近，所以优点和缺点一样的明显；优点是可以逼近几乎任何函数的任何精度，缺点就是很容易过拟合，需要根据业务场景注意在树的棵数和深度上做一定的裁剪，才能平衡精度和过拟合。详细的推导请参看论文，我也只大概看明白原理，因为对泛函还不熟悉，以后有机会再来细讲这个模型的原理。

4.3 FTRL

FTRL 是从 RDA、FOBOS 等针对 lr 的在线学习算法改进而来，主要是工业界强烈的在线学习的需求驱动而来。有意思的是前面提到的微软的 BOPR 也是一种天然的支持在线学习的算法。为什么要做在线学习？有哪些注意点呢？

在线学习背后的理念是每个人的兴趣是 non-stationary 的，离线训练的模型在线上可能不能快速对用户最新的行为作出反应。为了解决这个问题，一种做法是我们加快模型的频率，比如原来一天更新一次，现在一个小时更新一次，这种做法有很明显的瓶颈，比如如果我们的时间窗设置的比较长，用一个月或者两个月数据来跑模型，则可能导致模型在更新间隙内完不成训练；如果我们采用增量训练的方式，则增量时间窗的设置是个技术活，太短，很多曝光对应的点击还没有上来，导致训练数据的无效曝光比例偏高，如果太长，可能跟不上节奏；这也是在线学习的一个难点，在线学习一般也不会每一个回流数据立马更新模型，这会导致模型震荡频繁，攒一小段时间是个不错的选择，为此 facebook 的系统里有一个 online joiner 的组件来做曝光和点击的归约。

今日头条披露的资料来看，在模型更新方面他们采用了增量更新+定时校准的策略；类似于在线学习+定时离线校准。这种策略应该也可以用到点击率的场景。

在线学习另外一个要重点解决的问题是学习率；离线训练的时候 sgd 往往使用一个公用的学习率η，但是在线学习这样做会带来问题的；因为样本分布不均衡，某些覆盖不是很高的特征对应的权重因为样本少得到的更新次数比较少，如果使用相同的学习率，则这些权重的收敛势必落后于覆盖率高的样本的特征对应的权重，尤其是有做学习率衰减的情况下；因此我们需要针对不同的权重来设置不同的学习率，做法也比较简单，基本思路是统计该维度样本数，多的衰减快点，少的衰减慢点以期能做到基本持平，详见 [5]，相关的 rda、fobos 已经是前浪了，没时间可以不看，有时间酌情。

这里也顺带提一下 ftrl 和 gbdt+lr 的关系，ftrl 主要是针对 lr 部分的 online learning；gbdt+lr 是两种不同模型的级联，这两个方案是可以很方便的糅合在一起的变成 gbdt+ftrl-lr；但这里 gbdt 的更新没法做到 online learning；可以做定期更新。理论上这种做法可能会效果更好一点。

4.4 FM

[6]提出的 fm 是一种可以自有设置特征组合度数的回归算法，通常 d=2 的 fm拟合公式如下

!

选择一种损失函数后很容易用 sgd 之类的优化算法来计算 w 和 v；原文这块的论述有点模糊，没有指明目标函数的情况下对拟合公式使用了 sgd，有兴趣的同学可以一起探讨。

Fm 的优势是因为可以自动进行特征间的组合，这解决了两个问题，一个是系数数据因为特征组合而能得到不错的 backgroud model 效果；另一个是特征组合解决了人工组合的尴尬，GBDT+LR 与此有异曲同工之妙，因此 FM 常常和 GBDT+LR 来一起讨论；从应用范围来看，业界 GBDT+LR 的使用范围应该是比 FM 要广的；国内我所知只有世纪佳缘 [7]是使用 FM 替代了 GBDT+LR。

FM 的另一个优点是会算出每个 feature 对应的向量 v；这个向量可以看做对 feature 的一种 embeding，例如后面 WDL 的场景，或者是 GBDT+LR 里对 categorical feature 做 embeding，后者我们正在计划尝试；前者因为可以通过 joint learning 直接学习最佳的 embedding 向量，所以一般不会单独使用 fm 来对 feature 做 embeding。

FM 的不足之处是在 dense 数据集情况下，反而可能表现不佳，鱼与熊掌不可兼得啊！

4.5 FFM

[8]介绍了 FFM 在美团的一些应用，个人理解是 FM 的一个小改版，不多说。

5. 新用户：MAB、CB、泛精准

对于系统的一个新用户，在没有历史消费数据的情况下，想要预测用户的点击率是一件比较困难的事；这里提供一种按照数据丰富度划分阶段的思路；义工划分为四个阶段：1.全新用户；2.少量消费数据用户；3.一般消费数据用户；4.充分消费数据用户；每一个新用户和系统的交互分为这四个阶段，分段的标准可以根据具体场景的实验数据来拍一下脑袋，在不同的阶段，我们是用不同的策略来进行用户数据的获取。

全新用户阶段，将用户和广告的匹配看做一个多臂老虎机（MAB）问题，可供使用的 bandit 方法有 UCB[9]、汤普森采样 [10]等。这两者的区别在于 ucb 几乎没有随机性，根据预估收益率+置信度作为总的排序 score，选择最高的悬臂；汤普森采样是贝叶斯框架，将每个悬臂的收益概率 r 视为一个 Beta 分部；根据历史情况修正分部的参数，而需要选择的时候则对每个悬臂的分布进行采样，根据采样结果排序来选择悬臂，保持较好的随机性；在一些内容推荐系统也会经常使用汤普森采样来解决 expolore&exploit 问题。在点击率场景的全新用户阶段，我们使用 mab 不失为一个选择。

在少量消费数据阶段，我们可以使用 CB[11]，CB 的核心思想是给用户展示他消费过的物品最相似的物品，比如一个用户消费了盗梦空间，则他有可能想继续观看泰坦尼克号。CB 的难点在于对物品向量化。

对于第三个阶段的用户，有一定的数据又不是很多，此时可以采用 这种降级的 ctr 模型，并且对其中的一些特征使用 smooting 技术，如贝叶斯平滑、指数平滑等；可以参看后面部分的接受。

第四个阶段就是常规用户，使用我们前面提到的各种点击率模型就好了。

6.新广告：lookalike、相关广告信息挖掘

新广告的点击率预测是另一个比较大的话题，这里我先简单分为两类，一类是临时性投放，比如某个新广告主偶然来试投一下汽车广告。如果广告主能提供一批种子用户，我们可以使用 lookalike 的方法来优化之，可以参考 fandy 的，我理解是一个迭代处理，先基于种子用户和采样用户训练一个 model，然后用 model 对采样的用户做一轮 predict，把得分高的用户刨除掉，剩下的用户定义为有效负用户，然后再和种子用户一起训练一个新的 model，将这个 model 作为候选 predict 并圈取用户的指示器。

另一类新广告是广告主或者代理商在广告投放系统里投放的一个新的素材，这个时候虽然广告是全新的，但是我们任然可以从系统里挖掘出大量相关的信息，比如该广告对应的 pushlisher 的历史信息，对应的 advertiser 的信息，对应类比的信息等，具体可以参考 [12]。

7. rare event：贝叶斯平滑、指数平滑

这节单独介绍下 [13]这篇论文，和 6 不同，这篇文章主要是针对发生频率比较低的事情的一些优化，可以用于新广告，但也可以用于比较老只是频率低的广告。

想法的初衷是我们经常需要使用一些点击率特征，比如曝光两次点击一次我们可以得出 0.5 点击率，另一个广告是曝光一万次，点击五千次，也可以得到 0.5 的点击率，但是这两个 0.5 代表的意义能一样吗？前者随着曝光的增加，有可能会快速下滑，为了解决经验频率和概率之间的这种差异，我们引入平滑的技巧。

[13]中使用了指数 decay 和 beta 分布平滑两种技巧，这两个技巧也可以一起使用。对于 decay，既可以将历史信息融入到特种里，又保持了对历史信息的以往速度。是一个不错的平衡，从各个实践来看，使用平滑对模型性能都会有显著的提升。

8.WDL 介绍

随着深度学习的火爆，在图像识别、推荐系统等领域都出现了深度学习的模型，那么深度学习是否可以应用到点击率模型呢？答案是肯定的，在国内公开的资料中可以查到深度学习点击率的资料应该是 kintocai 所作，之前 kinto 也在内部做过一次分享，主要的出发点是 google 的这篇 paper[14];核心的图片截取如下

从这张图可以看出，在最上层还是使用了 lr 模型，和 GBDT+LR 对比可以看出两个模型的相似性和区别，前者使用 GBDT 来做特征的组合， 后者使用两项不同的技术来处理，首先是对 categorical feature 进行 embeding，然后和 continous feature 一起 concatenate 成一个向量，通过三层 relu 网络来做特征的表示学习；另一方面对于 categorical feature 还可以进行人工交叉组合，与左边网络自己学习到的特征一起加入到顶层 lr 模型里作为最终的特征。

这里需要提到的一点是对于 categorical feature 的 embeding，没有使用独立的 FM 之类的方法，而是通过 joint learning 直接学习出来的，具体做法是对最 embeding 层使用类似 EM 的做法，固定 W 后使用 bp 训练向量，交替进行。和 FM 之类独立训练的 embeding 向量相比，为什么联合训练的向量可能会更好呢？这个思想起源是哪里呢？

第一个问题我认为联合训练的 embeding 向量确实会比 FM 单独 embeding 出来的要好，原因比较细微，熟悉 CF 发展流程的同学应该知道，对传统 Item-based CF 和 User-based CF 的一个改进就是将 pearson 系数替换为可以联合训练的 wij，以 capture 到数据之间 interpolation 信息。详细的介绍可以参考我下一篇关于 CF 的综述。

使用了类似 joint learning 以同时获得 embeding 向量和权重矩阵的还有 [15]。有兴趣的可以参考。

关于 WDL 的性能，普遍认为会比传统 LR 高两位数百分点，浏览器正在尝试在 app 推荐场景下做一个横屏，从目前初步结论来看，GBDT+LR 相比于纯 LR 大约是两位数的提升，而 WDL 还没有看到明显效果，不过我们会进一步在参数调优上下些功夫，以期取得更好的效果。

WDL 的缺陷主要体现在两方面，一方面是在线 predict 时的性能瓶颈决定不能使用太宽、太深的网络，另一方面是如果做 online learning，这个问题据说百度凤巢是有做过，具体方案不得而知。

9. 强化学习

[16]对强化学习做了基本介绍，而国外对强化学习投入比较大也引起足够关注的应该是 DeepMind 以及阿尔法狗了。个人看来强化学习和监督学习的关系有如随机过程和概率论的关系。前者强调的是动态过程，后者强调的是静态概率。从这个角度讲，前面所有的点击率模型都是在追踪静态概率，哪怕使用 online learning 也只是做了某种程度的 approximation。

是否可以直接使用强化学习来做点击率或者推荐呢？答案我觉得是肯定的。这方面阿里应该是走在前沿，[17]中提到因为采用深度强化学习和自适应学习的技术，阿里的双十一销量有 10%-20%的提升。这是一个非常恐怖的数字，尤其是在阿里这样的体量下。请允许我引用其中一段文字来做个简单说明

“ 2014 年双 11 通过排序特征实时，引入商品实时转化率，实时售罄率模型进入搜索 match 和 rank，让售罄商品额无效曝光大幅减少，并实现了成交转化的大幅提升；2015 年双 11 推出双链路实时计算体系，在特征实时的基础上，引入排序因子的在线学习，预测，以及基于多臂机学习的排序策略决策模型，在预热期和双 11 大幅提升了搜索流量的成交转化效率；2016 年实时学习和决策能力进一步升级，实现了排序因子的在线深度学习，和基于强化学习的排序策略决策模型，从而使得淘宝搜索的智能化进化至新的高度，并在今年的双 11，分桶测试效果表明，成交金额取得了近 20% 的大幅提升。”

从这段描述可以看出阿里的技术演进思路，特征实时化->MAB->DL->RL。这套方案能否在鹅肠或者浏览器内部找到落地场景是我比较感兴趣的一个地方，接下来也会花一些时间来调研强化学习的。

结语

本文主要对笔者一段时间一来的阅读做一个小结，在机器学习领域，书籍出版是远远落后于业界知识更新的，这就逼迫我们每个从业者都需要大量阅读资料和论文，对一个已经工作几年的后台开发来说，是一个不小的挑战。

笔者为此做了不少的准备，包括花了两年的晚上时间把数学分析、概率论、线性代数、数值计算等数学基础复习一遍；然后才能够相对比较顺利的阅读 paper。在领略了一些点击率和算法的文章以后，深深感觉大家能看到的书籍太少，因此尝试做一个总结，试着梳理一个脉络，给后来者一个学习的 roadmap。然而由于本人生性驽钝，错误不实之处在所难免，唯望方家莫笑，以此顽石引出美玉，提升自己造福后人，如是而已。以上。

引用

1. Predicting Clicks:
Estimating the Click-Through Rate for New Ads；
2. Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine；
3. Practical Lessons from Predicting Clicks on Ads at Facebook；
4. greedy function approximation:a gradient boosting machine
5. Ad Click Prediction: a View from the Trenches
6. Factorization Machines.SteffenRendle
7. http://www.csdn.net/article/2015-09-30/2825828
8. http://tech.meituan.com/deep-understanding-of-ffm-principles-and-practices.html
9. https://zhuanlan.zhihu.com/p/21388070
10. An Empirical Evaluation of Thompson Sampling
11. Content-based Recommendation Systems；
12. Predicting Clicks:
Estimating the Click-Through Rate for New Ads
13. Click-Through Rate Estimation for Rare Events in Online Advertising
14. Wide & Deep Learning for Recommender Systems；
15. Deep Neural Networks for YouTube Recommendations
16. Reinforcement Learning： An Introduction
17. http://www.10tiao.com/html/639/201703/2247484414/1.html
18. Predictive Model Performance: Offline and Online Evaluations