【计算广告】在线分配算法之 —— HWM(High water mark)介绍

2024-05-24 21:18

本文主要是介绍【计算广告】在线分配算法之 —— HWM(High water mark)介绍,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

该算法是雅虎工程师提出的一个解决合约制广告或者说GD(担保式投放)投放系统在线分配问题的贪心算法,思路很直接,下面是本人对照其论文整理的思路,里面有自己的理解。

论文题目:Ad Serving Using a Compact Allocation Plan

google一下即可得到。

===========================================================================================

摘要:

在线广告有很大一部分是通过担保式合约来售卖的。这类广告的特点是:广告系统要保证广告主要求的定向条件的曝光量,有时间限制,超过时间没有完成可能会赔偿。这对广告系统意味着,当一次曝光机会到来时,可能会有多个广告主的单子满足曝光要求,广告系统需要决定这次曝光该展示哪一个合约,并且保证其他所有合约也完成。这个问题有两个挑战:(1)问题的数量级,可能会有百万级别的广告主合约和百万级别的流量;(2)不可预见性,合约通常是提前签订,因此需要预估流量。同时在分配流量时,也无法得知当天总流量的分布。我们这里提出了一种对担保式投放系统的分配方案。
我们提出了一个结局担保式投放系统分配问题的解决方案。分配方案离线计算,可以被广告投放系统有效使用。每一个合约的分配方案只需要O(1)空间。整个分配算法是无状态,可以方便地在分布式系统中使用。

简介:

GD(Guarantee delivery,担保式投送)广告投放系统中的核心问题是匹配supply和demand。当用户展示发生时,广告服务器需要在秒级延迟下选择出合适的合约,使得所有的合约都被满足。这是第一需求,也是核心需求。与此同时,还有很多次级需求,比如平滑,即广告不能在一瞬间展示完,应该均匀分布在合约期内。这个问题的难点在于一个是计算量很大,另一个是在做online决策时,并不知道这一刻流量的整体分布,只能基于历史数据做预测。
先看两种比较直观的思路:一种是基于完成度,一种是基于服务率。
完成度:广告服务器在选择合约时是基于每一个合约的历史展示情况来决定的。比如,如果来一个展示,有两个合约满足,一个合约马上就完成了,另一个还差很多,那么肯定优先展示差很多的那个,即按照完成率来定。这个思路很简单,但是会有一些问题:第一,这里需要给出完成度的确切定义,什么样的合约是快完成了,什么样的合约是还差很多。可能最直观的定义是,每一个合约都均匀显示在合约期内,比如30天展示30万次的合约,那么每天需要展示1万次。这可以让展示非常平滑,但是却忽略了一个事实,即实际的流量是变化的,工作日的流量会少于周末,晚上的流量会少于白天的。而且每一天都可能发生定向的流量骤降的情况,这就需要算法能够动态调整展示的概率。第二,由于需要记录每一个合约的完成度,整个系统是有状态的,这对于分布式系统有一些挑战,但是不是不可解,通过消息队列来处理曝光打点可以解决。
服务率:这种方案不需要考虑每一订单的完成度,而是离线计算出每一个订单的服务率。每来一个展示,就把符合条件的合约按照概率展示即可。这种方案的问题在于:第一,计算服务率肯定是需要流量预测的,那么对预测的准确性要求很高;第二,整个计算的过程是一个分配求解的过程,求解的规模很大。
那么,这里我们提出了一个结合上述两种思路的two-step的解决方案——HWM。第一,我们引入了一个离线计算分配方案的轻量级算法,分配方案是无状态的且是基于服务率的。第二我们提出了一个反馈模型,可以根据最近的历史数据来调整流量预测带来的误差。


问题定义:


图一
考虑上图的例子。有三个广告主的合约和六个流量节点。每一个都被标注了定向条件。如果每一个流量符合某一个合约,那么他们之间会有一条线相连。对于200k{male}的demand,我们可以把{male,ca,age=5}的100k流量给他,那么200k{ca}的demand就无法满足了,除非我们只把{male,ca,age=5}的100k流量给{ca}的demand。这里我们其实已经感受到了分配问题的含义。再强调一下现实问题中的挑战,每一个demand和supply的节点都成百万,而且标签的数目也相当大,远比这个例子复杂得多。
设I是预测的supply集合,J是合约集合。那么分配问题可以定义成一个二部图G。图中任一边e代表流量满足合约j。每一个supply节点被si标记,代表该节点的展示量,同理每一个demand节点被dj标记,代表合约约定的展示量。那么解决这个分配问题其实是找到xij,xij表示每一个supply节点i分配给合约j的占比。xij必须满足:


图二
另外,虽然不是强制,但是上述问题最好能考虑到平滑特性。
整体架构:

图三
离线部分,输入流量预测和合约,生成分配方案。在线部分根据分配方案来决定展示哪一个合约。离线部分,当然可以去解之前的分配方案,得到每一个xij,很直接。但是在在线部分,就需要把整个二部图载入内存,代价很大(xij意味着所有的边都需要载入)。所以关键点就是得到xij,但是不需要存储。我们的方案是通过一个aj来代替xij。aj代表每一个符合条件的supply展示合约j的概率。所有符合条件的supply节点的aj都是相同的。数学依据在另一篇论文。这样的方案,在线模块就只需要加载合约以及每一个合约的aj值即可。

算法:

HWM的离线算法会生成每一个合约的服务率,服务率的大小取决于合约的紧急程度。算法会把每一个demand连同符合条件的supply标记。设对于合约j,所有满足条件的supply节点的流量和为Sj,然后按照Sj/dj升序排序(原文是按照Sj排序,在另一篇论文里是按照Sj/dj排序,个人认为后者更合理,具体见附录),这个值越小,意味着这个合约优先级越展示。按照这个值对合约升序排序,得到一个叫allocation order的排序结果。接着计算服务率,算法如下:


图四
第一步:设ri为每一个supply节点的剩余流量,si为预测流量,那么最开始,ri=si;
第二步:对于所有的合约j,先按照allocation order排序,再求解aj。这个式子的含义是,把所有合约j满足的supply节点拿出来,对每一个supply节点都求出min{ri,si*aj}值,然后求和,使得和等于dj。如果没有解,那么aj=1;再更新每一个ri。
这个式子什么含义呢?
aj代表合约应该被展示的概率,si*aj代表supply节点i应该给合约j的量,但是可能这时i节点已经没有这么多量了,这时i节点应该给j的量就是ri,所以对每一个节点i,取的是最小值。对所有符合条件的节点i都求出展示量并且求和,就是节点j可以得到的展示量,这个值应该等于合约量dj。至此,一个合约的aj求出来了,然后再更新supply的ri值。下一次迭代。
现在来直观地理解一下这个算法:首先按照allocation order排序,那么最紧急的合约已经被排到了第一位。然后根据Sj/dj算出aj。aj表示你每一个服务条件的supply节点给我的量的比例。因为这是第一个demand点,所以不存在流量不够的情况。那么对于后面的demand节点,就可能存在某些supply节点量不够的情况,这时只能用ri代替,那么其他节点就需要多出量,所以这时得到的aj肯定是大于Sj/dj的。当然也可能所有的supply节点都不够,那么就把aj设为1。

图五

看上面的例子,排序结果是2-1-3。先算2,a2=200/200 = 1,更新第三个supply节点的ri=0;再算1,由于第三个节点ri=0,所以只能用前两个节点,a1=200/800 = 1/4;a3留给读者。
至此离线算法结束,我们已经为每一个合约都赋予了一个服务率aj。
下面是在线部分。
第一步:给定一个展示i,设J={c1,c2,。。。,c|J|}为所有符合条件的合约集合,并且按照allocation order升序排序;
第二步:设l是[1, |J|]中的最大值,A = a1+...al <= 1,但是a1+...a(l+1) > 1,那么令a(l+1) = 1 - A;
第三步:对于1 <= j <= l,每一个合约j的服务率就是aj,而j=l+1的服务率是上面计算得到的a(l+1)。然后按照这个服务率作为这些合约的概率,从中选出此次展示的合约。
注意,这里假设是aj求和大于1的情况,如果小于1,则意味着有些流量是浪费的。
看之前的例子:
如果展示{CA,age=5}到达,那么l=1,则合约1总是被选中;
如果展示{Male,age=5}到达,那么l=2,1/4的概率分给合约1,5/8的概率分给合约3,1/8的流量会不会被分配。这些流量可以被其他变现途径利用。
至此,HWM算法就介绍结束了。原文的评估部分没有继续探讨了,有兴趣的可以自行查阅。

小结:

GD系统的挑战:
1.计算量大;
2.依赖预测的准确性;
HWM的思路:
1.2-step;
2.用aj代替了xij,较少内存消耗;

附录:这是另一篇shale算法论文中对HWM的描述,其中allocation order的一句被定义为Sj/dj,与本文不同,个人认为shale论文的定义更合理。

这篇关于【计算广告】在线分配算法之 —— HWM(High water mark)介绍的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/999552

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

电力系统中的A类在线监测装置—APView400

随着电力系统的日益复杂和人们对电能质量要求的提高,电能质量在线监测装置在电力系统中得到广泛应用。目前,市场上的在线监测装置主要分为A类和B类两种类型,A类和B类在线监测装置主要区别在于应用场景、技术参数、通讯协议和扩展性。选择时应根据实际需求和应用场景综合考虑,并定期维护和校准。电能质量在线监测装置是用于实时监测电力系统中的电能质量参数的设备。 APView400电能质量A类在线监测装置以其多核

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO