原文：http://blog.csdn.net/mytestmy/article/details/18987881
互联网广告综述之点击率系统
声明：
1）该博文是整理自网上很大牛和专家所无私奉献的资料的。具体引用的资料请看参考文献。具体的版本声明也参考原文献
2）本文仅供学术交流，非商用。所以每一部分具体的参考资料并没有详细对应，更有些部分本来就是直接从其他博客复制过来的。如果某部分不小心侵犯了大家的利益，还望海涵，并联系老衲删除或修改，直到相关人士满意为止。
3）本人才疏学浅，整理总结的时候难免出错，还望各位前辈不吝指正，谢谢。
4）阅读本文需要互联网广告业的基础（如果没有也没关系了，没有就看看，当做跟同学们吹牛的本钱）。
5）此属于第一版本，若有错误，还需继续修正与增删。还望大家多多指点。请直接回帖，本人来想办法处理。
6）本人手上有word版的和pdf版的，有必要的话可以上传到csdn供各位下载
一．互联网广告技术
博文《互联网广告综述之生态圈》论述过互联网广告生态圈的各个平台，大家可以看到，其中的Ad exchange是躺着赚钱的平台，风险并不大。
其中的DSP就承担了比较多的风险，如果向Ad exchange请求的流量太贵，而广告主开价比较低的话，就可能面临亏钱。另外，广告主的需求是变化多样的，有些广告主愿意开一定价钱要求多少次点击，而有些广告主就希望开多少价钱有多少次互动，同时广告主会对效果有所需求。换句话说，评估流量的质量对DSP非常重要。
DSP需要评估流量质量，如果发现一个流量的质量很高，就开高价去竟争这个流量；如果流量质量低，就开低价去竟争。如果评估得太高，出很高的价钱拿到了质量很低的流量，那就达不到广告主的要求，会亏钱；如果评估得太低，一直拿不到流量，没办法赚钱。
所谓评估流量质量，说到底了是预估一个流量的ctr（点击率，也成为点击某广告的可能性），所以对于DSP来说，能否估准ctr是DSP生存的关键。
1.1互联网广告点击率预估
做点击率预估需要两方面的数据，一方面是广告的数据，另一方面是用户的数据，对于DSP来说，广告数据它自己有，用户数据可以从DMP获取，它自己的工作是利用这两方面的数据评估用户点击这个广告的可能性（也就是概率）。
1.1.1 预估方法讨论
对点击率的预估，做的工作可以用下面的图来描述。
预估一个人点击一个广告的概率，不可能是一个人在那里看着，来一个广告请求就估计一下，给个决定，这样人累死，估计得也乱七八糟，还效率不高，一天撑死了估计个几十万个请求，不得了了。
只能用机器来估，但是机器是很笨的，只能进行简单的规则运算，这些规则还必须提前指定。如果人工指定这些规则，如30岁用户点击匹克篮球的广告概率是多少，男性的用户点击匹克篮球的广告的概率是多少，年龄和性别在总的ctr预估里面占多少比重等等，则需要大量的先验知识，而且还不能根据实际情况变化，往往有问题。
这就需要机器学习方法来辅助了，一个是统计方法，一个是模型。
统计方法怎么用呢？如可以统计过去投放过的记录中，30岁的用户点击匹克篮球的广告的点击率是多少，这个数据直接就能根据投放日志统计出来；再统计男性的用户点击匹克篮球的广告的点击率是多少，这样前面的两个东西就得到了。
但是知道这两个点击率，还需要知道这两个点击率在评估这个人点击匹克篮球的广告的概率中分别起什么作用。这两个点击率加起来不行，相减也是不行的，加权累加可能是一种办法，但是这样行吗？为了解决这个事情，需要用模型来解决了。为了描述的方便，我们把这两个点击率称为特征，用一个向量x=(x1,x2)来统一表示，其中x1表示30岁的用户对匹克篮球的广告的点击率，x2男性的用户对匹克篮球的广告的点击率。
利用模型做ctr预估，用数学的方法来描述就是完成上面的图中函数f的形式。
本来这个函数的形式是很复杂的，但是太复杂的模型不利于扩展，就用简单的形式来。经过工业界长期的工作，认为下面的形式是比较有效的。
其中x是上面的那个x，w也是一个向量，表示的是x的每个特征的权重。这个w每取一个值，对相同的user和ad对就能得到一个预估的ctr，w同时也被称为是模型，因为它能根据x的取值，也就是特征的取值来决定ctr。
权重可以人工指定的，但是上面说过了，需要大量的先验知识，而且特征会特别多，如上面还有地域，职业，学校什么的，可以搞到成千上万的特征，人工指定没办法做到周全。所以这个权重的是要用算法来让机器自己学习到的，这个过程称为训练，这个训练过程还不能只根据一个记录user和ad对来训练，要根据很多对来训练。每个展示记录就是一个对，根据历史的一段时间内的展示记录，能有很多的的数据对可以进行训练。
用什么方法进行训练呢？上面user和ad对可以达到上亿的量级。
机器学习领域的把这个训练过程称为是拟合分布的过程，他们认为一次广告的展示是否被点击（每次展示被点击的概率可能不一样）是一个伯努利试验，对多个用户展示多个广告的过程是一个伯努利过程，总体的历史展示与点击数据符合一个伯努利分布，伯努利试验成功的概率就是上面的f(user,ad)的值。拟合这个伯努利分布的过程就是训练的过程。拟合分布往往用的是极大似然估计的方式去拟合，刚好做的事情就是跟做一个回归问题是一样的，这个回归叫做logistic回归。为了方便描述，改变一下f的写法，用下面的方式表示
其中y=1表示这个展示被点击了，y=0表示这个展示没有被点击。似然函数和对数似然函数也可以写成下面的形式
求上面的式子的最大值，就可以得到w的最优解，这个最优解w就表示当前展示数据的伯努利分布是拟合的最好的，用来预估ctr也是最好的。
有关求解最优化问题的基础可以参看博文《无约束优化方法读书笔记—入门篇》
有关极大似然估计的知识可以参看博客中转载的《从最大似然到EM算法浅解》。
有关逻辑回归及其相关知识的可以参看博文《从广义线性模型到逻辑回归》。
有关特征工程的知识可以参看博文《互联网广告综述之点击率特征工程》。
1.1.2 线上应用情况
下面的图显示了CTR预估的系统结构。
其中投放平台获取到用户的广告请求后，将请求交给CTR计算与排名模块，这个模块会获取用户数据和广告数据，再根据模型计算CTR。得到ctr后，有两种方式使用。一种是对CTR进行排名，返回排名ctr最高的广告，然后DSP就可以根据这个CTR出价了；另一种是将广告的出价与ctr相乘，得到每个广告的收益，根据收益排名，返回收益排名最高的广告。
投放平台获取这个广告后，根据一些条件，会把广告展示给用户，同时产生投放日志。用户会做出相应的反馈（点击或不点击），产生点击日志。
这些日志会产生三个作用。一种是存到日志数据存储工具。第二种是产生实时统计数据，以方便迅速更新特征。第三种是进行在线学习，不断更新线上的模型。
日志存储工具的日志有两种作用，一种是经过ETL，可以生成训练数据，然后用这些训练数据去训练模型，然后更新线上的模型；另一种是利用统计的方式或者其他方式产生特征。
线上模型有两种更新方式，一种是离线训练的更新方式，一种是在线学习的更新方式。
这两种方式分别用的是两种不同的训练算法。离线训练的更新方式比较慢，频率一般比较低，一般都是一天或者一个星期训练一次，用的方法一般是批量学习方式，就是对数据进行多轮的迭代，获取w的尽可能的最优解。在线学习的方式要求能快速更新线上模型，一般是来一个展示记录，就获取这个展示记录的特征，然后利用这个记录去进行只有一个数据的迭代，得到一个新的模型。
离线训练的方式有多种，其中一种可以参看转载的博文《OWL-QN算法》。
在线学习的方式也有多种，其中一种可以参看博文《在线学习算法FTRL》。
致谢
多位Google、Linkedln公司的研究员无私公开的资料。
多位博主的博客资料。
参考文献
[1] Ad ClickPrediction: a View from the Trenches. H. Brendan McMahan, Gary Holt et al，Google的论文
[2] http://blog.csdn.net/zouxy09/article/details/8537620@zouxy09的博客
[3] http://www.cnblogs.com/vivounicorn/archive/2012/06/25/2561071.html@Leo Zhang的博客
[4] Computational Advertising: The LinkedIn Way. Deepak Agarwal, LinkedIn Corporation CIKM
一．互联网广告特征工程
博文《互联网广告综述之点击率系统》论述了互联网广告的点击率系统，可以看到，其中的logistic regression模型是比较简单而且实用的，其训练方法虽然有多种，但目标是一致的，训练结果对效果的影响是比较大，但是训练方法本身，对效果的影响却不是决定性的，因为训练的是每个特征的权重，权重细微的差别不会引起ctr的巨大变化。
在训练方法确定后，对ctr预估起到决定性作用的是选用的特征。
1.1特征选择与使用
做点击率预估需要两方面的数据，一方面是广告的数据，另一方面是用户的数据，现在所有的数据都有，那么工作就是利用这两方面的数据评估用户点击这个广告的可能性（也就是概率）。
用户的特征是比较多的，用户的年龄，性别，地域，职业，学校，手机平台等等。广告的特征也很丰富，如广告大小，广告文本，广告所属行业，广告图片。还有反馈特征，如每个广告的实时ctr，广告跟性别交叉的ctr。如何从这么多的特征中选择到能刻画一个人对一个广告的兴趣的特征，是数据挖掘工程师的一个大难题。
选中了特征，还需要注意特征的选择方式，例如，如果单独把年龄作为一个特征，最终能训练出来啥吗？因为年龄相加相减是没有意义的，所以只能把每个年龄做为一个特征，但是光这样可以了吗？怎么用特征，是广告算法工程师的一个大课题。
1.1.1 选择特征
什么样的特征适合用来预估ctr？这个问题是很多广告算法工程师的需要考虑的。
机器学习算法最多会大谈模型，对于特征的讨论很少涉及。真正的应用中，多数数据挖掘工程师的工作都是在想特征，验证特征。
想特征是一个脑力加体力的活，需要不少的领域的知识，更让人郁闷的是，工业界并没有一整套想特征的办法，工业界有的只是验证特征的办法。对于互联网广告业，就简单说说通用特征怎么来的吧。
首先说年龄这个特征，怎么知道它跟点击率有关系？现在直观的解释是，年轻人普遍喜欢运动类的广告，30岁左右的男人喜欢车，房子之类的广告，50岁以上的人喜欢保健品的广告。可以看到，选择年龄作为特征的理由是基于对各个年龄段的人喜欢的不同类型的东西的一个粗略的划分，是一个很主观的东西。
再说性别这个特征，直观的感觉是，男性普遍喜欢体育类的，车类的，旅游类广告，女性普遍喜欢化妆品，服装类的广告。这也可以看到，选择性别作为特征也是基于相似的理由，就是认为男性和女性大体会喜欢不同的东西。
对于地域这个特征，这下就学问多了，华南的人在比较喜欢动漫和游戏，华北的人喜欢酒品和烟？
在广告方面的特征，广告的图片大小，广告前景色背景色真的能影响人的点击吗？这其实都是一种猜测。图片里面是一个明星还是一个动物之类的因素也可以考虑。
总之，想特征的这个事情基本没多大谱，只能天南地北地想象，还要多了解各行各业的知识，以便想到更多的特征，哪怕某个特征跟人关系并不大，也得好好验证一番。这基本上跟男人为回家晚想借口一样，得有借口要想着怎么解释得好听点，没借口就要想借口。
想到了特征，就要验证和进行判断。
验证特征的办法多，有直接观察ctr，卡方检验，单特征AUC等。直接观察ctr是个很有效的方法，如根据投放记录，化妆品的广告在女性上面的点击率就比在男性上面的点击率高很多，说明性别这个特征在化妆品行业是有预测能力的；又如体育用品的广告在男性上面的点击率也比女性高，说明性别这个特征在体育行业也是有预测能力的，经过多个行业的验证，就认为性别这个特征可以用了。
年龄这个特征的评估类型，主要是观察一个广告在不同年龄段的点击率是否有区别，再观察不同广告的点击率在不同年龄段的分布是否不一样，如果都有区别，说明年龄这个特征就可以用了。
在实际的使用中发现，性别这个特征比较有效，手机平台这个特征也比较有效，地域和年龄这两个特征有一定效果，但没有前两个那么明显，跟他们的使用方式可能有关，还需要进一步挖掘。
同时，实际使用中也发现，广告反馈ctr这个特征也很有效，这个特征的意思就是当前的广告正在投放，已经投放了一部分了，这部分的点击率基本可以认为是这个广告的点击率了，也可以认为是这个广告的质量的一个体现，用来预估一个流量的ctr是很有效的。
1.1.2 特征的处理和使用
选择得到特征，怎么用也是一个问题。
先说需求，其实预估ctr要做的事情是下面的图的工作——计算一个用户/广告组合的ctr。
上面已经选好了特征，暂定有广告的反馈ctr，用户年龄，性别三个特征。
一、离散化
反馈ctr是一个浮点数，直接作为特征是可以的，假设1号特征就是反馈ctr。对应年龄来说就不是这样了，因为年龄不是浮点数，而且年龄的20岁跟30岁这两个数字20,30大小比较是没有意义的，相加相减都是没有意义的，在优化计算以及实际计算ctr是会涉及这两个数字的大小比较的。如w.x，在w已经确定的情况下，x的某个特征的值是20，或者30，w.x的值相差是很大的，哪怕用逻辑化公式再比较，得到的值也是比较大的，但是往往20岁的人跟30岁的人对同一个广告的兴趣差距不会那么大。解决这样的情况的方法就是，每个年龄一个特征，如总共只有20岁到29岁10种年龄，就把每个年龄做一个特征，编号是从2到11（1号是广告的反馈ctr），如果这个人是20岁，那么在编号为2的特征上的值就是1，3到11的编号上就是0。这样，年龄这一类特征就有了10个特征，而且这10个特征就是互斥的，这样的特征称为离散化特征。
二、交叉
这样看起来就能解决上面的问题了，但是够了吗？
比如一个人是20岁，那么在编号为2的特征上面，它一直都是1，对篮球的广告是1，对化妆品的广告也是1，这样训练的结果得到的编号为2的权重的意义是——20岁的人点击所有的广告的可能性的都是这个权重，这样其实是不合理的。
有意义的应该是，这个20岁的人，当广告是跟体育相关的时候，它是一个值；当广告跟保健品相关的时候，它又是一个值。这样看起来才合理。如果这个不够深刻，基于跟上面同样的道理，性别这个特征也是一样的，假如也做了上面的离散化操作，编号是12和13,12是男性，13是女性。这样的话，对于一个男性/体育广告组合来说，编号12的特征值为1，男性/化妆品的组合的编号12的特征值也是1。这样也是不合理的。
怎么做到合理呢？以上面的性别的例子来说。编号12的特征值不取1，取值为该广告在男性用户上面的点击率，如对于男性/体育广告的组合，编号12的特征的值为男性在体育广告上面点击率，这样，编号为12的特征就变成了一个浮点数，这个浮点数的相加减是有意义的。
这样的做法称为特征的交叉，现在就是性别跟广告的交叉得到的特征值。还有很多其他的方式可以进行交叉，目前工业上的应用最多的就是广告跟用户的交叉特征（编号为1的那个特征）、广告跟性别的交叉特征，广告跟年龄的交叉特征，广告跟手机平台的交叉特征，广告跟地域的交叉特征。如果做得比较多，可能会有广告主（每个广告都是一个广告主提交的一个投放计划，一个广告主可能会提交多个投放计划）跟各个特征的交叉。
三、连续特征变离散特征
做到的交叉的特征值就足够了吗？答案还是不一定。
如编号为1的那个特征，就是广告本身的ctr，假设互联网广告的点击率符合一个长尾分布，叫做对数正态分布，其概率密度是下图（注意这个是假设，不代表真实的数据，从真实的数据观察是符合这么样的一个形状的，好像还有雅虎的平滑的那个论文说它符合beta分布）。
可以看到，大部分广告的点击率都是在某一个不大的区间内的，点击率越高的广告越少，同时这些广告覆盖的流量也少。换句话说，点击率在0.2%左右的时候，如果广告a的点击率是0.2%，广告b的点击率是0.25%，广告b的点击率比广告a高0.05%，其实足以表示广告b比广a好不少；但是点击率在1.0%左右的的时候，广告a点击率是1.0%，广告b的点击率是1.05%，并没有办法表示广告b比广告a好很多，因为在这0.05%的区间内的广告并不多，两个广告基本可以认为差不多的。也就是点击率在不同的区间，应该考虑是不同的权重系数，因为这个由广告点击率组成的编号为1的特征与这个用户对广告的点击的概率不是完全的正相关性，有可能值越大特征越重要，也有可能值增长到了一定程度，重要性就下降了。
对于这样的问题，百度有科学家提出了对连续特征进行离散化。他们认为，特征的连续值在不同的区间的重要性是不一样的，所以希望连续特征在不同的区间有不同的权重，实现的方法就是对特征进行划分区间，每个区间为一个新的特征。
具体实现是使用等频离散化方式：1）对于上面的编号为1的那个特征，先统计历史记录中每条展示记录中编号为1的特征的值的排序，假设有10000条展示记录，每个展示记录的这个特征值是一个不相同的浮点数，对所有的展示记录按照这个浮点数从低到高排序，取最低的1000个展示记录的特征值作为一个区间，排名1001到2000的展示记录的特征值作为一个区间，以此类推，总共划分了10个区间。2）对特征编号重新编排，对于排名从1到1000的1000个展示记录，他们的原来编号为1的特征转变为新的特征编号1，值为1；对于排名是从1001到2000的记录，他们的原来编号为1的特征转变为新的特征编号2，值为1，以此类推，新的特征编号就有了1到10总共10个。对于每个展示记录来说，如果是排名1到1000的，新的特征编号就只有编号1的值为1，2到10的为0，其他的展示记录类似，这样，广告本身的ctr就占用了10个特征编号，就成为离散化成了10个特征。
等频离散化需要对原有的每个特征都做，也就是原来的编号为1到13的编号，会离散化成很多的编号，如果每个特征离散化成10个，则最终会有130个特征，训练的结果w就会是一个130维的向量，分别对应着130个特征的权重。
实际的应用表名，离散化的特征能拟合数据中的非线性关系，取得比原有的连续特征更好的效果，而且在线上应用时，无需做乘法运算，也加快了计算ctr的速度。
1.1.3 特征的过滤与修正
上面提到，很多特征其实是反馈的特征，如广告反馈ctr，广告与性别交叉特征，这些特征本来可以通过历史展示日志的统计得到。但有些广告本来展示量很少，在男性用户上展示就更少，这时要计算广告与性别交叉的ctr是很不准确的，需要对这个特征进行修正。具体的修正方法可以参考博文《广告点击率的贝叶斯平滑》。
经过修正后的ctr再做特征，实际线上效果有了比较大的提升。
如果使用的特征又更多了，有了学校跟广告交叉特征什么的，离散化后有了上万的特征，这下就会产生特征过多导致的各种问题，如过拟合等。解决这个问题的方法一种是离线的数据评估，如用ctr的区分性。另一种就是利用正则，特别是L1正则，经过L1正则训练的得到的权重向量，其中某些特征如果对点击率预估预测性不强，权重会变成0，不影响预估。这就是特征过滤，具体的有关L1的一些论述与实现参看博文《从广义线性模型到逻辑回归》《OWL-QN算法》和《在线学习算法FTRL》。
致谢
多位Linkedln、百度公司的研究员无私公开的资料。
多位博主的博客资料。
参考文献
[1] Ad Click Prediction: a View from the Trenches. H. Brendan McMahan, Gary Holt et al，Google的论文
[2] http://www.cnblogs.com/vivounicorn/archive/2012/06/25/2561071.html @Leo Zhang的博客
[3] Computational Advertising: The LinkedIn Way. Deepak Agarwal, LinkedIn Corporation CIKM