论文Modeling Delayed Feedback in Display Advertising阅读笔记

Abstract

1. 评估广告投放效果的重要指标：转化率(conversion rate) —– 在广告网站上采取行动的人占总浏览人数的比例。使用机器学习预估 conversion rate，从而预估收益。
2. 然而conversion很可能延时发生，比如看过一个商品广告，当时有些心动但并没有马上去买，过了几天按捺不住又去购买（Delayed Feedback），给建模带来困难。
3. 这篇文章提出概率模型，对未采取行动的客户进行判别：可能会买or不可能会买

Introduction

广告计费模式：参考学习: 网络广告中，CPC、CPA、CPM 的定义各是怎样的？

这篇文章集中在CPA(cost per action)模式，更确切的说，是post-click conversion（点击后转化，转化被归因到之前的点击）。只有产生了预先商定的行动才付费。支持CPA模式的平台，就需要将广告标价，转化为eCPM(期望CPM），取决于conversion rate。

转化的延迟反馈特性导致构件训练集，设置匹配窗口长度的困难：过短则漏掉部分conversion；过长则导致模型停滞。

本文生成训练集时，将样本标记为positive和unlabeled，需要从正例和未标记数据中进行学习，但都假定标记正例从正类中随机选择，标签缺失的概率恒定。但与本文所讨论的情形不同：点击刚发生时，标签最易缺失。

本文引入模型II捕捉点击和转化之间的期望延迟，这有点类似于survival time analysis(生存时间分析，指治疗开始和患者死亡之间的时间)。有一些时间是截断（conversion一直没有发生）的， 这表明延迟（或者生存）时间至少是那个截断时间。

然而病人终有一死，而客户却未必转化。这就需要两个模型：一个预测是否转化；另一个预测相应的延迟时间。这两个模型共同训练，共同分配结果。

数据来源：Criteo流量日志；营利模式：收益（CPC/CPA，广告商）- 成本（CPM，出版商）

Conversions

Post-Click Attribution

post-view attribution: 将转化归因于之前的一次或几次浏览
post-click attribution: 将转化归因于被点击的广告
本文转化时间窗口长度固定为：30天

匹配除了时间窗要求，还要有相同的用户id和广告商。在多次点击导致一次转化时，按照行业标准归因于最后一次点击。若有多次转化匹配一次点击，则只保留第一个。也就是说，本文不考虑，单次点击导致多次转化的情形。

Conversion Rate Prediction

eCPM=CPA×Pr(conversion,click)$eCPM=CPA\times Pr(conversion,click)$
          =CPA×Pr(click)×Pr(conversion|click)$=CPA\times Pr(click)\times Pr(conversion|click)$
条件概率分解能降低数据负载，并且在没有conversion时仍能提供一定的click信息。建模Pr(click)需要可扩展的模型：单一平台每日广告投放量可达数十亿，而点击反馈是即时的；建模Pr(conversion | click)规模较小，但有反馈延迟。

Analysis of the Conversion Delay

New Campaigns

广告展示的各个因素都在持续变化，当新的活动被加入系统时，原来训练好的模型效能将会降低：Keep the model fresh！
在图2中，新活动的比例持续增长，这预示着30天的长时间窗模型将受到影响。

Model

• X$X$：特征集
• Y∈{0,1}$Y\in \{0,1\}$：转化是否已经发生
• C∈{0,1}$C\in \{0,1\}$：用户是否终会转化
• D$D$：点击和转化之间的延迟
• E$E$：点击后已经流逝的时间

Y=0⟺C=0 or E<D$Y=0⟺C=0orE<D$
Y=1⟹C=1$Y=1⟹C=1$
独立性假设：Pr(C,D|X,E)=Pr(C,D|X)$Pr(C,D|X,E)=Pr(C,D|X)$
也就是说，在这个模型中，不根据已经过了多久来判断转化最终是否发生和最终延迟时间。

给定数据集：(xi,yi,ei)$(x_i,y_i,e_i)$，如果yi=1$y_i=1$，还有相应的di$d_i$值。
用两个参数模型拟合数据：Pr(C|X),Pr(D|X,C=1)$Pr(C|X),Pr(D|X,C=1)$
训练好以后，前者被用来预测转换概率，后者被抛弃
这两个模型都是广义线性模型：前者是标准的逻辑回归：
Pr(C=1|X=x)=p(x),p(x)=11+exp(−wc⋅x)$Pr(C=1|X=x)=p(x),p(x)=\frac{1}{1+\exp (-w_c\cdot x)}$
后者是延迟的指数分布：
Pr(D=d|X=x,C=1)=λ(x)exp(−λ(x)d)$Pr(D=d|X=x,C=1)=\lambda (x)\exp (-\lambda (x)d)$
其中，为了保证λ(x)>0$\lambda (x)>0$，令λ(x)=exp(wd⋅x)$\lambda (x)=\exp (w_d\cdot x)$
则该模型的参数就是wc,wd$w_c,w_d$

Pr(Y=1,D=di|X=xi,E=ei)$Pr(Y=1,D=d_i|X=x_i,E=e_i)$
=Pr(C=1,D=di|X=xi,E=ei)$=Pr(C=1,D=d_i|X=x_i,E=e_i)$
=Pr(C=1,D=di|X=xi)$=Pr(C=1,D=d_i|X=x_i)$
=Pr(D=di|X=xi,C=1)Pr(C=1|X=xi)$=Pr(D=d_i|X=x_i,C=1)Pr(C=1|X=x_i)$
=λ(xi)exp(−λ(xi)di)p(xi)$=\lambda (x_i)\exp (-\lambda (x_i)d_i)p(x_i)$

Pr(Y=0|X=xi,E=ei)$Pr(Y=0|X=x_i,E=e_i)$
=Pr(Y=0|C=0,X=xi,E=ei)Pr(C=0|X=xi)$=Pr(Y=0|C=0,X=x_i,E=e_i)Pr(C=0|X=x_i)$
+Pr(Y=0|C=1,X=xi,E=ei)Pr(C=1|X=xi)$+Pr(Y=0|C=1,X=x_i,E=e_i)Pr(C=1|X=x_i)$
=1−p(xi)+p(xi)exp(−λ(xi)ei)$=1-p(x_i)+p(x_i)\exp (-\lambda (x_i)e_i)$
⇑$\Uparrow$
Pr(Y=0|C=1,X=xi,E=ei)=Pr(D>E|C=1,X=xi,E=ei)$Pr(Y=0|C=1,X=x_i,E=e_i)=Pr(D>E|C=1,X=x_i,E=e_i)$
=∫∞eiλ(x)exp(−λ(x)t)dt=exp(−λ(x)ei)$={\int }_{e_i}^{\mathrm{\infty }}\lambda (x)\exp (-\lambda (x)t)dt=\exp (-\lambda (x)e_i)$

Optimization

Expectation-Maximization

EM算法学习参考:简单易学的机器学习算法——EM算法
把C$C$看作隐藏变量

Joint Optimization

Loss Function:
argminwc,wdL(wc,wd)+μ2(||wc||22+||wd||22)$\arg \underset{w_c,w_d}{min}L(w_c,w_d)+\frac{\mu }{2}(||w_c|{|}_2^2+||w_d|{|}_2^2)$
其中，μ$\mu$是正则化参数，L$L$是负对数似然：
L(wc,wd)=−∑i,yi=1logp(xi)+logλ(xi)−λ(xi)di$L(w_c,w_d)=-\sum _{i,y_i=1}\log p(x_i)+\log \lambda (x_i)-\lambda (x_i)d_i$
                    −∑i,yi=0log[1−p(xi)+p(xi)exp(−λ(xi)ei)]$-\sum _{i,y_i=0}\log [1-p(x_i)+p(x_i)\exp (-\lambda (x_i)e_i)]$
该优化问题是无约束且二次可微的，本文使用L-BFGS进行优化，可参考：优化算法——拟牛顿法之L-BFGS算法

Tips

这篇文章的主要贡献：首次对延时反馈进行建模！
数据集：http://labs.criteo.com/tag/dataset
评价指标：平均负对数似然NLL
参数设置：μ:=1n||xi||22$\mu :=\frac{1}{n}||x_i|{|}_2^2$