论文名称： Smart Pacing for Effective Online Ad Campaign Optimization
1.摘要
个性化在线广告中，广告主希望在预算计划的内最大化广告投放活动的效果。大多数广告主希望预算在投放时间段内预算被平稳地花掉，这样可以使得广告活动有更广泛的受众并产生持续的影响。目前在线广告中的大多数曝光都是通过公开竞拍交易的，流动性使得价格具有弹性，供求之间的出价格局也在发生动态变化。因此，既要控制预算消耗的节奏，又要最大化广告的效果，是很有挑战的工作。本文提出了一种智能调节方法，其中每个广告活动的预算消耗速度从都是离线和在线数据中学习的，以实现平稳消耗和最佳效果的目标
2.引言
在线广告是一个数十亿美元的产业，近年来一直保持着两位数的增长。这个市场涌现了搜索广告、上下文广告、保量展示广告以及最近基于拍卖的广告交易平台。本文主要研究以拍卖为基础的广告交易平台，这是一个流动性最高的市场，即每个广告曝光通过公开拍卖的方式以不同的价格进行交易。在这个市场中，DSP是主要的参与者，它们扮演着许多不同广告主的代理角色，通过广告网络或实时竞价广告交易平台去获得不同的曝光，控制广告活动的整体效果。广告主在DSP上的诉求可总结如下：
达成投放和效果目标：对于品牌宣传活动来说，目标通常是花费预算来触达广泛的受众，同时使得广告活动的效果尽可能的好。对于效果广告活动来说，目标通常是达到效果目标，同时花费尽可能多的预算。其它广告活动的目标通常介于这两个目标之间 执行预算消耗计划：广告主通常希望他们的广告可以在投放计划时间段内匀速地展示，以达到更广泛的受众和可持续的影响，并增加与其它媒体(如电视和杂志)广告活动的协同效应。因此，广告主可能会有他们个性化的预算消耗计划。图一给出了两个预算消耗计划的例子：平稳调节和基于流量的调节 降低创意服务成本:除了dsp收取的成本外，通常还有第三方创意服务提供商收取的创意服务成本。如今，随着越来越多的广告活动以视频或富媒体的形式出现，这一点变得更加重要。这类广告的创意服务成本可能与额外库存成本相当，因此广告商总是愿意降低成本，并有效地将广告投放给正确的用户 
然而，同时实现上述目标变得越来越具有挑战性。在单个活动层面，每个活动都可能有自己的预算、预算消耗计划、目标受众、效果目标、计费方式、创意服务成本等。在网络层面，越来越多的DSP通过公开拍卖在多个广告交易平台同时竞争以获取库存，因此，需求和供应之间的价格弹性和竞价格局是动态变化的。即使是单个活动，这些活动和网络层面的多样性也使得优化变得非常困难
幸运的是，由于移动应用和用户生成内容平台等新兴互联网行业的迅速发展，在线广告行业的广告库存大幅增加。如今的DSP每天都会收到来自数十个供应端平台(SSPs)的数百亿个广告请求，因此比以前更灵活地将预算用于大量的广告机会。在这篇论文中，我们考虑了这些趋势所引发的一个问题：我们是否足够的智能去决策将预算花在哪些曝光上，从而实现广告活动的所有目标？ 我们用一个真实的DSP来研究这个问题，并探索模型和算法来有效地服务于它所管理的广告活动。本文贡献总结如下：
以真实的广告活动为基础，使用综合分析的方法对上述多目标问题进行建模，并提出智能调节方案 开发了一种基于控制的方法，它可以从在线和离线数据中学习，以便同时优化预算节奏和活动效果 在一个真实的DSP上实现了所提出的方法，并进行了广泛的在线/离线实验评估。结果表明，我们的方法可以有效地提高活动效果，实现交付目标
3.问题定义
一个广告活动代表一个广告，是广告活动的预算，是广告活动的效果目标。预算消耗计划是个时间段的预算序列，指定了每个时间段需要花费的预算额度，用表示预算计划，其中，。用表示DSP收到的第个请求。正如上一节我们讨论的，我们使用概率平滑来调节预算
，表示广告参与拍卖的概率
表示如果广告参与的拍卖，获胜的概率，它依赖于竞价出价
表示如果广告被采用所需要付出的成本。这个成本包括库存成本和创意服务成本
如果广告被采纳，用户是否会给与一些期望反馈(如点击)
表示广告活动的总体成本
是广告活动的效果(如CPC，期望反馈是点击)
是在个时间段的消耗，其中是第个时间点的消耗，
给定广告活动，定义函数表示实际消耗与预算支出计划的偏差惩罚。值越小，对齐效果越小。下面是一个定义惩罚函数的例子：
3.1 在线广告优化中的智能调节问题
在线广告中广告商需要同时寻找支出预算、执行支出计划并优化广告活动效果。然而，对于这样一个抽象的多目标优化问题，可能存在多个帕累托最优解。在实际情况中，广告主在不同的广告活动中会考虑不同的优化目标。对于品牌推广活动，广告主通常会将预算支出放在首位，然后与支出计划保持一致，效果通常不是首要的考虑因素。在广告请求期间，由于我们使用概率平滑，唯一可以控制的就是。因此，对于没有具体效果目标的广告活动，智能调节问题实际上就是确定的值，可表述为如下优化问题：
其中为实际消耗偏离支出计划的容忍程度。相反，对于具有特定效果目标的广告活动，最高优先级是实现效果目标，实际消耗是否偏离支出计划则不需要着重考虑。对于有具体效果目标的广告活动，智能调节问题也是确定的值，可表述为如下优化问题：
其中，表示对预算没有花完的容忍程度。考虑到市场的动态性，即使是单目标优化问题，解决起来也是非常有挑战性的。目前行业内广泛采用的方案一般只涉及效果目标和预算支出目标。然而，很难保证避免超支或者开支不足的情况。平滑调节控制的一个例子是引入全局调节率，这样所有广告请求被广告活动竞价出价的可能性是相同的。然而，这些现有的方法都无法解决我们在此阐述的智能调节问题。为了解决这个问题，我们做了一些有助于解决问题的分析：
CPM广告。广告商对每个曝光收取固定数额的费用。对于品牌广告的广告主来说，活动优化的定义如公式(2)所示。只要实际消耗和支出计划保持一致，高反馈的广告请求就应该比低反馈的广告请求有更高的点平滑率，这样才能优化效果。对于效果广告来说，活动优化的定义如公式(3)所示。显然，高反馈的广告请求应该有更高的点平滑率来实现效果目标 CPC/CPA广告。广告商根据点击/转化的绝对数量进行收费，这其中隐含了效果目标，来保证DSP在代表广告主竞标时不赔钱，因此，它属于等式(3)定义的优化范畴。无论从广告主还是从DSP的角度来看，给与高反馈的广告请求更高的点平滑率都将更加有效：广告主在创意服务成本上花费更少，而DSP可以节省更多的广告机会服务其它广告活动 动态CPM广告。DSP对每个曝光收取动态金额，而不是固定金额。这些广告活动通常有特定的效果目标，因此属于等式(3)的优化范畴。与CPC/CPA广告类似，高反馈的广告请求应给与更高的平滑率，以减少创意服务成本和节省广告机会
3.2 解决方案总结
基于这些观察结果，我们开发了新的启发式方法来解决智能调节问题。启发式算法试图找到满足方程(2)或者(3)的所有可行解，然后通过反馈控制进一步优化目标。我们首先从离线服务日志中学习并建立一个反馈预测模型，这有助于区分高反馈的广告请求和低反馈的广告请求；其次，我们对广告请求进行分组，将反馈概率相似的广告请求分在同一组，同一组的请求使用相同的平滑率，从而减少解决方案空间。高反馈率的请求有较高的平滑率(如图2a所示)；最后，我们开发了一种基于控制的方法来学习在线反馈数据和动态调整群组的平滑率以逼近最优解。我们假设广告活动是CPM计费，包含或者不包含eCPC目标。我们的方案可以应用于其他计费方式和效果目标，以及其它分组策略，如基于分组
4.反馈预测
我们的解决方案依赖于一个精确的反馈预测模型来预估。有大量的文献工作都在研究和解决这个问题，我们简要介绍一下我们如何进行预估的。在我们的方案中，首先利用数据中的层次结构来收集不同粒度的反馈特征，例如，在广告方面，从根源开始，一层接一层依次是广告主类别、广告主、广告活动，最后是广告。层次结构上不同层次的历史反馈率可以用作特征来学习机器学习模型(如LR、GBDT等)，以给出的原始估计。然后利用用户的年龄、性别等属性构建一个浅树，树的每个叶节点都表示一组不相交的广告请求，每一组广告请求的平均响应率是不同的，且对于每一组广告请求来说，是很难再继续分割下去的；最后，我们对叶节点内的对应的进行校准，得到最后的结果。该方案可以得到一个相当准确的反馈预测
5.基于反馈的解决方案
正如第3节中我们讨论的那样，线上环境是很难达到公式(2)和公式(3)所需要的最优解的。我们探索使用启发式算法来减少原问题的解空间。更具体地说，使用第4节描述的反馈预测模型，相似的广告请求分在同一个组，它们共用相同的平滑率。不同的群组有不同的平滑率，反映出我们对于高反馈率请求的偏好。将原问题中求解各点的平滑率转化为求解一组群组平滑率的问题。为了便于在线反馈数据能够即时应用在活动优化中，我们采用了一种基于控制的方法来调整群组平滑率的方法。换句话说，在整个广告活动生命周期中，群组的平滑率是动态调整的
5.1 分层描述
对于每个广告活动，我们维护一个分层的数据结构，其中每一层都对应于一个广告请求组。我们在分层结构中保留了每个广告请求组的以下信息：反馈预测模型得出的平均反馈率，如CTR；广告请求组的优先级，如平滑率，即对广告请求组中的广告请求进行竞价的概率；广告活动在广告请求组上的实时消耗。其原则是：1）高反馈率的广告请求组对应的层应该享有高优先级；2）高优先级层对应的平滑率不应该小于低优先级层对应的平滑率
对于每个广告活动，当DSP收到一个合法的广告请求时，首先决定该广告请求属于哪个广告请求组，参照相应的层获取平滑率。然后DSP代表广告活动进行竞价出价
5.2 线上平滑率调整
我们采用基于控制的方法利用实时反馈去调节每一层平滑率。假设有层，每一层的预估反馈率是，如果我们期望的反馈是点击，记每一层的eCPC为，其中。记每一层在个时间点的平滑率为，对应每一层的消耗为，基于控制的方法会基于广告活动的目标，在第个时间点来临时，推导出
5.2.1 没有特定效果目标的广告活动
首先针对没有特定效果目标的广告活动，设计调整方法。回想一下，对于这样的活动类型，主要目标是实际消耗与支出计划保持一致。因此，在每个时间段的末尾，算法需要决定在下一个时间段中花费的预算数额，并调整每一层的平滑率以准确地花费该预算数额
下个时间段的预算数额是根据当前的预算支出情况来决定的。对于一个特定的广告活动，假设它的总预算是，预算支出计划是，在运行了个时间段后，剩余预算为。我们需要决定每个剩余时间段内的期望消耗，用来表示，以达到预算可以被花完且惩罚最小的目的
如果采用了等式(1)中的惩罚函数，最优解决方案如下式：
其中，。在线上环境中，假设最近的一个时间段实际消耗是，我们定义残差，它有助于我们做调节决策
算法1描述了平滑率调节的细节。假设索引代表高优先级，索引代表低优先级，用表示具有非零平滑率的最后一层。如果，说明不需要调整；如果，说明应该提高预算消耗速度，平滑率应该自上而下地调整。从等开始，一层接一层地提高平滑率直至。第5行计算了当前层为抵消残差所需的平滑率。如果且，那么就设置层的平滑率为；如果，说明应该降低预算消耗速度，平滑率应该自下而上地调整直至残差被抵消
这种贪心策略试图在线上环境中逼近方程(2)的最优解。在每个时间段内，它试图在总预算和支出计划的约束下，最大化广告效果
5.2.2 具有特定效果目标的广告活动
对于具有特定效果目标的广告活动，平滑率调节相对更加复杂。预测未来所有时段的广告请求流量是非常具有挑战性的，而反馈率分布是随时间变化的。因此，给定预算支出目标，探索当前时间段内所有满足效果目标的广告请求可能不是方程(3)的最佳解决方案。算法2描述了针对这种类型的广告活动，应该如何调整平滑率。在算法1的基础上，我们采用了基于效果目标进一步调整的启发式算法。在算法2中，如果期望效果不满足效果目标，平滑率将会从低优先级的层一个接一个降低以达到期望效果目标。第7行描述了为达到整体效果目标，当前层平滑率的计算方式。如果平滑率从调整到，第2~4行的函数描述了当前层的预估eCPC
5.3 层数、初始化及Trial Rates
我们需要设置适当的层数、初始化及试验平滑率。对于没有任何历史数据的新广告活动，我们在我们的DSP中识别出最相似的广告活动，并估算出可以将预算花完的全局平滑率。层的数量被设置为。值得注意的是，适当数量的层比过多的层效果更好，原因有以下两个：1）当层数过多时，各层的数据统计结果差异不显著；2）从系统的角度来看，过多的层会占用过多的带宽和内存
一旦确定了层数，我们就会以全局平滑率运行广告活动。这个阶段就是初始化阶段，在此阶段可以收集相关数据。我们根据预期反馈率将曝光分组到期望层数中，以识别层的边界。在下一个时间段，每层的平滑率将根据下一个时间段内的支出计划重新分配，高反馈率层的平滑率将设置为1.0，而低反馈率的平滑率将设置为0.0
在调节算法中，非零平滑率挨着的层将会被分配一个实验平滑率，其目的是收集这一层的相关数据，为未来的加速做准备。这个实验平滑率应该是比较低的。我们通过预留预算的一定比例(如)来作为下一个时间段的支出计划，这里记试验层为第层，下一个时间段的预算支出计划是，回想一下，我们至少有这一层一个时间段的历史消耗和平滑率，则可以推导出试验平滑率为：，其中，和的历史平滑率和消耗
简要总结一下，我们采用基于预估反馈率的广告请求分层表示，并在每一层执行预算平滑控制，以实现分配和效果目标。当前时间段的消耗和剩余预算都被考虑用于计算下一个时间段的分层平滑率。我们还尝试了另外一种方法来控制阈值，以达到只有预估反馈率高于阈值的广告请求才会被出价。但是，这种方案的效果并不好，其主要原因是广告请求不会按照反馈率进行平滑分布，因此，很难实现通过单一阈值实现平滑控制
