我们可以有很多种不同的方式来定义点击问题，本文会列举两种方式。
从分类角度出发，我们有很多算法可以用，比如贝叶斯分类器、svm、最大熵等等，我们也可以使用回归算法通过阈值来处理。
另一种看法假设每个
将用户是否点击一个物品看成回归问题以后，使用最广泛的模型当属逻辑回归LogisticRegression，[1]是一篇很不错的关于逻辑回归的综述，这里不打算展开讲逻辑回归的细节，简单做个介绍并说明实际使用中的一些注意点。
首先逻辑回归使用sigmoid函数来建模，函数如下：
该函数对应的图像如下所示：
LR的优点很明确，首先sigmoid函数的取值范围是0-1，刚好可以解释为点击概率，而输入的范围却可以很宽广。所以LR是历史最悠久、使用最广泛的点击率、转化率模型。
除了训练算法之外，LR模型最需要注意的是特征的呈现方式，从sigmoid的解析式可以看到LR其实是广义线性模型的一种（GLM），所以LR既不能很好地处理连续型特征，也无法对特征进行组合。相反，对于categoricalfeature反而处理得很好。因此，使用LR模型的时候往往伴随着大量特征工程方面的工作，包括但不限于连续特征离散化、特征组合等。
对于continousfeature，如年龄、薪水、阅读数、身高等特征，如果要添加到lr模型中，则最好先进行离散处理，也叫one-hot编码；离散化处理的方式有几种，等值分桶、等频分桶等；或者直接根据对业务的理解分桶。例如对于电商类，可能20岁以下的没有什么经济能力，20-40的经济能力差不多，这时候可以人工划分。
等值分桶是指每个区间同样大小，比如年龄每隔5岁为一个桶，则年龄特征变成一个20个区间（假设上限是100岁）的编码，如15岁对应（0、0、1、0、0、0…）。
等频分桶则是需要先对样本做一个分布统计，还是以年龄为例，首先我们要基于统计得到一个年龄分布直方图，通常这类特征都会大致符合正态分布，这时候对于中间阶段就需要多拆分几个桶，而对于两边的部分可以少一点；如0-16一个区间，16-18一个区间，18-20一个区间，20-30一个区间。目标是使得每个区间里的人数分布基本持平。
特征离散化的好处我理解是风险均摊，不把鸡蛋放在一个篮子里。举个例子，如果年龄特征对最终的预测结果很重要，则可能在LR模型中获得一个比较大的权重w，这时候如果有一个异常数据，某个人年龄写的是200岁，就会一下子将函数值推到接近1的区域。这明显不是我们想要的，相反如果通过离散化，年龄特征的权重会分散到各个桶对应的特征里，这时候单个特征的异常就不会造成很大的影响。
假设模型里有年龄、性别、身高三个特征，这时候就会出现特征组合的问题。比如年龄+性别可以作为一个新的特征，可能某类物品对于这种组合特征有偏好，如16岁以下的小男孩对变形金刚很感兴趣（我实在想不到什么例子）。这种需求LR是没有办法自动完成的，只能人工来添加。
从我自己阅读的一些paper里，我总结了两个所谓的"套路"。
另一个套路是使用数据不同方面的信息，这个策略更加隐晦。举个例子，我们可以根据用户的资讯阅读历史计算一个兴趣画像，但是这个画像我们可以分成几个画像，比如拿一周的历史算一个，一个月的历史算一个，然后通过实践decay算一个历史全量的。这样场中短期分开的画像可以作为独立的特征放到模型中去。另一个例子是cf论文中一个很有意思的做法，在Netflix的数据集里，user-item矩阵嵌入了一个隐藏信息是user-打分item的对应关系，所以我们可以从user-rating矩阵里提取一个二元取值的user-item关联矩阵，如果u对i打分了，则这个矩阵对应ui的位置为1，否则为0。把这个矩阵作为一个implicitfeedback加入到cf里，会有进一步的效果提升，这就是数据信息的不同facet。
这一小节是后补的，主要介绍几种常用的评价指标以及他们各自的优缺点，主要取材于[21]。这里选取AUC、RIG、MSE三个来重点说下，其他的指标有需要的请参考原文。
AUC是ROC曲线下的面积，是一个[0,1]之间的值。他的优点是用一个值概括出模型的整体performance，不依赖于阈值的选取。因此AUC使用很广泛，既可以用来衡量不同模型，也可以用来调参。比如
这是用AUC用来调超参的一个例子，横坐标是GBDT的树的棵数，纵坐标是对应模型收敛后在test集和train集上的AUC值，从图中可以看到在120棵树附近GBDT就开始出现过拟合情况了，不过两个集合的AUC都还在持续上升。除此之外，AUC还可以作为一个在线监测的指标，用来时刻监测在线模型的表现。
AUC指标的不足之处有两点：一是只反映了模型的整体性能，看不出在不同点击率区间上的误差情况；二是只反映了排序能力，没有反映预测精度。简单说，如果对一个模型的点击率统一乘以2，AUC不会变化，但显然模型预测的值和真实值之间的offset扩大了。
Netflix比赛用的RMSE指标可以衡量预测的精度，与之类似的指标有MSE、MAE，以MSE为例，计算公式如下
如果我们要对比不同的算法的模型的精度怎么办呢？除了MSE有没有其他选择？这里提供一个RIG：
这张图直接取自[21]，表达式有点问题，我先留给大家来发现吧，正确的表达式在本文另一篇参考文献里有，先留个悬念：）
这里要强调的一点是RIG指标不仅和模型的质量有关，还和数据集的分布情况有关；因此千万注意不可以使用RIG来对比不同数据集上生成的模型，但可以用来对比相同数据集上不同模型的质量差异。这一点尤为重要。
[3]是微软内部竞赛推出的一个算法，也被后续很多算法作为对比的baseline。
这个算法的细节可以直接去看原文，这里只对优劣做一个简单介绍。该算法的基本思想是参数w是一个先验分布为正态分布的分布，参数为u、ó；在贝叶斯框架下，每一个样本都是在修正对应的分布参数u、ó；对应的更新公式为
该模型的优点是基于贝叶斯模型，因此可以做到在线学习，每个样本都可以对参数进行微调，同时onlinelearning带来了在线学习的能力，可以及时应对用户兴趣的变化。
不足之处在于每个feature对应权重都需要两个参数来描述，模型的尺寸是LR的两倍，在复杂模型场景下这个成本可能比较难接受。
从文末的评测来看，BOPR和朴素贝叶斯相比，BOPR能在比较宽的pctr维度很好地拟合经验点击率的情况。
[4]是14年facebook出的一篇ctr领域非常经典的论文，15年去北京参加QCon大会时，机器学习方向的演讲几乎都提到了这篇论文，可见该方法的成功。
前文提到，随着特征的增加，特征组合这件事将变得尤为困难，人力很难应付。假如一个点击率预测的系统涉及到100个特征，则熟悉二项式定理的同学可以心算出来所有可能的组合特征接近2100；这个数据有多恐怖呢？一张纸对折50次对应250，出来的高度是1125899906米，大约是几十万个珠穆朗玛峰那么高。而特征组合是在特征离散化以后做的，稍微几个特征分桶可能就不止100了，再组合，特征就会爆炸掉。
[4]就是尝试提出一种解决特征组合问题的方案，基本思路是利用树模型的组合特性来自动做特征组合，具体一点是使用了GBDT的特征组合能力。整体架构如下：
先在样本集上训练一个GBDT的树模型，然后使用这个树模型对特征进行编码，将原始特征x对应的叶子节点按照01编码，作为新的特征，叠加到LR模型里再训练一个LR模型。预测的时候也是类似的流程，先对原始特征x通过GBDT计算一遍，得到叶子节点情况，以图中为例，如果x落到第一棵树的第二个节点，第二棵树的第一个节点，则转换后的输入特征为(0、1、0、1、0)；
GBDT+LR模型确实明显优于单独的LR模型，我们在浏览器多个场景做了测试，AUC都有非常明显的提升，接近10个百分点。从训练来看，GBDT也确实像[5]所说那样，很容易过拟合，但叠加LR以后却能取得很不错的性能。GBDT因为是在函数空间对残差进行连续逼近，所以优点和缺点一样明显：优点是可以逼近几乎任何函数的任何精度，缺点就是很容易过拟合，需要根据业务场景注意在树的棵数和深度上做一定的裁剪，才能平衡精度和过拟合。详细的推导请参看论文，我也只大概看明白原理，因为对泛函还不熟悉，以后有机会再来细讲这个模型的原理。
FTRL是从RDA、FOBOS等针对LR的在线学习算法改进而来，主要是工业界强烈的在线学习的需求驱动而来。有意思的是前面提到的微软的BOPR也是一种天然支持在线学习的算法。为什么要做在线学习？有哪些注意点呢？
从今日头条披露的资料来看，在模型更新方面他们采用了增量更新+定时校准的策略；类似于在线学习+定时离线校准。这种策略应该也可以用到点击率的场景。
这里也顺带提一下FTRL和GBDT+LR的关系，FTRL主要是针对LR部分的onlinelearning；GBDT+LR是两种不同模型的级联，这两个方案是可以很方便的糅合在一起的变成GBDT+FTRL-LR；但这里GBDT的更新没法做到onlinelearning；可以做定期更新。理论上这种做法可能会效果更好一点。
[7]提出的FM是一种可以自有设置特征组合度数的回归算法，通常d=2的FM拟合公式如下：
选择一种损失函数后很容易用sgd之类的优化算法来计算w和v；原文这块的论述有点模糊，没有指明目标函数的情况下对拟合公式使用了sgd，有兴趣的同学可以一起探讨。
FM的优势是可以自动进行特征间的组合，这解决了两个问题：一个是系数数据因为特征组合而能得到不错的backgroudmodel效果；另一个是特征组合解决了人工组合的尴尬，GBDT+LR与此有异曲同工之妙，因此FM常常和GBDT+LR一起讨论。从应用范围来看，业界GBDT+LR的使用范围应该是比FM要广的，国内我所知只有世纪佳缘[8]是使用FM替代了GBDT+LR。
FM的另一个优点是会算出每个feature对应的向量v；这个向量可以看做对feature的一种embeding，例如后面WDL的场景，或者是GBDT+LR里对categoricalfeature做embeding，后者我们正在计划尝试；前者因为可以通过jointlearning直接学习最佳的embedding向量，所以一般不会单独使用FM来对feature做embeding。
FM的不足之处是在dense数据集情况下，反而可能表现不佳，鱼与熊掌不可兼得啊！
[9]介绍了FFM在美团的一些应用，个人理解是FM的一个小改版，不多说。
对于系统的新用户，在没有历史消费数据的情况下，想要预测用户的点击率是一件比较困难的事。这里提供一种按照数据丰富度划分阶段的思路，一共划分为四个阶段：1.全新用户；2.少量消费数据用户；3.一般消费数据用户；4.充分消费数据用户。每一个新用户和系统的交互分为这四个阶段，分段的标准可以根据具体场景的实验数据来拍一下脑袋，在不同的阶段，我们用不同的策略来进行用户数据的获取。
在少量消费数据阶段，我们可以使用CB[12]，CB的核心思想是给用户展示他消费过的物品最相似的物品，比如一个用户消费了盗梦空间，则他有可能想继续观看泰坦尼克号。CB的难点在于对物品向量化。
对于第三个阶段的用户，有一定的数据又不是很多，此时可以采用[13]这种降级的ctr模型，并且对其中的一些特征使用smoothing技术，如贝叶斯平滑、指数平滑等；可以参看后面部分的介绍。
第四个阶段就是常规用户，使用我们前面提到的各种点击率模型就好了。
[16]中使用了指数decay和beta分布平滑两种技巧，这两个技巧也可以一起使用。对于decay，既可以将历史信息融入到特征里，又保持了对历史信息的遗忘速度，是一个不错的平衡，从各个实践来看，使用平滑对模型性能都会有显著的提升。
从这张图可以看出，在最上层还是使用了LR模型，和GBDT+LR对比可以看出两个模型的相似性和区别：前者使用GBDT来做特征的组合，后者使用两项不同的技术来处理，首先是对categoricalfeature进行embedding，然后和continousfeature一起concatenate成一个向量，通过三层ReLU网络来做特征的表示学习；另一方面对于categoricalfeature还可以进行人工交叉组合，与左边网络自己学习到的特征一起加入到顶层LR模型里作为最终特征。
这里需要提到的一点是对于categoricalfeature的embedding，没有使用独立的FM之类的方法，而是通过jointlearning直接学习出来的，具体做法是对最embedding层使用类似EM的做法，固定W后使用bp训练向量，交替进行。和FM之类独立训练的embedding向量相比，为什么联合训练的向量可能会更好呢？这个思想起源是哪里呢？
第一个问题我认为联合训练的embedding向量确实会比FM单独embedding出来的要好，原因比较细微，熟悉CF发展流程的同学应该知道，对传统Item-basedCF和User-basedCF的一个改进就是将pearson系数替换为可以联合训练的wij，以capture到数据之间interpolation信息。详细的介绍可以参考我下一篇关于CF的综述。
使用了类似jointlearning以同时获得embedding向量和权重矩阵的还有[18]。有兴趣的可以参考。
关于WDL的性能，普遍认为会比传统LR高两位数百分点，浏览器正在尝试在app推荐场景下做一个横屏，从目前初步结论来看，GBDT+LR相比于纯LR大约是两位数的提升，而WDL还没有看到明显效果，不过我们会进一步在参数调优上下些功夫，以期取得更好的效果。
WDL的缺陷主要体现在两方面，一方面是在线predict时的性能瓶颈决定不能使用太宽、太深的网络，另一方面是如果做onlinelearning，这个问题据说百度凤巢是有做过，具体方案不得而知。
是否可以直接使用强化学习来做点击率或者推荐呢？答案我觉得是肯定的。这方面阿里应该是走在前沿，[20]中提到因为采用深度强化学习和自适应学习的技术，阿里的双十一销量有10%-20%的提升。这是一个非常恐怖的数字，尤其是在阿里这样的体量下。请允许我引用其中一段文字来做个简单说明：
"2014年双11通过排序特征实时，引入商品实时转化率，实时售罄率模型进入搜索match和rank，让售罄商品额无效曝光大幅减少，并实现了成交转化的大幅提升；2015年双11推出双链路实时计算体系，在特征实时的基础上，引入排序因子的在线学习，预测，以及基于多臂机学习的排序策略决策模型，在预热期和双11大幅提升了搜索流量的成交转化效率；2016年实时学习和决策能力进一步升级，实现了排序因子的在线深度学习，和基于强化学习的排序策略决策模型，从而使得淘宝搜索的智能化进化至新的高度，并在今年的双11，分桶测试效果表明，成交金额取得了近20%的大幅提升。"
[1]PredictingClicks:EstimatingtheClick-ThroughRateforNewAds；
[2]Web-ScaleBayesianClick-ThroughRatePredictionforSponsoredSearchAdvertisinginMicrosoft’sBingSearchEngine；
[3]PracticalLessonsfromPredictingClicksonAdsatFacebook；
[4]greedyfunctionapproximation:agradientboostingmachine
[5]AdClickPrediction:aViewfromtheTrenches
[6]FactorizationMachines.SteffenRendle
[10]AnEmpiricalEvaluationofThompsonSampling
[11]Content-basedRecommendationSystems；
[12]PredictingClicks:EstimatingtheClick-ThroughRateforNewAds
[13]Click-ThroughRateEstimationforRareEventsinOnlineAdvertising
[14]Wide&DeepLearningforRecommenderSystems；
[15]DeepNeuralNetworksforYouTubeRecommendations
[16]ReinforcementLearning：AnIntroduction
[18]PredictiveModelPerformance:OfflineandOnlineEvaluations