展示量合约广告的核心技术

展示量合约广告的核心技术包括在线分配 、流量预测、频次控制。合约广告的关键特征，是广告投放的价格和量由双方协商约定。合约广告的重点形式是按指定受众购买的、按CPM计费的展示量合约广告。

01 担保式投送系统

与展示量合约对应的广告系统称为担保式投送系统。在展示量合约这样的交易结构中，只要合约都被满足，系统的收益就是一定的。

不过，这一系统多了合约带来的一组量的约束条件，因此变成了一个带约束优化问题。有时，展示量合约还会约定投放量未达到时的惩罚，在这种情况下，目标不再是一个常数，不过这仍然可以用在线分配的一般框架来解决。

担保式投送系统的整体架构如图所示

在此系统中，在线投放引擎接收用户触发的广告请求，根据用户标签和上下文标签找到可以匹配的广告合约，然后由在线分配模块决定本次展示投放哪个广告。

完成决策后，将展示和点击日志送入数据高速公路。这些日志一方面进入离线分布式计算平台以后，通过日志的整理，完成合约的计划，即确定在线分配算法的参数，再将分配方案送给线上投放机使用；另一方面，日志也送到流计算平台，在反作弊和计价的基础上，再对索引进行快速调整。

可以看出，这一系统的核心技术是在线分配的算法策略与执行过程。担保式投送需要用到的核心技术，最重要的就是在线分配。关于在线分配，最后介绍。担保式投送还有另外两项主要的支持技术：流量预测和频次控制。

02 流量预测

在展示量合约广告中，流量预测是一项支持技术，它对于在线分配的效果至关重要。

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

流量预测一般的方法其实并不是预测，而是根据历史数据的统计来拟合未来的流量（在我做商业化流量预估中，其实用的也是上周历史数据的统计。）当然，也可以引入时间序列分析的方法，从流量在时间轴上的规律预测未来某个时间段的流量，这主要适用于需要短时预测的场景，对广告业务来说并不十分必要。

用统计的方法解决流量预测问题，工程上的主要挑战在于，给定的受众标签组合可能性非常多，不可能将所有这些组合都预先做好统计。可行的思路是将其视为一个反向检索的问题：

用反向检索的方案来进行流量预测，主要包括以下几个步骤：

（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_i,u_i,c_i）=µ（a_i,u_i,c_i）bid_a，然后根据相应的eCPM直方图hist_i计算a能获得的流量。这样，就可以估算出a在出价bid_a情形下近似能获得的流量。

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

03 频次控制

频次，指的是某个用户在一段时间内看到某个或某组广告的曝光次数。一般来说，随着某个用户看到同一个创意频次的上升，点击率呈下降的趋势这一点是可以被验证的。因此，在按照CPM采买流量时，广告主有时会要求根据频次控制某个用户接触到某创意的次数，以达到提高性价比的目的。特别是在视频广告这样有效曝光程度较高的广告产品中，频次控制的意义和重要性尤为显著。

传统广告有一个著名的“三打理论”，认为三次展示对广告效果最好。上图给出了某广告产品中实际的频次与广告效果（eCPM）的关系曲线。将这一量化结果与传统广告的频次理论相对比，会有一些新的发现：首先，广告效果随着频次的上升呈单调的下降趋势，而并非在三次时达到最佳；其次，频次较高的广告展示效果很差，因此，没有足够的广告主数量，整体的广告效果会受到相当大的限制。

问题定义：频次控制的需求可以描述成，控制各（a,u）组合在一定的时间周期内的展示量。应该说，频次的明确要求主要存在于展示量合约广告中，而在CPC结算的竞价广告中，可以将频次作为CTR预估的特征之一，从而隐式地对广告的重复展示进行控制。

频次控制有客户端和服务器端两种解决方案。

客户端的方案就是把某个用户对某个广告创意的频次值记录在浏览器cookie中，投放决策时再把这个值传给服务器来决策创意。这一方案的好处是简单易行，而且服务成本低。缺点是扩展性不好，当同时跟踪多个广告的频次时，cookie可能会变得很重，从而影响广告响应时间。当然，在移动应用广告中利用SDK做前端投放控制的场景，客户端的方案是非常好的选择。

服务器端的方案是在后台设置一个专门用于频次记录和更新的缓存，当广告请求到来时，在缓存中查询候选广告的频次，并根据最后实际投放的广告更新频次。

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

问题特性：对我们有利的问题特性主要有以下两点。

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

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

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

04 在线分配

在线分配问题指的是在通过对每一次广告展示进行实时在线决策，从而达到在满足某些量的约束的前提下，优化广告产品整体收益的过程。

此问题计算上最困难的地方在于“在线”，也就是在信息尚不全面的时候作出决策；而系统上最困难的地方在于分配策略需要是弱状态的，同时各广告投放机之间耦合程度也要尽量低。

在线分配是计算广告中比较关键的算法框架之一，它适用于许多量约束下的效果优化问题，而这实际上是广告业务非常本质的需求。由于在线分配问题的重要性超越了担保式投送本身，我们先来介绍此问题的应用场景与算法。

1、供给与需求二部图

以担保式投送为代表，可以看出在线分配问题有两个主要的挑战：一是要在量的约束下优化效果；二是要实时对每一次展示作出决策。直接在这两个要求下优化，会使得求解过程相当困难。

因此，在在线分配问题中，一般将此问题简化为一个二部图匹配的问题。这里的“二部”指的是代表广告库存的供给节点（集合记为I，其中某个节点代表的是所有标签都相同的流量库存）和代表广告合约的需求节点（集合记为A）。

供给节点、需求节点和在线分配二部图的示例如上图所示。在这个示例中，下方的6个节点为供给节点，而上面的三个节点为需求节点。如果某个供给节点的受众标签能够满足某个需求节点的要求，就在相应的两个节点间建立一条连接边。

我们把这个二部图记为G=（I∪A,E），其中E为I与A之间边的集合，并用r(a）表示所有与需求节点a∈A相邻的供给节点的集合，而r(i）表示所有与供给节点i∈I相邻的需求节点的集合。我们的任务就是求解由i∈I到a∈A的分配比例，使得满足供给方和需求方的约束的同时，某个与广告效果相关的目标函数达到最优。s

二部图中的供给节点有时为一组标签约束下的流量集合，在这种情况下，用s_i表示供给节点i的总流量；有时也会用一个节点代表一次展示，这适用于不假设对流量有预测能力的场景或者需要精细区分每次展示的场景下。

这样的二部图结构实际上假设了在同样一组供给节点和需求节点之间发生的广告展示，其目标函数或回报r是没有差别的。在这一近似下，r由（a, u, c）组合的函数变成了供给节点i和需求节点a的函数，将其记为r_ia。为了方便起见，从分配问题的物理意义出发，往往还假设整体的收益或目标函数是可分的，这一目标函数表示为如下的形式：

其中s_i为供给节点i的总供给量，而x={x_ia}_|I|x|A|中的每个元素表示s_i分配给合约a的比例，这就是在线分配问题求解的变量。

在这种表达中，供给节点的数目会随着定向条件的增加而呈几何级数上升，也就会使得对应的分配问题变得过于复杂而无法有效求解。

下面我们来看此优化问题有哪些约束。

2、需求约束与供给约束

在线分配问题的第一个约束条件是分配给某广告合约a的收益要至少等于其约定的量d_a，这个约束称为需求约束:

其中q_ia为将供给节点i 连接到需求节点a 的单位流量惩罚，其具体意义将在后面举例说明。简单起见，一般都假设这一需求约束是线性的，实际上这也已经能满足所有常见场景中的需求。

实际产品中常见的需求约束有两类：一类是预算、服务成本等的上限要求；另一类是合约量的下限要求。在后一种情形下，q_ia为负数，需求约束实际上描述的是一个收益项的下界。

在线分配问题的另一个约束条件是每个供给节点被分配出去的量不能多于其总流量，这个约束称为供给约束，其意义很容易理解。供给约束可以表示成下面的形式：

3、问题框架

根据上面的讨论，引入供给约束与需求约束，得到下面的在线分配优化问题框架表示：

除了供给约束和需求约束，上式中还有第三个约束，它用以保证分配变量非负。上述公式是一个比较一般性的数学表达，不仅仅适用于GD问题，也适用于其他量约束下的在线分配问题。有关它的一些算法和结论也不仅仅用于合约式广告系统，在后面介绍的竞价广告系统或广告交易市场中也有着广泛的应用。

如果可以离线对上述公式进行决策，那么这是一个一般的带线性约束的优化问题。然而在广告投放实际环境中，不可能达到全局最优，而是必须对每次广告展示马上作出决策，这就要求设计一种比较聪明的策略，使得整体流量情况尚不明朗时，仍然可以相对合理地作出决策，而最终目的是全部流量上的分配结果与离线最优化的结果尽量接近。

4、在线分配问题举例: GD问题

在线分配技术并不仅仅适用于GD问题，其他典型的问题还有AdWords问题、展示广告问题、最大代表性分配问题以及广告交易平台中的询价优化问题等。

在此举例介绍GD问题和AdWords问题的具体表达。

GD问题:在线分配的最典型应用就是GD（担保式投送）问题。在此主要考虑按CPM结算的市场。在GD合约的情形下，由于按CPM售卖广告在所有合约都满足时，如果不考虑合约a未完成的惩罚，收益是一定的常数。那么GD的优化问题可以写成：

可以看出，GD问题的优化目标主要在于更好地满足所有合约的要求，而不是优化eCPM。有时，GD合约在未达成时会有相应的惩罚，在这种情形下，目标函数就不是常数了，可以引入惩罚项来改写上面的问题，使其仍然在在线分配的框架内，在此不详细描述。

GD问题的两个约束都非常容易理解：

供给约束的含义是每个供给节点分配给所有需求节点的流量比例之和不超过1；需求约束的含义是每个需求节点被分配到的流量总和应该大于等于对应合约的展示量要求。

5、在线分配问题举例: AdWords问题

AdWords问题，也被称为有预算约束的出价问题，讨论的是在CPC结算的竞价广告环境下，给定各个广告主的预算，整体化市场营收的问题。在这种情形下，目标函数和需求约束都有所变化，其对应的在线分配问题体现为如下的形式：

为了便于理解，可以把这里的供给节点i具体想象成搜索广告中的一个关键词。于是，q_ia代表的是将关键词i的一次点击分配给广告a的期望收益，即广告a对关键词i的出价;s_i为关键词i的总点击量；而x_ia为关键词i分配给广告a的流量比例。

AdWords问题的优化目标是整个市场的收入最大化；而需求约束的含义是每个广告主的花费应该小于该广告主的预算。

研究AdWords问题的目的是为了探讨在广告主有预算上限的情形下，是否可以通过全局的分配调整影响整个市场的收入。不过对这一问题的实际意义和效果，工业界存在着不同的看法：在自助式投放中，广告主有时会先预设较少的预算，并在预算将花完时判断是否要追加。因此，在系统中看到的预算并不是一个强约束。但是，这样的思考方式以及在线分配对于各种量约束下优化问题的框架意义是值得体会的。

05 实用优化算法

假定未来一段时间内需要投放的合约是已知的，如果广告流量的分布在各个循环周期内是近似一致的，那么在线分配的问题就可以在流量预测的指导下进行，这是大多数在线分配实用工程方法的基本出发点。

1、直接求解的原始分配方案

在实际的工程系统中，假定流量的分布是平稳的，我们会利用历史流量数据来拟合未来流量s_i，把在线分配转化成离线问题，离线对如下公式进行决策。

这是一个一般的带线性约束的优化问题，当优化目标为线性函数或二次函数时，是一个标准的线性规划或二次规划问题，可以采用相应的优化工具直接求解该问题。当所求解的问题规模较小时，比如定向标签很少、广告主也较少时，求解过程也很简单。

在大型的合约广告系统中，由于定向条件的复杂性，供给节点的数目会随着定向条件的增加而呈几何级数上升，需求节点数也会达到数千个，边|E|的数目会在百万级以上，这就使得对应的分配问题变得过于复杂而无法直接有效求解。我们令n为变量的个数（正比于供需二部图中边的数目 |E|），求解线性规划问题的经典算法如内点法（时间复杂度为n的多项式级别）和单纯形法（时间复杂度为O（n^1.5 – n²））在小时级延迟的定期更新求解是几乎不可能的。另外，这样直接求得的解参数正比于|E|的数量，规模有可能过于庞大，在线上投放时使用很不方便。因此，我们有必要探索更新效率更高、空间复杂度更低的在线分配方案。

2、基于对偶算法的紧凑分配方案

在实际的广告系统中，不仅要考虑离线分配方案规划时的复杂度，还要考虑线上的快速响应。模型的分配策略不能给服务器带来内存和计算上的很大负担，而前述原始分配方案中求解出来的原问题的方案过于庞大（变量数正比于|E|）。因此，往往需要一个更紧凑的分配方案。

除了紧凑性的要求，如果分配策略能做到一定程度上无状态，即投放策略与前面的投放历史无关，这对于广告投放机的实现非常有利：如果与投放历史无关，多台广告投放机之间就不需要频繁进行同步以完成状态更新，而是根据预先计算好的策略进行投放即可，这对于系统的稳健性和扩展性非常有益。

在线分配对偶问题的解不是紧凑解，其变量数目正比于约束的数目，包括供给约束和需求约束，前者变量的量级数为十万甚至百万千万，但后者的量级在数千级别。为了分配方案的紧凑性，可否只保留需求约束对应的对偶变量，通过数学变换恢复出供给约束的对偶变量和分配率x 呢？通过对相应对偶问题的K.K.T条件的分析，推导得到了一个由β恢复α和x最优解的计算方法：

由于β 的维数正比于合约数目 |A|，远远小于x的维数（正比于 |E|），我们把这样的方案称为紧凑分配方案。利用这一方法，只需要在一部分历史数据上求解对偶问题得到α，就可以很高效地进行在线分配。

在实际应用中，由于使用所有历史数据求解上述问题规模太大，需要对数据作一些采样以便更高效地得到分配方案。

3、综合分配方案SHALE

前述的基于对偶算法的紧凑分配方案，虽然在线分配时确实达到了紧凑和无状态的特性，但是求解的代价仍然较高。在SHALE算法中，作者对求解对偶变量的步骤进行了优化，采用原始对偶方法迭代进行求解，每次迭代的过程中改善对偶解。这样的方法，可以比较高效地求解。

基于迭代的对偶问题求解方法节省了线下的计算时间，同时也能更好地支持插入新合同时的增量求解。

4、启发式的分配方案HWM

上述根据历史流量数据来求解紧凑分配方案的方法原理上可行，但在实际的工程应用中仍然显得有些复杂，比如离线仍要耗费大量时间求解对偶解。

我们希望实现一种快速算法，保持前述方法紧凑分配、无状态的特性，效果上也能近似最优。前述方案中通过合同节点的对偶变量（是否容易满足约束）即可恢复最优解，受其讨论启发，我们可以发现，只要大体确定好每个合同在分配中的相对优先级以及分配时得到某次展示的概率，就可以构造出一种直觉上可行的在线分配方案。

高水位（High Water Mark, HWM）算法就是这样一种方案，虽然其数学上不是完全严谨，但是由于根据历史数据来制定分配方案本身就具有相当程度的近似，因此其实际效果也相当不错，又加上工程上的便利性，可以考虑在在线分配方案中采用这种算法。

HWM分配规划算法的关键有两点，一是根据历史流量确定每个广告合约资源的紧缺程度，进而得到分配优先级；二是根据优先级确定各个广告合约的分配比例。优先级可以通过可满足各合约的供给节点总流量的升序排列得到，而在确定了合约的优先级之后，按照优先级依次确定各合约的分配率以满足其流量要求。下面的Matlab代码描述了HWM离线制定分配计划的算法。

根据上面离线生成的分配方案，也即对每个需求节点计算出来的分配优先级（order）和分配率（rate），可以很方便地在线上服务中对每次展示作出简单的决策，这一决策的过程如下图所示。

HWM算法在线分配的基本逻辑是：

根据优先级依次检查各个符合条件的候选，直至它们的累积分配比例超过1，然后，按照这些合约对应的分配比例随机选择一个合约投放；

如果所有的候选合约总的分配比例不足1，那么以1减去其总分配比例的概率请求其他剩余流量变现的广告产品。

此分配过程的关键思想在于以概率和优先级相配合的方式进行投放决策。

总结：展示量合约广告的核心技术包括在线分配 、流量预测、频次控制（展示量品牌合约广告一般有要求，实际竞价广告将频次作为CTR预估的特征之一，从而隐式地对广告的重复展示进行控制。）