《Budget Pacing for Targeted Online Advertisements at LinkedIn》 阅读笔记

发表于 标签

《Budget Pacing for Targeted Online Advertisements at LinkedIn》 是 LinkedIn 在 2014 年发表的一篇关于预算控制的论文，里面的预算控制的策略并不复杂，并且具有很强的实践性和工程性。本文主要是根据论文总结了这个方法的基本原理、工程实现以及实验效果。

顾名思义，预算控制（budget control）在广告系统中的作用就是该如何合理花掉广告主的预算。在实际中经常会出现广告主预算消耗过快的问题，这会导致广告主早早退出竞价，不仅会影响广告主体验，也会导致整个广告生态的竞争力下降（因为那些有竞争力的广告主消耗早早就花光了），在二价的机制下，直接影响了平台的收入。论文为了解决这个问题，提出了一个 budget pacing 的算法。

原理

算法的主要思想就是令每个 campaign（推广计划）的消耗趋势与其曝光变化趋势基本保持一致，以天为时间单位，campaign 为预算控制单位，首先为每个 campaign 预测出其在当天的曝光情况；然后基于其曝光情况，在当前时间片，假如 已消耗/当天预算 的比例大于 已曝光/预测的总曝光 的比例，则说明预算已经消耗过快，需要减小消耗的速度，反之则要加快消耗的速度。

下面详细讲述这个算法的原理

对于某个 campaign \(i\)，记其出价为 \(b_i\)，当天预算为 \(d_i\)。一天的时间被划分为 \(T\) 个时间窗口， \(s_{i,t}(0 \le t \lt T)\) 表示截止到第 \(t\) 个时间窗口开始时的累积预算，\(f_{i,t}\) 与 \(s_{i,t}\) 对应，表示截止到第 \(t\) 个时间窗口开始时的累积曝光 (\(f_{i,t}\) 是预测出来的，下式的 \(f_{i,T}\) 表示预测出来 campaign \(i\) 在当天的总曝光)。则在时间窗口 \(t\) 开始时，有

\[\begin{align} a_{it} := \frac{f_{i, t}}{f_{i, T}}d_i \end{align}\]

根据上面的比例，在每次竞价开始时，为 campaign \(i\) 算出其参与这次竞价的概率 \(p_{i,t}\)，论文称这个概率为 PTR（pass through rate）, 计算方式如下

\[\begin{align}p_{i,t} = \begin{cases} p_{i, t-1}*(1 + r_t)& s_{i, t} \le a_{i, t}\\\ p_{i, t-1}*(1 - r_t)& s_{i, t} \gt a_{i, t} \end{cases}\]

上式中的 \(r_t(0 < r_t < 1)\) 称作调整速率（adjustment rate）。

对于 campaign \(i\) , \(a_{it}\) 在当天开始已经确定，因为 \(f_{i,t}\) 是预测出来的， 因此控制预算就完全是针对 \(s_{i,t}\) 的变化进行。

除了这种调整 campaign 参与竞价概率的控制方式，某些文献也建议通过调整出价的方式进行干预，如下所示是论文 [1] 提出的调价方式

\[\begin{align} b_i^* = b_i \psi(s_{i, t}/d_i) \end{align}\]

其中 \(\psi(x) = 1 - e^{x-1}\)，但是 LinkedIn 这篇论文的作者不建议采用这种方式，原因是对于那些快耗尽预算的 campaign，bid 修改的幅度很小，且出价一般存在着保留价（reserve price），因此可调整的幅度很小。论文也对这种方式做了实验，结果显示该方式对提升 campaign 的预算消耗时长无帮助。

整个算法就是这么简单，下面主要说一下具体的实现细节。

实现细节

更新 PTR 频率

更新 PTR 频率设置成每分钟一次，也就是说时间窗口的大小为 1 min，实验证明这个更新频率使得整个系统更快达到一个稳定状态。

预估曝光量

上面预估某个 campaign 的曝光量可以说是整个算法至为关键的地方，论文并没有针对这一点提出自己的方法，而是采用了论文 [2] 里面的方法，这篇论文是 Yahoo 在做保量的合约广告时提出的预估流量的方法。这里不详细展开了，会另外写一篇博客加以阐释。

调整速率的设置

调整速率也就是上面的 \(r_t\)，目的是控制 PTR 变化的快慢，论文将这个值设置为固定的 10%，这不仅实现简单，鲁棒性也很强。另外一种更复杂的设置方法就是将这个值设置成 \(s_{i,t}\) 的变化率，也就是 \(\partial s_{i,t}/\partial t\), 表示消耗过快的 campaign 其对应的调整速率也应该较大。然后论文还是选择了固定的 10% 的值，原因有两个

1）\(s_{i,t}\) 表示的曲线并不光滑（一系列离散的点），尤其是对于 CPC 这种有了点击才会扣费的广告，这时候的 \(s_{i,t}\) 波动会比较大，从而使得计算出来的 \(\partial s_{i,t}/\partial t\) 会比较 noisy 2）PTR 的更新频率比较频繁，因此即使当前 PTR 不在最合适的位置（\(\partial s_{i,t}/\partial t\)），也能够很快更新到理想位置

设置 PTR 初始值（Slow Start）

论文将每个 campaign 的 PTR 初始值设置为 10%，并将这种方式称为 slow start，因为这个初始值较小。设置较小的初始值给予系统以时间来调整每个 campaign 的 PTR，反之若 PTR 一开始就设置得很高，会导致预算很快被花光。

同样，更合理的方式是为每个 campaign 设置一个 PTR，但是论文并没有针对这一点进行深度的探讨。

Fast Finish

由于系统存在统计偏差，使得 PTR 的值偏低，这会导致当天预算没法完全花出去，而 fast finish 就是针对这个问题的一种解决方法。具体的做法就是修改上面预测的 \(f_{i,t}\) (allocation curve)，令最后两个小时的曝光量为 0，这样会导致 budget pacing 这个算法每天会尝试在 22 小时内花光预算。

工程上的设计

下图是 LinkedIn 的广告系统概览图，advertiser action 是指广告主的行为，包括创建 campaign、修改 bid 或 budget 等；ad requests 则是指用户浏览而触发的广告请求。在 ad sever 中的 campaign index 记录着每个 campaign 当前的状态（曝光，消耗等情况），pacing module 会根据预设的更新频率从 database 中获取最新的数据来更新 campaign index。

engineering design

需要注意的是，pacing module 的更新并不是一次立刻完成，而是采用了较为平缓的方式，上文提到了 pacing 的更新频率为每分钟一次，因此在实际更新是大概每 7s 更新 12% 的 campaign；这种更新频率能够让系统的负载较为均匀，也能够较快达到一个稳定状态。

实验的设计与效果

由于以上的 pacing 方式是以 campaign 为单位的，因此实验会将所有的 campaign 等分为两部分，分别作为实验组和对照组（当然，也可以采用灰度而不是全量的方式）。

为了避免时间因素（weekly，seasonality）的影响，论文认为设计的实验至少要持续两周，如下图所示是一个 campaign 的实验设置情况，其中 On 表示采用上述的 pacing 算法，Off 表示不采用。

design of experiment

则采用 pacing 的效果是标为 On 的那些天的效果的均值，那么该采用哪些指标来评估效果？

首先我们要认识到，在线广告是一个广告主、平台和用户的三方博弈过程，因此在考虑任意机制带来的收益或损失时都要同时考虑到这三方的利益；论文也是同时考虑了这三方的利益，设置了以下指标

  1. 广告主的利益
    • Campain life time：预算消耗 95% 所消耗的时间
    • Unique impressions per spend：单位消耗给广告主带来的 unique user 数量，计算方式 number of unique user/total spend
    • Number of campaigns：表示当天平台服务的 campaign 的数量
  2. 平台的收益
    • Cost per request：每次请求的平均收益，计算方式 total revenue/number of requests
    • Over delivery: 超扣的金额占预算的比例
  3. 用户体验
    • Unique campaings served: 用户看到的所有广告中有几个 unique campaign，表示用户看到的广告的多样性，论文认为这个值越大越好

论文在 LinkedIn 的两种广告（Direct Ads 和 Sponsored Status Updates）上分别做了这个实验，结果如下，带加号 + 的指标表示 On 在 oFF 的基础上的变化比例；根据下表，在各个指标上均有较高提升

effect 1
effect 2

且根据 cost per click 指标，可在一定程度上了解目前系统的竞争力情况，该值越大，表示系统竞争越激烈，论文也根据这个指标对比了采用这个策略前后系统的竞争力，如下图所示，可以看到，采用 pacing 后前期的竞争有所缓和（slow start 导致的），而后期的竞争力比原来有所提升，原因是 campaign life time 变长了，因此有竞争力的 campaign 不会早早就退出了竞价环境。

competition

论文参考文献

[1] A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani.Adwords and generalized on-line matching. Journal of the ACM, 54(5):Article no. 22, October 2007 [2] D. Agarwal, D. Chen, L.-j. Lin, J. Shanmugasundaram, and E. Vee. Forecasting high-dimensional data. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, pages 1003–1012, New York, NY, USA, 2010. ACM.