c++ 记忆化搜索_计算广告：竞价广告计价算法、搜索广告系统

1、竞价广告计价算法

第 5 章中介绍了搜索广告和广告网络这两种最典型的竞价广告产品。在进入这些具体产品的技术之前，我们先来了解一下“竞价”这一核心逻辑的具体实现，顺便引出此核心逻辑的几项主要支持技术。

5.2 节中介绍了位置拍卖市场中一些常用的定价策略，包括 GSP、MRP、价格挤压等，单独理解这些策略都不困难。在实际的系统中，我们需要将这几种策略综合起来执行。以
按 CPC 计价的竞价广告产品中一次广告展示为例，我们将实际的计价算法用下面的代码描
述，可以对照表 5.2 来进一步直观地理解这一完整的定价过程。

1. 1 //In:
2. 2 // cands : 候选广告 ID
3. 3 // ctrs : 候选广告预估的点击率
4. 4 // bids : 候选广告的出价
5. 5 // MRP : 市场保留价
6. 6 // squash : 价格挤压因子
7. 7 // slotNum : 要求的广告条目数
8. 8 //Out:
9. 9 // results : 排序结果
10. 10 // prices : 计价结果
11. 11 void auction(vector<int > & cands, Vec & ctrs, Vec & bids, float MRP,
12. 12 float squash, int slotNum, vector<int> & results, Vec & prices) {
13. 13 int candNum = cands.size();
14. 14
15. 15 // 按照给定的 squashing 因子调整预估 CTR
16. 16 for (int c = 0; c < candNum ;c ++)
17. 17 ctrs[c] = ctrs[c] ^ squash ;
18. 18
19. 19 // 计算调整后的 eCPM
20. 20 Vec eCPMs ;
21. 21 eCPMs.resize(candNum, 1e -10f);
22. 22 for (int c = 0; c < candNum; c ++)
23. 23 if (bids[c] >= MRP)// 跳过那些出价小于市场保留价的候选
24. 24 eCPMs[c] = ctrs[c] * bids[c];
25. 25
26. 26 // 将所有候选按照 eCPM 排序
27. 27 for (int c1 = 0; c1 < candNum; c1 ++)
28. 28 for(int c2 = c1 + 1; c2 < candNum; c2 ++)
29. 29 if (eCPMs[c1] < eCPMs[c2]) {
30. 30 SWAP(cands[c1], cands[c2]);
31. 31 SWAP(eCPMs[c1], eCPMs[c2]);
32. 32 SWAP(ctrs[c1], ctrs[c2]);
33. 33 }
34. 34
35. 35 // 得到各竞价结果并计算定价
36. 36 results.clear(); prices.clear();
37. 37 for (int c = 0; c < candNum - 1; r ++) {
38. 38 if (eCPMs[c] <= 1e-10f)
39. 39 break;
40. 40
41. 41 // 按照 GSP 计算定价
42. 42 float price = eCPMs[c + 1]/ ctrs[c];
43. 43 if (price < MRP)price = MRP;
44. 44
45. 45 results.push_back(cands[c]);
46. 46 prices.push_back(price);
47. 47 }
48. 48 }

在实际的广告产品中，还有可能同时存在若干种计费方式，其 eCPM 估算过程也不同，我们用下面的一小段代码来说明在各种计费方式并存的情况下完整的 eCPM 计算逻辑。当然，这里的逻辑比较简单直觉，有关 CPM 和 CPC 混合竞价的拍卖过程与定价机制的探讨，可以进一步查阅参考文献 。

1. 1 enum BidMode {CPM,CPC, CPS};
2. 2
3. 3 float calcuECPM( float bid, BidMode mode ) {
4. 4 switch ( mode ) {
5. 5 case CPM:
6. 6 return bid;
7. 7 case CPC:
8. 8 return predictCtr() * bid;
9. 9 case CPC:
10. 10 return predictCtr() * predictClickValue();
11. 11 }
12. 12 }

从定价过程的输入可以看出，对于一个 CPC 结算的竞价广告系统，需要先得到广告候选集合，并计算每个候选的点击率，这对应竞价广告两个最关键的计算问题，即广告检索和广告排序，这也是本章要讨论的重点技术问题。
竞价广告中根据 eCPM 对广告进行排序，而根据 2.3.1 节的介绍，按照点击和转化两个发生在不同阶段的行为，eCPM 可以分解成点击率和点击价值的乘积，eCPM 的估计主要就是点击率预测和点击价值估计两个任务：

r(a, u, c) = µ(a, u, c) · ν(a, u) （13.1）

我们认为点击率 µ 是广告 3 个行为主体的函数，而点击价值则是用户 u 和广告商 a 的函数，而在 CPC 计算的竞价广告中，点击价值是广告主的出价，不需要估计。在分别介绍搜索广告和广告网络的架构和技术点之后，我们将把主要篇幅放在广告检索和点击率预测这两项核心技术上。

2、搜索广告系统

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

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

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

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

2.1　查询扩展

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

1．基于推荐的方法

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

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

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

3．基于历史效果的方法

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

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

2.2　广告放置

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

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

以上内容摘选自《计算广告 互联网商业变现的市场与技术》 第2版

《计算广告 互联网商业变现的市场与技术》 第2版

编辑推荐：

适读人群 ：无论是互联网公司商业化部门的产品技术人员，还是对个性化系统、大数据变现或交易有兴趣的产品技术人员，传统企业互联网化进程的决策者，传统广告业务的从业者，互联网创业者，计算机相关专业研究生，都会从阅读本书中受益匪浅。

本书第 1版出版以后，获得的业界反响超乎了我们的想象。实际上，本书已经广泛被互联网公司采用，作为商业化相关部门的培训教程，甚至还成了某大公司商业化部门年会时的”阳光普照奖”奖品。

经过一段时间的补充与修订，我们向读者奉上这次的新版，希望本书能帮助读者深入了解互联网流量与数据变现，洞察互联网增长与财富的秘密，搭建商业化与获客的产品技术体系。

对以下读者，我们相信本书值得一读：

• 互联网公司的商业化、大数据和用户增长部门的朋友；
• 传统广告与数字广告从业者；
• 对推荐、大数据、人工智能技术的应用有兴趣者；
• 转型中的传统企业和创业公司的战略决策者；
• 计算机相关专业学生。

在新版中，我们特别注重了从人工智能方法论的视角审视整个计算广告体系。通过本书对计算广告领域抽丝剥茧的解读，读者会认识到，除解决传统的感知和认知问题以外，人工智能领域形成的方法体系在广告这样的海量数据驱动且人类自身能力不强的问题上，有着巨大的施展空间。

内容简介

计算广告是一项新兴的研究课题，它涉及大规模搜索和文本分析、信息获取、统计模型、机器学习、分类、优化以及微观经济学等诸多领域的知识。本书从实践出发，系统地介绍计算广告的产品、问题、系统和算法，并且从工业界的视角对这一领域进行具体技术的深入剖析。

本书立足于广告市场的根本问题，从计算广告各个阶段所遇到的市场挑战出发，以广告系统业务形态的需求和变化为主线，依次介绍合约广告系统、竞价广告系统、程序化交易市场等重要课题，并对计算广告涉及的关键技术和算法做深入的探讨，这一版中更是加入了深度学习的基础方法论及其在计算广告中的应用。

无论是互联网公司商业化部门的产品技术人员，还是对个性化系统、大数据变现或交易有兴趣的产品技术人员，传统企业互联网化进程的决策者，传统广告业务的从业者，互联网创业者，计算机相关专业研究生，都会从阅读本书中受益匪浅。

作者简介

刘鹏（@北冥乘海生），现任科大讯飞副总裁，大数据研究院院长。他在清华大学获得博士学位后，加入微软亚洲研究院，从事人工智能研究，后参与创建雅虎北京研究院，出任高级科学家。他还曾任MediaV首席科学家a、360商业化首席架构师等职。在多年从业经历中，他一直致力于将人工智能方法与海量数据相结合来解决工业界问题，负责过多个大型互联网商业产品体系。

他特别重视计算广告和大数据技术的普及，他讲授的“计算广告”在网易云课堂有超过3万名学生，已经成为业界进行相关培训的基础教程。他还曾担任北京大学、中国传媒大学等高校客座教授，讲授计算广告相关课程，为推动中国广告产业的数字化、智能化做出了贡献。

王超（@德川），于北京大学获得硕士学位后，曾就职于微博、汽车之家等公司的广告部门，从事计算广告领域的研究和实践工作。现任百度主任研发架构师，从事个性化推荐领域相关的工作。