点击率预估是大数据技术应用的最经典问题之一，在计算广告，推荐系统，金融征信等等很多领域拥有广泛的应用。本文不打算对这个话题做个全面叙述，一方面这过于庞大，另一方面也已经有很多文章和演讲材料相当不错。本文只打算对已有的一些文字作个补充，从贴近实际的角度列举一些经过商业检验的点击率模型。
最经典的模型当然是逻辑回归，这是绝大多数商业公司的选择，简单的逻辑回归有实现容易，训练快速等优点。自从逻辑回归出现后，针对它的改进主要围绕两方面：如何正则化；如何最优化。正则化是机器学习的重要技术，它的主要目的是让防止模型过拟合，目前比较常用的正则化有L1和L2。通常L2在减少预测错误上表现更好，这是因为当两个特征相关时，L1会只选择一个，而让另外一个系数为0，因此可以产生稀疏解；而L2则会同时保留2个特征然后另它们的权重系数收缩。因此在数据维度有限时，L2会既有防止过拟合的优点，还不会导致模型预测损失。然而对于大规模机器学习框架，L1的稀疏解会更有吸引力，加入L1正则化的损失函数在优化后，绝大多数特征的权重都是0。这个特性可以大大减少点击率预估时的内存占用，并提高预测的速度。关于最优化，因为逻辑回归的损失函数是一个可以求导的凸函数，所以通常可以采用梯度下降或者拟牛顿进行最优化。不论是梯度下降，还是拟牛顿，都是频率派的最优化手段，贝叶斯学派也有自己的手段，这就是微软的AdPredictor提出的Bayesian Probit Regression[3]。AdPredictor有一些比较好的特性：它只需要一次迭代就可以收敛到最优解，而不是像梯度法或者拟牛顿法那样需要反复迭代；它不仅能预测出一个样本是正样本的概率，而且还可以给出对于这个概率预测值的置信度，因此很多在线广告公司都采用AdPredictor作为其点击率预估的方法。由于AdPredictor假设特征权重的先验分布遵循高斯分布，因此它相当于是L2正则化，这在许多大规模场景下难以接受，因此Google在13年发表的FTRL-Proximal提供了既是L1正则化，又具备AdPredictor优点的方案，FTRL-Proximal公式较多，读者可以从[7]获得更完整的叙述。
另一方面，回到模型本身，采用简单的线性模型会导致其他一些问题，比如高维场景下，究竟应当如何选择特征，大部分公司以来人工特征工程，随着过程深入，这种方式的收益会逐步达到上限。此外，简单线性模型无法捕捉特征之间的关联，这对于提升长尾用户行为的点击率尤其关键。有一些公司在这些方面也做了不少工作。首先比较重要的是Facebook的工作[4]，它的主要贡献在于通过利用非线性模型GBDT来进行特征选择，GBDT的输出作为线性模型逻辑回归的输入，通过这样的级联产生了明显的提升。这种手段应当可以作为新一代点击率预估系统的标准配置。
关于特征关联发现，先来看看排名第一的重定向广告公司Criteo的工作，在其点击率方案中[5]直接利用x_u*M*x_a来修正sigmoid函数，其中M为一个矩阵，x_u和x_a分别代表用户和广告特征，因此矩阵的大小取决于用户和广告特征的基数。通常，这两个数字都会很大，因此矩阵就会变得非常很大和稀疏，Criteo主要是借助于特征Hashing来减少矩阵尺寸，但这会导致冲突情况下无法判断是哪些特征组合信号强的问题。
再来看看Linkedin的LASER系统，由于LASER的作者源自Yahoo内容优化和推荐引擎团队，因此我们可以认为LASER跟Yahoo的工作如出一辙。
LASER点击率预估系统建模跟Criteo类似，都很简单直接，但是引入了上下文信息和更多特征。Y_ijt表示用户i对于广告j在上下文t下是否会点击。相比传统的逻辑回归只用简单的单一种类特征，LASER同时引入了用户特征x_i，广告特征c_j，以及上下文特征z_t，并且还要考虑这些特征之间的相互关联信息。这种建模的思路是解决冷启动问题的有效方式，因为这意味着即便没有很多的用户行为数据，也可以根据特征之间的关联信息作出不算太离谱的预测，当然，如果能够有用户行为数据，则可以锦上添花，为此，LASER把传统逻辑回归的Logit对数差异函数s_ijt分成图中所示的三个组成部分：第一个部分表达了概率密度跟所有一阶特征的关系；第二部分表达了概率密度跟所有特征之间关联程度的关系，包括用户特征和广告特征之间，广告特征和上下文特征之间，以及用户特征和上下文特征之间三种关联，因此称为二阶特征。整个模型如果光有这部分数据，也能够做出比较靠谱的预测，因此把这两部份加起来称作冷启动。相比之下，第三部分称作为热启动，用来表示用户当前对于冷启动选择出的Top K广告的偏好转移，为便于快速实时计算，这部分只包含广告和上下文的一阶特征。
可以看到，冷启动部分是LASER的主要工作，为训练这部分模型，LASER采用了交替方向乘子ADMM算法和L2正则化。ADMM是一种求解优化问题的计算框架，适用于求解分布式凸优化问题，ADMM 通过将大的全局问题分解为多个较小、较容易求解的局部子问题，并通过协调子问题的解而得到大的全局问题的解。在高精度要求下，ADMM 的收敛很慢；但在中等精度要求下，ADMM 的收敛速度可以接受（几十次迭代），因此ADMM非常适合大规模机器学习使用。在LASER里，又采用了一些额外优化，比如在不同分区同时进行计算，然后拿各分区的均值作为ADMM初始化参数，并且动态调节各分区计算的步长，这样在实际中把ADMM的迭代次数可以降到更低（如十多次迭代），因此一方面提升了训练性能，另一方面，也让整个冷启动部分的训练可以在一些不适合机器学习的框架如Hadoop上运行良好。在Spark还不稳定的2013年，这样做的价值是显而易见的。在稀疏方面，LASER没有考虑太多，因此大规模特征，比如百万维以上，是不能采用的。
再来看看阿里的[2]CGL，意思是Coupled Group Lasso，就是在损失函数中分别用Group Lasso去正则化用户特征和广告特征。在文章前边我们提到逻辑回归正则化主要有L1和L2，其中L1也可叫Lasso，L2也可叫Ridge，除了L1和L2之外，还有一些其他的手段，比如结合L1和L2优点的Elastic Net，而Group Lasso是对Lasso的推广，通过预先定义分组，以组为单位进行变量选择。为了建模特征之间的关联，CGL把普通逻辑回归的sigmoid函数修改为如下：
其中x_u和x_a分别代表用户和广告特征，因此x_u*M*x_a就可以表征特征之间的关联，而把矩阵M分解W*V'后就可以转化成图中的形式。采用这种方法改写的原因是避免引入过于庞大的M矩阵，因此模型的参数可以少很多。
在解决特征组合的手段中，除了上面提到的针对逻辑回归的工作之外，还有FM(Factorization Machine)，FM的建模跟LASER其实有一些类似，看下边公式就知道了，都是把线性关系和特征笛卡尔积共同列出做统一优化，因此也具备特征关联发现功能。
在以FM为核心的几个方案赢得一些点击率预估大赛之后，FM已经为更多的公司所接受，从竞赛和学术方案走向商业成熟。
前边列举的主要是机器学习手段，而我们知道深度学习系统也能够给点击率预估带来很大收益，百度是这方面的先行者之一，由于相关资料少我们就不单独列举了。由于LASER是笔者团队曾经实现的系统，因此篇幅有些不合时宜得多。关于如何设计一个现代的点击率系统，请诸位参考德川同学撰写的“关于点击率模型，你知道这三点就够了”一文，德川同学采用的GBDT+FM，是经过商业检验的优秀方案，也是非基于深度学习的点击率预估系统的最佳实践之一。
参考文献：
[1] LASER: A Scalable Response Prediction Platform For Online Advertising, Deepak Agarwal, WSDM 2014
[2] Coupled group lasso for web-scale ctr prediction in display advertising, Yan, Ling and Li, Wu-jun and Xue, Gui-Rong and Han, Dingyi, ICML 2014
[3] Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's bing search engine, Graepel, Thore and Candela, Joaquin Q and Borchert, Thomas and Herbrich, Ralf, ICML 2010
[4] Practical lessons from predicting clicks on ads at facebook, He, Xinran and Pan, ADKDD 2014
[5] Simple and scalable response prediction for display advertising, Chapelle, Olivier, ACM Transactions on Intelligent Systems and Technology 2014
[6] Click-through prediction for advertising in twitter timeline, Li, Cheng and Lu, Yue and Mei, Qiaozhu, SIGKDD 2015
[7] 冯扬, 在线最优化求解
