Question

与展示量合约对应的广告系统称为担保式投送（Guaranteed Delivery，GD）系统。在展示量合约这样的交易结构中，只要合约都被满足，系统的收益就是一定的，于是公式2.2中的优化目标变成了常数。不过，这一系统多了合约带来的一组量的约束条件，因此变成了一个带约束优化问题。关于此问题的具体描述和解法将放在后面的在线分配部分中介绍。有时，展示量合约还会约定投放量未达到时的惩罚，在这种情况下，目标不再是一个常数，不过这仍然可以用在线分配的一般框架来解决。

担保式投送系统的整体架构如图11-2所示。在此系统中，在线投放引擎接收用户触发的广告请求，根据用户标签和上下文标签找到可以匹配的广告合约，然后由在线分配模块决定本次展示投放哪个广告。完成决策后，将展示和点击日志送入数据高速公路。这些日志一方面进入离线分布式计算平台以后，通过日志的整理，完成合约的计划，即确定在线分配算法的参数，再将分配方案送给线上投放机使用；另一方面，日志也送到流计算平台，在反作弊和计价的基础上，再对索引进行快速调整。可以看出，这一系统的核心技术是在线分配的算法策略与执行过程。

由于担保式投送需要用到人群标签或上下文标签，因此在广告检索的过程中也需要用到用户标签（user attribute）和页面标签（page attribute）这两个标签库，由于标签的生成过程与担保式投送本身的关系不大，我们将放在后面受众定向技术部分集中讨论。

担保式投送需要用到的核心技术，最重要的就是在线分配。关于在线分配，我们将在下面用专门的章节介绍。除了在线分配以外，担保式投送还有另外两项主要的支持技术：流量预测和频次控制。

图11-2 担保式投送广告系统架构示意

11.2.1 流量预测

在展示量合约广告中，流量预测^[75]是一项支持技术，它对于在线分配的效果至关重要。除此以外，在广告网络中，一般来说也需要根据定向条件和出价估计广告展示量，以辅助广告主进行决策。因此，流量预测是一项在计算广告中广泛使用的技术。

流量预测的问题可以描述为：给定一组受众标签组合以及一个 eCPM 的阈值，估算在将来某个时间段内符合这些受众标签组合的条件、并且市场价在该 eCPM阈值以下的广告展示量。这里的 eCPM 阈值主要是用于竞价广告系统中，目的是了解在某出价水平下的流量情形。对于展示量合约式广告来说，这个阈值是不需要的，或者为了工程上一致，将该阈值设为一个很大的常数。

流量预测一般的方法其实并不是预测，而是根据历史数据的统计来拟合未来的流量。当然，也可以引入时间序列分析的方法，从流量在时间轴上的规律预测未来某个时间段的流量，这主要适用于需要短时预测的场景，对广告业务来说并不十分必要。因此，此节将主要介绍根据历史数据统计的方法。用统计的方法解决流量预测问题，工程上的主要挑战在于，给定的受众标签组合可能性非常多，不可能将所有这些组合都预先做好统计。可行的思路是将其视为一个反向检索的问题：在一般的广告检索问题中，索引的文档是广告a，而查询是（u，c）上的标签；而在流量预测问题中，索引的文档由广告 a变成了每次展示，而文档的内容即是这次展示上的（u，c）上的标签，而查询由（u，c）上的标签变成了广告设置的受众条件。可以看出，这两个问题是对偶的，可以用类似的技术方案来解决。

对比广告检索问题，流量预测的检索问题要简单一些：首先，（u，c）供给节点不存在布尔表达式描述，而是简单的特征集合；另外，流量预测的大多数应用场景对实时性的要求都不算高，例如，在竞价系统辅助决策时，秒级的响应完全可以满足要求，这比起线上广告检索毫秒级的要求显然要低得多。用反向检索的方案来进行流量预测，主要包括以下几个步骤。

（1）准备文档。将历史流量中，（u，c）上的所有标签的展示合并为一个供给节点i，并统计其总流量s_i以及这部分流量上eCPM的直方图hist_i。这样的每个供给节点作为流量预测反向索引的一篇文档。

（2）建立索引。对上一步生成的每个供给节点建立倒排索引，文档的terms即为此供给节点（u，c）上的所有标签。同时，在索引的正排表部分记录s_i 和hist_i。

（3）查询结果。对一条输入的广告a，将其限定的标签条件作为查询，得到所有符合条件的供给节点的集合。

（4）估算流量。遍历上一步得到的每个供给节点，对于某个供给节点i，首先计算其与该广告 a 的 eCPM 即 r（a，u_i，c_i）=µ（a，u_i，c_i）bid_a，然后根据相应的 eCPM 直方图hist_i 计算a能获得的流量。这样，就可以估算出a在出价bid_a 情形下近似能获得的流量。

基于反向索引的流量预测方法如图11-3所示。实际操作过程中，由于历史广告投放日志可能流量非常大，将所有的供给节点都建立索引规模上是无法承受的。当然，实际上我们也并不需要这样做，在流量预测误差允许的范围内，我们可以在上面的第 1 步和第 2 步之间加一个采样的过程，将索引中的供给节点的数量控制在合理的规模。

图11-3 基于反向索引的流量预测示意

11.2.2 频次控制

频次，指的是某个用户在一段时间内看到某个或某组广告的曝光次数。关于频次对广告效果的影响，Herbert E.Krugman 博士在 1972年提出了著名的“三打理论”（three hit theory）^[48]：第一次，刺激消费者试着了解信息，去问“这个广告是什么？”；第二次，刺激消费者去评量，去问“广告内容是什么？”“我曾经看过这个广告吗？”；第三次，消费者接触到广告时会回忆并开始逃离广告。三次足以对消费者产生作用。这个理论对广告投放的效果有重要的指导意义，但是主要适用于传统广告，并且是假设用户已经顺利通过了关注阶段。对于互联网广告，技术手段能够记录到的展示，在广告位置差异的影响下，离有效展示有相当大的距离，因此无法直接套用三打理论。不过，一般来说，随着某个用户看到同一个创意频次的上升，点击率呈下降的趋势这一点是可以被验证的。因此，在按照CPM采买流量时，广告主有时会要求根据频次控制某个用户接触到某创意的次数，以达到提高性价比的目的。特别是在视频广告这样有效曝光程度较高的广告产品中，频次控制（frequency capping）的意义和重要性尤为显著。

图11-4给出了某广告产品中实际的频次与广告效果（eCPM）的关系曲线。将这一量化结果与传统广告的频次理论相对比，会有一些新的发现：首先，广告效果随着频次的上升呈单调的下降趋势，而并非在三次时达到最佳；其次，频次较高的广告展示效果很差，因此，没有足够的广告主数量，整体的广告效果会受到相当大的限制。而这些特点在竞价广告产品中更加容易利用，我们将在第13章中再讨论。

图11-4 频次与广告效果的关系示例

从计算的角度来看，频次是使得公式2.2中的可分性假设不成立的最主要影响因素。而将频次作为一个可控制的定向条件引入广告系统后，这个问题虽不能被彻底解决，却是大大地缓解了。频次控制的需求可以描述成，控制各（a，u） 组合在一定的时间周期内的展示量。应该说，频次的明确要求主要存在于展示量合约广告中，而在 CPC结算的竞价广告中，可以将频次作为CTR预估的特征之一，从而隐式地对广告的重复展示进行控制。

频次控制有客户端和服务器端两种解决方案。客户端的方案就是把某个用户对某个广告创意的频次值记录在浏览器cookie中，投放决策时再把这个值传给服务器来决策创意。这一方案的好处是简单易行，而且服务成本低。缺点是扩展性不好，当同时跟踪多个广告的频次时，cookie可能会变得很重，从而影响广告响应时间。当然，在移动应用广告中利用SDK做前端投放控制的场景，客户端的方案是非常好的选择。服务器端的方案是在后台设置一个专门用于频次记录和更新的缓存，当广告请求到来时，在缓存中查询候选广告的频次，并根据最后实际投放的广告更新频次。

频次控制用到的缓存，同时存在高并发读和高并发写的要求。而且随着频次控制粒度要求的不同，需要记录的频次变量数目也可能很大。比如在创意级别控制频次就比在广告主级别控制频次需要更多的缓存容量。不过考虑到问题的实际情况，这一缓存实际上可以有很轻量级的方案。对我们有利的问题特性主要有以下两点。

（1）频次存储的规模是有上界的。如果我们在某个时间周期内控制频次，那么上述的频次变量总数一定不会超过这个时间周期内的展示总数，这会远远小于所有可能的（a，u）的组合数量。因此，缓存实际的存储规模没有我们想象的那么大。

（2）当用（a，u） 的组合生成缓存中对应的键时，实际上并不需要处理冲突，因为从业务角度来说，对极少比例的冲突组合上的频次控制不准是可以接受的。因此，我们用简单的MD5之类的散列方法生成键就可以，这会比哈希表的方案要简便高效一些。这实际上也反映了广告系统投放过程弱一致的设计原则。

由于频次控制有上述这些特点，并且存在高并发读写的要求，大多数通用型的 NoSQL存储方案并不能很好地用于频次控制的缓存服务，因此很可能需要自行实现一个非常轻量级的内存（key，value） 方案来满足需求。而且，就大多数广告产品的流量规模来看，此缓存完全可以放在广告投放机本机的内存中。