〈搜索引擎怎么竞价〉搜索引擎非竞价!

感谢王先胜百忙之中完成算法约稿。

搜索引擎竞价排名广告，又称付费搜索，赞助搜索（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市场通常没有设计成实时竞价，因此出价策略在一定时间内相对稳定。

上面介绍了搜索竞价广告涉及到的几个主要技术问题，可以看到搜索广告跟展示广告所涉及到的技术还是具有相当大的差异，由于搜索广告仅仅在搜索引擎能够占据流量入口的前提下才能存在，因此玩家也只能局限在几个搜索引擎巨头之间。由上面可见关键字的出价对广告主而言是很重要的一环，接下来简单介绍几种自动出价算法。

出价问题通常抽象为背包问题， 需要解决的问题定义如下：

给定预算B， 竞价N个关键字k1, k2, …kn，每个关键字出价b1, b2, …bn， 每个关键字有M个广告位，已知每个广告位的cpc（cost per click）、ctr（clickthrough rate，点击率）以及关键字的展示量impression（根据之前的统计数据），求b1, b2, …bn，使w(k,b)之和小于B， 且收益v(k,b)最大。其中v(k,b)表示关键字k出价b时获得的收益，可以是广告带来的纯收入或者简单的广告点击量（ Clicks( k, b) = CTR( k, b) * Impr( k, b)）， w(k,b)表示对应的花费。

均价算法：

我们先考虑简化的情况，即只竞价一个关键字的情况。

假设有M个广告位，广告位i的点击率为ctr(i)，点击收费cpc(i)，则期望花费cost(i) = ctr(i) * cpc(i)。以cost为横坐标， ctr为纵坐标，得到二维坐标系下的一系列点（成本-收益图）， 求这些点的凸包。以单次点击预算B画直线x=B，与凸包上边界相交的两个端点即为需要的出价， 按线段比率随机出价。例如下表所示的广告位

得到的成本收益图如下：

虚线框表示凸包， 红线表示预算$0.70时出价，其与上边界相交的边上的两个端点即为出价。

如果竞价多个关键字，但是出价相同， 也可以使用此算法， 此时上图由各个关键字的广告位<cost, clicks>复合而成。

遗传算法：

如果出价多个关键字，每个关键字有多个广告位，则是典型的多选择背包问题，其时间复杂度为O(K^M)，其中K为关键字个数，M为每个关键字的广告位数目，算法复杂度为指数级别。当K、M很小时，简单的组合算法即可求出最优解；若预算B很小，则可用动态规则思路解决。但若K、M、B较大，则需要使用近似算法。遗传算法便是其中一种。

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。初始种群经过多次迭代进化，优胜劣汰逐步逼近最优解。主要由以下步骤组成：

init: 随机生成若干组出价，每组出价称为一个个体，每个个体是出价问题的一组解，比如<b1, b2,…bn>即为一个个体。个体的优劣由适应度（fitness）函数计算，这里一般就是上文所述的收益v(k,b)之和。这些个体组成初始的第一代种群。

selection: 从上一代的个体里随机选择交配个体， 选择算法一般使用 Weighted Roulette Wheel Selection (Weighted RWS) 或者 Stochastic Universal Sampling (SUS)算法， 这些算法能使优秀的个体有更多的机会被选中。

crossover: 每两个个体交配， 分别取其中的部分值（出价bi）生成两个新的个体。这些新的个体形成下一代的种群，继续往下进化。

elitism： 为了保证特别优秀的个体解不被稀释， 给予其特权，不用交配直接加入下一代种群，这个比例一般为最优秀的一对个体。

mutation: 新一代种群中的个体按一定概率（如1%）变异，随机更改其中的部分出价，防止局部最优。

当迭代了若干代或者两代之间的收益不再提高时，算法结束， 输出适应度最高的个体作为出价。

在线算法：

下面介绍一种在线实时出价算法，此算法更多的适用于流式输入请求的实时出价。这里仅考虑只有一个广告位的情况。

假设当前需要出价的关键字广告点击获得的收益为V，已经使用的预算比率为z(t)，则t时刻出价：

b(t) = V/( 1 + f(z) )， 其中f(z) = (U*e/x)^z (x/e)，x为很小的正数，e为自然对数， U=V/bmin， bmin是搜索平台规定的最小出价。

从公式可以看出，此出价只和当前已使用的预算比率及广告收益有关，不需要知道ctr和其他出价者的出价，计算代价小，适合实时出价。可以证明， 此出价具备很高的近似最优比。具体证明过程可以参考相关论文。

参考文献：

1. 均一出价： Budget Optimization in Search-Based Advertising Auctions, Jon Feldman S. Muthukrishnan, Martin P´al, Cliff Stein.

2. 遗传算法： The Adomaton Prototype: Automated Online Advertising Campaign Monitoring and Optimization, KYRIAKOS LIAKOPOULOS, STAMATINA THOMAIDOU, MICHALIS VAZIRGIANNIS.

3. 在线算法： Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems, Yunhong Zhou, Deeparnab Chakrabarty, Rajan Lukose