ML学习分享系列|ML学习分享系列3_计算广告小窥[下]要啥自行车！机器学习|广告系统|计算广告

【ML学习分享系列|ML学习分享系列3_计算广告小窥[下]要啥自行车！】原作：@面包包包包包包
修改：@寒小阳 && @龙心尘
鸣谢：百度德川、阿里怀人、阿里口肃、腾讯Fandy王、优酷吕红亮
时间：2016年8月
出处：http://blog.csdn.net/breada/article/details/52275063 ,
http://blog.csdn.net/han_xiaoyang/article/details/52275318
声明：版权所有，转载请联系作者并注明出处
1. 引言提笔写这篇博客，我的内心是惶恐的。原因很简单，作为一个资历尚浅的研究生，是没有资格对计算广告这样一个伟大的行业、领域和学科来评头论足的。之所以这么做，一是总结自己已掌握的知识，二是降低同学们的学习成本。本人能力有限，更缺乏实践经验，文章内容多为书籍和论文的读后感，若有不当或者错误之处，还望各位同学指出，我定悉心求教。在此，向编写《计算广告》的刘鹏和王超两位老师致谢，向各位paper作者致谢。
[关于ML学分计划]

由寒小阳和龙心尘发起，一个互帮互助的机器学习知识共享平台。
我们是一群对机器学习感兴趣的小伙伴，对于神奇的机器学习经常有“一探究竟”的冲动，却因为孤身一人学习的寂寞、亦或繁忙考试工作之余的小小拖延症，而没有持续这份对知识的渴求和热情。
由于深感类似情况的小伙伴之多，我们希望建立一个“ML学分计划”——机器学习的学习和分享计划——来帮助我们一起更高效地学习、更集中地整理分享我们的知识和经验。因为我们也深信”证明自己真的透彻理解一个知识，最好的方法，是给一个不熟悉这个内容的人，讲清楚这个内容“。

[关于原作@面包包包包包包]

海淀区明光村计算机职业技术学院，研三学生。
关注计算广告点击率预估和竞价算法，关注机器学习和深度学习，初学者。
机器学习QQ群：数据科学3群 285273721，行业同学和研究者472059892。

(上)(中)(下)全文目录

引言
广告=>互联网广告：“您好，了解一下”
互联网广告=>计算广告：指哪儿打哪儿！
计算广告四君子：谁在弄潮？
计算广告关键技术：这孙子怎么什么都知道？
广告系统架构：要啥自行车！
手把手系列之教你搭建一个最小广告系统：mieSys

6. 广告系统架构：要啥自行车！

一句话解释广告系统架构：“道生一，一生二，二生三，三生万物。”

场景1

时间：13:40 地点：北邮北门人物：快车司机，我事件：去面试状态：忐忑

坐在车里，手机打开为知笔记，想再瞅一眼的树的几种遍历方法。眼睛跟着递归，思绪却爆了内存：面试官长什么样？他会问我什么问题？部门名字听起来还挺高大上的？面试完在附近吃点什么呢？听同学说附近的小吊梨汤很赞啊！面包包包，那就小吊梨汤吧？好啊好啊，出来再加个西少爷肉夹馍吧？好啊好啊！“噗”的一下笑出了声，还好司机师傅并没有在意。我连忙收起自己的小尴尬，平复一下心情，然后开口问道，“师傅，今天您拉几单了？”
场景2

时间：14：20 地点：中关村某大厦十几层的一个小会议室内人物：我事件：等待面试官状态：好奇，兴奋

原来大家工位都是在一起的呀。这这会儿灯都关着，还有午休呢。门口小哥和我差不多大，聊的还不错。面试官还没来，先把简历和白纸都摆摆好。一切准备就绪，抿了一口水，可以，这很怡宝。
场景3

时间：14：30 地点：中关村某大厦十几层的一个小会议室内人物：面试官，我事件：一面状态：轻松，愉悦

我：面试官好！
面试官：你好，请坐（拿着简历开始看），先简单介绍一下自己。
我：blablabla…
面试官：嗯，来写道题吧。
我：正面钢，不能怂！挥笔写下了一行代码：
return "烫烫烫" == "屯屯屯" ？ "烫屯烫" ： "屯烫屯"；
面试官：

我：

面试官：加个微信吧，以后要是没事儿了咱们斗图玩儿。
我：哪儿斗得过您呀，跟着您多收藏几个表情，来我扫您二维码。
场景4

地点：中关村某大厦十几层的一个小会议室内人物：leader，我事件：二面状态：认真，专注

leader：听说你们刚刚斗图斗的很开心，我这儿没图，咱们换一种玩法吧。
我：我心想没图你说个。。说一声啊，我发您。
leader：不闹了哈，我看你简历上说你对计算广告有些了解，那你能不能通过一个case能让我知道你对计算广告都了解到什么程度呢？
我：我也顿时来了精神，这个问题好啊！我觉得最好的case是走一遍广告投放的整个流程，在商业逻辑的指导下带出系统框架、功能模块和关键技术，不知您是否感兴趣？
leader：非常好，那你打算从哪里切入呢？
我：就从我们来的地方吧，不忘初心。
时间回到那个清晨，网站收入报表错落着叠放在桌子的一角，左手旁是一杯冷了的速溶咖啡，鼠标有些油腻，用了一年的Cherry青轴依然趁手。敲下最后一个回车，他两手交叠，揉了揉两手酸胀的虎口，“呵，这一夜”。窗外已蒙蒙亮，他有点兴奋，因为今天的太阳，特别好看。

我们在《计算广告小窥[上]》中提到过，互联网广告相较于传统广告，显著之处就在于广告效果可以被衡量。在用结果说话的今天，数据自然拥有着至关重要的戏码。对于媒体网站来说，最重要的数据莫过于用户在什么时间，从什么地方，在网站上做了什么事情。有了这三方面的基础数据，理论上我们可以做任何我们想做的事，譬如在《计算广告小窥[中]》里我们讨论过的受众定向，为用户打上标签，这才有了饼图中的男和女；又譬如点击率预估，将用户可能点击的广告放在最显眼的位置上，提升网站收益。自计算广告诞生以来，类似的应用和场景数不胜数，时刻为用户、广告主和用户服务着。为了能够准确无误的完成上述使命，一个好的广告系统必不可少。那么问题来了，想要完成一次广告投放，需要我们的广告系统具备哪些功能呢？下面我们实地走一遭，完成一次广告投放，看看在这个过程中我们会遇到什么问题、我们如何分析以及如何去解决。所谓一个系统的设计思路，大抵如此吧。
万事俱备，只欠case，具体的case怎么选呢？我替大家选啦！目前为止，我们对饼图应该是最熟的，它那咱们就“重走长征路”，看看如何得到这张饼图，然后用饼图来指导广告投放吧。OK，我们来定义一下问题，我们要完成的是：从数据中挖掘出用户的性别，根据性别为用户展示TA们最可能点击的广告。好了，问题定义完毕，在实际操作之前先从方法论的角度分析一下什么是广告系统，主要有微观和宏观两个方面。
6.0 方法论之——“先把书读厚”
先看前半句，从数据中挖掘出用户的性别，这个好理解，输入是媒体网站的数据，输出就是每个用户的性别，典型的分类问题嘛，打个标签，规则也好，机器学习也好，都是可以做的。后半句呢，根据性别为用户展示TA们最可能点击的广告，输入是用户性别，输出是广告。这些广告是哪儿蹦出来的？想必一定是有一个广告库，这些广告是被挑选出来的，而挑选的依据就是性别。再有，什么叫最可能点击的广告？这个很好理解，当然是用户感兴趣的广告啦，光感兴趣还不行，你还得让用户看到，这就需要排序了，把用户点击率最高的广告放在最显眼的位置上。有没有觉得这些字眼都很熟悉呢？分类，标签，点击率，排序，我们好像在哪儿见过？这不就是我们在中篇里讨论过的关键技术嘛！看来那些高大上的关键技术也是很接地气的，就这么一个看似简单的投放场景，这些技术我们几乎都用到了，好像有点意思哈！现在让我们将上述过程进一步具体，让程序员们可以看懂，便可归纳出下述表格。

步骤	输入	输出	关键技术
Step1	媒体网站日志数据	用户性别	受众定向
Step2	用户性别	召回的广告	广告检索
Step3	召回的广告	排序的广告	CTR排序

6.0 方法论之——“再把书读薄”

根据这张表，一个模型已经清晰地呈现在我们眼前，如上图。在这里，“输入-系统-输出”是一个非常基本且通用的模型，大家可以在很多交叉学科里见到它的身影，例如通信工程里的《信号与系统》和《通信原理》，或者控制工程里的《现代控制原理》，再如机器学习中模型的训练过程，抽象出来都是如此。虽然应用场景各有千秋，但是核心问题只有三个：输入是什么？输出是什么？如何保证系统的稳定性？想要回答这三个问题其实也很容易，以问题场景与核心需求为导向，多问几个为什么即可。所谓：“道生一，一生二，二生三，三生万物”，就是这个道理。
方法论介绍完，微观和宏观都有了，现在让我们回到广告系统中来。系统的输入是媒体网站的数据，输出是排好序的广告，中间部分便是我们要设计的了。得嘞，那咱们走着！
6.1 日志模块

一句话解释日志模块：我有一个小咪咪秘密

系统的原始输入是媒体网站的日志数据，具体而言就是网站的访问日志以及用户的行为记录。想不想偷偷看一眼？就一眼哦。

挺丑的哈~丑不要紧，我们有split(” “)！从日志中我们可以看出，每一条记录都是由IP地址、访问时间、GET请求、资源URL和HTTP Header组成的，其中时间就是访问时间，IP地址表示用户所处位置，做了什么就是GET。可是所有人的数据都堆在一起，我哪能分清谁是谁呢？不是有IP地址嘛！IP地址相同的就是一个人。这个思路可以，但一般不这么用，因为IP地址一般是动态的，不够稳定，而且有NAT这种东西存在，粒度不够细。那怎么办？用Cookie！
Cookie，这个？

噢不不，是这个。

Cookie往简单了说，就是媒体网站给用户起的名字，作为用户在该媒体网站上的唯一标识。有了Cookie之后，媒体网站就能很方便的从日志文件里区分出每个人的行为记录，然后就可以给每个用户打上合适的标签，做受众定向了。哇噻，这么简单呀！有数据，有Cookie，做完受众定向就能输出性别啦？没错，从原理上讲的确就这么简单，输入和输出都有了，这个日志模块算是走完了。但工业上要更复杂一些，因为我们一直没说这些日志文件都存哪儿了。心想这有什么好聊的呀，存个文件或者存个数据库不就完了？NONONO，门户网站每天访问量都是按亿算的，简单方法达不到要求。那工业上用的是什么呀，答曰Hadoop——分布式数据处理平台。（以下开源工具部分内容摘自刘鹏、王超老师著作《计算广告》，人民邮电出版社）
通常情况下，数据处理需要一个能够存储和加工海量数据的基础设施，实际上这也是大多数大数据系统都需要的平台。在开源的这类平台工具中，Hadoop几乎是工业界的标准选择。Hadoop的核心架构包括HDFS、Hadoop MapReduce和HBase，其中HDFS是GFS(Goole File System)的开源实现，MapReduce是Google MapReduce的开源实现，而HBase则是Google BigTable的开源实现。
HDFS是一种易于横向扩展的分布式文件系统，提供大规模数据文件存储服务，支持PB级数据规模。它可以运行在上万台的通用商业服务器集群上，提供副本容错机制，为海量用户提供性能优越的存取服务。计算广告系统里的海量日志文件等就是通过数据高速公路传送，最终存储在HDFS上，为各种离线计算任务提供服务。
Hadoop MapReduce是一种分布式计算框架，顾名思义，它由两个部分组成：Map和Reduce。Map是将一个作业分解成多个任务，而Reduce是将分解后多任务处理的结果汇总起来。在程序设计中，一项工作往往可以被拆分成多个任务，任务之间的关系可以分为两种：以是不相关的任务，可以并行执行；另一种是任务之间有相互依赖，先后顺序不能够颠倒，MapReduce适用于第一种类型，庞大的集群可以看作是硬件资源池，将任务并行拆分，然后交由每一个空闲硬件资源去处理，能够极大的提高计算效率，同时这种资源无关性对计算集群的横向扩展提供了最好的设计保证。
在广告系统中，Hadoop主要承担着离线数据的存储和计算需求，可以说是计算广告系统进行大规模数据处理不可或缺的基础平台。无论受众定向、点击率预估还是基础的报表生成，都需要在Hadoop上进行大规模的数据处理。
到这里，媒体网站数据的存储方式就很清楚了，它们分布式的存储在HDFS中。当我们需要做统计或者计算任务时，可以通过编写MapReduce程序来实现。搞定了日志的存储和Cookie分配，日志模块就算是告一段落了。有了稳定的数据，系统才会有稳定是输入。现在数据有了，怎么得到用户性别呐？请看下一节，受众定向模块。
6.2 受众定向模块

一句话解释受众定向模块：双兔傍地走，安能辨我是雄雌？

日志模块为媒体网站提供了大规模的存储和计算服务，为广告系统稳定的数据输入提供了强有力的保障。接下来的任务是根据日志数据来判断用户性别，在开始之前，我们先来看看古人是怎么判断兔子性别的。
《木兰诗》中写道“雄兔脚扑朔，雌兔眼迷离；双兔傍地走，安能辨我是雄雌？”小时候每次读到这里就觉得智商受到了侮辱，一个眯着眼，一个乱扑腾，俩走一块儿怎么就看不出来雌雄了？我看很容易嘛！提溜起耳朵，眼睛瞪的溜圆乱舞扎的是公的，眯缝着眼睛畏手畏脚的是母的。所以木兰你还真认为自己没有被认出来吗，我怎么觉得是大家不愿点破呢。至于不愿点破的原因，是个细思极恐的故事，一会儿电台就不让播了。
说完兔子现在来说人，上面我们用“腿+眼睛”的不同表现来判断兔子公母，这种方法叫做“规则”，放程序里就是个if..else..。现在我们要判断人的性别，场景虽然迁移，但解决问题的方法并没有改变，那都有哪些规则可以用来判断人的性别呢，先来看看下面两个用户的购买记录吧。

用户A和用户B的性别分别是什么？这个应该还是很明显的，因为他们分别买了多个有明显性别倾向的商品，例如裙子和女鞋，男袜和男鞋，所以A是女性B是男性。从这里我们可以得到一个非常简单并且符合直觉的假设：如果一个用户经常浏览或购买女性的商品，那么该用户可能是女性，反之是男性。假设有了，那我们假设的正确吗？迭代验证之后发现准确率高达90%（我编的），现在我们可以用它来区分用户性别了。这种规则的实质上是一种投票与统计的方法，看这个的行为记录是更像男性一些，还是更像女性一些，最后取其大者即可。一提到统计，大家都很熟悉，定义一个计数器即可。但是我们的场景是存储在HDFS中的海量数据，如何来实现这步操作呢，用MapReduce嘛，下面我随手写个代码，大神请轻喷！

# mapper.pyimport sys# 逐行读入data，输出cookie_id和商品性别属性 for line in sys.stdin: line = line.strip().split("\t")# line = ['cookie_id', 'item_sex'] cookie_id = line[0] item_sex = line[1] if item_set == 1: print "cookie_id : 1" else: print "cookie_id : -1"# 中间的shuffle过程略过...# reducer.py # 对data进行聚合，统计性别属性的正负性 # reduce阶段看到的data长这样 # cookie_id : 1 # cookie_id : 1 # cookie_id : 1 # cookie_id : -1 # .. # cookie_id : -1 # cookie_id : 1sex_value = https://www.it610.com/article/0 old_cookie_id ="null" for line in sys.stdin: cookie_id, tag = line.strip().split(" : ") if cookie_id == old_cookie_id: sex_value += int(tag)# 输出当前cookie_id统计结构，初始化sex_count和cookie_id else: # 第一行null时不输出 if old_cookie_id != "null": print old_cookie_id, sex_value old_cookie_id = cookie_id sex_value = https://www.it610.com/article/int(tag) print old_cookie_id,sex_value

在map中，如果该商品是男性，则返回{cookie_id : +1}，否则{cookie_id, -1}。在reduce中，对于每个cookie_id，定义一个变量sex_value来求所有该cookie_id的val总和，如果sex_value>0，说明该用户购买的男性商品更多，从而判断该用户是男性，女性同理，sex_value<0。程序输出如下图。

话说这么着来判断用户性别，是不是太随意了点。才不是呢！毕竟这个策略是符合业务场景的！好吧好吧我承认是我偷懒没有去研究更多更先进的算法和模型，砖我是扔出来了，坑我也挖下了，下面就看您各位的了，口喜口喜~
不经意间，我们已经完成了一个系统单元的设计了，它的输入是HDFS中的日志数据，输出是用户性别，中间的数据处理是受众定向,Step1搞定啦！

步骤	输入	输出	关键技术
~~Step1~~	~~媒体网站日志数据~~	~~用户性别~~	~~受众定向~~
Step2	用户性别	召回的广告	广告检索
Step3	召回的广告	排序的广告	CTR排序

基本的说完了，再延伸一些工业中常用内容吧，以下内容来自《计算广告》。我们得到的用户性别通常情况下是一个{key : value}键值对，key是用户的cookie_id，value是性别，1代表男0代表女。一般来说，这种键值对特征的数目非常庞大，无法放进广告投放机的内存中，需要采用独立的缓存服务。在这样的需求下，这种缓存服务的特征非常明显，一是往往只需要存储简单的键值对，二是大多数情况下需要支持高并发的随机读和不太频繁的批量写。在这样的需求下，Redis是比较合适的开源工具之一。
Redis是一种NoSQL数据库，它主要提供的是高性能的键值存储，采用的是内存数据集的方式。Redis的Key可以包括字符串、哈希、列表、集合和有序集合等数据类型，因此也被称作是一款数据结构服务器。Redis会周期性地把更新的数据写入磁盘或者把修改操作写入追加记录文件，并且在此基础上实现了主从同步，具有非常快速的非阻塞首次同步、网络断开自动重连等功能。同时Redis还具有其他一些特性，其中包括简单的check-and-set机制，pub/sub和配置设置等，使得它能够表现的更像高速缓存(cache)。Reids还提供了丰富的客户端，支持现阶段流行的大多数编程语言，使用起来比较方便。在使用了Redis存储用户性别之后，我们的广告系统现在长这样，思路应该还是挺清晰的，嗯嗯。

6.3 广告检索模块

一句话解释广告检索模块：找我啊，找到我就让你嘿嘿嘿

迈出了第一步，渐入佳境，趁热打铁我们来看第三个模块：广告检索。在这个模块中，输入是用户性别，输出是候选广告集合，这些广告该怎么找呢？
有人说了，这简单呀。现在要为一位女性喜欢买鞋的用户找一些合适的广告，直接在广告数据库里写一句SELECT * FROM TABLE_NAME WHERE USER_TAG = "shoes" AND USER_SEX = "female" 不就搞定了吗？没错，这是一种方法，我在mieSys最小广告系统(Github)里也是这么做的，但是可以十分肯定的说，这么做是不太合适滴。

朝阳群众：啥？
西城大妈：387，到北京西站387。
海淀网友：宝宝心里苦，但宝宝不说。
吃瓜群众：自己用不让我们用，要不要脸？

好了好了大家消消气，我承认是我将问题简（偷）化（懒）了。诚然，用数据库的确可以实现广告的检索，但是在大规模的场景下，这种方法几乎不可用，感兴趣的同学可以在一个1000W行的表里写一个SELECT试试，耗时十分感人。阿里有10亿商品，这要是检索一次，嗯。。

朝阳群众：嗯？
西城大妈：刚上车的乘客请往里走。
海淀网友：宝强真是可怜啊，不过以后当个经纪人好像也不错。
吃瓜群众：然后嘞，那还能咋查？

除了数据库，还有更通用的检索方法，常见于搜索引擎中，这就是倒排索引。所谓倒排索引，就是根据结果查原因。举个不恰当的例子，我们都知道1+1=2，从1+1得到2是正排索引，那么从2得到1+1就是倒排索引。如果这个解释还是很抽象的话，那就用程序员的方式吧。

# ----------------------# # author:Bread# # date:2016.08.18 00:33 # # Python2.7# # ----------------------## coding:utf-8docid_tokens = { "D0" : "谷歌地图之父跳槽 FaceBook", "D1" : "谷歌地图之父加盟 FaceBook", "D2" : "谷歌地图创始人拉斯离开谷歌加盟 FaceBook", "D3" : "谷歌地图创始人跳槽 FaceBook 与 Wave 项目取消有关", "D4" : "谷歌地图创始人拉斯加盟社交网站 FaceBook" }# IN:docid_tokens:{doc_id : [token_id1, token_id2, .. ]} # OUT:tokens_docid:{token_id : [doc_id1, doc_id2, ..]} def create_invindex_dict(docid_tokens): tokens_docid = {}# 对于每篇文档 for doc in docid_tokens:# 得到文档中的每一个分词 list_tokens = docid_tokens[doc].strip().split(" ")# 对于每个词，建立/添加token:doc_id的索引 for token in list_tokens: if tokens_docid.get(token, "not_exist") == "not_exist": tokens_docid[token] = [doc]# 如果该doc已经在该token的字典中，跳过；否则添加 else: if doc in tokens_docid[token]: pass else: tokens_docid[token].append(doc) return tokens_docid# IN:tokens_docid:{token_id : [doc_id1, doc_id2, ..]} # IN:token # OUT:invindex result:[doc_id1, doc_id2, ..] def get_invindex_res(tokens_docid, token): # 打印整个倒排dict if token == "ALL": for token in tokens_docid: print token, ":", tokens_docid[token]# 返回倒排结果 else: return tokens_docid[token]def main(): print "-----------------doc_tokens(正排)-----------------" for doc in docid_tokens: print doc, ":",docid_tokens[doc] tokens_docid = create_invindex_dict(docid_tokens) print "-----------------token_docs(倒排)-----------------" token = "ALL" get_invindex_res(tokens_docid, token)token1 = "谷歌" token2 = "Wave" rst1 = get_invindex_res(tokens_docid, token1) rst2 = get_invindex_res(tokens_docid, token2) print "------------------token查询-----------------------" print "token:", token1, rst1 print "token:", token2, rst2 print "根据两token检索到的文档:", set(rst1) & set(rst2)if __name__ == "__main__": main()

这段代码中，doc_tokens是一个字典，key是文档id，value是该文档中出现的句子，分词之后以单词(token)的形式存在。tokens_docid也是一个字典，key是token，value是出现过该token的文档id。当我们想要在搜索引擎中检索同时包含“谷歌”和“Wave”的网页是哪一个，对两个token的结果求一下交集即可，即D3。

朝阳群众：噢？
西城大妈：年轻人来少坐会儿，给老人小孩让个座儿。
海淀网友：宝宝去上诉了，看他面容好憔悴啊。
吃瓜群众：还是没看懂倒排跟广告检索有啥关系？

受众定向模块所完成的，就是给用户打上各种标签；而广告检索模块将要完成的，就是根据这些标签为用户召回相关的广告。这里面其实有三方关系：用户标签、广告标签和广告。通常，用户标签和广告标签是存在着映射关系的，所以我们可以通过用户标签，来找到相应的广告标签。如果将广告看作是doc，将广告标签看作token，那么通过广告标签找广告的过程就是倒排索引。
鉴于上述描述，广告检索通常也用倒排索引来实现，其中查询的条件可以看作一个由“与或”关系连接的布尔表达式，例如我们刚才提到的一位用户标签为“喜欢买鞋的女性”，其对应的广告标签就是“类别：鞋” 和 “性别：女”的交集。根据标签“类别：鞋”我们可以检索到广告集合S1，根据标签“性别：女”可以检索到广告集合S2，二者取交集之后的结果，记为我们检索到的广告。

朝阳群众：哈？
西城大妈：前方到站是阜成门南，下车乘客请提前换到车门处，下车请刷卡。
海淀网友：宝强在美国那个别墅一般般啊，那个会说英语的“哥哥”会不会是经纪人呀。
吃瓜群众：有点意思了，那这些检索到的广告都有用吗？

非常好的问题，检索到的广告都有用吗？假设我们只有用户的性别标签，阿里有10亿商品，男女各一半，那我这一下就得到了5亿条商品的广告。下面用这5亿条去做CTR排序，我想那一定是疯了，肯定不是这样的。通常情况下，我们会将这些检索得到的广告通过模型的方法做一下截断和粗选，将头部相关性较高的保留下来作为广告检索的最终结果。其实在实际的工业场景中，类似具体的问题还有很多，例如用倒排索引的方法做广告检索其实还会遇到一些具体问题，这里暂不细表，感兴趣的同学可以看一看《计算广告》P223。

步骤	输入	输出	关键技术
~~Step1~~	~~媒体网站日志数据~~	~~用户性别~~	~~受众定向~~
~~Step2~~	~~用户性别~~	~~召回的广告~~	~~广告检索~~
Step3	召回的广告	排序的广告	CTR排序

广告检索的完成，意味着我们的Step2完成了。万事俱备，只欠Ranking，想想还有点小激动呢！现在我们的广告系统，就长这样啦。

朝阳群众：嗯，没人吸毒。
西城大妈：终点站北京西站到了，祝您旅途愉快。
海淀网友：儿子还真不像宝强-_-。
吃瓜群众：原来是这样，我听懂了。那现在既然找到了广告，说好的嘿嘿嘿呢？

面包君满脸黑线，撒腿就跑，边跑边说“追我呀，追到我我就让你嘿嘿嘿。略~~~”

6.4 CTR预估模块

一句话解释CTR预估模块：排排坐，吃果果。

终于来到了最后一个模块，该模块的输入是候选的广告集合，输出是一个根据用户pCTR从高到低排序的一个广告序列。
在计算广告[中]里我们曾经介绍过CTR预估相关内容，下面我们简单回顾一下。
点击率与点击率预估的对比，就是0.1%与那80%。之所以点击率预估十分重要，是因为它直接关系到媒体网站的收入，也直接关系到广告主的推广效果。广告位的个数就那么几个，显眼的更少，凭什么把你放在头条呢？靠的就是点击率预估。
点击率预估是机器学习中十分经典并且难度极高的问题。既然聊到了机器学习，那一定得聊一聊特征选择及构造，模型的选择和调参，这其中任何一个单拎出来都是工业界中十分热门的话题。在这里，我就来个抛砖引玉，看看常用的思路都有哪些。
6.4.1 点击率预估综述用于点击率预估的数据主要是日志数据，一般会有点击行为(点击为1，没点为0)、广告信息(广告位、广告主id、广告标签和广告描述等)、用户信息(用户id和用户标签等)、上下文信息和时间戳等。有了这些原始数据之后，需要对数据进行清洗，然后利用统计或模型的方法构造特征，进而做特征选择和特征组合，最终特征的数量级大约在10亿-100亿维。完成了特征工作之后，在模型方面，较为经典的点击率预估模型是线性模型Logistic Regression，由于LR在通过sigmoid之前是一个[0,1]之间的浮点数，利用LR的特点，我们可以将这个浮点数作为用户点击该广告的概率，把广告按照这个概率从高到低放置在相应广告位上，就完成了广告排序。
6.4.2 特征工程 1.特征分类

从数值上看，特征主要分为连续型特征和离散型特征。连续型特征是指特征值是一个可连续变化的实数，例如某个广告的点击次数{ad1:87, ad2:13, ad3:2}；离散型特征是指特征值非0即1，例如{性别：0}表示该用户是女性，{性别:1}表示该用户是男性。
从来源上看，可以分为统计特征和概率特征。统计特征就好比上面提到的广告点击次数，是经过简单统计得到的绝对值累加。概率特征例如某个广告的点击率(点击量/展示量){ad1:0.01, ad2:0.13, ad3:0.07}。

2.特征表示

离散化。离散化要完成的任务主要是对连续型特征做分类，拿用户年龄举例。年龄是一个在0~100间的实数。在一般的业务场景中，我们不会去care用户到底是21岁还是22岁，但是会care用户是11岁还是21岁。鉴于此，我们可以将年龄按10岁为间隔做一下分类：1~10岁用1表示，11~20用2表示，以此类推。间隔的选取要依赖具体业务场景，在人口统计中间隔10岁可能比较好，但在电商中，可能1~18代表1，18~24代表2效果会更好一些。
归一化。归一化要完成的任务是使不同连续特征间建立起可比关系，拿成绩和GPA来举例。成绩一般是百分制，比如{score：87}，GPA一般是4分制，比如{GPA：4.0}。如果单看数值，那87肯定要比4大，但是实际上4.0在GPA中代表的是优秀：90~100分，比87要大。所谓归一化，就是当前特征值在该特征范畴下的相对大小，score:87就是87/100=87%，GPA:4.0就是4.0/4.0=100%，这下两个特征间就产生了可比性。归一化的方法也有多种，这里就不多说了。
Dummies。有人叫它“哑变量”，我总感觉怪怪的，就叫原名吧。Dummies是实现One-Hot的一种方式，例如特征性别{1：男， 2：女， 3：不详}。在这里，1，2，3仅仅用于指代作用，并没有数值上的大小关系，但是对于模型来说，1、2、3这样的值会影响模型的迭代，因为在梯度下降中

θj:=θj?α(y(i)?hθ(x(i)))x(i)j 这里 x(i)j 就是第 j 个特征的数值，可见用于指代作用的数值并不适合直接带入模型参与计算。正是因为此，我们需要把用于指代作用的数值或字符串变成One-Hot形式，依然拿性别为例：
1：男—-> [1, 0, 0]
2：女—-> [0, 1, 0]
3：不详—>[0, 0, 1]
通过Dummies，我们将一维特征扩展到了三维，既保留了特征的物理含义，也使得模型训练更加可信，是不是好了很多呢~

3.特征组合
特征组合是一个充满了智慧和经验的领域，花样繁多，令人赞叹。这里说一种常规的方法：笛卡尔积。
在数学中，两个集合X和Y的笛卡儿积（Cartesian product），又称直积，在集合论中表示为X × Y，是所有可能的有序对组成的集合，其中有序对的第一个对象是X的成员，第二个对象是Y的成员。

其实之前我们已经了解特征组合了，在哪里呢？嘿嘿，还记得那位“喜欢买鞋的女性”用户吗，让我们看看在特征层面如何表示这种信息。假设我们有一个特征，叫做商品类别{1：上衣， 2：裙裤， 3：鞋， 4：其他}, 还有一个特征是用户性别{1：男， 2：女， 3：不详}。通过笛卡尔积，我们可以得到新特征“喜欢买鞋的女性”{(商品类别：鞋)， (性别：女)}，至于特征值嘛，一般常见的操作就是加减乘除对数之类的。
4.特征选择
同特征组合一样，特征选择更是一个将“人工的智能”体现的淋漓尽致的领域。特征选择的根本任务，是找出那些影响力大，冗余性小的特征集合。最理想的情况当然是获得描述问题的不同“角度”，一个不多一个不少。
理想是求最优解，但是显然这是一个NP Hard的问题，即便如此，也难不倒我们的各路数据英雄。他们个个身怀绝技，充分发挥主观能动性，在实战中练就了一身特征选择的好本领。
从方法论上来说，特征选择有三种方法：Filter、 Wrapper和Embedded。Filter通常用来做预处理，通过特征与label之间相关性（主要是统计信息，例如互信息、显著性检验等）的评估，先过滤掉一部分；Wrapper是指将特征子集带入模型，通过模型效果来进行特征重要性的评估；Embedded是指特征选择和模型训练同时进行，直接决定是选择特征还是拒绝特征，比较经典的是决策树和神经网络。就实战方面而言，我常用的有下面几种方法，还请各路英豪多多指教：

利用统计方法，评估特征重要性
利用L1正则将不重要的模型，删除权重为0的特征
特征带入模型，根据权重算特征的相对重要性
暴力循环，如果加上该特征效果更好就保留，否则不加

不知不觉说了这么多，还是没说广告点击率预估的特征工程到底该怎么做呀。其实任何机器学习问题都是有场景的，即便都是CTR预估，所面临的数据规模，业务需求都不一样，所对应的特征工程也各有千秋，但总归起来方法大致就是这些。至于我是怎么做的，其实没用太复杂的东西，能满足我的需求即可。在下一章介绍最小广告系统mieSys(Github)时会大致说一下，这里就略过啦。
6.4.3 模型选择就模型方面来说，DNN几乎横扫了数据领域各个会议，无论哪个领域都要把CNN, RNN和LSTM套进来试一试效果。即便如此，LR在CTR预估中的霸主地位还是很难撼动的，这玩意儿实在太好用了，经过优化那是又快又准。DNN在语音、图像和自然语言处理领域的成效是有目共睹的，但是面对广告这样的高维向量也是犯起了老大难，直到最近注意到有用FM做embedding做降维的做法，倒是可以较好的解决这个问题。至于Online Learning方面，FTRL还是很好用的，国内好几家都在用。
上面这一段说下来，忽然觉得自己好像懂很多的样子。。好了，不装了，我去啃论文推公式了！关于模型选择就说这么多，我是忠实的LR粉，没啥说的，表衷心！至于Deep Learning，这种没有理论依据就靠矩阵运算颠过来倒过去不是Embedding就是梯度弥散再者就是Relu或者Dropout的东西，对此我只想说：请带上我！
不知不觉，特征和模型都说完了，这就意味着CTR预估模块讲完了？CTR预估讲完了，候选广告有了序，TopN的一展示，我们的任务就完成了？来对照一下问题定义。我们要完成的是：从数据中挖掘出用户的性别，根据性别为用户展示TA们最可能点击的广告。我们将问题分解成多个基本的“输入-系统-输出”模块之后，先后完成了单元模块的设计，最终打通了整个系统的流程，经过多个模块的处理和流水线式的输入输出，我们确实得到了我们想要的结果。

步骤	输入	输出	关键技术
~~Step1~~	~~媒体网站日志数据~~	~~用户性别~~	~~受众定向~~
~~Step2~~	~~用户性别~~	~~召回的广告~~	~~广告检索~~
~~Step3~~	~~召回的广告~~	~~排序的广告~~	~~CTR排序~~

没错！你看那主页上那广告不是达芙妮的女鞋吗！
我们的系统建成了，就是这么简单！兴奋着兴奋着，突然就清醒过来，看了看四周，原来我还在那个会议室里，已经过去了将近两个小时。对面坐着leader，正慈眉善目的看着我，悠悠的说了句：
“不错，挺好的。但是，是不是少了点什么？”
我一愣，少了点什么？不少呀！这不都挺好的，广告也展示出来了，功能也实现了，还少啥？但是又仔细一想，难道leader是想问那些？噢噢那还真是少了。我不好意思的向leader吐了个舌头，“嗯，确实还少了些东西”。
6.5 Server模块
怎么把这个给漏了呢，说好的场景是媒体网站，没有Server就意味着没有页面，给用户看个啥？嗯嗯这个不能少。
6.6 计费模块
这个是最不该漏掉的，既然是广告系统，那怎么能不提钱呢？刚才的广告确实是展示了，但是广告商的账户里还有余额吗？额…好像，没了。。
6.7 反作弊模块
这个模块大家可能都不太熟悉，其实我也不太熟，但它却至关重要。我们所有的决策和算法，都是建立在数据的基础上，那么有一个非常严肃的问题：如果数据是错误的，甚至是假的呢，这些策略还有效吗？想到这里，我是觉得背后一凉，很难想象那种金玉其外败絮其中的场景，嗯补上补上。
leader点点头，说“基本都补上了，那么，还有吗？”。
面试到这种程度，看来必须要放大招了。“有，看图！”

这张图是刘鹏老师在网易公开课中讲课时用到的，是工业级别的在线广告系统的框架图。从里面找找我们刚刚讨论过的吧。
数据模块找到了吗？最下面绿色的，Data Highway以及Session log generation。受众定向呢？就是Audience Targeting。然后到了中间，Ad retrieval就是广告检索，看到和它连着的Ad index了吗，倒排呀！随后就是CTR模块，是CTR Model以及Ad Ranking。这就是最基本的四个模块，那后来加的三个呢？Server就是Web,在左上角和中间上部；计费和反作弊都在右下角。嗯，看来咱们弄的还挺全乎的。
那其他那些模块是什么呢？我也只是知道个大概，这里就不献丑，有了解的同学还请多多指教。
场景5

时间：17：00 地点：中关村某大厦十几层的一个小会议室内人物：leader，我事件：二面状态：认真，专注

leader沉思许久，最后冲着我重重的点了点头，说了句河南话：“中！”
我赶紧回了句，“谢谢”。
leader神秘一笑，“那下面我们来做道算法题吧…”
我心说什么？广告系统都有了，还要做题！要啥自行车？上表情包！

leader：哈哈开个玩笑，恭喜你，面试过了。
我：谢谢您！Mua~~~~

场景6

时间：17：30 地点：路边人物：来往行人，我事件：找吃的状态：饿

大众点评搜索“小，吊，梨，汤”。噢！在这儿呢，不远不远，看了下评价还不错。刚迈开步子准备过去，路边站着一位小姑娘，怀里捧着一沓宣传单，给过路行人发放着。我走过去，她注意到我，熟练的抽出一张，笑着说道：
“您好，请了解一下”。
7.展示广告最小系统mieSys 这一章就随便聊聊mieSys的来历吧，不讲技术了。
mieSys的地址是http://115.159.33.50/，这两个月来多次被抓肉鸡，可能是Redis的问题，最近稳定了。前不久我将系统开源了，代码写的不好，好多地方都可以优化，先放个v1.0吧Github地址：https://github.com/breadada/mieSys
为什么想做这个最小系统呢，仅仅是因为觉得好玩。之前在海淘的时候，就被Amazon的推荐效果给惊到了，我刚点了一双鞋进去，再次退到首页的时候，大多数广告位都与我刚点的那双鞋有关，或者是同一品牌，或者是同一款式。当时我就心想，我也要做一个。后来刘鹏和王超老师出了《计算广告》，读到后面有介绍开源广告框架，我心想这好啊，比葫芦画瓢的整一个呗？还正在犹豫中，就被介绍Nginx的一句话打动了：

在广告系统中，用Nginx作为前端Web服务器，而将广告投放机的功能用C/C++语言实现成fastCGI插件，是一个开发成本较低、性能又很不错的方案。实际上，这一方案已经实现了一个基本的广告投放机，从事最简单的广告投放业务，而其他模块和功能则可以根据需求逐步开发。

看到这里，那就干吧，可是两眼一抹黑，先想想我会啥吧。当时的我看过一堆计算广告方面论文，了解机器学习基本知识，代码能力一般，噢还写过小爬虫。就这么着学着试着，查着用着，大约用了3周时间，系统就搭好了。当推荐的广告第一次正确展示的时候，那种喜悦，：）
至于搭建的过程，记不是很清楚了，挑重点说吧。
首先，我搭建的模块是Nginx，先把页面做了出来。后台我用的是Flask来处理HTTP请求，静态页面框架写好，用template往里面动态添加页面元素。架构方面是Nginx+uWSGI+Flask，有了uWSGI之后页面响应快了不少。
然后就是广告数据了。我先设计了一套简单的标签体系，有三类商品：一类是适合男性用户的电子商品digital，一类是适合女性用户的护肤品skins，最后是二者都适合的鞋shoes。对每种商品，我都选了高、中、低三档，主要体现在价格为品牌上。从标签体系出发，在淘宝上找了一些广告图片，截图后存在了本地，同时在数据库中填上每个广告的属性值，这算是完成了广告库的建设。
第三就开始设计页面逻辑，仿照着Amazon的做法，分为新用户和老用户两种情况。新用户来时展示的是所有品类的广告，如果用户有点击行为，那随后推荐的结果就是与点击相关的。从这个角度出发，先后设计了Cookie分发，访问日志等，这都是属于数据模块的事情。
第四，这时页面已经可以访问并且点击了，处理完些数据库方面的增删改查之后就开始设计受众定向的方法。我所用的方法很简单，就是投票。因为商品本身有性别标签和商品标签，用商品给用户打标签就可以了。从这里也可以看出，一套完整的标签系统是十分必要的。
第五，广告检索，我还真是写了一个SELECT查询，只因为我的广告库一共才36条广告不要考虑效率，这个是最没啥可说的，没用倒排。
第六，CTR预估。这里首先不得不提一个细节，那就是训练数据的问题。正例好说，就是有点击的广告，那负例呢？我采取的策略是引入了Session，5分钟内的点击行为记为正，出现但未点击的记为负，5分钟一过，就是另外的一组正负样例，互相独立。就这个小逻辑还设计了很久，就不提数据库UPDATE的时候把之前所有结果都给置1了，囧。特征工程做的并不复杂，用dummies全打成One-hot也就50多维，主要有品牌、价格、性别、广告id等。特征组合和选择都没做，直接扔LR后出了一个概率。至于效果，我觉得还成，就是简单粗暴了些。
第七，广告位设计。广告位分两行，第一行五个和第二行五个。我的策略是推荐结果只呈现在第一行五个广告位上，第二行的五个位置随机出，这样可以避免推荐结果中全部都是之前看过的商品，掉进死循环。
至于其他的，记不太清楚了，都在代码里，我先干为敬。
有同学问，那后来就没再继续做这个系统了吗？当然做了，我和实验室的师弟又重构了一套，使用开源框架搭的。Server是Nginx, 离线部分有HDFS, Flume和Spark，在线部分有Redis和Kafka。这些内容在这里就不再写了，有机会的话由他来写写，我已经老了。
尾声到此，《计算广告小窥[下]》就算是写完了，隔了大半年，挺抱歉的。自从过完年开学到现在，一直没有消停过。经历了找实习，面试，实习之后，属于自己的时间确实少了。接下来校招马上就全面开始了，又是一轮新的挑战，估计时间会更加紧张。一咬牙，赶在校招之前完成了《计算广告小窥》，了却了一桩心事，生怕放凉了某颗求知的心。还好还好，总算是写完了。
发自内心的感谢一下。
在这里要感谢许多的人，首先要感谢刘鹏老师的倾心之作，为我们学生群体乃至广大从业者指明了方向，而且还要感谢刘鹏老师提供的平台，在计算广告微信公众号中对博文进行了转发，覆盖面极广，多次包括我的面试官。
然后要感谢寒小阳和龙心尘两位师兄，如果没有你们，我也不会想着着手写这篇博客。感谢你们帮我转发，你们是极其优质的自媒体，下面可以考虑接广告了！
还要感谢在交流或者面试中，就广告方面对我提出过指导性意见或建议的各位前辈，特别感谢百度德川、阿里怀人、阿里口肃、腾讯Fandy王和优酷吕红亮，是你们让我受益良多。
最后要感谢的是各位读者，感谢你们的关注和每一条评论，希望这三篇能带你们走进计算广告的大门，多拉一个是一个，我也算是做了一件有社会增量的事情了哈哈哈。
当然了，绝对不能忘了在我身后默默奉献的石医生，你辛苦了~~
至于以后博客还会再写点什么，主题还没有定，但是出发点是肯定的，那就是帮助初学者入门的文章，例如机器学习常见算法的推导，算法间的相互关系以及应用等。其实我会的也不多，借着这个机会也督促一下自己，毕竟只有自己有了心得，才能够说的出来。除此以外，还会有一些志愿者项目，例如我和寒小阳、龙心晨以及《大数据文摘》中其他大牛一同参与的斯坦福CS224D：《自然语言处理与深度学习》课程的导读和翻译工作，也会有文章陆续发过来，敬请关注。
到这里吧，就到这里了。
祝好！
面包包包包包包
2016.8.20 北京