Question

搜索广告是最早产生的，也是最为重要的竞价广告系统。搜索广告的优化目标在公式2.2的基础上加以调整，可以用下式来表达：

这个目标相对简单清晰：对每次展示的各个候选，根据查询估计其点击率µ，并乘以广告主出的点击单价得到eCPM，再按此排序即可。而在eCPM的估计过程中，根据上下文即用户输入的查询来决策。

搜索广告是竞价广告中最典型的系统之一，它与一般广告网络最主要的区别是上下文信息非常强，用户标签的作用受到很大的限制。搜索广告的检索过程一般都不考虑用户u的影响，而上下文信息 c，即查询，又是实时通过用户输入获得，因而离线受众定向的过程基本可以被省略。在这样的应用场景下，搜索广告的系统架构如图13-1 所示，它与一般的竞价广告系统架构的主要区别是没有上下文和用户标签的缓存，但是其检索模块由于查询扩展的需求，会比一般的竞价广告系统要复杂，并且在排序后的收益优化阶段还需要进行北区和东区的广告放置决策。

搜索广告算法上最关键的技术是点击率预测，这一点会在后面专门讨论。除此之外，搜索广告还有一个技术上的重点，那就是查询词的扩展，即如何对简短的上下文信息进行有效的拓展，由于搜索广告的变现水平高，这样的精细加工是值得而且有效的。

13.2.1 查询扩展

搜索广告中查询的重要性极高，粒度又非常细，如何根据广告主需求对关键词进行合理的拓展对于需求方和供给方来说都有很大意义。需求方需要通过扩展关键词获得更多流量；供给方则需要借此来变现更多流量和提高竞价的激烈程度。因此，查询扩展是搜索广告的重要技术，它主要用于5.1.3节中介绍的广泛匹配情形下。搜索广告的查询扩展与搜索中的查询扩展既有相通之处，又有一些显著的区别。相关的方法很多，在此只介绍3种主要的思路。

图13-1 搜索广告系统架构示意

1.基于推荐的方法

如果把用户一个会话（session）内的查询（query）视为目的相同的一组活动，可以在{session，query}矩阵上通过推荐技术产生相关的关键词。这种方法利用的是搜索的日志数据，而基本上个性化推荐领域的各种思路和方法都可以适用。以查询扩展的问题为例介绍一下推荐技术的基本问题。

给定一组用户会话 s={1，···，M} 和一组关键词 w={1，···，N}，可以产生一个对应的交互强度矩阵{x_mn}_M×N。如果其中某个用户搜索过某个关键词，则矩阵相应的元素就置为一个相应的交互值，比如该用户在一段时间内搜索过该词的次数。

显然，这个矩阵中大多数单元都是空白，但这并不意味着用户搜索该词的可能性为零。而推荐的基本任务就是根据这个矩阵中已知的元素值去尽可能预测性地填充那些历史上没有观测到的单元。类似的场景除了搜索，还广泛出现在各种互联网应用当中，比如商品的浏览或购买记录以及在线电影的打分记录都可以抽象出类似的交互强度矩阵以及相应的推荐问题。这样根据群体用户的选择关联性进行推荐的问题也被称为协同过滤（Collaborative Flittering，CF）问题。

基于协同过滤的推荐问题有非常多的算法，它们可以分为基于内存的非参数化的方法和基于模型的参数化方法。后者是用维数较低的空间概要性地刻画交互矩阵，然后根据该空间的生成参数恢复矩阵里未知的值。这种将空间降维的思路与文档主题模型乍看起来很相似，不过问题本身还是有明确的区别：在推荐问题中，应该把那些未观测到的交互单元视为未知，而在文档主题模型中，合理的方法是认为未在某文档中出现的词交互强度为0。关于推荐算法的综述可以参考[58，68]等文献。

各种推荐方法的本质都是对 {x_mn}_M×N 矩阵进行平滑，从而将 x_mn 变成平滑后的值。为什么可以利用推荐的方法进行关键词扩展呢？对某一个关键词w_n来说，其原始的交互强度矢量（x_1n ，···，x_Mn ）^>，虽然我们也可以根据两个关键词对应矢量的相似度来找到近似的关键词，不过由于其元素过于稀疏，这一方法在实用中往往不可行。在经过了推荐算法的平滑以后，这一矢量变成，矢量中的未知元素也都被填充上相对合理的值，于是就可以稳健地比较关键词的相似度。

2.基于主题模型的方法

除了利用搜索的日志数据，也可以利用一般的文档数据进行查询扩展。这类方法实质上就是利用文档主题模型对某个查询拓展出主题相似的其他查询。关于文档主题模型的介绍可以参考12.2.2节。

在主题模型的描述下，每个词w_n都可以对应于一个文本主题组成的矢量{z_n1，z_n2，···，z_nK}。于是，也可以用两个词对应的主题矢量来计算它们相似度。这种方法与上一种方法相比，主要考虑的是语意上的相关性，而非用户意图上的相关性，因此效果会差一些，只能作为用户搜索行为数据不足时的补充方法。

3.基于历史效果的方法

对搜索广告而言，还有一类查询扩展方法很重要，那就是利用广告本身的历史eCPM数据来挖掘变现效果较好的相关查询。由于在广告主选择竞价的关键词时，一般来说都会选择多组，如果从历史数据中发现，某些关键词对某些特定广告主的eCPM较高，那么应该将这些效果较好的查询组记录下来，以后当另一个广告主也选择了其中的某个关键词时，可以根据这些历史记录，自动地扩展出其他效果较好的查询。

虽然这种方法得到的扩展结果经常会与前两种方法得到的结果相重合，不过由于这种方法直接使用广告的优化目标，即 eCPM 来指导查询扩展，往往能够成为前两种方法非常重要的补充手段，而且对提高营收起到的效果往往还要好于前面的两种方法。

13.2.2 广告放置

如5.1.3节中讨论的，广告放置指的是搜索引擎广告中确定北区和东区广告条数的问题。考虑到用户体验，需要对北区广告的数量进行限制，因此，这是一个典型的带约束优化的问题：约束是系统在一段时间内整体的北区广告条数，而优化的目标则是搜索广告系统的整体营收。在进行广告放置之前的排序过程中，比较的都是单条广告的eCPM，不过此处的优化需要处理一组广告，并且需要考虑位置因素，此问题可以表达如下：

其中 n_i 和 e_i 分别表示第 i次展示的北区和东区广告条数。在 eCPM的表达 r 中，多了一个表示位置的参数^[12]，例如，N_s 表示北区的第s个位置，E_s 表示东区的第s个位置。C 为北区的平均广告条数上限。显然，调整北区广告准入的一些指标，如MRP、相关性、质量度等，都会影响此问题的解。为了不使表达过于复杂，这些参数在公式13.3中没有显式出现，但读者可以很容易地在实际系统中找到它们的作用并模拟其影响。显然，这个问题形式上不是可导的，而且要调整的参数也不太多，可以采用10.2.2节中介绍的下降单纯形法求解。

搜索广告虽然不宜进行深入的个性化，但在广告放置问题上存在着很大的个性化空间。不同用户对于广告接受和容忍的程度有着很大的不同，实际上，即使在北美这样的用户教育水平较高的市场上，也至少有30%～40%的用户不能完全分辨搜索结果和广告。因此，对不同的用户动态调整北区的条目数可以使得在北区平均广告数目相同的约束下，整体系统的营收有显著的提高。在考虑单个用户的广告接受程度后，我们可以对公式 13.3 中的收入作个性化的调整。例如，对于北区的一个广告展示，改成下面的形式：

这里的分别表示用户u_i对北区广告的平均点击率和所有用户对北区广告的平均点击率。在计算点击率的过程中需要对北区不同位置的点击做归一化，并且需要做平滑，参考13.5.4节。用r⁰替换公式13.3中的r后，可以用同样的框架求解。