技术博客|第8期:广告流量匹配算法在Hulu/Disney Streaming平台的实战

2022年第008篇

订单优先级

保量广告订单按照订单类型、单价、广告主的不同会被切分为从高到低不少于十个优先级。当流量不足以满足所有订单目标需求的情况下，需要首先保证高优先级的订单可以满足投放需求。订单优先级也不是固定不变的，商业团队的一部分人会根据多种因素实时调整订单的优先级。

提前投放

严格来说，这并不是一个业务需求，只是为了避免流量波动对保量投放造成影响的解决方案，但是这个方案普遍存在于保量广告的业务场景，以至于不少订单直接设置了这个需求。

这个需求的出发点来自于：最理想情况下，每一个广告订单都是严格匀速投放的。但是订单售卖情况和实时的流量大小都存在随机的上下波动，在订单售卖率较低或者流量向上波动的时期如果严格保证每个订单的匀速投放，势必有一些流量没有投放任何广告，造成浪费。

因此允许订单在前期多投放一些，可以有效避免后期流量紧张的时候无法完成投放目标，这种前期多投后期少投的表现被称为提前投放（frontload)。但是提前投放并不是理想的均匀投放，需要设置一个可以接受的范围，一个订单真实的投放结果落在这个可接受的范围内都是合理的，其目标是保证尽量多的订单完成投放。

动态投放限制

在广告投放系统中普遍存在如下的规则：相邻广告位不能出现多于一个来自于同一行业的广告；同一用户在任意一周的时间窗口内，不能投放超过两次来自于某一品牌的广告；一个视频流的全部广告中，来自同一个订单的广告不能超过三次；一些剧集上不能或投放指定行业或品牌的广告。这些规则可以保护用户观看视频内容的体验和广告主的效果，但是对构建学术论文中频频出现的二部图带来巨大挑战，尤其是想要在广告开始投放之前预先构建二部图。

不完全保量订单

系统中存在一些优先级和单价都较低的一类不完全保量订单，这些订单允许没有完成投放目标，但是不允许过快投放或者过早完成投放目标。投放这些订单时的目标主要是提高流量利用率，并且在允许范围内尽量优先选择单价较高的订单投放，提高这部分流量的价值。

图1：流量分配算法在广告投放系统的实践

系统中存在的理想投放曲线有两条，一条对应匀速投放的行为，一条对应提前投放的行为。投放曲线表达的是在某时刻（横轴），某个广告订单的累积投放数量（纵轴），横纵两个坐标轴都归一化到0-1之间。为了避免引入过度的复杂性，首先假设流量在时间轴上的分布是均匀的。匀速投放曲线在这种情况下就是斜率为1的对角线。提前投放曲线的选取应该满足如下的几个原则：

• 曲线的初始斜率是1+θ，其中θ是一个可以配置的比例，代表提前投放曲线在开始阶段可以超过匀速投放速度的倍率。

• 曲线的斜率随时间推进逐渐下降，并且最终停在横纵坐标都为1的点，代表在订单截止时间订单的投放数量刚好达到100%

我们选择如下微分方程的解作为提前投放的理想曲线：

其含义是在时刻t，累积投放量x，此时的投放速度是该点到终点直线斜率的1+θ(1-t)倍。这个微分方程的解是：

这就是我们选择的提前投放曲线形式。

实际情况中，流量在时间轴上的分布肯定是不均匀的，订单也可以包含某段时间不投放的规则。这种情况下，我们把曲线横轴的含义改成截止到某时刻，该订单的累积流量占总流量的比例。这样我们之前选定的曲线就可以在真实情况下代表我们预期的含义。

下图展示了匀速曲线和θ=0.2的提前投放曲线

图2：匀速投放曲线和提前投放曲线

选择系数的计算遵循一个负反馈的原则：当实际投放曲线超过理想曲线的时候，减小选择系数；当实际投放曲线不及理想曲线的时候，增大选择系数。PID（proportional-integral-derivative）控制器是一种经典的负反馈控制器：我们以x(t)，y(t)分别代表理想曲线和实际曲线，c(t)代表选择系数，则

上面公式等号右边的三项分别称作比例项、微分项、积分项，kp, kd, ki是三个可以调节的参数。PID控制器的积分项通常用来控制待控制信号的积分等于预期信号的积分，我们把广告的累积投放当作待控制信号，并不需要控制其积分项，我们最终选择删除这一项，减小复杂度。

另外我们希望选择系数的含义大致是选择概率本身，不希望这个数有可能取到负值，因此我们使用选择系数的对数作为控制变量，得到系数的负反馈计算逻辑

这里kp, kd是两个待定的系数，系数的大小会影响控制器的收敛速度和震荡幅度，所以需要选择合适的kp, kd。常见的做法是通过重复模拟实验得到经验上的取值但需要耗费大量时间调参，这里我们通过对一个简化的系统建模进行分析直接得到理论上这两个系数的取值。

系统建模选择最简单的场景：整个系统只有一个订单，选择系数c就是这个订单的选择概率，这个订单的总流量是 I (>1)，理想曲线 x(t)=t, 0 ≤ t ≤ 1。订单在时刻 t 的投放速度就是cI，即

记 δ = y-x，有

我们的PID控制方程

就可以转化为：

当δ→0，δ ̇→0时，上式可化简为二阶线性动力方程

这个方程在临界阻尼条件下达到比较理想的收敛效果，此时两个系数的设置符合条件

ω是系统固有震荡的圆频率。实践中，我们设置系统的固有震荡周期为12个小时，这个参数设置在真实系统上得到了验证。下图展示了理论上不同阻尼条件下单订单系统的策略收敛性

图3：不同阻尼状态的收敛性质

选择概率主要依据每个广告的两个选择系数进行计算，是流量分配算法实践上唯一的在线计算逻辑，这个计算逻辑的设计需要符合业务场景的需求，并且要基本符合二部图理论分析中在线计算逻辑的原则。下面罗列一下选择概率计算逻辑的各方面要求：

• 这个模块的输入是一列符合定向需求的广告，每个广告有优先级、订单类型等元数据，也有两个选择系数（后面我们分别称它们为系数c和上系数u）

• 系数和上系数的含义是选择概率，保证订单的投放不超过指定的曲线范围就是要保证订单的选择概率不超过两个系数规定的概率范围

• 根据二部图理论，当选择系数的和比较大的时候，一部分订单的选择概率缩减至小于其系数的值，甚至可以缩减为0

• 不完全保量订单只有不允许超投的需求，没有保证完成投放的需求，因此其选择概率计算应该仅仅根据上系数计算，不应该考虑系数

感兴趣的读者可以先自己思考一下选择概率的具体计算逻辑，根据我们的经验，线上选择概率计算逻辑有很多可以灵活处理的地方，可以满足业务需求的选择概率计算算法可能多种多样。下面总结了我们系统里这个算法的几个关键点，再举出几个具体的例子帮助读者理解。

• 选择概率的计算过程就是给每个广告分配概率的过程，初始每个广告的选择概率都是0，然后做两轮概率分配，第一轮按照系数分配，第二轮按照上系数分配，直到把100%的选择概率分配完或者第二轮分配完成。如果订单的系数和大于1，概率分配会在第一轮停止，高优先级的订单会率先分配等于其系数的概率，直到某一优先级的广告按系数分配剩余的概率，优先级更低的广告的选择概率被缩减到0。如果所有广告上系数的和小于1，所有广告都会分配等于其上系数的概率，剩余概率这个广告位会出现空选的情况。

• 不完全保量订单的概率分配遵循按单价从高到低的顺序依次给这些订单分配等于其上系数的概率，直到剩余概率为0或者所有广告的概率分配完毕。

下面是几个具体的例子，例子里圆圈代表广告订单，c、u分别代表选择系数和上系数，p是选择概率的计算结果

例1：只按选择系数进行一轮概率分配

在这个例子里，高优先级的订单首先按照选择系数分配0.4的投放概率，剩余0.6的选择概率不够剩余两个低优先级订单按照它们的选择系数进行分配，这时按照选择系数的比例把0.6的选择概率分配给这两个订单。

例2：按选择系数和上系数进行两轮概率分配

三个订单在第一轮概率分配中按照各自的选择系数分配到了0.2的选择概率，剩余0.4的选择概率在第二轮按照上系数进行分配。第二轮分配首先把高优先级订单的选择概率提升至上系数0.3，再把两个低优先级订单的选择系数分别提升至各自的上系数。

例3：不完全保量订单选择概率计算

这三个不完全保量订单已经按照单位价格进行了排序，首先给单价最高的两个订单分配0.4，0.5的选择概率，剩余0.1的选择概率小于第三个订单的上系数，则全部分配给第三个订单。

我们在Disney Streaming业务场景下实战流量分配算法的方式是把整个方案拆解为三个部分：

1）计算理想投放曲线；

2）计算选择系数；

3）计算选择概率。

这三个部分的算法会根据业务需求做出具体的设计，我们这里举出的几个例子，是设计这篇博客里的解决方案最重要的需求。真实业务场景中，还有其他同样非常重要，需要特别设计解决方案的需求。比如不可预测的洪峰流量，博客中的方案在这种场景会出现瞬时投放过多的表现，不符合匀速投放的需求。为了解决这个问题，我们对短时间内每个广告的选择次数进行了计数，在选择次数过多的时候停止继续选择这个广告。

表面上看我们实践中的算法和《经典广告流量匹配算法》给出的算法非常不同，但是我们这套实践算法的设计思路还是尽量寻找同时符合经典理论和现实需求的算法逻辑，从这套实践算法也可以看出一个经典算法在面对真实场景的业务需求时，常常并不能直接生搬硬套，而是需要结合实际进行改造，这也正是算法工作有趣的地方所在。

Dingming Wu，广告智能团队首席算法研究员。

北京广告智能团队的使命是通过使用数据和AI技术，在电视和流媒体上优化广告业务并革新广告平台。我们构建各种解决方案以衡量和优化广告生命周期的各个环节。我们是一支强大的跨职能团队，致力于提供端到端解决方案，涵盖了从机器学习，大数据，微服务到数据应用等各方面技术领域。

职位信息: 职位列表链接

感兴趣的同学发送简历至：bjindustry@disney.com

（烦请标注申请职位+姓名）