原作：面包包包包包包
改动：寒小阳 && 龙心尘
时间：2016年2月
出处：http://blog.csdn.net/Breada/article/details/50697030
http://blog.csdn.net/han_xiaoyang/article/details/50697074
http://blog.csdn.net/longxinchen_ml/article/details/50697105
声明：版权全部。转载请联系作者并注明出处
1. 引言
提笔写这篇博客，我的内心是惶恐的。
原因非常简单。作为一个资历尚浅的研究生，是没有资格对计算广告这样一个伟大的行业、领域和学科来评头论足的。之所以这么做，一是总结自己已掌握的知识，二是减少同学们的学习成本。本人能力有限。更缺乏实践经验，文章内容多为书籍和论文的读后感，若有不当或者错误之处，还望各位同学指出。我定悉心求教。
在此。向编写《计算广告》的刘鹏和王超两位老师致谢，向各位paper作者致谢。
[关于ML学分计划]
由寒小阳和龙心尘发起，一个互帮互助的机器学习知识共享平台。
我们是一群对机器学习感兴趣的小伙伴，对于神秘的机器学习经常有“一探究竟”的冲动，却由于孤身一人学习的寂寞、亦或繁忙考试工作之余的小小迟延症，而没有持续这份对知识的渴求和热情。
由于深感相似情况的小伙伴之多，我们希望建立一个“ML学分计划”——机器学习的学习和分享计划——来帮助我们一起更高效地学习、更集中地整理分享我们的知识和经验。
由于我们也深信”证明自己真的透彻理解一个知识，最好的方法。是给一个不熟悉这个内容的人，讲清楚这个内容“。
[关于原作@面包包包包包包]
海淀区明光村计算机职业技术学院，研二学生。
关注计算广告点击率预估和竞价算法，关注机器学习和深度学习，刚開始学习的人。
机器学习QQ群：刚開始学习的人373038809，行业同学和研究者472059892。
(上)(中)(下)全文文件夹
引言
广告=>互联网广告：“您好，了解一下”
互联网广告=>计算广告：指哪儿打哪儿！
计算广告四君子：谁在弄潮？
计算广告关键技术：这孙子怎么什么都知道？
广告系统架构：要啥自行车，这里有宝马。
手把手系列之教你搭建一个最小广告系统：mieSys
5. 计算广告关键技术：这孙子怎么什么都知道？
一句话解释关键技术：没声音，再好的戏也出不来。
广告作为一项商业活动，是须要资本来滋养的。
作为整个产业链的金主。仅仅有广告主花钱做广告。使资金流动起来，整个广告行业才干正常运转。所谓关键技术。就是那些能让广告主认为“这钱花的值”，让媒体站点认为“这钱挣的快”的技术。详细都有哪些呢？以下我们一一来表。
5.1 合约广告关键技术：受众定向
计算广告发展到合约广告阶段。媒体站点依靠受众定向技术给用户打标签，在实现了媒体站点广告位的时分复用的同一时候。还提高了广告主的投入产出比，极大的激发了广告主在互联网上做广告的积极性。因此，受众定向是合约广告中的关键技术。
我们知道。仅仅要描写叙述物体的维度足够高，那么世间万物都是独一无二的。在广告系统中，标签就是描写叙述用户的维度。媒体站点为了精准的刻画用户，标签的种类和数量自然也不会少。
为了更加直观地了解受众定向技术，我们从用户、上下文和广告三个方面讨论打标签的思路和一般方法。
用户标签：主要用性别、年龄、收入、地理位置、教育程度和用户行为等标签来刻画用户。从而回答“你是谁”的问题。
上下文标签：主要用网页的地域、主题和频道等标签来刻画用户当前所处的媒体站点环境，从而回答“你在看啥”的问题。
广告标签：主要用广告主、广告创意、广告计划和广告关键词等标签来刻画广告的相关内容，将广告内容与用户和上下文进行匹配后。从而回答“你该看啥”的问题。
5.1.1 用户标签关键技术
对一个用户来说，性别是不会轻易变的，可是用户的喜好和兴趣却是时刻都在变化的。
依据标签属性的变化频率，我们这里私自将用户标签分为静态和动态两类。
静态标签主要指年龄、性别、地理位置、收入和教育程度等这样的不变或者非常长时间之内都不变的标签，行话叫“人口属性”；动态标签则是指用户的浏览、搜索和点击等能够反映用户短时喜好和兴趣的行为标签，行话叫“行为定向(BT:Behaviroal Targeting)”。以下我们针对静态和动态这两类标签分别讨论。
一句话解释静态标签和动态标签的关系：价格环绕价值上下波动。
静态标签(人口属性)
在《计算广告小窥[上]》中。我们曾简要地提到过一种受众定向的方法：
通过对点击日志的分析，媒体站点发现点击过女性护肤品的用户又点击过媒体站点上其它女性品牌。
在“女性用户对女性品牌可能更感兴趣”的合理假设下，推断这些用户的性别为女。男性用户同理。
如今我们能够更加清楚的认识到，上述媒体站点所打的标签是静态标签中的“性别”。使用的是基于规则的方法，即：满足了某种条件，就是某种人。
这样的基于规则的方法简单而且易于实现，但也存在着致命的缺点：基于规则的方法对数据非常敏感，若数据本身存在噪音(如误点击)，那么标签的品质也将大打折扣。这可怎样是好？简单的不行，那就来点复杂的嘛——用机器学习模型来实现(自带音效：当当当当，当当~~)。
假设我们已经知道一部分用户的真实性别。那么就能够用机器学习中有监督的二分类模型来预測用户性别。
首先，我们须要对原始数据进行清洗，合理地处理缺失值和神秘值，并划分训练集、交叉验证集和測试集；其次，要在业务的指导下做特征project，利用统计或模型的方法构造特征。并进行特征选择和特征组合；然后。我们要选择合适的模型(如SVM等)，设置合适的评价标准并进行模型的训练；最后。通过模型调參和模型融合。获得性别预測模型。
动态标签(行为定向)
一句话解释行为定向：唐伯虎喜欢如花多一些，还是凤姐多一些？
“假设一定要比較一下，那唐伯虎是喜欢如花多一些，还是凤姐多一些？”这个看似荒谬的问题。正是行为定向要解决的。
假设唐伯虎是异性恋。那他应该是喜欢凤姐多一些的，否则是如花。这也就告诉我们，在行为定向中，推断的标准至关重要。以下我们借助一个样例来分析该用户的动态标签究竟是什么。
有数据显示，某用户在过去的三个月时间中，点击广告的标签和次数例如以下表所看到的：
| 标准 | 单反爱好者 | 跑鞋爱好者 | 饮料爱好者 | 护肤品爱好者 | … |
|---|---|---|---|---|---|
| 点击 | 25 | 4 | 2 | 1 | … |
对上述数据进行分析，我们能够轻而易举的得到答案：该用户的标签应该是“单反爱好者”，由于他的点击行为集中在这个标签上。
可是，这个答案是我们以用户的点击行为作为标准得来的，假设以用户的浏览和搜索行为做标准。答案也是“单反爱好者”吗？我们再来看一下相关数据。
| 标准 | 单反爱好者 | 跑鞋爱好者 | 饮料爱好者 | 护肤品爱好者 | … |
|---|---|---|---|---|---|
| 浏览 | 15 | 2 | 0 | 0 | … |
| 标准 | 单反爱好者 | 跑鞋爱好者 | 饮料爱好者 | 护肤品爱好者 | … |
|---|---|---|---|---|---|
| 搜索 | 7 | 16 | 5 | 3 | … |
是不是出问题了？以点击和浏览为标准，该用户标签应该是“单反爱好者”，可是以搜索为标准。标签应该是“跑鞋爱好者”。
假设该用户的标签仅仅能有一个，那该选哪一个呢？为了解决问题。我们从数学角度分析一下好了。嘿嘿。数学噢。前方高能预警！
我会尽量让这个过程变得简单，大家跟上我的思路哈。
Step1. 泊松分布
一句话解释泊松分布:猜猜我在哪儿~~~
我们先来介绍下泊松分布。啊啊啊啊。一上来就是数学。我不听我不听我不听，泊松分布是什么鬼？咳咳，那，那就先不丢公式了，咱们看图解决问题好了，以下是泊松分布绘出的曲线图，实际project中要解决的问题就是找到图中的最高点，例如以下图：
这个肉眼找最高点的过程不要太简单了！！
！我们能够看到：图中最高点的纵坐标大约为0.36，而相应的横坐标是1。OK，你就算会用泊松分布了哦！那个，感兴趣的同学们，能够一起来看看相应上图的泊松分布的公式。
pt(h)=λhte−λth!
p_t(h)=\frac{\lambda_t^he^{-\lambda_t}}{h!}
公式相对于图，是有那么点点复杂啦。只是，我们仅仅需知道λt\lambda_t影响泊松分布的形状，一个λt\lambda_t相应一个泊松分布就能够了。
这个场景下要做的事情就是找到相应泊松分布图像的最高点。
Step2. 一个结论
一句话解释这个结论：一个萝卜一个坑。
我们先说一个结论：在一个标准下，用户在全部标签上的概率分布是满足泊松分布的。
对于这个结论，有兴趣的同学能够參见Stanford 《Introduction to Computational Advertising》讲义Page-81，我们在这里就直接拿来用了。而所谓“标准”，就相应泊松分布公式中的λt\lambda_t，在我们这里的场景下与用户行为有关。我们有点击、浏览和搜索三种行为，也就相应三个λt\lambda_t，绘出三条曲线例如以下。(此图为演示样例数据上绘出的图像，非实际数据)：
我们能够清楚的看到。在以“点击”和“浏览”为标准时。图像最高点都出如今5号标签，用户标签应该是标签5。以“搜索”为标准时，图像最高点出如今6号标签。用户标签应该是标签6，标签发生了冲突。接下来。我们就要想办法用数学方法去解决标签冲突的问题。思路是这样的：先选出一个最佳标准，然后以此标准画正态分布，最后找最高点相应的标签就可以。
Step3. 最佳标准
一句话解释最佳标准：盲人摸象
“盲人摸象”比喻以偏概全，如今我们想要知道大象全貌。把每一个人摸到的拼起来便是了。
在广告系统中，搜索、点击和浏览三种行为数据都仅仅能从一个側面反映用户的行为，要想完整的刻画一个用户。我们虚要将这三种行为融合起来之后找到一个最佳标准。提到融合，较为经常使用的方法是投票，我们能够写出下列公式：
λt=∑i=1nωi∗ti ，where t∈(搜索，点击。浏览)
\lambda_t = \sum_{i=1}^n\omega_i*t_i\text{ ，where t}\in\text{(搜索，点击。浏览)}
简单解释一下：tit_i是标准，分别代表了搜索、点击和浏览行为。ωi\omega_i是标准的权重，即该标准对于完整描写叙述用户行为的贡献。
我们用机器学习中的广义线性模型对该问题进行建模，模型训练完毕后可得各标准的权重ωi\omega_i，从而预測出最佳标准λt\lambda_t。
Step4. 最终求解
通过广义线性模型，我们找到了最佳标准λt\lambda_t。如今，我们依据该λt\lambda_t画出相应泊松分布，例如以下图：
回想Step2中的结论：在一个标准下。用户在全部标签上的概率分布是满足泊松分布的。如今最佳标准下的泊松分布我们已经画了出来，该用户在全部标签中的概率分布也应该符合这个分布的。还是老步骤，我们找最高点所相应的标签，即标签5。所以该用户的动态标签是标签5。问题完美解决。
在学习了泊松分布和机器学习之后。媒体站点最终完毕了用户标签的工作，看着那圆圆的饼图，流下了激动了泪水，哽咽着说“嗯..最终..最终能够卖钱了..”没错。流量能够变现了，互联网广告一脚踏进合约广告时代。可是仅仅知道“你是谁”，粒度还是太粗。卖不了好价钱。“要是知道你正在干嘛就好了”媒体站点嘴里嘟囔着。突然脑海中灵光一闪，大叫一声：(图片来自网络)
5.1.2 上下文标签关键技术
一句话解释上下文标签的做法：吃的是URL。挤的是标签。
“我当然知道他在干嘛！
我有日志啊！我有他正在訪问页面的URL！
啊哈哈哈哈哈！”有了用户标签的经验。媒体站点处理起上下文标签来就显得轻车熟路了，总共分两步：第一，依据用户当前页面的URL。抓取用户当前浏览的页面内容。第二，提取页面内容的关键词。作为当前页面的标签。
通过URL获得页面内容是一个典型的爬虫应用。与搜索引擎的爬虫不同的是，广告系统的爬虫仅仅抓取用户请求的页面，而非全网页面。鉴于上述原因。广告系统使用“半在线抓取系统”，该系统有三个特点。
第一，仅对用户发起请求的页面进行抓取。节省了时间和成本；第二。将{URL:标签}存储下来，当其它用户发起同样页面请求时，直接返回标签结果，避免反复抓取。
第三。考虑到某些频道页面内容可能会更新(比如”旧浪体育”)。还可设置合适时间，周期地更新已存页面的标签。
在抓取到页面之后，怎样提取标签也有几种常见方法。最简单的是利用规则。在URL层面上人为做映射。比如sports.oldna.com相应的页面标签就是”旧浪体育”。若用户是通过搜索发起的页面訪问，还能够依据搜索词作为页面标签。当然，在广告系统使用范围较广的方法还是机器学习中的主题模型，得到页面内容在几个主题上的分布，从而推断页面标签。比如，sports.oldna.com页面内容在”体育”、”財经”和”游戏”三个主题上的概率分布分别为：
| 体育 | 財经 | 游戏 |
|---|---|---|
| 0.85 | 0.10 | 0.05 |
我们能够非常easy的看出sports.oldna.com的标签是”体育”。这里值得注意的是，假设想要加工出”体育”、”財经”和”游戏”这样的可解释的标签。通常须要採用有监督的主题模型。
能用的数据都用了，能打的标签也都打了。知道了“你是谁”和“你在看什么”之后。媒体站点这才感觉踏实了些。
以下的工作就简单了很多。把标签卖给广告主就能够了，也算是一劳永逸。深藏功与名。
至于用户会看到什么。那是广告主的地界，就无论媒体站点什么事儿了。
5.1.3 广告标签关键技术
普通的广告标签就是广告本身的属性，如所属广告主、广告大小、广告类别和目标人群等，当广告和用户两两匹配时。该广告就会展示给用户。可是。这里我们想说的广告标签是在程序化交易中的“个性化标签”。在《计算广告小窥[上]》中我们提到：“程序化交易是广告主为实现个性化营销举行的海天盛筵。”品尝过个性化营销的甜头之后，广告主就想：“既然这些人是回头客，那各方面表现和这些回头客非常像的人，有没有可能也是我的回头客呢？世界那么大，我得去找找这样的人。
”
look-alike
一句话解释look-alike：比葫芦画瓢。
这个技术的名字还挺洋气呢，英文的，“看起来像”？说白了就是比葫芦画瓢，找到那些看起来像回头客的新用户，行话叫“新客推荐”。
这里一定要注意了，千万不能翻译成“看起来像”，那样显得逼格不够。就叫英文的，look-alike~
关于look-alike的详细实现，市面上没有统一的做法，毕竟我们正在经历。
这样一来我的心也放下了。由于即便我以下都是胡扯也不一定是错的。
look-alike的核心是按着回头客的样子去找新用户。
那简单呀，看看回头客的标签是什么样子，对着去找同样的不就可以了？没错，这算一种方法，而且是一种基于规则的方法。可是直觉告诉我们这样做粒度太粗，没有充分考虑到广告主因素。同一时候经验也告诉我们。基于规则的不如基于模型的效果好。所以我们还能够得出一个基于模型的做法：将某用户是否是潜在用户建模成一个机器学习中的二分类问题，利用回头客数据训练模型。并在新用户上做预測。是就是1不是就是0。也挺好理解的。
受众定向关键技术我们就介绍到这里了。如今我们来回想一下。
为了更加精准的刻画用户，我们从用户标签、上下文标签和广告标签三个方面来介绍受众定向。虽说角度不同。但总的说来，不外乎两种方法：基于规则和基于模型。在受众定向技术的支持下。互联网广告进入合约广告时代。在经见了在线分配的大坑之后，媒体站点发现合约不可保。便使用竞价方式售卖流量，指定广告主。那在竞价广告中，又有什么关键技术呢？请看下一小节：竞价广告关键技术：点击率预估。
5.2 竞价广告关键技术：点击率预估
郭德碗：聊(bi)了(bi)了这么久，想必衣食父母也都累了。
于 兼：是有点儿。
郭德碗：能坚持看到这儿的人不多。
于 兼：东西太难。
郭德碗：那就歇了吧，《计算广告小窥》到此结束！
于 兼：给我回来！
像话嘛这个。
郭德碗：还想怎么着啊？
于 兼：说好的点击率预估呢？大伙都冲这个来的。
郭德碗：真有冲这个来的？
(有！)
郭德碗：怎么不提钱跟我说呢？
(吁~)
郭德碗：好了。玩笑归玩笑，驴鞭归于兼，以下呀，我..
于 兼：您等会儿，那玩意儿归我干嘛呀？
郭德碗：嘿嘿嘿。
(吁~)
郭德碗：你们都懂？
(吁~)
郭德碗：仁者见仁。污者见污哟。
(下去吧~)
我知道非常多同学是冲着点击率预估来的。所以不能让你们白来不是，免费送您一小段儿，别跟我提钱哈哈。等最后聊到最小广告系统。帮我贡献几次点击就可以，我也好收集一些高质量数据。训练模型自己玩儿。
言归正传，以下我们将从“是什么”、“为什么”和“怎样做”三方面来介绍点击率预估。
5.2.1 点击率预估是什么
点击率
一句话解释点击率：0.1%
既然聊到点击率预估，那我们先来看看什么叫点击率。点击率这个概念我们是第一次提起，但事实上我们早就知道它了。
我们在《计算广告小窥[上]》以前提到：
“自从广告上了互联网。广告的面貌就焕然一新。造成行业巨变的原因，是由于互联网广告的效果能够被衡量。”
假设接着往下说，以什么标准来衡量呢？没错，最经常使用的衡量标准就是点击率。点击率(CTR:Click-Through Rate)是指的是媒体站点上某个广告的点击量/展示次数。之所以使用点击率来衡量广告效果是有原因的，先来看分母：分母是某广告的总展示次数。
在《计算广告小窥[上]》中我们曰过，广告展示机会是广告主通过竞价获得的，展示机会越多。意味着广告主的出价越高，所以总展示次数能够用来表征广告主的广告投入。再来看分子：分子是总点击量，而点击行为代表了用户的注意力，说明用户渴望进一步了解广告内容。因此点击率越高，意味着广告主在同样投入的情况下。收获了很多其它的用户注意力。完美诠释了广告主做广告的初衷，所以点击率是广告主和媒体站点经常使用来衡量广告效果的标准。我听过一个数字，广告平均点击率为千分之中的一个。也就是每展示1000次广告才会收获1次点击，所以点击率预估中数据都是非常稀疏的。
点击率预估
一句话解释点击率预估：80%
了解了点击率。我们再来看看什么叫点击率预估。
从字面上理解，点击率预估是预測媒体站点上某个广告的点击量/展示次数。然而这样理解并非非常准确，我先给出我的理解：点击率预估。是指预測特定用户点击特定广告的概率，比如小明点击某信二手车广告的概率是80%。
为什么对媒体站点广告点击率(0.1%)的预測，会变成了对用户点击某广告概率(80%)的预測呢，接着往下看啦。
5.2.2 为什么要做点击率预估
一句话解释为什么要做点击率预估：钱。
在竞价广告阶段，广告主与媒体站点之间以按点击付费(CPC)的方式结算。因此我们能够用下列公式来表征媒体站点在某次广告活动中的收入：
媒体站点收入 = (点击率 * 展示次数) * 单次点击价格 = 点击量 * 单次点击价格
我们知道。展示次数和单次点击价格这两部分都是广告主參与竞价后才干决定的，与媒体站点无关，所以媒体站点的收入就与点击率直接挂钩。在收益最大化的驱使下，媒体站点有提高点击率的动力。
点击率的定义是点击量/展示次数。展示次数又是广告主通过竞价决定的，因此媒体站点仅仅能想方设法提高点击量。
对于媒体站点而言，他所拥有的资源就是页面上几个固定的广告位和海量的用户。为了提高点击量，一种简单明了的想法就是让展示的广告尽可能多的被点击，即“指哪儿打哪儿”。为了实现这个理想，亟需解决两个问题：首先须要知道用户感兴趣的广告有哪些，其次须要让用户尽可能多的点击这些广告。
第一个问题叫做“广告检索”。是指媒体站点依据用户的定向标签或其它方式检索出符合用户口味的广告候选集合。这部分内容是搜索引擎的核心，在这里我们就不展开讨论了。
我们来看第二个问题，假设我们已经得到了一个符合用户口味的广告候选集合。怎样能让用户很多其它的点击呢？非常简单，把用户最可能点击的广告放在最显眼的地方，为了定量描写叙述用户最可能点击的广告。这便引出了点击率预估的问题。
因此我们说。点击率预估并非来预估媒体站点上点击量/展示次数，而是预測某个特定用户点击某个特定广告的概率。OK。那预估完干什么呢？刚才不是说了嘛。把最可能点击的广告放在最显眼的地方呀！
最显眼的地方
一句话解释最显眼的地方：你也是柳岩的球迷？
为了较为直观地描写叙述用户的注意力分布。我找了一张LinkdIn的用户注意力热力分布图。(图片来自网络)
图中。颜色越红代表用户注意力越集中。
能够看到。用户最关注的是页面的上半部分，其次是右半部分，最后是下半部分。这样的注意力分布基本我们日常的浏览习惯，即假设能在页面靠前位置找到我们所需的信息，一般就不会再关注页面其它地方。了解了注意力分布，我们来看一下某度搜索页面上的广告位分布。
某度广告位主要分布在北区、东区和南区三部分，以LinkedIn页面中的用户注意力分布来猜測。用户在某度页面上注意力分布从高究竟各自是北区、东区和南区。假设某度共同拥有10个广告位，那么将用户最可能点击的10个广告依照点击概率由高到低顺序分别排在北区、东区和南区。然后还干嘛？没有了。万事俱备，仅仅欠点击。
不知道您听明白了没。我来帮您捋捋。为了提高媒体站点的收益，我们结合业务场景不断简化问题，从提高媒体站点点击率入手。到提高总点击量，再到获得广告候选集合，预測出了用户点击广告的概率。仅仅预測点击概率媒体站点还赚不着钱。因此媒体站点依据点击概率在页面广告位上对广告进行排序。所以为什么要做点击率预估呢？都是为了钱。都是为了钱！都是为了钱！
5.2.3 点击率预估怎么做
一句话解释点击率预估怎么做：使尽浑身解数，仅仅为更懂你。
自计算广告学诞生以来，点击率预估就是一个在学术界和工业界被广泛研究和实践的课题。剥去种种详细场景，点击率预估的本质事实上还是一个机器学习中的二分类问题。一般来讲，媒体站点PV数据的数学分布是非线性的。为了拟合这样的非线性关系，学术界側重于模型的研究。工业界側重于特征的构造，双方优势互补，已取得了相当丰硕的成果。以下我们将先介绍展示广告和搜索广告这两种互联网广告的主要形式。然后阐述二者在点击率预估问题上的不同之处，最后介绍一些点击率预估的方法。
展示广告
展示广告(Display Advertising)是一种以“图片+文字”的方式进行广告宣传的互联网广告形式。
从广告触发方式来看。展示广告是媒体站点依据用户历史行为所做的推荐。对用户而言广告是被动接收的，例如以下图。
搜索广告
搜索广告(Sponsored Search)是一种以“标题+超链接”的方式进行广告宣传的互联网广告形式。
从广告触发方式来看。搜索广告是媒体站点针对用户当前检索所做的广告匹配，广告是用户主动发起的，例如以下图。
依据上面我们对展示和搜索广告的描写叙述。我们能够对两种广告形式的点击率预估有一个浅显并直观的认识：展示广告的点击率预估能够看作是一个推荐问题，依据历史记录猜測用户对哪些广告更感兴趣；搜索广告的点击率预估能够看作是一个检索问题，依据用户当前的查询来做广告匹配。前者推荐后者检索，问题性质的不同也决定了点击率预估所採用方式的不同。
点击率预估方法
有关展示广告和搜索广告的实现算法和应用细节都是各家互联网公司的商业机密，由于场景的不同，各家对点击率的预估也是八仙过海各显神通。作为一个没有实战经验的小屁孩儿。想要较为流畅地阐述这个话题，还是力不从心，毕竟眼界太窄太年轻。为了保证文章结构的完整，这部分还必须要写，那么我就抛开业务场景，仅从机器学习角度来和大家聊一聊我所知道的内容。写的不好。还请各路大神多多不吝赐教，如有不当指出，请严厉指出。我定感激不尽！
上面我们提到过，从用户浏览网页到广告获得展示。要经过三个阶段：用户定向、广告检索和广告排序。用户定向和广告检索就不多说了。最终在广告库中能够找到符合你口味的广告。即“万里挑十”。
在广告排序阶段。须要将这十个广告位放置在页面上。通常做法有两种，一个是基于规则，一个是基于机器学习。我们这里从机器学习的角度入手。可是各位千万不要忽视了规则的能力。聊到机器学习。主要就是双方面，特征和模型。
以下我就依据我所了解的内容，重点介绍一下线性模型+海量特征的方法，然后简介一下点击率预估的发展。
<1>线性模型 + 海量特征
用于点击率预估的数据主要是日志数据。通常会有点击行为(点击为1，没点为0)、广告信息(广告位、广告主id、广告标签和广告描写叙述等)、用户信息(用户id和用户标签等)、上下文信息和时间戳等。
有了这些原始数据之后。须要对数据进行清洗。然后利用统计或模型的方法构造特征，进而做特征选择和特征组合，最终特征的数量级大约在10亿-100亿维。
完毕了特征工作之后。在模型方面，较为经典的点击率预估模型是线性模型Logistic Regression，由于LR在通过sigmoid之前是一个[0,1]之间的浮点数，利用LR的特点，我们能够将这个浮点数作为用户点击该广告的概率。把广告依照这个概率从高到低放置在相应广告位上，就完毕了广告排序。
为什么要造出维度这么高的特征向量呢？我的理解是这样的。对于PV数据来说，点击行为与其它特征之间的关系是非线性的，为了拟合这样的非线性关系，我们依旧能够从特征和模型双方面入手。
通常来说，非线性模型的效果要更好一些。可是效率太低，不适合工业界的现实场景，所以高速简单的线性模型就成为了模型的首选。那线性模型怎样拟合非线性关系呢？这就须要在特征层面做文章，利用特征project的方法来构造出高阶特征，同样能够实现非线性。这个思路理解起来还是不难的，如以下两式对比：
特征工程前：y1=w1x1+w3x2+1
\text{特征project前}\text： y_1= w_1x_1 + w_3x_2 + 1
特征工程后：y2=w1x21+w2x1+w3x2+w4x1x2+1
\text{特征project后}\text： y_2= w_1x_1^2 + w_2x_1 + w_3x_2 + w_4x_1x_2 + 1
<2>点击率预估的发展
为了构造出维度如此巨大的特征向量。特征project差点儿占领了70%的项目时间。而且主要是靠努力的程序猿人工来实现的。
那有没有自己主动选择特征的方式呢？ADKDD’14有一篇Facebook的paper《Practical Lessons from Predicting Clicks on Ads at Facebook》提出了一种使用GBDT自己主动选择特征的方法，用每棵树上的叶子节点来表达特征，比方{1:2, 2:3}指的是第一棵树上第2个节点和第2棵树上第五个节点，依据每棵树的节点个数用one-hot表示就可以。多说一句，GBDT选特征的方法已经经过实践验证，在Kaggle-Criteo点击率预估大赛中。冠军的解决方式便是GBDT+FFM的方法获得的。
说到FFM，它是FM的一个变种。FM(Factorization Machine)：因式分解机是近期比較火的一个模型，这个模型能够挖掘出特征间的非线性关系，而且能够在O(n)O(n)的时间内完毕计算，非常吸引人。
最后就是深度学习了。在视频、图像和语音领域有较为突出的成果。最新的听说MSRA出了一个152层的网络。OMG…国内在广告领域应用深度学习最早的应该是百度IDL，据说有三十多层，评价指标提升了三个百分点，看来DL的能力还是非常强的。我自己也在探索阶段，期待能有好的结果。这里就不多说了。
点击率预估环节到这里就结束了，以上内容不知是否和您心意。
部分内容可能须要一些机器学习背景，对此感兴趣的同学能够加入我们的QQ群(刚開始学习的人373038809，行业同学和研究者472059892)。我们共同讨论。好累呀，卖个萌再往以下写吧。(图片来自网络)
5.3 程序化交易关键技术：出价策略
在上半部分中，我们以前介绍过程序化交易中的參与者，除了用户外，主要还有代表媒体站点利益的SSP、代表广告主利益的DSP和小三ADX。通俗来讲。SSP是管仓库的，ADX是管传话的，DSP是管花钱的，如今我们要開始聊程序化交易中的关键技术，您认为我们应该把目光放在谁上面呢？已经讲到如今了，我们要收起情怀，统一思想，当然是要重点关注DSP啦！你可能会想，花钱谁不会啊。这要啥技术？没错。花钱是没什么难的。但对于广告主而言，花钱做广告是一种投资。本质和风投股票文玩楼盘高利贷没什么差别。追求的就是高的投入产出比，真刀真枪的动起钱来，弄不好会走火入魔的。这钱。您还敢花吗？
敢啊！
要是不敢我还怎么写博客嘛，哈哈哈哈哈~~~花钱不要紧，仅仅要能挣就可以了呀！那我们就来聊聊怎样才干挣的比花的多吧。
5.3.1 出价原则
上面我们提到，广告主花钱做广告实际上是一种投资行为，既然是投资。就要对风险进行评估。
详细到DSP来说，“投资”是指广告主投钱给DSP。让其參与实时竞价，期望获得良好的广告效果(点击/购买/注冊/下载等)。“风险”是指钱花了，但由于效果太差，没见着收益。为了规避风险，获取较高的投入产出比，DSP在出价时须要进行“风险评估”。即预估本次广告展示机会所能带来的收益。以此作为出价的參考。
在出价时。要注意以下几点原则。可能并不全面，还请行业内的同学补充。
预算限制：广告主一次就给这么多，超了算你的。
时间限制：到时间花不完就收回去了。
花钱为主：都说了是投资。能花了就别留着。
见好就上：出价与流量品质成正相关。
这些出价原则理解起来没什么难的。但我想要着重说一下第四条见好就上，这才是最关键的部分。怎样定义流量品质，又怎样出价呢，好戏立即開始。
5.3.2 怎样定义流量品质？
所谓流量品质。就是在此时此刻此情此景，用户点击广告能为广告主带来的收益，主要分为两部分：一是点击率，二是点击价值。
点击率的预估就不多说了，和媒体站点上点击率预估是相似的，仅仅只是在实时的场景下要求会更高一些。点击价值是什么意思？刘鹏老师在《计算广告》中这样解释道：（有部分改动。括号内容为我的解释）
点击价值能够分解为到达率、转化率和转化单位价格三个量的乘积。到达率是指实际打开广告次数与点击次数的比例，这与广告主站点的页面你打开延迟关系最大，与媒体的属性、特别是误点情况也有一定关系；转化率指的是到达广告主页以后，有多少比例产生了广告主定义的转化行为(购买/注冊/下载等)；转化单位价格是指广告主指定的转化费用(即DSP做一单能挣多少)。
上述三个变量中。到达率和转化单位价格都是非常好统计的，仅仅有转化率的预估是比較困难的。转化率预估的方法能够參照点击率预估。可是由于转化数据要比PV数据少得多，除非是在有充足行业数据支持的情况下，否则用机器学习方法建模有较大困难。
实践中比較可行的办法基本上都是简单统计与运营经验相结合来估算转化率。
5.3.3 怎样出价？
最终进入到了最核心的出价环节。
依照“见好就上”的原则，出价与流量品质成正相关。那究竟是採用线性策略好，还是非线性策略好呢？我们来细致分析一下。
线性出价策略
我们在CTR预估阶段提到过用户注意力，广告位这个物理因素对点击率的影响是十分显著的。我曾看到过一个数字，同样一个广告。把它放在第一位所获得点击率是放在第二位时的两倍。
若採用线性出价策略，DSP在出价时就有必要出两倍于第二位的价格去參与竞价。这个思路非常好理解，感兴趣的同学能够參照KDD’12的paper《Bid Optimizing and Inventory Scoring in Targeted Online Advertising》。
非线性出价策略
非线性策略是我想说的重点，主要是想借着这个机会介绍一下限制条件下的优化问题以及其解法，这对于我们做科研或者project项目都是非常有帮助的，以下我们通过KDD’14《Optimal Real-Time Bidding for Display Advertising》一文来了解一下非线性出价策略的来龙去脉。以下内容是我对这篇paper的个人理解。可能并不到位，既然写出来就不怕大家笑话啦，有错就改嘛嘿嘿。
<1>. 文章大意
实时竞价的场景中，在预算限制条件下怎样设计出价策略是我们关注的焦点。为了实现这一目标。分为三步。第一，将现实问题用数学方法建模为限制条件下的优化问题，并通过拉格朗日乘子法。求得出价策略的数学表达式；第二，利用品友RTB出价算法大赛的数据拟合出价策略中的參数。第三，验证结果，发现了一个有意思的结论：相比少量高品质的展示机会。那些大量低品质的展示机会同样能够具有较好的广告效果，值得出价。这个发现对于那些预算不够，同一时候又想做广告的小广告主来说，简直就是福音。
<2>. 建立模型
在一切開始之前。让我们先考虑清楚要解决的问题是什么，简单来说就一句话：选择合适的出价策略，在预算的限制下实现广告效果最大化，用数学语言描写叙述就是以下这样：
b()ORTB=argmaxb()NT∫xθ(x)w(b(θ(x),x),x)px(x)dx
b()_{ORTB} = argmax_{b()} N_T\int_x \theta(x)w(b(\theta(x),x),x)p_x(x)dx
subject to NT∫xb(θ(x),x)w(b(θ(x),x),x)px(x)dx
\text{subject to }\text N_T\int_x b(\theta(x),x)w(b(\theta(x),x),x)p_x(x)dx
我靠！这一堆是什么玩意儿。你TM在逗我？淡定。。看不懂就对了啊哈哈哈哈！
以下我来做一下简化，告诉你这个模型在我眼中长什么样。
b()ORTB=argmaxb()一大坨 ！
b()_{ORTB} = argmax_{b()}\text{一大坨 }\text。
subject to 又一大坨 !<B
\text{subject to 又一大坨 !}\text
这下是不是好多了？反正我第一次看到这个模型就长这样，把积分部分当作一大坨，就非常easy看懂了。这个模型一共同拥有两个公式。我们一一来看。
b()ORTB=argmaxb()一大坨 ！
b()_{ORTB} = argmax_{b()}\text{一大坨 }\text！
第一个公式是一个等式。等号左边是我们想得到的出价策略函数b()ORTBb()_{ORTB}，等号右边是argmaxb()argmax_{b()} 跟上一大坨。这里argmaxb()argmax_{b()}的意思是：当后面一大坨取最大值时，返回在最大值情况下的那个b()b()。将等号左右两边连起来，这个等式所表达的意思就是：当后面一大坨取最大值时，返回在最大值情况下的那个b()b()作为我们要求的出价策略b()ORTBb()_{ORTB}。这个思路是不是有点眼熟？没错，在前面合约广告关键技术——受众定向中，讲到用户动态特征时我们对泊松分布的处理方式有些相似。
综上所述，对于这个等式而言，我们要做的工作就一个：求最大值。
subject to 又一大坨 !<B
\text{subject to 又一大坨 !}\text
第二个公式是一个不等式。subject to是“受限于”的意思。在这里，又一大坨 !<B\text{又一大坨 !}\text 想要表达的就是一个限制条件，在等式求最大时插上一脚。还记得我们在高中时学过的线性规划吗，一样的道理。
如今我们的任务已经明白了：在限制条件下求等式最大值。
那么这个数学任务和我们的实际问题：选择合适的出价策略。在预算的限制下实现广告效果最大化是怎么匹配上的呢？这就须要去看那两大坨了。那一大坨全都是各种符号，我们看不懂。所以须要一张符号对比表，例如以下图。为了方便，我再把模型公式再贴一次。
b()ORTB=argmaxb()NT∫xθ(x)w(b(θ(x),x),x)px(x)dx
b()_{ORTB} = argmax_{b()} N_T\int_x \theta(x)w(b(\theta(x),x),x)p_x(x)dx
subject to NT∫xb(θ(x),x)w(b(θ(x),x),x)px(x)dx
\text{subject to }\text N_T\int_x b(\theta(x),x)w(b(\theta(x),x),x)p_x(x)dx
有了符号定义和模型。我们開始聊(啃)一聊(啃)这两大坨吧。先看第一坨。我们从右往左看。
dxdx：x代表一次bid request。是ADX发给DSP的竞价请求“标识XXX,男性，20-25岁。跑鞋爱好者。广告位为首页”，即一次广告展示机会。之所以是dxdx而不是xx，是由于我们关注的是整个广告推广计划中全部的竞价过程，而非某一次竞价。
px(x)p_x(x)：广告展示机会的概率密度分布，我的理解是在全网全部的竞价中，满足我DSP要求的、或者是我能收到的bid request所占的比例。因此，px(x)∗dxp_x(x)*dx的物理意义是“我能收到的展示机会”。
θ(x)\theta(x)：θ\theta是赢得此次竞价所能带来的收益(KPI)，本文用CTR来衡量，CTR越高。收益就越高。
b(θ(x),x)b{(\theta(x), x)}：对于此次展示机会，在能带来收益为θ(x)\theta(x)的情况下，我所出的价格bid。
ω(b(θ(x),x),x)\omega{(b(\theta(x), x), x)}：对于此次展示机会。在能带来收益为θ(x)\theta(x)的情况下。我的出价bid能获胜的概率是多少。
因此。ω(b(θ(x),x),x)∗px(x)∗dx\omega{(b(\theta(x), x), x)}*p_x(x)*dx的物理意义是“对于本次我所收到的这个展示机会来说，在该机会能带来收益为θ(x)\theta(x)。我出价为bid的情况下，我能打败对手获得此次展示机会的概率”。
θ(x)\theta(x)：依旧收益。所以θ(x)∗ω(b(θ(x),x),x)∗px(x)∗dx\theta(x) * \omega{(b(\theta(x), x), x)}*p_x(x)*dx的物理含义是“我出价为bid，赢得这次展示机会后，所能获得的收益”。
NTN_T：一次广告推广活动中全部的bid request。
有了上面的解释。我们能够非常easy的得出第一坨的物理意义：对于一次广告推广活动中的全部竞价，我使用b()b()的出价策略所能获得的收益。和等式连起来，即：对于一次广告推广活动中的全部竞价，我使用b()b()的出价策略所能获得最大收益时所相应的b()b()，就是我们想要的出价策略。
有了第一坨的经验，第二坨啃起来就easy多了。前面都不变。仅仅有到最后把θ(x)\theta(x)换成了b(θ(x),x)b{(\theta(x), x)}。变为b(θ(x),x)∗ω(b(θ(x),x),x)∗px(x)∗dxb{(\theta(x), x)}*\omega{(b(\theta(x), x), x)}*p_x(x)*dx，其物理意义为：对于这次广告展示机会，我出价为bid且赢得这次展示机会所花费的预算。所以对于整个广告推广活动而言。全部的出价要小于预算。
就这样，我们顺利的将预算限制写进了数学模型里。
好了，分析完两大坨积分的含义之后，我们合起来解释一下该模型(ORTB)所表达的物理意义：在整个广告推广活动中。在出价总和小于预算的限制条件下。当广告收益取得最大值时所相应的那个出价策略。就是我们梦寐以求的出价策略b()ORTBb()_{ORTB}。再来对比一下我们的任务：选择合适的出价策略，在预算的限制下实现广告效果最大化。这下匹配了吧！
完美！
(图片来自网络)
<3>. 模型求解
截止到眼下，我们已经得到了模型表达式，由一个等式和一个不等式组成。接下来我们就要開始求解了：求最大值。最大值有什么好求的？让导数等于0之后带入极值点不就完了？你说的对，假设仅仅有一个等式我们是这么求的，但问题是我们如今除了一个等式，另一个不等式。这样的情况下怎么来求最大值呢？用拉格朗日乘子法。
通过拉格朗日乘子法，我们能够将不等式乘一个參数λ\lambda后和等式写进一个公式里(化简过程已省略)。得到例如以下结果。
L(b(θ),λ)=∫θθw(b(θ))pθ(θ)−λ∫θb(θ)w(b(θ))pθ(θ)dθ+λBNT (6)L(b(\theta), \lambda) = \int_\theta\theta w(b(\theta))p_\theta(\theta) - \lambda\int_\theta b(\theta)w(b(\theta))p_\theta(\theta)d\theta + \frac{\lambda B}{N_T}\ \ \text{(6}\text)
有了这个公式，我们就能够对它进行求导等于0了，可得例如以下结果：
θpθ(θ)∂w(b(θ))∂b(θ)−λpθ(θ)[w(b(θ))+b(θ)∂w(b(θ))∂b(θ)]=0 (7)\theta p_\theta(\theta)\frac{\partial w(b(\theta))}{\partial b(\theta)}-\lambda p_\theta(\theta)[w(b(\theta)) + b(\theta)\frac{\partial w(b(\theta))}{\partial b(\theta)}] = 0\ \ \text{(7}\text)
通过化简，可得出价函数b()b()与胜率函数w()w()的关系：
λw(b(θ))=[θ−λb(θ)]∂w(b(θ))∂b(θ) (8)\lambda w(b(\theta)) = [\theta - \lambda b(\theta)]\frac{\partial w(b(\theta))}{\partial b(\theta)}\ \ \text{(8}\text)
也就是说。我们想要的出价函数b()b()与胜率函数w()w()有关，那我们就来看看他们之间究竟有什么关系。通过对数据的统计。能够画出出价函数b()b()与胜率函数w()w()的关系图像：
从图像中我们能够看出，出价函数b()b()与胜率函数w()w()的关系是非线性的。而且这个曲线的走势和y=xc+xy=\frac{x}{c+x}非常像。我们来对比一下。这里c=3。
没错。的确非常像。基于此。为了达到消元的目的。作者做了一个出价函数b()b()与胜率函数w()w()之间的假设。仿照着y=xc+xy=\frac{x}{c+x}得到以下公式：
w(b(θ))=b(θ)c+b(θ) (9)
w(b(\theta)) = \frac{b(\theta)}{c + b(\theta)}\ \ \text{(9}\text)
将出价函数b()b()与胜率函数w()w()的9式关系带入到倒数为0的7式中，化简可得：
bORTB1(θ)=cλ+c2−−−−−−√−c (13)
b_{ORTB1(\theta)} = \sqrt {\frac{c}{\lambda} + c^2} - c\ \ \text{(13}\text)
就这样，我们得到了我们的出价策略bORTB()b_{ORTB()}的表达式(公式13)。我们来看看这个公式里有什么。这个公式是由θ\theta， cc和λ\lambda组成的。当中cc和λ\lambda都是常量，仅仅有θ\theta一个变量。cc是出价函数b()b()与胜率函数w()w()之间的系数，λ\lambda是拉格朗日乘子。而θ\theta是每次广告展示的收益。按CTR高低来评判。我们来验证一下：CTR越高。由该策略算出的出价也就越高，符合我们的预期，大功告成。
我们来梳理一下思路。
在建模环节，我们已经得到了我们所需的模型：一个等式+一个不等式。
我们的任务是要求等式的最大值，通常方法直接对等式求导等于0就可以。由于我们这里是一个限制条件下的优化问题。所以须要用到拉格朗日乘子法。将限制条件写进等式中。构造出一个新的公式(公式6)。对于新的公式，我们就能够用求导等于0了(公式7)。在化简过程中。我们发现了出价函数b()b()与胜率函数w()w()存在着数学关系(公式8)，为了消元，我们依照实际数据的分布构造出出价函数b()b()与胜率函数w()w()的表达式(公式9)，将公式9带入公式7，继续化简就得到了我们的出价策略：bORTB()b_{ORTB()}，剩下的工作就是依据数据去拟合λ\lambda和cc就可以。这里就不多说了。这里须要强调的是，这样的限制条件下的优化方法在统计与机器学习中是非经常见的，比如SVM的推导过程。感兴趣的同学能够试一试，事实上并不难。
<4>. 结果分析
既然有了公式，那我们就来看看ORTB的出价有什么特点吧。
我们能够非常直观的看出，我们所得到的出价策略是一个非线性的。横坐标θ\theta代表了广告展示计划的品质，ORTB会对低价值的展示机会出高价，这样的结果能为我们带来什么。谁会去要那些低价值的展示机会呢？我们来看以下这张图。
在此图中。我们盯着一条曲线看，比方蓝色的(1/32)。随着λ\lambda添加，收获的点击量是添加的，意味着λ\lambda越高。我们的收益越高。对于我们获得的出价策略而言。λ\lambda越高，我们的出价是越低的。也就意味着这次展示机会的价值是非常低的。这样的结果值得我们深思，我们以为低价值的展示机会是不值钱的，但数据说明。这些看似不值钱的展示所能带来的回报还算不错。
特别地。在λ\lambda=1e-05时三条曲线的差点儿重合，而红色代表有钱的广告主。蓝色代表穷广告主，尽管预算差了16倍。可是获得的收益是同样的，这个结论对于预算有限的小广告主而言，是个天大的好消息：尽管我们钱不多，但仅仅要我们出价合适。依旧能够收获非常好的广告效果。四两拨千斤，极大的调动了小广告主參加程序化交易的积极性。
我们知道，“二八原则”是客观存在的。在广告主中也不例外，假设能吸引这80%的小广告主參与程序化交易，玩家一多。需求自然很多其它。
为了满足金主的需求。势必会推动相关计算技术的发展。这对于计算广告的未来而言，是一件好事。
讲完了非线性出价策略，程序化交易中的关键技术也接近尾声了。出价策略之所以重要，是由于就是DSP赖以生存的看家本领，没有这些真本事，DSP是走不了多远的。
到此，计算广告关键技术就讲完了。啥也不说了，给自己鼓个掌吧(图片来自网络)。
历时大半个月。中间又加上过春节。最终把这章给写完了。没想到这一章的内容要比上半部分全文都要多。在本篇《计算广告小窥[中]这孙子怎么什么都知道》中。我们从理论的角度探讨了计算广告各阶段的关键技术：在合约广告中，我们讨论了受众定向技术，从用户、上下文和广告主三个方面简介了打标签的经常使用思路和方法，为计算广告实现精准营销打下了坚实的基础。在竞价广告中。我们讨论了点击率预估的来龙去脉，感受到了互联网人的智慧，为媒体站点流量变现提供了直接保障；在程序化交易广告中。我们通过学术论文了解了当下学术界率先的DSP出价策略，近距离地感受了一下科研的魅力。
曾有人叹息到“我们这一代最聪明的人居然都在这里思考着怎样让人们去大量的点击广告。真衰。”我个人不认同这样的说法，由于在计算广告这样复杂的场景下，相关技术和解决方式的水准必定是顶尖的，稍加改动就可以解决其它场景下的疑难杂症，这恰似军工技术反哺民用，又恰似女生随手甩一个不要了的护肤品给男生。那可都是宝。
受篇幅所限，原定于本篇要完毕的第五章和第六章仅仅好放在《计算广告小窥[下]广告系统架构：要啥自行车，这里有宝马。
》中来写了。
在下篇中，我们将介绍一个通用的广告系统架构。在领略在线和离线过程的同一时候。还将见到时下工业界最火热的技术，譬如Nginx。Hadoop。Spark等在计算广告领域的位置与应用。
除了广告系统架构，我还将介绍一个我自己搭的最小广告系统mieSys。能够先放出来给大家玩一玩，链接是http://115.159.33.50/。
用法：用户点击页面中广告，等一段时间后刷新页面，在页脚处会显示用户的兴趣标签和性别，在第一行五个广告位中会展示符合用户口味的广告。须要注意的是，由于眼下缺少PV数据，CTR模型并不准，为了保证演示效果，临时仅仅能用离线取代在线，所以您在点击过后估计要10分钟(用户多的话甚至更长)才干看到页面效果。我后期会进行优化。还望轻拍，效果图例如以下。第一张为默认页面。第二张为结果页面。
这个系统是我用大概20天的时间搭成的，眼下来说主要的功能都有。但还是太简单，而且算法没有优化。我会逐步的往上面加入模块和算法，眼下思路已有，就差各位为我提供PV数据了[嘿嘿嘿嘿···]。假设您发现mieSys挂了。不是用户太多就是我在调程序，在系统成熟的时候我会选择开源，愿意与有兴趣的同学多交流。
哦对了，至于为什么起名为mieSys，由于我女朋友属咩，呵呵哒~
好了，我们《计算广告小窥[下]》再见！
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i ').text(i));
};
$numbering.fadeIn(1700);
});
});
