合约广告的关键特征，是广告投放的价格和量由双方协商约定。展示量合约广告的投送系统称为担保式投送系统。它依赖于受众定向、流量预测、点击率预测这3项基本技术，并采用在线分配的方式完成实时决策。

    一是在未来流量分布未知的情形下，如何估计在线分配算法的极限性能；二是在根据历史数据能进行相对合理的流量预测的情形下，如何利用这些预测搭建一个实用的在线分配系统。流量预测是在线分配的基础，也是后面竞价广告系统中广泛使用的功能。流量预测的方法有多种类型，频次控制则是广告主为了展示的有效性提出的控制性要求。

一、广告排期系统

对于按CPT结算的广告位合约，媒体一般采用广告排期系统来管理和执行。

排期与动态广告混合系统

对一个广告位合约与动态广告混合投放的系统来说，需要同时考虑CPT广告和防天窗广告的投放逻辑。我们以Web页面上的广告投放为例来描述这一调度过程。

（1）前端的广告位代码从CDN上获取一个默认广告素材，并标示此广告是优先的CPT广告还是防天窗广告的参数。

（2）根据上述参数，如果CDN上获得的是一个CPT广告，那么直接将素材渲染在页面上即可。

（3）如果CDN上获得的是一个防天窗广告，则优先向广告投放机发送请求，如果在指定延迟时间内有广告返回，则将其渲染在页面上。

（4）如果服务器在指定延迟时间内没有广告返回或发生其他错误，则将从CDN里得到的防天窗广告渲染在页面上。

二、担保式投送系统

    与展示量合约对应的广告系统称为担保式投送（GuaranteedDelivery，GD）系统。

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

1、流量预测

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

    流量预测的问题可以描述为：给定一组受众标签组合以及一个eCPM的阈值，估算在将来某个时间段内符合这些受众标签组合的条件并且市场价在该eCPM阈值以下的广告展示量。

    流量预测一般的方法其实并不是预测，而是根据历史数据的统计来拟合未来的流量。

    用统计的方法解决流量预测问题，工程上的主要挑战在于，给定的受众标签组合可能性非常多，不可能将所有这些组合都预先做好统计。可行的思路是将其视为一个反向检索的问题：在一般的广告检索问题中，索引的文档是广告a，而查询是(u,c)上的标签；而在流量预测问题中，索引的文档由广告a变成了每次展示，而文档的内容即是这次展示上的(u,c)上的标签，而查询由(u,c)上的标签变成了广告设置的受众条件。可以看出，这两个问题是对偶的，可以用类似的技术方案来解决。

    用反向检索的方案来进行流量预测，主要有如下一些步骤。

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

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

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

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

2、频次控制

    频次指的是某个用户在一段时间内看到某个或某组广告的曝光次数。

    关于频次对广告效果的影响，Herbert E.Krugman博士在1972年提出了著名的“三打理论”：第一次，刺激消费者试着了解信息，去问“这个广告是什么？”；第二次，刺激消费者去评量，去问“广告内容是什么？”“我曾经看过这个广告吗？”；第三次，消费者接触到广告时会回忆并开始逃离广告。三次足以对消费者产生作用。这个理论对广告投放的效果有重要的指导意义，但是主要适用于传统广告，并且假设用户已经顺利通过了关注阶段。对于互联网广告，技术手段能够记录到的展示在广告位置差异的影响下离有效展示有相当大的差距，因此无法直接套用三打理论。

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

    频次的明确要求主要存在于展示量合约广告中，而在CPC结算的竞价广告中，可以将频次作为CTR预估的特征之一，从而隐式地对广告的重复展示进行控制。

三、在线分配

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

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

1、在线分配问题

供给与需求二部图

    以担保式投送为代表，可以看出在线分配问题有两个主要的挑战：一是要在量的约束下优化效果；二是要实时对每一次展示做出决策。

    在在线分配问题中，一般将此问题简化为一个二部图（bipartite graph）匹配的问题。

需求约束与供给约束

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

    在线分配问题的另一个约束条件是每个供给节点被分配出去的量不能多于其总流量，这个约束称为供给约束（supplyconstraint）

2、在线分配问题举例

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

GD问题

    这里主要考虑按CPM结算的市场。在GD合约的情形下，由于按CPM售卖广告，在所有合约都满足的情形下，如果不考虑合约a未完成时的惩罚，收益是一定的常数。GD问题的优化目标主要在于更好地满足所有合约的要求，而不是优化eCPM。

AdWords问题

    AdWords问题，也称为有预算约束的出价（budgetedbidder）问题，讨论的是在CPC结算的竞价广告环境下，给定各个广告主的预算，整体化市场营收的问题。

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

3、极限性能研究

    极限性能研究的指标主要是某在线分配策略的有效性。所谓有效性，可以描述如下：如果能够完全确定所有的流量分布情况，那么可以根据全局的信息求得一个分配的最优解；但是由于分配是在线执行，最优解并不一定能达到，如果某种在线分配策略在最差情形下能够达到上述最优解目标函数的 倍，那么我们就说这一分配方案是 -competitive的。

4、实用优化算

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

直接求解的原始分配方案

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

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

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

综合分配方案SHALE

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

启发式的分配方案HWM

    上述根据历史流量数据来求解紧凑分配方案的方法原理上可行，但在实际的工程应用中仍然显得有些复杂，例如离线仍要耗费大量时间求解对偶解。我们希望实现一种快速算法，保持上述方法紧凑分配、无状态的特性，效果上也能近似最优。

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

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