本来打算写文章介绍一下业界内广告搜索引擎的业务及架构的，但是觉得应该先介绍一下整个搜索广告的大背景的，所以周末学习了一下斯坦福大学的Introduction to Computational Advertising课程，下文主要内容都是翻译自此课程的幻灯片，由于我目前只对搜索广告有所了解，所以只翻译了搜索广告相关的一部分内容，原文中的很多内容没有涉及到，例如展示广告，定向广告，推荐系统等。
什么是计算广告(Computational Advertising)：
计算广告是计算机科学中出现的一个相对较新的子科学领域，利用算法来给用户展示[通常是在浏览器中]出最佳的广告。它集合了下面的技术于一身：
信息检索 (Information retrieval)
大规模搜索与文本分析(Large scale search and text analysis)
统计建模(Statistical modeling)
机器学习 (Machine learning)
微观经济学 (Microeconomics)
博弈论、拍卖理论与机制设计 (Game theory, auction theory, mechanism design)
分类(Classification)
优化(Optimization)
推荐系统 (Recommender systems)
计算广告的核心挑战：
在一个给定场景下的给定用户和合适的广告之间找到一个最佳的匹配(Find the "best match" between a given user in a given context and a suitable advertisement.)
如果把广告看作一种信息，那么找到一个“最佳广告”就是一个信息检索问题，这个问题附带有多个可能互相矛盾的效用函数。
为什么需要“计算”广告?
1)把传统广告学和计算机的计算能力相结合
2)从算法的角度来思考旧的挑战
传统广告与计算广告的特点对比：
传统广告：
相对而言平台较小--杂志、广告牌、报纸、传单、电视等
每个平台花费巨资(几百万的电视广告费用)
不可能个性化
只能由聪明的广告人来决定在哪里投放
很难度量投资回报率(ROI)
计算广告：
亿级别的投放机会
亿级别的创意形式
完全个性化
每次投放而言花费很小
更容易度量
约翰*沃纳梅克，著名的百货商店之父曾经说过：
我在广告上的投资有一半是无用的，但是问题是我不知道是哪一半。
计算广告的分类：
根据广告主的计费方式，可以分为
千次展现付费 CPM(cost per thousand impressions) 主要用于品牌曝光,例如淘宝的钻展业务
每次点击扣费 CPC(cost per click) 通常用于文本广告,例如百度凤巢，Google Adwords
成交/行为付费 CPT/CPA(cost per transaction/action) 例如淘宝客业务
根据展现形式分为:图片广告[Graphical Ads]、文本广告[Textual Ads]、视频等。
根据不同的产品形式分为
搜索广告(Sponsored Search)，例如百度凤巢，Google Adwords
上下文广告[Contexual Ads]，例如Google Adsense
展示广告[Display ads]，例如淘宝钻展业务线
定向广告[Targeting Ads]，例如Google Adsense
在互联网中，搜索广告是最主要的文本广告的形式。
互联网广告的意义：
广告支撑起了互联网上一个巨大的生态系统：
1.内容提供商通过广告赚钱，养活了 宏观/微观的内容提供商 [就是各种大小网站]
2.精准触达/定向使得长尾生意成为可能
3.广告主的收入使得大批“免费”的服务成为可能：Facebook, Google, Twitter,Yahoo
如果没有广告，互联网就不可能像现在这么发展迅速、规模宏大。广告给消费者提供了直接和间接的巨大价值。
计算广告的参与方：
1.流量提供方(Publishers)
2.广告主(Advertisers)
3.浏览者/用户(Users)
4.广告平台/广告网络(Match maker/Ad network)
这些参与者有各自不同的诉求：流量提供者渴望每次展现/搜索的高收益，广告主渴望高投资回报率(ROI)和流量，用户希望高相关性，广告网络渴望收益与市场份额。而广告的选择，就是要兼顾四个参与者的收益，达到最优状态,需要权衡长期和短期的商业目标。
计算广告对性能的要求很高：
亿级别：
搜索广告中有数亿级别的广告
每个小时有亿级别的搜索
万亿级别页面展现次数
亿级的用户
毫秒级别：
请求是在用户“等待”过程中完成的，必须在100ms内返回钱：
每个请求都需要消耗CPU资源
数据通常放在内存中 [需要大量内存，而内存比硬盘贵]
每次请求的耗费必须比收益要低
过低的点击率(ctr)使得上面的挑战更加困难
搜索广告：
什么是搜索广告(sponsored search)：
搜索广告是由搜索关键词驱动的广告。广告主选择一个“竞价词”，当用户触发某个搜索请求时，广告主的广告得以展现。
业界的系统：Google AdWords, 百度凤巢，淘宝搜索直通车
在上文中我们提到的计算广告中有4个参与方，在搜索广告中，流量提供方是搜索结果页 SERP(search results page)，通常流量提供方和广告平台是同一个(Google，Bing)，当然也可以不一样(微软给雅虎提供广告搜索)。
在搜索广告中三个参与者之间有如下的交互行为：
广告主：
1.提交广告，购买相关的竞价词
2.为了获得好的展示位置而竞价
3.为获得的点击付费
浏览者：给搜索引擎提交查询串，表达一定的意图
搜索引擎：
1.根据用户的查询串在web页面语料库和广告语料库中分别进行检索
2.把自然搜索结果和广告搜索结果结合到一起，展示在搜索结果页 SERP上
搜索广告中存在的三个子问题
从搜索引擎的角度来看，搜索广告中存在三个子问题：
1.广告检索
2.给拿到的广告排序
3.根据点击收费
以上三个顺序是搜索广告事件发生的顺序,这里面1和2属于信息检索问题，而2和3又属于微观经济学问题。
文章一开头提到了计算广告中涉及到了博弈论，拍卖理论，机制设计，到底在哪里用到了呢?想了解这些疑问就得接着往下看。
对于目前的搜索广告来说，都被设计成了拍卖的机制。搜索引擎拍卖的是每个流量中可能的广告位，广告主提交对购买的关键词的每次点击的最高出价，广告主是不知道其他人的出价信息的。虽然每个流量中一般会有多个广告位置，但是广告主只出一个价格。最终搜索引擎根据广告主竞价和广告的点击率CTR来对广告进行排序，决定最终的展示位置。‖
点击扣费时，目前普遍采用的是Google发明的广义第二价格扣费GSP(General Second Price)，有两种策略：
竞价排序：根据广告的出价倒序排列，位于第i个的广告支付第i+1个广告的竞价
根据广告平台的收益排序：根据期望最大收益ecpm来排序
ecpm=bidprice*ctr
被点击的广告主i付的费用为
price=bidprice(i+1)*(ctr(i+1)/ctr(i))
由于bidprice(i)*ctr(i)>bidprice(i+1)*ctr(i+1),可以从上述公式看到广告主实际扣费肯定小于最高出价
在广告搜索引擎中，不能直接拿着用户的查询串在倒排索引中进行广告检索的，因为这样可能导致搜出来的广告深度不够，而且查询多种多样，在搜索引擎有限的资源下，不可能对所有查询建立倒排索引，所以需要经过查询改写来改写出归一化后的多个搜索词，用这些搜索词去检索广告。
查询改写(Query Rewrite)
把用户查询(Query)改写成竞价词(Bidword)的过程。总的来说有离线(offline)改写和在线改写(online)两类。
离线改写：
在离线的时候利用相对在线而言更多的数据来处理用户的查询，生成一个query->bidword的映射关系表，缺点是只能给那些高频词进行离线处理。这里有两个问题：我们应该改写哪些查询--我们需要市场深度的查询上。我们应该改写成什么样的查询--那些市场深度足够的查询上。
在线改写：
对于离线不能处理的少数请求需要我们进行在线改写，在线改写相对离线而言，资源受限(内存限制，时间限制)，需要在很短的时间(数ms)内做分析。
广告选择(Ad Selection)
给定一个查询，搜索引擎可以展示两类广告：
精确匹配EM(Exact match): 广告主对特定的查询竞价
高级匹配AM(Advanced match)或广泛匹配(Broad match): 广告主并不对特定的词进行竞价，但是这个查询被认为是广告主感兴趣的。
搜索广告中的流量具有长尾效应，非常多的长尾流量查询在搜索广告中没有对应的广告，高级匹配主要是为了解决这相当一部分流量没有被竞价的问题，广告主不关心竞价词，他们只关心转化--卖掉商品。如何覆盖到相关的流量呢，从引擎的角度出发，高级匹配比精确匹配更有挑战性。
两阶段广告选择
在广告搜索引擎中，广告语料库中的广告数量巨大，高达百万之多，而实际展示的过程中，只有极少数量的广告能够展示出来，目前业界普遍采用两阶段广告选择来解决性能问题。
广告检索过程中，整个广告的选择分为两部分：
广告检索(Ad Retrieval):从整个广告语料库里面选出一个最可能的候选集合。此过程是粗选阶段，我们用来排序的目标函数(例如评估相关性)可能和最终排序的函数(例如ecpm)不同。
广告重排序(Ad Reordering)：利用更多的数据来对第一阶段返回的有限的候选广告集合进行更为精细，更为复杂的计算。这个阶段必须综合考虑竞价和相关性分数(例如ecpm)。
对于广告重排序阶段，目前有两种主流的方法，以赛马为例：
反应式(Reactive)：选定一匹马，根据它的历史成绩来预测未来的表现
预估式(Predictive)：根据体重，腿长等特征为赛马建模，找到这些特征在预测比赛名次终的重要程度，然后基于这些特征来给见过、未见过的赛马预测成绩。
当我们拥有对某赛马的足够信息的时候，就使用这些信息(反应性)，否则使用模型(预测性)。