搜索引擎竞价排名广告，又称付费搜索，赞助搜索（Sponsored Search），是跟展示广告并列的巨大广告市场之一，从早期的Google Adwords，Yahoo Sponsored Search，Microsoft Bing Ads，到后来国内的百度凤巢，阿里巴巴直通车，等等，凡是拥有流量入口的搜索引擎，都拥有自己的变现手段——竞价排名广告。相比展示广告，Sponsored Search直接根据用户查询产生定向流量，由于用户查询代表了最强的用户意图，因此Sponsored Search拥有更强的变现能力，也是最早和最成熟的定向广告平台；除此之外，搜索广告从一开始就具有原生广告的特点，因为它的商业化结果与自然结果一样由用户的主动意图触发，并且展示形式上与自然结果相差不大。因此在百度凤巢之前，以原生广告形式混排是百度的主要变现方式，甚至到现在，搜索原生广告也一样在百度搜索结果中存在。
Sponsored Search广告市场设计中有两个问题需要解决：
1. 如何在广告位上分配适合的广告；
2. 广告的定价。
关于第一点，所有的竞价搜索都是采用类似的解决手段，既根据排序来决定广告位的展现，排序取决于两个因素：广告的质量，以及广告主的出价。Google Adwords此前曾经公开他们的排序是按照出价跟广告质量的乘积做为排序因子。Microsoft Bing Ads的排序取决于广告点击率，相关度，以及广告主出价，但如何计算并没有公开。跟展示广告Adx类似，Sponsored Search也大部分采用广义第二出价来进行关键词竞价，既关键词由出价最高的广告主赢得，出价则为排名第二的广告主。
Sponsored Search的账户体系有三级组成：账户，推广计划Campaign，以及推广单元Ad Groups。一个Campaign有自己的预算和定向条件（地理，时间，等等），每个Campaign由一个或者多个Ad Group组成，一个Ad Group包含一组广告创意，以及一个关键词列表，这些关键词可以触发这些广告的展现。在Google Adwords里，Ad Groups又称为Line Item。下图展示了一个通用的Sponsored Search账户结构，以及展现的广告创意。
本文首先谈谈广告检索。通常情况下，Sponsored Search支持4种匹配类型：
1. 精确匹配：这种情况下，仅当用户输入的关键词跟竞价关键词完全一样时，广告才可能被展现；
2. 短语匹配：这种匹配要求用户输入关键词的顺序跟竞价关键词一样，但允许包含非竞价关键词。例如查询“HTC手机报价”，可能命中的关键词有“HTC”、“手机报价”、“HTC智能手机”、“HTC价格”等等；
3. 宽泛匹配broad match：这种匹配要求用户查询包含广告主竞价的所有关键词，也就是说前者是后者的超集；
4. 否定匹配：这种匹配要求广告主竞价的关键词不能出现在用户查询中。
宽泛匹配是上述四种匹配类型中最常见的情形，因为它最灵活，可以让广告主有可能吸引更多的流量。精确匹配很不灵活，然而如果广告主设置大量的关键词，采用精确匹配可以吸引到更加精准的定向流量——宽泛匹配有时候会由于语义鸿沟的问题而导致搜索跟匹配广告相关度不高，尽管它们存在部分关键词重叠。
广告检索是一个跟搜索引擎本身相关的问题：用户输入查询，找到对应的广告，然后排序。然而，跟搜索引擎不同，广告检索需要支持宽泛匹配语义，例如用户查询包含关键词A,B,C,D，广告主如果仅仅针对里边某一个关键词竞价，那么都需要被命中从而参与竞价过程。对于通常搜索引擎来说，情况则相反，用户查询包含关键词A,B,C,D，那么需要返回包含这些关键词（全部或者部分）的文档。从宽泛匹配的检索过程可以看出，广告检索类似于一种“触发”，每个广告创意所竞价的关键词就是触发器。
针对这样的检索需求，最容易想到的就是针对用户的查询进行求并检索，既返回的广告是所有关键词对应倒排索引链的并集合。用通常的倒排表构建索引，会导致这样检索的性能过低，尽管引入roaring位图这样针对求交或者求并迅速的压缩位图，检索性能可以大大提升，但是求并检索带来的另一个问题是对排序的压力过大，因为引入了大量相关度很低的广告，因此广告数量很多时，性能下降严重，然而对于垂直领域的竞价搜索，这样的方案不失为快速有效的选择，例如阿里直通车应当就是采用了这种机制（还有待于内部同学确认，从公开的slide上推断如此）。
第二种手段是把相关度分析和检索合并在一起。用户输入查询时，首先针对该查询进行用户意图判定，具体做法是把查询送入分类器，然后针对
查询进行重写，这样，最终把宽泛匹配转化为精确匹配问题，因此最终的精确匹配过程仅仅需要一个hashtable，key值就是精确匹配查询，value则是对应的Ad Id列表。
除此之外，微软Bing提出了一种专门用于Sponsored Search的索引结构，也是类似hashtable的变种。针对宽泛匹配的语义，所有关键词的子集作为hashtable的key值，如图所示：
在检索时，给定查询，首先产生所有关键词的组合，然后查表，取出Ad列表。然而随着查询长度的增长，这样会引起空间的指数级膨胀，造成过多次查询hashtable引起性能开销，因此需要减少查询次数，具体做法是：假如两个广告A和B，如果A的竞价关键词列表是B的子集，那么把B的value节点移动到A的value节点，这个过程叫做remapping。
在实际系统中，前两种手段因为简单直接而更为广泛使用。
大型Sponsored Search系统中，常常面临的问题是广告主竞价的关键词过于集中，而用户的查询非常长尾，因此有大量广告主无法针对关键词赢得出价而缺乏展现的机会。所以对于宽泛匹配来说，有时候触发的广告不仅仅需要由用户查询命中部分关键词，还常常会引入语义分析而让具备相似度的查询也会触发广告，这样可以给广告主带来更多的流量，例如搜索“HTC手机”可以触发“HTC智能手机报价”，“Android手机”等。基于简易的向量空间模型（例如TF/IDF）是一种计算相似度的手段，但很可能会引起很大的语义鸿沟，比如查询“土豆网”，简单的TF/IDF可能会触发诸如“土豆批发”之类无关的广告。因此，寻找到具有高度相关的触发关键词，是大型Sponsored Search体系中重要的挖掘任务之一。通常的做法会从搜索引擎的用户日志中进行挖掘，包括同一个session内的查询日志，查询后点击日志等，具体手段有对分网络图挖掘，关联规则，共现等手段可以生成语义相关的候选关键词pair列表，然后送入分类器决定这些候选是否语义相关。如果缺乏类似日志，那么可能就需要不同的建模手段来寻找到语义相关的候选集，机器翻译是一个可用的选择，但是需要准备适合的数据集做为训练用，最近一段时间，利用大型主题模型进行类似的工作是一个值得注意的方向，因为可以发掘出更多的长尾候选关键词列表，这个话题过于庞大，我们会在日后逐渐来描述。
Sponsored Search另外一个重要问题是竞价。广告主给定预算，那么它应当如何分配在每个关键词上的出价，才能使得自己的收益最大，在关键词数量少时，广告主可以人工管理每关键词的出价，但是在拥有大量关键词时，人工无法做到全局收益最优，因此引入自动竞价优化是必须的，既由系统来自动为每个广告主的每关键词管理出价。如果系统知道所有广告主的在每个时刻的关键词出价，那么该问题可以转化为常规算法中的背包问题。在实际系统中，由于用户查询以数据流的方式不断到来，因此无法进行如上假设，可转化优化问题为在线背包问题：给定预算和T个关键词，假定每项在t时刻都有收益和损耗，假如t时刻的损耗远远小于总预算，并且收益和损耗之比可以确定上下界，那么就可以在线的方式确定每个时刻的预算分配。跟展示广告不同，Sponsored Search市场通常没有设计成实时竞价，因此出价策略在一定时间内相对稳定。
本文介绍了搜索竞价广告涉及到的几个主要技术问题，可以看到搜索广告跟展示广告所涉及到的技术还是具有相当大的差异，由于搜索广告仅仅在搜索引擎能够占据流量入口的前提下才能存在，因此玩家也只能局限在几个搜索引擎巨头之间。
