Question

本章中我们讨论的重点是展示量合约广告以及相应的担保式投送系统。展示量合约广告的优化问题与公式 2.2 表达的一般问题，主要区别在于合约量的要求引入了一些约束条件，这引出了在线分配问题。

在线分配问题指的是在通过对每一次广告展示进行实时在线决策，从而达到在满足某些量的约束的前提下，优化广告产品整体收益的过程。很容易理解，此问题计算上最困难的地方在于“在线”，也就是在信息尚不全面的时候作出决策；而系统上最困难的地方在于分配策略需要是弱状态的，同时各广告投放机之间耦合程度也要尽量低。

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

11.3.1 在线分配问题

我们的出发点仍然是公式2.2的计算广告核心问题。此问题优化的是一组广告展示上的利润，而在线分配问题进一步引入了量的约束。为了讨论方便，需要先对公式2.2做一些变化，得到适合于描述在线分配问题的带约束优化问题。

1.供给与需求二部图

以担保式投送为代表，可以看出在线分配问题有两个主要的挑战：一是要在量的约束下优化效果；二是要实时对每一次展示作出决策。直接在这两个要求下优化，会使得求解过程相当困难。因此，在在线分配问题中，一般将此问题简化为一个二部图（bipartite graph）匹配的问题。这里的“二部”指的是代表广告库存的供给节点（集合记为 I，其中某个节点代表的是所有标签都相同的流量库存）和代表广告合约的需求节点（集合记为A）。

供给节点、需求节点和在线分配二部图的示例如图11-5 所示。在这个示例中，下方的6个节点为供给节点，而上面的三个节点为需求节点。如果某个供给节点的受众标签能够满足某个需求节点的要求，就在相应的两个节点间建立一条连接边。我们把这个二部图记为G=（I∪A，E ），其中 E 为 I 与 A之间边的集合，并用 Γ（a）表示所有与需求节点 a∈A相邻的供给节点的集合，而 Γ（i） 表示所有与供给节点 i∈I 相邻的需求节点的集合。我们的任务就是求解由i∈I 到a∈A的分配比例，使得满足供给方和需求方的约束的同时，某个与广告效果相关的目标函数达到最优。

图11-5 在线分配中的二部图匹配问题示意

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

请大家注意，与2.2的计算广告一般问题相比，这样的二部图结构实际上假设了在同样一组供给节点和需求节点之间发生的广告展示，其目标函数或回报r是没有差别的。这虽然不够准确，但却是更直接地研究在线分配算法的一种合理近似。在这一近似下，r由（a，u，c）组合的函数变成了供给节点 i和需求节点 a的函数，将其记为 r_ia。为了方便起见，从分配问题的物理意义出发，往往还假设整体的收益或目标函数是可分的^[73]，这一目标函数表示为如下的形式：

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

这一在线分配问题的目标函数，直观上看与2.2的一般广告问题目标大有不同，不过这实际上是通过二部图假设简化后得到的表示。另外，在这种表达中，供给节点的数目会随着定向条件的增加而呈几何级数上升，也就会使得对应的分配问题变得过于复杂而无法有效求解。下面我们来看此优化问题有哪些约束。

2.需求约束与供给约束

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

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

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

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

3.问题框架

根据上面的讨论，从公式2.2定义的计算广告目标出发，引入供给约束与需求约束，得到下面的在线分配优化问题框架表示：

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

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

11.3.2 在线分配问题举例

在线分配技术并不仅仅适用于GD问题，其他典型的问题还有AdWords问题、展示广告问题、最大代表性分配（Maximal Representative Allocation，MRA）^[35]问题以及广告交易平台中的询价优化问题等。在此举例介绍GD问题和AdWords问题的具体表达，其他问题还会在本书的后面遇到。

1.GD 问题

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

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

GD问题的两个约束都非常容易理解：供给约束的含义是每个供给节点分配给所有需求节点的流量比例之和不超过1；需求约束的含义是每个需求节点被分配到的流量总和应该大于等于对应合约的展示量要求。

2.AdWords 问题

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

为了便于理解，可以把这里的供给节点i具体想象成搜索广告中的一个关键词。于是，q_ia代表的是将关键词i的一次点击分配给广告a的期望收益，即广告a对关键词i的出价^[7]；s_i为关键词 i的总点击量；而 x_ia 为关键词 i分配给广告 a的流量比例。AdWords问题的优化目标是整个市场的收入最大化；而需求约束的含义是每个广告主的花费应该小于该广告主的预算。

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

11.3.3 极限性能研究

如果不对未来的流量分布做假设和预测，那么在线分配的效率上限如何，什么样的策略更加合理呢？虽然这样极端情形的讨论对实用系统的帮助有限，但这一极限情形的研究却对我们理解问题的本质特点和算法方向有指导意义。

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

公式11.4是一个典型的带约束优化问题，根据第10章介绍的最优化知识，可以应用拉格朗日乘子法来分析这一问题。公式11.4的拉格朗日算符可以表达为：

不进行预测，把每次展示当作一个供给节点，则有s_i=1，于是上式的对偶问题为：

原问题的每个约束条件对应着一个对偶变量。在参考文献[31]中，利用这些对偶变量，作者给出了在Free Disposal^[8]前提下，在线分配的一种优化方案框架。该方案有如下的几个步骤。

（1）初始化每个需求约束的对偶变量β_a←0。

（2）当一次展示i到达时，令a⁰←arg max_a r_ia−β_a取得最大值的广告合约a（即分配给收益最大的合约，如果该值对所有的广告都为负，则所有合约都不需要分配）。

（3）令x_ia0=1，如果 a⁰已经被分配了 d_a0次展示，令i⁰为其中最小的，并将x_i0_a0 设置为0。

（4）在对偶问题中，令α_i=r_ia0−β_a0 ，并通过一定的更新规则来更新β_a0。不同的更新规则对应了不同的分配算法，也相应地会导致不同的分配性能。

这个过程的关键在于两点：一是第2步实际上是把展示分配给最难满足的一个合约；二是第 4 步如何更新 β_a0 ，即如何重新估计需求合约的满足难度。参考文献 [31] 中对几种典型的β_a0 的更新策略进行了讨论，并且给出了一种有效性为（1−1/e）-competitive的分配方案，实际上，可以证明这是在线分配问题可以达到的有效性的上界。表11-1 对比了参考文献[31]中讨论的几种在线分配策略。在几种β_a0 更新策略中，指数加权的极限性能最佳，而且1−1/e被证明是所有分配算法理论上能达到的最好的极限性能。

表11-1 若干在线分配策略的对比

直观地理解，β_a 可以对应于将一个新的展示替换原有已分配给 a的展示时，被替换掉的收益部分。显然，当合约a被分配展示少于d_a 时，β_a 应该为0，而上面的研究告诉我们，按照已分配的权重进行指数加权会有比较好的极限性能。在实际的工程系统中，不可能不利用历史流量数据来进行在线分配。然而，上面的研究对于深入理解在线分配的合理策略会有很大的帮助。

11.3.4 实用优化算法

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

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

在实际的工程系统中，假定流量的分布是平稳的，我们会利用历史流量数据来拟合未来流量s_i，把在线分配转化成离线问题，离线对公式 11.4 进行决策。这是一个一般的带线性约束的优化问题，当优化目标为线性函数或二次函数时，是一个标准的线性规划（linear programming）或二次规划（quadratic programming）问题，可以采用相应的优化工具直接求解该问题。当所求解的问题规模较小时，比如定向标签很少、广告主也较少时，求解过程也很简单。直接求解的Matlab代码如下所示。

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

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

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

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

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

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

下面的Matlab模拟实验代码描述了这一过程。

还原原问题的原始解x_ij：

在实际应用中，由于使用所有历史数据求解上述问题规模太大，需要对数据作一些采样以便更高效地得到分配方案。关于采样的方法以及采样以后该问题求解的稳定性分析，参考文献[73]中也都进行了详细讨论，有兴趣的读者可以进一步探索。

3.综合分配方案 SHALE

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

读者可以自行验证，通过原始对偶方法得到的α和前述直接求解的α一致。在得到了合同的对偶解后，之后的算法和参考文献[73]中的就一样了。基于迭代的对偶问题求解方法节省了线下的计算时间，同时也能更好地支持插入新合同时的增量求解。

4.启发式的分配方案 HWM

上述根据历史流量数据来求解紧凑分配方案的方法原理上可行，但在实际的工程应用中仍然显得有些复杂，比如离线仍要耗费大量时间求解对偶解。我们希望实现一种快速算法，保持前述方法紧凑分配、无状态的特性，效果上也能近似最优。前述方案中通过合同节点的对偶变量（是否容易满足约束）即可恢复最优解，受其讨论启发，我们可以发现，只要大体确定好每个合同在分配中的相对优先级以及分配时得到某次展示的概率，就可以构造出一种直觉上可行的在线分配方案。高水位（High Water Mark，HWM）算法^[23]就是这样一种方案，虽然其数学上不是完全严谨，但是由于根据历史数据来制定分配方案本身就具有相当程度的近似，因此其实际效果也相当不错，又加上工程上的便利性，可以考虑在在线分配方案中采用这种算法。

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

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

图11-6 HWM算法在线分配方案示意

HWM 算法在线分配的基本逻辑是：根据优先级依次检查各个符合条件的候选，直至它们的累积分配比例超过 1，然后，按照这些合约对应的分配比例随机选择一个合约投放（如图11-6 的上图所示）；如果所有的候选合约总的分配比例不足 1，那么以 1 减去其总分配比例的概率请求其他剩余流量变现的广告产品（如图11-6的下图所示）。此分配过程的关键思想在于以概率和优先级相配合的方式进行投放决策。下面的Matlab代码描述了HWM在线分配的算法。