论文A Practical Framework of Conversion Rate Prediction for Online Display Advertising

定期更新,获取更多,欢迎star

一、论文基本描述。

本论文基于Yahoo! BrightRoll (Oath)雅虎的RTB(视频)买方平台(DSP)。 由于CPA成为主流出价方式,所以转化率预估变成了关键的问题。

难点:

  1. 转化数据非常稀疏。(extremely sparse conversions)
  2. 数据延迟回传。(delay feedback)
  3. 和第三方平台归因差异。(attribution gaps between the platform and the third party)

过度预估导致的过度出价是CPA广告在真实RTB环境下的核心挑战。(we first show that over-prediction and the resulted over-bidding are fundamental challenges for CPA campaigns in a real RTB environment)

本文提出了一个安全预测框架,其中包含归因调整【基于PC的场景】,以及处理过度预测并进一步缓解不同级别的过度竞价。

二、评价指标。

eCPA: effective cost per action or acquisition.[每次操作和获取的有效成本]

eCPA=sum(cost)/sum(action)eCPA=sum(cost)/sum(action) :表示的广告主实际为每个转化库存花费的成本。

eCPC=λ∗Gcpc∗sum(pCTR)/sum(CTR)(0<λ<1)eCPC=λ∗Gcpc​∗sum(pCTR)/sum(CTR)(0<λ<1)

eCPA=λ∗Gcpa∗sum(pCVR)/sum(CVR)(0<λ<1)eCPA=λ∗Gcpa​∗sum(pCVR)/sum(CVR)(0<λ<1)

三、解决方法,思想。

CPA出价的好处:
1. 直接关系到广告主的投资回报率(ROI)。
2. 受在线作弊的影响比较小。
挑战
  1. 归因问题: DSP方是在一个时间窗口(predefined time window)内,把追踪到的转化都算作自己平台的转化(local attribution),而最后的转化是按照第三方平台归因的转化。
  2. 和CTR比较问题。表面上看CVR是CTR问题的自然延伸,因此CVR的文献也较少。但是,转化要求用户的参与度远高于点击,因此,用户的行为特征是更加重要的。 面临的挑战:
    1. 转化稀疏,通常比CTR小几个数量级。导致的问题是CVR过度的预测与广告主实际的eCPA差距很大。
    2. 数据延迟回传。这样导致两个问题:
      1. 转化模型需要预测将来一段时间发生的事情
      2. 基于非延迟数据的算法基本就不太适用。
    3. 本地和全局归因:有时候会导致差异巨大【?业务经验】
    4. 展示值区别。这个是由于广告在竞价的时候通常采用广义第二高价,这和CPC计费可以直接用CTR预估不同,CPA不能直接用CVR描述,还会受到其他因素影响有关系。
过度预估

过度预估的问题:可能导致获取大量的低质流量,预算消耗过快的问题。【解决这个问题成为本文的最高优先级的事情】

  1. 无经验下限:转化其实是表达了用户强烈的兴趣点。pCTR是有一个经验下限的,可以保证预估的效果达到优化目标。但是CVR由于上边介绍,存在的一些问题,是不能保证类比eCPC的eCPA能够达到优化目标的。

  2. 预测与观测的差异: 过度预测是固有的,即使预测是无偏的。

引理:给定n次展示,让C1,C2,…,CnC1​,C2​,…,Cn​表示真实的转化率,CˉCˉ是经验转化率,假设预估的转化率C^C^是无偏的,C^=1n∑1nCiC^=n1​∑1n​Ci​,以预估的值C^⋅GcpaC^⋅Gcpa​出价,且假设对每一个展现出价最高的第三方服从对数-正太分布lnN(μi,σ2)lnN(μi​,σ2),其中μi=Ci⋅Gcpaμi​=Ci​⋅Gcpa​,那么C^C^就是一个过度预估:
C^≥CˉC^≥Cˉ
对所有的展现都有相同的转化率,即C1=C2=⋯=CnC1​=C2​=⋯=Cn​时等号成立。

具体证明过程略。 这里有一个关键假设是对于每一个展现都存在其他卖方平台,基于前面介绍的所有卖方平台的归因技术是相同的,因此它们的平均出价和我们的相同或者是在均衡条件下。

  1. 训练数据限制和偏差
    1. 由于转化数据是广告主独有的,因此对于某个广告主的CVR预估模型的训练数据,是需要排出掉其他广告主的数据的。
    2. 训练数据只包含了赢得RTB竞价的数据,这个样本集是和线上模型集合有严重偏差的。【15、17文献在解决这两个问题】
CVR安全预测框架

使用的方法是集成树的方式,每一个叶子节点代表一个特征子空间。和传统集成树的区别是,这里用到的每棵树不是完成的,是会继续迭代的【生长、删除叶子节点】。

  1. 数据驱动树(Data-Driven trees)是枚举树,其中同一树中的每个叶节点对应于来自相同特征子集的唯一值组合。数据驱动树的限制是在活动开始时,它们没有叶节点,因此不能自己启动。
  2. 机器学习树(machine -learning trees)使用机器学习模型进行预测。它们的主要目的是帮助在活动初期阶段启动数据驱动树的生成。
数据驱动树
  1. 建造树,利用GBDT来完成特征的组合,并利用这些特征组合来构建数据驱动树。首先利用GBDT训练一个所有广告主的模型,但是不是直接来预测,只是指导如何构建数据驱动树。当GBDT模型训练后,我们基于从根节点到每个叶节点的路径提取特征集,然后为每个唯一特征集构建数据驱动树。
  2. 预测。叶子节点利用Beta-Binomial模型作为预测。CVR(p),impressions(B)服从Binomial(B,p)分布。p:B(α,β)=Beta(α,β−α)p:B(α,β)=Beta(α,β−α) αα是均值,方差Var(p)=α(β−α)β2(β+1)Var(p)=β2(β+1)α(β−α)​ 。求 αα,ββ时,采用指数衰减随时间变化的方法,因为它在实践中的预测精度方面优于其他方法。
  3. 树更新。在观察到足够多的展现和转化后更新叶子节点。一个叶子节点出现是B(α^,β^)B(α^,β^​) 分布满足:α^<α0,β^<β0α^<α0​,β^​<β0​Var(p)<v0Var(p)<v0​,其中α0,β0,v0α0​,β0​,v0​是阈值。
机器学习树

为了构造机器学习树,需要首先定义一个置信区间。通常取GBDT预测的Top10%

集成预测

数据驱动树和机器学习树都会有一个预测值。p1,p2,…,pnp1​,p2​,…,pn​是这些树的预测值。有三种方法来求集成的预测值:

  1. 最大值法。p^=max⁡p1,p2,…,pnp^​=maxp1​,p2​,…,pn​.
  2. 均值法。p^=1n∑1nCip^​=n1​∑1n​Ci​
  3. 权重平均。p^=∑1nVar(pi)−1pi∑1nVar(pi)−1p^​=∑1n​Var(pi​)−1∑1n​Var(pi​)−1pi​​.其中,Var(pi)=αi(βi−αi)βi2(β+1)Var(pi​)=βi2​(β+1)αi​(βi​−αi​)​

实际采用3。

归因调整

目标是预估预估的CVR和真实的CVR之间的差距,从而指导CPA出价。

  1. 对延迟数据的转化调整。 【这里介绍了一个延迟回传可能导致低估的问题【低估的是经验转化率!(will lead to underestimation of the empirical CVR)】,和必然过度预测无关】 每日展示次数和转化次数都具有强烈的“日-星期”模式,优化归因时间窗口内差距最小。
min⁡∑j=T+1n[∑i=j−Tj(∑j′=ii+TCi,j′)∗Pj−1,D(i)−∑i=j−TjCi,j]2minj=T+1∑n​[i=j−T∑j​(j′=i∑i+T​Ci,j′​)∗Pj−1,D(i)​−i=j−T∑j​Ci,j​]2
s.ts.t
∑k=0TPd(k)=1k=0∑T​Pd​(k)=1
0≤Pd(k)≤10≤Pd​(k)≤1
  1. 本地归因调整。 本地归因和第三方归因差异最小。
min⁡∑j=Tn[∑i=1k(Pgi⋅Cgi,j)−Cj]2minj=T∑n​[i=1∑k​(Pgi​​⋅Cgi​,j​)−Cj​]2
s.ts.t
0≤Pgi≤10≤Pgi​​≤1
出价调整

出价: Vplain=f(t)⋅pt⋅GcpaVplain​=f(t)⋅pt​⋅Gcpa​

初始值: Vbaseline=ft0(t)⋅pt′⋅GcpaVbaseline​=ft0​​(t)⋅pt′​⋅Gcpa​

ΔV=Vplain−Vbaseline=[1−ft0(t)ft(t)]⋅VplainΔV=Vplain​−Vbaseline​=[1−ft​(t)ft0​​(t)​]⋅Vplain​.其中1−ft0(t)ft(t)1−ft​(t)ft0​​(t)​是调整因子,是需要接下来求的值。

ft0(t)=∫tt0+Tq(x−t0)⋅k(x)dxft0​​(t)=∫tt0​+T​q(x−t0​)⋅k(x)dx 其中qq表示对于时间x,在t0t0​时间内转化归因到展示的条件概率,k(x)k(x)服从“小时-天”的一个V字形函数。

算法1描述了估计增量值的步骤。 基本思想是对历史数据进行离散化并估计κ(x)κ(x)q(x−t0)q(x−t0​)的每小时概率值,然后将其用于计算调整因子的最终估计。


算法1: 输入:

`$t_0$`:之前展示的时间。
`t`:当前竞价展示时间。
`T`:归因时间窗口。
`W`:转化时间窗口。

n小时的历史数据。

  1. i,j∈{1,2,3,⋯,n}i,j∈{1,2,3,⋯,n},Ci,jCi,j​表示对于j小时的转化归因到i小时展示的数据。
  2. 计算k(x)在h≤Wh≤W的概率质量。
  3. 计算q(x−t0)q(x−t0​)在h的概率质量。
  4. 计算归因的概率:

f^t0(t)=∑h=tt0+Tq^(h−t0)⋅k^(h)f^​t0​​(t)=∑h=tt0​+T​q^​(h−t0​)⋅k^(h) 且f^t(t)=∑h=tt+Tq^(h−t0)⋅k^(h)f^​t​(t)=∑h=tt+T​q^​(h−t0​)⋅k^(h)

输出

预估调整因子值1−ft0(t)ft(t)1−ft​(t)ft0​​(t)​


四、实验。

实现了2000+GBDT树,562个分类特征,限制每棵树的内部节点不超过8,树的最大深度为7,单一特征不超过7,去重之后的到214个特征集合。

一些online的A/B实验。

五、应用&借鉴。

  1. 明确CVR与CTR的差异。CVR其实表现的和CTR有诸多的不同,因此处理的策略也不同。
  2. 树形模型的有效性。
  3. 转化具有的“日-星期”,“小时-天”模式。

六、相关推荐。

  1. Large Scale CVR Prediction through Dynamic Transfer Learning of Global and Local Features
  2. Post-Click Conversion Modeling and Analysis for Non-Guaranteed Delivery Display Advertising
  3. Estimating Conversion Rate in Display Advertising from Past Performance Data
05-23 04:44