注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

计算广告学-合约广告系统-在线分配问题  

2013-02-15 22:31:33|  分类: 计算广告学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

合约广告系统

原作者:刘鹏 @北冥乘海生

编辑:Koala++/屈伟

视频课程:师徒网

推荐拙译:在线分配问题的High Water Mark算法论文。

在线分配(Online Allocation)问题

在线分配问题

       前面提到过广告是三方博弈,用户,广告主,媒体之间的博弈,而推荐系统是用户与媒体的博弈。它们之间的区别其一是广告主通媒体reach用户是有量的需求的,推荐系统是自己把内容推给用户,不见得有明显的量的需求。广告的量的需求体现在两个方面,一种是我前面提到的GD广告系统,有量的下限的需求,或者说有固定流量的需求,二是Non- Guaranteed delivery,即非合约方式,它有一种上限的限制,它受到广告预算的受限。所以在线分配问题的核心是:在量的某种类型的限制下,完成对质的优化。

我下面列出的是google的做法,可以将在线分配问题看成是二部图匹配的问题,二部图一边是广告结点,另一边是在线到达的页面和用户。

计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog

 

注意广告中的a, u, c三个要素都在这出现了。将contextuser根据audience targeting分成不同的segment,每一个segment是要分配给不同的合约,要分配多少的比例,这就是allocation的问题。广告的分配与通用的二部图匹配有什么不同呢?因为广告是一个实时系统,不能离线地计算匹配问题。实时的在线分配问题在理论界和工程界都进行了大量的探讨,产生了大量的算法,读者没有必要把这些算法都理解清楚,重要的是深刻理解在线分配的问题,并结合自己的问题设计自己的算法。

因为有量的限制,它是一个constrained optimization(受限优化)的问题,最早google提出的是AdWords Problem

计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog

 

 

简单解释一下,先看目标函数,bia是把一次展示(Impressioni)分给一个(Ad, a)产生的收益(bid * ctr, b,即ecpm),xia是指一次展示(impression, i)是否分给了一个广告(Ad, a),这个值只能为0或是1,因为一次展示只能或是分配给一个广告,或是没分配。sum(i, a)也就是整个系统的收益,max sum(i,a)即是优化的核心问题:如何最大化整个系统的收益。它的限制是:对每个广告商来讲,有一个budget,每个广告商所消耗的资金应该小于他的budget,即式中Ba

后来研究者把这个问题推广到display problemdisplay problem中有很多CPMcampaign,它希望优化的是每一个CPM的效果。

计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog

效果即是它收获到的点击量,点击量的计算方法为把所有的展示的Xia乘上点击率起来就是点击量。优化目标有两个constrain,一个是称之为Demand Constrain,它是指每一个广告商来讲,他需要Ca次展示,那么媒体提供的展示数应该小于等于Ca,注意这里是NGD的问题,广告系统提供的展示次数可以小于需求的量,另一个ConstrainSupply Constrain,是对于任何展示,xia加起来小于等于1,可以小于是因为这次广告也可以不分配给任何广告,它可以交给下游的其它变现手段。上面所讲的就是Allocation描述成Constrained Optimization的形式。需要注意的是大家不要纠结于到底是Display problem还是Adwords problem,因为这些问题在框架上看都是一样的,都是linear programming的问题。

       Maximally Representative allocationMRA)是另一个准则,它反映了定向广告的一些本质的市场需求。比如一个广告主买了加州的用户的流量,那个广告主实际有一个隐含的需求,他希望得到的是按自然分布的加州的用户流量。即比如不能全给广告主男性用户的流量。如果我们仅按上面的公式进行优化,会有一定的问题,比如一个广告主出高价买走了所有加州女性的用户,那其它广告主得到的流量就只能是男性用户的流量了,虽然流量还是符合用户的要求,这也就不符合广告主的本源商业需求了。所以MRA会在Objective上做一些加工,使它既优化量,又在一定程度上接近流量在一定程序上接近人群的真实分布。

拉格朗日方法

       拉格朗日方式是在解受限优化中比较通用的一种方法。原问题是由下面几个部分组成:一个目标函数f(x),一组小于0的不等式Constrain g(x),一组等于0Constrain h(x)。(注:大于0的,可以加负号把它变成小于0的)。

计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog

     这里只对拉格朗日做简单的介绍,先用原问题构造拉格朗日函数,拉格朗日是x, lamda, mu的函数。它是把g(x)h(x)分别加上lamdamu系数放到原问题后面。

计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog

拉格朗日会产生一个对偶函数,对偶函数是对L求它的下确界(或者说最小值),对x求最小值,就将x消掉。 

计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog 

对偶问题是在lamdamu上求它的最小值。

计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog

       这个方法的几何意义是比较清楚的,下图来自于wiki

计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog

 

目标函数是f(x,y)的最小值,它的等高线是图中的两个圈f(x,y)=d­1f(x,y)=d2Constraing(x,y)=c。思考一下即可以得出,要满足g(x,y)=c的约束,f(x,y)最小值一定是在曲线与等高线相切的位置,找相切的问题就是找下确界,一般用导数等于0的方式找。

       在凸优化情形下KKT条件是一定满足的,而非凸优化也可能会满足KKT条件。

在线随机分配算法

       如前面所讲,把原问题中的Supply ConstrainDemand Constrain用拉格朗日方法得到一个对偶问题,对每一个a产生一个Betaa,对每一个i产生一个zi,去解这样一个对偶问题,Betaazi就对应Supply ConstrainDemand Constrain

       具体的算法步骤如下:

?      对每个a, 初始化对偶变量βa0

?      当展示i在线到达时, 将其分配给a’以最大化μ­ia – βa

?      xia’= 1. 如果a’已经得到Ca’次展示, i为使得此值最小的展示, xia’= 0

?      在对偶问题中, ziia’a’ , 并按照一定规则更新βa’ , 不同更新规则对应了不同的算法

通过这种方式,它构造出一种在线随机分配的算法,对每个at初始化对偶变量Betaa0,我们可以认为Betaa的物理意义是这个广告a已经收获的点击量,比如要优化一个广告商的点击数,他已经收获的Impression里有多少点击。当每次展示i到达时,要分配某个广告a的物理意义是很直接的,分配的准则是这次展示i对广告a的点击率减去它收获的平均点击率Betaa,选择差值最大的a,意义就是选择这次展示会给广告最大提升的广告。问题的关键是每一步如何去更新Betaa,不同的Betaa对应了不同的在线分配算法,这些算法研究关注点是:在线分配的算法与离线分配的算法相比,在线分配的算法不要比离线分配的算法差的太远,尽可能接近,离线分配算法是指将一天的展示收集后批量分析的方式。

Betaa更新策略

策略

算法

有效性

Greedy

对每个a, βa是分配给a的前Ca个高权重展示中最低的权重, 也即a接受一个新的展示需要抛弃的权重

1/2 competitive

Uniform Weighting

对每个a, βa是分配给a的前Ca个高权重展示的权重的算术平均. 如果分配给a的展示少于Ca, βa是这些展示总权重与Ca的比.

1/2 competitive

Exponential Weighting

对每个a, βa是分配给a的前Ca个高权重展示的权重的指数加权。即:设μ1 μ2μCa,则:

Ca对每个a 都充分大时为(1 ? 1/e) competitive

       请大家对上面算法的公式不必太认真,因为这些讨论主要是理论的讨论。它们主要是解决对流量没有任何先验知识的情况下,通过一定的策略,可以达到最优的程度,但这和真实的问题差别比较大,因为实际情况中,我们一定对流量是有一定的预知能力的,比如,流量有会有多少,男性用户比例如何等等。前面的讨论是在没有流量预测做指导的情况下的处理,而实际中是一定有流量预测做指导的。另一方面,最重要的一点,在线决策时是要避免存储xia,前面的讨论中,广告主a需要Ca次展示,哪些展示分配给了广告主a都要保存下来,这样空间复杂度很高,这种方法似乎实现不了,只是理论性的讨论。

流量预测指导下的GD在线分配

       下面要讲的算法是High Water Mark算法,是Yahoo!实际系统中用的方法,它分两个阶段,离线计划阶段和在线分配阶段。

离线计划:

l  令每个人群维度组合k的剩余supply(rk)等于预测量(sk)rk = sk

l  对于每个合约j,按照分配优先级对每个a

l  解下式得到其serving rate αa:计算广告学-合约广告系统-在线分配问题 - quweiprotoss - Koala++s blog 

如果无解,则令αa=1

l  对Γ(a)中的每个k, rk = rk min{rk, skαa}

在线阶段:

l  对在线到来的某个impression, A = {a1, a2, …, a|A|}为按照分配优先级排序的所有满足要求的广告

l  按照A中的每个广告的serving rate随机分配其展示机会。

这种算法的好处是各个它是一个概率的算法,各个ad server之间可以没有通信,每个广告只需要保存αa,而前面的算法每一个Impression到达都要更新βa,换言之,serving是有状态的,每次impression都要改变状态。线上有很多ad server,要同步它们的状态是比较麻烦的。而HWM因为它是离线分析的,所以它需要尽快更新alphaa,在几个小时更新alphaaHWM在算法角度上不如前面的算法完美,它是一个简化的版本,但它在工程中比较实用。

Yahoo! GD广告

       Yahoo! Advertising Solutions首要运行的是GD广告,GD市场广告主数据为几千,年收入为Boillion量级。GD无法分配的流量转接到NGDnon-guaranteed delivery,即Rightmedia exchange)。

       它是通过compact allocation plan完成线上决策,提供下列受众定向:地域,人口属性,行为(较为粗浅,常用的仅有几十个分类)。合约式销售中,品牌广告主对曝光往往有独占要求,这与竞价广告系统完全不同,比如京东,在投品牌广告的时候,合约里会签定不能出类似的电商广告,比如苏宁易购的广告。

 

  评论这张
 
阅读(6630)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017