|
|
Real time bid optimization with smooth budget delivery in online advertising原论文
实时广告投竞标优化与预算控制
摘要
在当今的在线广告市场，每天都有数以十亿计的广告展示位通过实时竞价（RTB）交易所进行公开拍卖。在这种情况下，广告商需要在毫秒级时间内为每个收到的RTB广告请求提交投标。受预算限制，广告商的目标是购买一定数量的广告展示次数，以尽可能多地触及目标用户。同时，广告商希望能够在一天内平稳地分配预算，以覆盖更广泛的受众并产生持续的影响。
广告商关心的转化行为（如购买产品、填写表格、注册电子邮件等）因广告商不同而有所不同。然而，实现预算和性能目标的挑战在于转化事件较少且反馈通常存在延迟。为解决这一问题，文章提出了一种在线方法，旨在平滑预算交付的同时优化转化性能。该算法通过自适应地选择高质量的广告展示次数，并根据先前的性能分布调整投标价格，实现在时间上最优地分配预算。
实验结果表明，在实际广告活动中，这种方法能有效地解决广告投放中的预算和性能目标之间的挑战。
近年来，实时竞价（RTB）交易所在广告位的销售方面取得了显著增长。RTB交易所利用算法投标技术为广告商提供了一种参与公开拍卖的方法，以便针对每个独立的广告展示进行投标。这种机制使广告商可以以高性价比购买广告库存，并确保在合适的时间、适当的场景向目标受众展示广告。然而，要实现这一目标，广告商需要实时智能地评估每个广告展示的价值。
为了解决这个问题，需求方平台（DSP）提供了一种名为实时竞价优化的解决方案，帮助广告商在每秒接近一百万次的广告请求中找到最佳的投标价值。实时竞价优化的过程旨在在预算和投放限制的约束条件下最大化广告活动的性能指标。这些性能指标通常包括最小化每次点击费用（CPC）和每次操作费用（CPA），以及最大化点击率（CTR）和行动转化率（AR）。
为了实现可持续的广告影响力，广告商通常采用平滑预算投放策略，即在设定时间段内保持一定比例的库存不投放广告，以防止过早耗尽预算或避免短时间内大量投放广告。这种策略有助于广告商在高峰流量期间避免大量广告投放（尽管性能可能会下降），并扩大受众覆盖范围。
然而，在RTB环境中进行实时竞价优化面临诸多挑战。首先，由于每个广告请求的投标决策和投标价格评估需在数毫秒内完成，因此对时间敏感性要求极高。其次，实时评估个体广告请求时，通常缺乏大量信息，例如前期决策的反馈。具体而言，点击信息的收集可能因日志记录过程中的数据去重而延迟，而大多数视图操作可能需要长达七天的时间才能被转换并归属到相应的广告活动。因此，在实时竞价优化过程中，广告商需要不断应对这些挑战。
对于非搜索广告而言，点击和转化事件较为罕见，导致评估过去广告效果时的方差较大。因此，我们提出了一种在线方法，旨在优化广告性能指标，同时确保每个广告活动在预算消耗方面保持平稳。
首先，我们的方法利用控制反馈环路，迭代地预测未来的广告消费率，以满足平滑交付约束。接下来，通过消费率选择高质量展示机会，并根据先前的广告性能分布调整出价，以实现性能目标的最大化。
论文的结构如下：
在第二部分，我们详细阐述了问题的形式化定义以及先前相关研究。
在第三部分，我们描述了我们提出的在线竞价优化方法。
在第四部分，我们讨论了在竞价优化过程中遇到的实际问题以及提出的解决方案。
在第五部分展示了详细的实验结果，
最后在第六部分通过讨论我们的方法和可能的未来工作来做出结论。
2 背景和相关工作
我们首先将竞价优化问题表示为在线线性规划问题。然后，我们回顾了文献中的先前相关工作，分析为何这些解决方案在实践中不适用于我们的在线竞价优化问题。
在在线竞价优化场景中，我们考虑按索引 i 顺序依次到达的 n 个广告请求。广告商需要对所有 i∈{1,...,n} 做出决策，即是否对第 i 个广告请求进行投标。这个决策可以用指示变量 xi∈{0,1} 表示。
广告商拥有总日预算 B 用于购买广告展示机会。通常，广告商希望预算消费平滑进行，以避免以下两种情况：
提前结束活动：广告商不希望广告活动在一天内过早耗尽预算，从而错过剩余时间的机会。过早的预算支出可能导致活动提前数小时结束1(a)。
支出波动：广告商希望能够定期分析他们的广告活动，预算波动过大会使结果的一致性受到质疑。因此，类似于图1(b)所示的预算分配方案是不可行的。
一个简单且常用的平滑预算消费策略是均匀分配预算，即在一天内平均分配预算1(c)。但这种策略存在两个主要问题：
流量问题：在线流量在一天内的不同时间段根据目标受众有很大变化。均匀预算分配策略可能无法适应这些变化，导致预算无法在一天结束前耗尽，或被迫在低质量展示时段购买广告1(d)。
性能问题：不同受众群体的在线流量质量在一天内会发生变化。预算分配策略应将更多预算分配给质量高的时间段。这样的策略可能导致预算波动较大，从而违反平滑预算消费约束1(e)。
为了解决这些问题，我们需要寻找一种能够考虑流量和广告性能的预算分配策略。这将有助于广告商在满足平滑预算消费约束的同时，实现更高的广告效果。
在平滑交付约束下平衡流量和性能具有挑战性。在本文中，我们提出了一种旨在同时解决这两个问题的策略。
为了实现平滑交付约束（将在第1节中详细解释），整个每日预算B可以分解为一系列时间段预算分配{b1，...，bT}，其中bt∈R表示分配给时间段t的预算，并满足∑T t=1 bt = B。在下一节中，我们将介绍如何应用不同的节奏策略来分配bt，以便选择更高质量的展示次数。
每个广告请求i都与一个价值vi∈R和一个成本ci∈R相关联。如果给定的广告请求i被受众看到，则价值vi表示广告商认定的实际价值。成本ci表示广告商需要支付给提供相应展示次数的发布者的实际成本。
总之，带有平滑预算交付约束的竞标优化问题可以被表述为：
在时间段t内，Ⅱt表示所有广告请求的索引集合。由于在决定是否购买广告请求i（即决策xi）时，未来广告请求的成本和价值尚不明确，因此该优化问题需要离线处理。具体来说，在收到广告请求i后，竞价优化的在线算法必须在没有观察到更多数据的情况下做出决策xi。对于动态竞价活动，优化过程还需要估计实际竞价价格^ci。需要注意的是，竞价价格与收到请求i的成本ci并不相等，因为成本是由实时竞价（RTB）交易中的二价拍卖决定的。
为了在二价拍卖中获胜并实际支付ci，竞价者应当以竞价价格^ci=ci+εi进行竞价。εi的值取决于拍卖属性，但在竞价时尚不可知。
简而言之，为了解决这个优化问题，我们需要开发一个在线算法，在收到广告请求后，能够在不观察更多数据的情况下做出购买决策。同时，我们还需要估计实际竞价价格以确保在二价拍卖中获胜。通过这种方法，我们可以在遵循平滑预算交付约束的前提下，选择更高质量的广告展示次数，并提高整体广告投放效果。
2.2 相关工作
在线线性规划（Online Linear Programming）是许多实际问题的通用框架，例如在线竞价[8、19]、在线关键词匹配[21]、在线背包问题[11]和在线资源分配[7]。尽管已有一些论文对相关方法进行了全面调查[3、6]，我们在此仅总结几种代表性方法。
周等人[21]将受预算约束的竞价优化问题建模为在线背包问题。他们提出了一种基于指数函数的简单策略，用于在预算期间选择高质量的广告请求。随着时间的推移，所提出的算法将选择越来越高质量的广告请求。然而，这种方法有一个底层的假设：广告请求的供应是无限的，即在实时竞价（RTB）环境中有无限量的广告请求。这种假设对于那些有严格受众定位限制的广告活动来说是不切实际的。
Babaioff等人[5]将动态竞价定价问题建模为多臂赌博机框架，然后应用上限置信区间策略来探索在线交易的最优价格。这种方法不需要任何关于先前分布的信息。然而，多臂赌博机框架通常需要快速从环境中收集反馈，以更新效用函数。不幸的是，在RTB环境中，竞标和性能信息的收集时间延迟较长，这种方法并不适用于广告展示。
Agrawal等人[3]提出了一种通用的在线线性规划算法来解决许多实际的在线问题。首先，他们应用标准的线性规划求解器来计算已在系统中看到的数据的最优对偶解。然后，通过检查新实例的对偶解是否满足约束条件来决定新实例的解。问题在于，在广告请求到达时，其真实价值vi和成本ci是未知的。如果通过某些统计模型或其他替代方案来估计vi和ci，为了准确地施加预算约束，需要更频繁地重新计算每个广告活动的对偶解。这会在实时竞价系统中引入高计算成本。
3 在线出价优化
在本节中，我们将详细探讨在线出价优化的方法。首先，我们将回顾平滑交付约束的概念，并解释如何在每个广告请求按顺序到达时自适应地控制支出速度。接着，我们将讨论如何迭代地应用支出信息来选择广告请求并调整其出价，以便优化目标函数。
我们需要认识到广告投放中存在两种不同类型的广告系列：（i）固定CPM系列，和（ii）动态CPM（dCPM）系列。这两种类型之间的主要区别在于固定CPM系列提交一个恒定的出价，而动态CPM系列则优化出价。在两种广告系列中，都需要决定是否竞标广告请求。在固定CPM系列中，决策的优劣通常由点击率（CTR）或者行动转化率（AR）来衡量；而在动态CPM系列中，通常采用有效每点击成本（eCPC）或有效每行动成本（eCPA）作为衡量标准。无论哪种系列类型，我们都试图优化以下目标：
在这个优化问题中，我们的目标是最大化广告系列的投资回报，同时考虑以下约束条件：
- 总日预算约束，其中 s(t) 代表在时间槽 t 花费的预算；
- 基于计划 b(t) 的平稳交付约束，以确保广告支出在整个投放期间保持均衡；
- eCPM 不得超过上限 M；
- 使得 dCPM 活动在时间上看起来像 CPM 活动，这意味着我们需要在 dCPM 中使用 CPM 作为度量标准。
在这个优化问题中，优化参数是 b(t)，因为总预算 B 和平均印象成本上限 M 由广告商设定。在本节的剩余部分，我们将详细介绍我们的预算配额方案，并展示如何通过智能预算配额来改进此优化。
3.1 平稳预算交付
平稳预算交付的主要目标是根据每日预算实时计算每个广告活动的投放计划。DSP 将依据这些计划在一天内均匀分散各个活动的广告展示次数。为实现这一目标，我们将一天划分为 t 个时间段，并在每个时间段为各个活动分配预算。
在时间段 t 中，购买广告展示的支出与该时间段所提供的展示次数成正比。这一假设基于活动在特定时间段内的单次展示成本保持相对稳定。实际操作时，我们需要选取适当的时间段长度，以便降低每个活动单次展示成本的波动。分析实际数据表明，只要选择合适的时间段长度，这一假设便成立。
因此，对于每个活动，我们为每个时间段 t 分配一个预算比例。这样，我们就能确保广告活动的预算在一天内得到平稳且合理的分配。
(3)
在这里，
s(t) 表示支出的金额，
reqs(t) 表示在时间段 t 内符合广告活动受众定向限制的到来的广告请求数量，
bids(t) 表示该广告活动在时间段 t 内对广告请求的竞标数量，
最后 imps(t) 是广告活动在时间段 t 内的总展示次数，即赢得的拍卖次数。
有了这些定义，我们自然地将竞标数量与广告请求数量之比定义为 pacing rate，将展示次数与竞标数量之比定义为 win_rate。注意，如果我们假设满足特定广告活动受众定向要求的广告请求在所有到来的广告请求中均匀分布，那么可以用一个常数乘以所有到来广告请求的总数来替代 reqs(t)。这个常数可以被方程（3）中的比例所吸收。
为了优化广告投放，我们希望采用一种动态顺序方法，在考虑到上一个时间段的消费反馈后，调整下一个时间段的 pacing rate。这样，我们可以实时优化广告活动的投放效果，确保广告预算在整个投放期间得到合理且高效的利用。通过对比例(3)进行操作，下一个时间段的 pacing rate 可以通过以下简单的递归方程得到：
(4)
在这里，「reqs(t+1)」和「win rate(t+1)」分别表示下一个时间段 t+1 内预测的广告请求数量和预测的赢标率。这些预测可以通过利用历史数据来完成，而关键在于我们关心这些参数与前一个时间段值的比值，而非它们的绝对值。这种递归定义为平稳预算分配引入了一种简单的自适应反馈控制。
在方程（4）中，未来的支出「s(t+1)」被设置为在时间段 t+1 内理想的期望支出「bt+1」相等，以实现预算限制。不同的「bt+1」选择引入了不同的预算分配策略。例如，一种称为均匀分配的简单策略试图在一天内平均消耗预算。这种策略可以通过将「bt+1」定义为「bu(t+1)（u 表示均匀）」来轻松实现。这样，我们可以确保广告预算在整个投放期间得到均匀且合理的分配。
。这种策略可以通过定义「bt+1」为「b u t+1（u表示均匀）」来轻松实现:
在这里，第一个因子代表当天剩余的预算，第二个因子表示时间段 t+1 的长度与当天剩余时间长度的比率。具体来说，L(t) 代表时间段 t 的长度。如果各个时间段的长度相等，那么我们可以简化公式（5），以便在整个投放期间实现均匀的预算分配。这将确保广告预算在投放过程中得到合理且高效的利用，从而实现更好的广告效果。
图2：展示了我们基于绩效的预算控制方法在按千次展示付费的广告活动中的应用。
正如第 2.1 节所讨论的，均匀预算控制策略并不一定是最佳策略。因此，我们提出了一种策略，旨在在广告活动有更高机会获得感兴趣事件（例如点击或转化）的时间段中分配更多预算。为了实现这一目标，我们分析广告活动的历史数据，并评估活动在每个时间段的表现。基于这些评估，我们构建了一个离散概率密度函数，表示点击或转化的概率列表：p0，...，pT。假设一天有 T 个时间段，且概率之和为 1（即 ∑T pt = 1）。
接下来，在每个时间段，我们计算下一个时间段 t+1 的理想支出「bp(t+1)」（其中「p」表示概率）。通过这种方式，我们能够根据广告活动在不同时间段的历史表现来调整预算分配，从而实现更高的广告效果。
与均匀预算控制情况类似，如果时间段长度相等，这个公式也可以简化为
实际操作中，需要注意的是，如果某个时间段的 pj = 0，则广告活动将永远无法在该时间段分配预算，并且无法探索该时段的潜在机会。
为防止这种情况，可以将预算分配给上述两种策略的组合，这样广告活动就始终有机会探索所有可能的机会。
在计算预算控制速率之后，每个广告活动可以将这些信息应用于自适应地选择高质量的广告请求，并调整出价以最大化目标函数。我们将在接下来的子节中详细解释这些步骤。
3.2 高质量广告请求的选择 - 固定CPM广告活动
我们将固定CPM广告活动和动态CPM广告活动分开讨论，因为前者不需要计算出价，而后者则需要。对于始终向RTB交易所提交固定出价c的固定CPM广告活动，目标是在考虑当前时间段预算控制速率的情况下选择一组广告请求进行竞标。由于我们无法预先知道当前收到的广告请求在出价优化过程中是否最终会导致点击或转化事件，因此我们通过使用统计模型来预测其点击率（CTR）或行动转化率（AR）来评估广告请求的实际价值。关于CTR或AR预测的离线训练过程的详细信息，请参见第3.4节。
请注意，为了满足平稳交付限制，我们需要在一定时间内提供一定数量的展示。最小展示数量计算如下：
只有在我们拥有以下情况时，才能达到此展示次数：
同样地，为了获得这么多的竞标机会，我们期望拥有以下情况：
现在，我们将从一组入站广告请求中选择那些具有高点击率或转化率的广告请求进行出价。为此，我们基于每个广告活动的历史数据构建CTR或AR分布的经验直方图qt(x)，其中qt(x)表示在时间段t中被认为具有x的CTR或AR的广告请求数量，例如参见图2。我们的在线算法在时间段t中找到一个阈值τ(t)，以过滤具有低CTR或AR率的qt(x)区域中的广告请求，以实现平滑交付。这样的阈值可以表示为：
在实际应用中，由于点击率（CTR）或行动转化率（AR）的分布qt(x)难以计算，如果qt(x)与当前广告请求的分布相差较大，那么不同时间段的阈值τ(t)可能会出现波动。需要注意的是，qt(x)是基于可能与当前情况不完全相关的历史数据生成的，因此这种不匹配很有可能发生。为了解决这个问题，我们对阈值参数τ(t)的置信区间进行了评估。
我们使用在线自适应方法逐步更新阈值τ(t)的均值µτ(t)和方差σ²τ(t)。在线自适应方法能够根据实时收到的新数据对参数进行动态调整。这种方法可以帮助我们更好地适应广告请求的分布变化，从而使广告投放策略更加有效。
简而言之，我们首先评估了阈值参数τ(t)的置信区间，然后使用在线自适应方法对阈值τ(t)的均值µτ(t)和方差σ²τ(t)进行实时更新。这样做的目的是在实际应用中更好地适应广告请求的分布变化，降低因分布不匹配而导致的投放效果波动。具体来说，在每个时间段t，我们可以使用收集到的数据，通过以下公式更新阈值τ(t)的均值µτ(t)和方差στ(t)
其次，假设阈值参数τ(t)符合高斯分布，我们对τ(t)进行了限制。阈值τ(t)的上限和下限分别可以表示为µτ(t) + γστ(t)/√d和µτ(t) - γστ(t)/√d，其中d是我们查看数据历史记录的天数来进行统计的。关键值γ=1.96提供了95%的置信区间。CTR或AR阈值的上限和下限在每个时间段内都会更新。
将所有内容整合在一起，当广告请求到达系统时，其CTR或AR值首先通过统计模型进行估计。如果预测值大于阈值的上限，则保留此广告请求，并将固定出价v∗提交给实时竞价（RTB）交换。如果预测值小于阈值的下限，则此广告请求将被简单地丢弃，不做进一步处理。如果预测值位于阈值的上限和下限之间，则广告请求将以等于节奏率(t)的概率随机选择。虽然这种方案是近似的，但它确保了满足平稳交付约束，同时在高质量和低质量广告请求的边界上继续进行机会探索。
3.3 高质量广告请求的选择 - 动态CPM广告活动
在dCPM广告活动中，目标是通过动态调整每个进入的广告请求的竞价价格（ci），以较低的成本获得足够数量的高质量展示。为了实现这一目标，首先构建一个竞价直方图，其中c*表示ci的历史平均值，并在时间段t内表示好和坏展示的统计信息。然后，我们根据当前的节奏速率（t）合理调整基础竞价，以满足预算要求。在本段中，我们将重点讨论如何进行调整，以简化讨论，我们以CPA广告活动为例。
节奏速率（t）控制了竞价的频率。然而，如果提交的竞价价格不够高，广告活动可能无法在公开拍卖中赢得展示。相反，如果竞价价格过高，每次行动的成本可能会增加。为了调整竞价价格，我们定义阈值0≤β1≤β2≤1，根据节奏速率（t）的不同区间分为：（a）安全区域：当t≤β1且无交付问题时；（b）关键区域：当β1≤t≤β2且交付正常时；（c）危险区域：当t≥β2时，广告活动难以找到并赢得足够的展示。针对不同情况采取不同策略。
通常，dCPM广告活动的目标是达到或超过CPA目标G（与eCPA相比）。我们使用目标值定义基础竞价价格u_i = AR × G，其中AR是当前广告请求的预测AR。在下一节中，我们将讨论如何估计AR。当广告活动处于关键区域时，我们将提交b_i = u_i作为竞价价格，因为在满足预算要求方面，广告活动表现良好。
告活动位于安全区域的情况，我们可以从第二价格拍卖中学习最佳出价策略。特别地，我们关注我们提交的出价和实际支付的第二价格之间的差异，以便对好的和坏的印象加以区分。如果使用的AR估计算法是一个高质量的分类器，我们可以预期在高质量印象中看到更大的差异。这是因为高质量分类器会为高质量印象生成较高的AR值，从而导致较高的ui值，进而与第二价格之间的差距更大，除非所有竞价者都采用相同或类似的算法。
假设在过去我们提交了b_i作为我们的出价价格，并实际支付了c_i。对于那些产生行动的印象，我们可以计算θ = c_i / b_i，并构建θ的直方图。接着，找到θ为直方图底部1或2百分位的值。在这种情况下，我们建议将b_i = θ * u_i作为出价价格提交。这个策略可能会增加支出，但同时提高表现；然而，因为广告活动处于安全区域，这不是问题。
最后，对于处于危险区域的广告活动，我们需要了解为什么它们会处于此状态。交付不足的主要原因有两个：（i）受众定向约束过于严格，导致没有足够的广告请求可供竞价；（ii）竞价价格过低，以至于我们无法在公开拍卖中获胜。我们无法解决第一个问题，但可以通过提高竞价价格来解决第二个问题。
考虑一个出价价格上限C，实际上由每个RTB交易所设置。我们希望使用参数ρ* ≥ 1来增加出价价格，以便在预预算控制速率大于β2时，参数ρ∗随着预算控制速率的增加而增加。一种建议是线性增加，如下所示：
最终，我们提交^ci = ρ∗ui作为我们的出价价格。请注意，如本小节开头所定义的c∗是ci的历史平均值，并且随着展示次数的市场价值的变化而动态（缓慢）变化。
3.4 CTR和AR的估计
在本文中，我们基于一个假设：我们有一个有效的系统，可以准确地估计点击率（CTR）和行动或转化率（AR）。在本节中，我们将详细描述如何进行AR估计。为了简单起见，并且不损失一般性，我们将重点关注AR。
AR估计在出价优化系统中起着关键作用，原因有以下几点：
估计的AR为每个广告请求提供了质量评估，从而帮助决定采取何种行动。
基本出价价格设定为估计的AR乘以CPA（每次转化成本）目标，这直接影响广告成本。
在文献中有很多关于估计AR的建议。由于转化是罕见的事件，因此对于每个（用户，发布者，广告商）的三元组组合的特征的分层结构常用于平滑和插入没有足够转化事件的叶节点的AR [1, 2, 13, 14, 20]。这种方法通过考虑不同层次的特征组合来实现平滑，从而使AR估计更加稳定和可靠。
另一方面，也有一些研究试图根据用户的行为和兴趣对用户进行聚类，然后在每个用户群集中估计AR，例如，请参见 [4, 9, 16]。这种方法有助于发现具有相似兴趣和行为的用户群体，进而提高AR估计的准确性。
此外，许多标准机器学习方法，例如逻辑回归 [13, 17] 和协同过滤 [15]，被用来结合不同层次或用户群集中的多个AR估计，以生成最终的加权估计。这些方法可以对各种特征进行建模，将其与AR关联起来，并为不同场景下的广告请求提供更精确的AR估计。
总之，AR估计在广告出价优化中起着至关重要的作用。文献中提出了许多不同的方法来估计AR，包括使用特征的分层结构、基于用户兴趣和行为的聚类以及标准的机器学习技术。实际上，每种方法在特定情况下可能都有其优势。因此，研究人员和从业者可以尝试将这些方法结合起来，以提高AR估计的准确性和鲁棒性。
在广告生态系统中，AR估计不仅影响基本出价价格，还有助于评估广告质量和有效性。因此，不断改进AR估计方法对于提高整个在线广告行业的效率至关重要。这需要研究人员和从业者不断尝试新的技术和方法，以便在广告领域实现更精确的估计和更高的收益。
随着大数据技术和人工智能的发展，未来AR估计方法可能会更加强大和精确。利用深度学习、神经网络和其他高级机器学习算法，我们可以挖掘更丰富的用户特征和行为数据，从而实现更精确的AR估计。例如，使用深度神经网络，可以自动学习广告与用户之间的潜在关系，从而更好地预测潜在的转化率。
我们采用了 [13] 中介绍的方法，并在此基础上进行了改进。在这种方法中，我们使用层次结构为每个（用户，发布者，广告商）三元组组合找到广告反馈率（AR）。实际的广告创意是广告商树形层次结构的叶子节点。该层次结构从根节点开始，一层接一层地包含广告商类别、广告商、插入顺序、包、行项目、广告和最后的广告创意。使用历史数据，我们可以通过聚合它们子节点的印象和行动的总数，获得对该节点的AR的原始估计。我们可以为发布者和用户维度使用相同的层次结构和原始估计。
在构建三种层次结构的所有初始原始估计之后，我们使用类似于 [1,2] 中讨论的平滑算法，根据（用户，发布者，广告商）三元组在层次结构树上的相似性和亲密程度来调整不同层次的原始估计。然后，对于每个广告创意，我们在该创意的叶子节点到根节点的路径上运行逻辑回归，以获得该创意的AR估计。这种方法产生了相当准确的估计。
简单来说，该方法使用层次结构来表示广告的各个维度，使用历史数据来估计每个节点的AR。通过对不同层次的估计进行调整，并在树的路径上运行逻辑回归，我们可以得到准确的广告反馈率估计。
图3：我们提出的竞价优化框架中广告请求工作流程的示意图
该图说明了我们提出的竞价优化框架中的广告请求工作流程。在这个过程中，所有传入的广告请求需要经过AR预测模型的估计，以确定其潜在质量。
根据请求的质量和竞价速率，只有高质量请求才会被选中并发送给RTB交易所进行竞价。
竞价优化模块会根据不同的竞价策略和出价，为每个请求优化成本效益。
竞价结果会返回给竞价优化模块，从而决定是否继续进行下一轮竞价或直接投放。
这是一个简单的广告竞价流程，它涵盖了广告请求的评估、筛选、竞价和投放步骤。在此过程中，竞价优化模块起到了重要的作用，通过对竞价策略和出价的调整，以优化广告请求的成本效益。
4 实际问题
本节中，我们讨论了在实现我们提出的竞价优化方法中遇到的几个实际问题，并介绍了我们目前的解决方案。
4.1 冷启动问题
当一个新的广告系列开始时，点击或转化事件需要一些时间才能反馈到系统，因此没有足够的信息来执行CTR或AR估计以及竞价优化。这被称为冷启动问题，在文献中得到了很好的研究，例如[10,12,18]。我们采用类似的思想，应用内容特征，如用户和发布者属性，通过推断现有广告系列之间的相似性，来推荐一些高质量的网站和受众群体。此外，在在线竞价优化过程中，执行基于上下文的contextual-epsilon-greedy策略。如果传入的广告请求位于其中一个推荐的发布者或受众群组内，则会放置更高的出价。否则，广告请求将被随机选择，使用默认出价进行探索未见过的网站和用户。随着广告系列变老并积累更多的数据，在线探索的活动将减少，正常的预测模型将发挥竞价优化的主要作用。
当一个新的广告系列开始时，由于点击或转化事件需要一些时间才能反馈到系统，因此在早期阶段，我们没有足够的信息来执行点击率（CTR）或转化率（AR）估计以及竞价优化。这个问题被称为冷启动问题，在学术文献中已经得到了广泛的研究，例如文献[10,12,18]。为了解决这个问题，我们借鉴了类似的方法，通过利用内容特征，例如用户和发布者属性，以及在现有广告系列之间推断相似性，来向广告商推荐一些高质量的网站和目标受众。
此外，在在线竞价优化过程中，我们执行基于上下文的contextual-epsilon-greedy策略。当传入的广告请求与我们推荐的发布者或目标受众群体相匹配时，我们会放置较高的出价。如果广告请求与推荐的发布者或受众群体不匹配，我们将随机选择广告请求并使用默认出价来探索尚未接触过的网站和用户。
随着广告系列的进行，积累的数据逐渐增多，我们可以逐步减少在线探索的活动，转而让正常的预测模型发挥竞价优化的主要作用。这样一来，广告系列的效果将随着时间的推移而逐步改善，最终实现更精确的目标受众定位和竞价优化。
4.2 预防预算过度消费
由于预算消耗受到节奏速率的控制，当广告请求突然激增时，整体的每日支出可能会超过分配的每日预算B。为了解决这个问题，我们实施了一系列监控程序，以定期检查整体每日预算支出以及每个时间段t内的支出。如果整体支出超过了每日预算B，广告系列将被完全暂停。如果某个时间段的支出超过了bt + δ（其中δ是允许的误差范围），竞价活动将被暂停，直到进入下一个时间段t + 1。
4.3 分布式架构
图3展示了简化的单独广告请求处理算法流程图。值得注意的是，提交竞价的整个工作流需要在不到50毫秒的时间内完成。为了实现这一目标，我们在多个分布式计算集群上实现并行化处理，以便在不同数据中心快速处理近百万的广告请求。因此，整个竞价优化过程在许多分布式计算集群上得以实现和并行化。
离线训练过程利用了诸如 R、Pig 等分布式计算技术。在线竞价优化则使用了实时计算引擎，如 Storm 和 Samza。此外，为了获得更广泛的覆盖，我们还将广告请求发送到多个不同的实时竞价（RTB）交易所。
通过这种分布式架构，我们确保了广告竞价过程的高效和稳定性，同时还能够在短时间内处理大量广告请求。这有助于提高广告投放的准确性和整体竞价策略的有效性，从而使广告主能够在有限的预算内获得更好的投资回报。
表1：CTR改进了七个精选的CPM广告系列。
图4：均匀预算支出的模拟结果。x轴表示时间段，y轴表示总预算支出。蓝线描绘了理想的均匀支出，红线描绘了我们均匀预算节奏的实际支出。
我们使用 Hadoop 生成分层的点击率（CTR）和转化率（AR）估计值，同时训练大量活动的活动特定预测模型。在线过程将传入的广告请求流式传输到多个服务器，并通过实时消息总线计算出价价格。在这个分布式环境中，我们提出的算法表现优异，详细的实验结果将在下一节中展示。
5 实验结果
我们提出的出价优化框架已经在 Turn 中实现，测试并部署。Turn 是互联网广告行业的领先 DSP（Demand-Side Platforms）。在本节中，我们将展示阶段环境中的模拟结果，以比较不同的预算节奏策略。此外，我们还展示了实际活动的结果，这些活动每天提供大量的曝光，以展示成本每点击（CPC）或成本每行动（CPA）绩效指标的整体改进。
5.1 节奏策略比较
在本节中，我们将展示我们在分级环境中的预算节奏的仿真结果，以验证我们提出的出价优化框架不会违反在公式1中指定的预算约束，即不会过度或不足地预算。对于仿真实验，我们启动一个平坦的CPM伪活动并分配一定量的日预算。在每个时间段中随机生成一组广告请求。然后，仿真服务器根据节奏率生成出价，并将获胜曝光记录在数据库中
图4显示了理想的均匀支出和使用我们在公式6中的均匀节奏策略的实际支出。可以看到，这两条线非常接近，所有时间段的平均差异为0.56美元，相对于日预算而言，误差不到1％。图6展示了基于相对性能（如图5所示）使用公式8中的基于性能的节奏策略的理想花费和实际花费，实际支出曲线确实遵循理想的支出曲线，平均差异为0.17美元，这是每日预算的约2.3％的误差。
图5 展示了不同时间段之间的相对表现。横轴表示时间段，纵轴表示相对表现，以1/ECPA为单位衡量。
图6：基于表现分布的预算支出模拟结果。X轴代表时间段，Y轴代表总预算支出。蓝线描绘了基于表现分布的理想支出，红线描绘了基于表现的预算节奏的实际支出。
5.2 实际活动表现评估
在本节中，我们评估整个出价优化框架在我们系统中的两个主要类别活动：平坦CPM活动和动态CPM活动。对于平坦CPM活动的评估，使用CTR指标，较高的比率代表较好的表现。对于动态CPM活动的评估，则使用CPC和CPA指标，因为这些指标考虑了印象总成本和点击和转化的总数。CPC和CPA指标的较低值代表较好的表现。
我们首先报告了七个活跃的平坦CPM活动的表现改进，这些活动随机地选择了不同广告商类别。这七个活动是基于我们提出的方法和现有的基线方法运行的。每种方法运行一周，最终收集了两周的性能比较数据。我们的基线方法是一种简单的自适应反馈控制算法，根据时隙t中的节奏率乘以当前CTR τ（t）的阈值的常数因子。表1中的前两行分别代表我们提出的方法和基线方法的CTR表现。第三行显示了每个个体活动的改进百分比。我们提出的方法平均实现了123％的性能提升。
接下来，我们想报告动态CPM活动的表现改进。在这次评估中，我们试图将我们的提议方法与仅应用节奏率以均匀地选择传入广告请求而不进一步调整出价的现有基线方法进行比较。两组基于目标类型（CPC和CPA）的活动在不同的广告商类别中随机选择。表2和表3显示了每个个体活动的CPC和CPA值以及表现提升的百分比。我们可以观察到，运行在我们提议框架上的所有二十个选定的活动在CPC和CPA指标方面表现更好，CPC活动的平均表现提升为19.02％，CPA活动的平均表现提升为30.87％。
表2：选定的十个动态CPM广告活动的CPC改进。
表3：选定的十个动态CPM广告活动的CPA改进。
结论
我们提出了一种通用且简易的方法，用于实时优化广告投放出价，同时满足预算和平滑交付限制。由于算法简单高效，目前我们的实现可以处理每秒高达一百万个广告请求，并有潜力进一步扩展。实验评估表明，我们的算法在每点击成本(CPC)和每次操作成本(CPA)等关键性能指标上取得了显著改进，同时避免了预算超支或不足的问题。未来，我们希望将实时分析的能力集成到横跨更多用户、发布者和广告商属性的在线优化中 |
|
发表于 2023-4-10 07:20:43
