论文A Practical Framework of Conversion Rate Prediction for Online Display Advertising
定期更新,获取更多,欢迎star。
一、论文基本描述。
本论文基于Yahoo! BrightRoll （Oath）雅虎的RTB(视频)买方平台（DSP）。 由于CPA成为主流出价方式，所以转化率预估变成了关键的问题。
难点：
- 转化数据非常稀疏。（extremely sparse conversions）
- 数据延迟回传。(delay feedback)
- 和第三方平台归因差异。（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. 受在线作弊的影响比较小。挑战
- 归因问题： DSP方是在一个时间窗口（predefined time window）内，把追踪到的转化都算作自己平台的转化（local attribution）,而最后的转化是按照第三方平台归因的转化。
- 和CTR比较问题。表面上看CVR是CTR问题的自然延伸，因此CVR的文献也较少。但是，转化要求用户的参与度远高于点击，因此，用户的行为特征是更加重要的。 面临的挑战：
- 转化稀疏，通常比CTR小几个数量级。导致的问题是CVR过度的预测与广告主实际的eCPA差距很大。
- 数据延迟回传。这样导致两个问题：
- 转化模型需要预测将来一段时间发生的事情
- 基于非延迟数据的算法基本就不太适用。
- 本地和全局归因：有时候会导致差异巨大【?业务经验】
- 展示值区别。这个是由于广告在竞价的时候通常采用广义第二高价，这和CPC计费可以直接用CTR预估不同，CPA不能直接用CVR描述，还会受到其他因素影响有关系。
过度预估
过度预估的问题:可能导致获取大量的低质流量，预算消耗过快的问题。【解决这个问题成为本文的最高优先级的事情】
无经验下限：转化其实是表达了用户强烈的兴趣点。pCTR是有一个经验下限的,可以保证预估的效果达到优化目标。但是CVR由于上边介绍，存在的一些问题，是不能保证类比eCPC的eCPA能够达到优化目标的。
预测与观测的差异： 过度预测是固有的，即使预测是无偏的。
引理：给定n次展示，让C1,C2,…,CnC1,C2,…,Cn表示真实的转化率,CˉCˉ是经验转化率,假设预估的转化率C^C^是无偏的，C^=1n∑1nCiC^=n1∑1nCi,以预估的值C^⋅GcpaC^⋅Gcpa出价,且假设对每一个展现出价最高的第三方服从对数-正太分布lnN(μi,σ2)lnN(μi,σ2),其中μi=Ci⋅Gcpaμi=Ci⋅Gcpa,那么C^C^就是一个过度预估：
对所有的展现都有相同的转化率，即C1=C2=⋯=CnC1=C2=⋯=Cn时等号成立。
具体证明过程略。 这里有一个关键假设是对于每一个展现都存在其他卖方平台，基于前面介绍的所有卖方平台的归因技术是相同的，因此它们的平均出价和我们的相同或者是在均衡条件下。
- 训练数据限制和偏差
- 由于转化数据是广告主独有的，因此对于某个广告主的CVR预估模型的训练数据，是需要排出掉其他广告主的数据的。
- 训练数据只包含了赢得RTB竞价的数据，这个样本集是和线上模型集合有严重偏差的。【15、17文献在解决这两个问题】
CVR安全预测框架
使用的方法是集成树的方式，每一个叶子节点代表一个特征子空间。和传统集成树的区别是，这里用到的每棵树不是完成的，是会继续迭代的【生长、删除叶子节点】。
- 数据驱动树(Data-Driven trees)是枚举树，其中同一树中的每个叶节点对应于来自相同特征子集的唯一值组合。数据驱动树的限制是在活动开始时，它们没有叶节点，因此不能自己启动。
- 机器学习树(machine -learning trees)使用机器学习模型进行预测。它们的主要目的是帮助在活动初期阶段启动数据驱动树的生成。
数据驱动树
- 建造树，利用GBDT来完成特征的组合，并利用这些特征组合来构建数据驱动树。首先利用GBDT训练一个所有广告主的模型，但是不是直接来预测，只是指导如何构建数据驱动树。当GBDT模型训练后，我们基于从根节点到每个叶节点的路径提取特征集，然后为每个唯一特征集构建数据驱动树。
- 预测。叶子节点利用Beta-Binomial模型作为预测。CVR(p),impressions(B)服从Binomial(B,p)分布。
p:B(α,β)=Beta(α,β−α)p:B(α,β)=Beta(α,β−α)αα是均值，方差Var(p)=α(β−α)β2(β+1)Var(p)=β2(β+1)α(β−α)。求αα,ββ时，采用指数衰减随时间变化的方法，因为它在实践中的预测精度方面优于其他方法。 - 树更新。在观察到足够多的展现和转化后更新叶子节点。一个叶子节点出现是
B(α^,β^)B(α^,β^)分布满足：α^<α0,β^<β0α^<α0,β^<β0且Var(p)<v0Var(p)<v0，其中α0,β0,v0α0,β0,v0是阈值。
机器学习树
为了构造机器学习树，需要首先定义一个置信区间。通常取GBDT预测的Top10%
集成预测
数据驱动树和机器学习树都会有一个预测值。p1,p2,…,pnp1,p2,…,pn是这些树的预测值。有三种方法来求集成的预测值：
- 最大值法。
p^=maxp1,p2,…,pnp^=maxp1,p2,…,pn. - 均值法。
p^=1n∑1nCip^=n1∑1nCi - 权重平均。
p^=∑1nVar(pi)−1pi∑1nVar(pi)−1p^=∑1nVar(pi)−1∑1nVar(pi)−1pi.其中，Var(pi)=αi(βi−αi)βi2(β+1)Var(pi)=βi2(β+1)αi(βi−αi)
实际采用3。
归因调整
目标是预估预估的CVR和真实的CVR之间的差距，从而指导CPA出价。
- 对延迟数据的转化调整。 【这里介绍了一个延迟回传可能导致低估的问题【低估的是经验转化率!(will lead to underestimation of the empirical CVR)】，和必然过度预测无关】 每日展示次数和转化次数都具有强烈的“日-星期”模式，优化归因时间窗口内差距最小。
- 本地归因调整。 本地归因和第三方归因差异最小。
出价调整
出价： 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+Tq(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小时的历史数据。
- 对
i,j∈{1,2,3,⋯,n}i,j∈{1,2,3,⋯,n},Ci,jCi,j表示对于j小时的转化归因到i小时展示的数据。 - 计算k(x)在
h≤Wh≤W的概率质量。 - 计算
q(x−t0)q(x−t0)在h的概率质量。 - 计算归因的概率：
f^t0(t)=∑h=tt0+Tq^(h−t0)⋅k^(h)f^t0(t)=∑h=tt0+Tq^(h−t0)⋅k^(h) 且f^t(t)=∑h=tt+Tq^(h−t0)⋅k^(h)f^t(t)=∑h=tt+Tq^(h−t0)⋅k^(h)
输出
预估调整因子值1−ft0(t)ft(t)1−ft(t)ft0(t)。
四、实验。
实现了2000+GBDT树，562个分类特征，限制每棵树的内部节点不超过8，树的最大深度为7，单一特征不超过7，去重之后的到214个特征集合。
一些online的A/B实验。
五、应用&借鉴。
- 明确CVR与CTR的差异。CVR其实表现的和CTR有诸多的不同，因此处理的策略也不同。
- 树形模型的有效性。
- 转化具有的“日-星期”，“小时-天”模式。