延迟反馈问题

Posted on

常见于在线 pCTR pCVR 预估任务，挑战：窗口期正样本少；窗口期负样本会延迟转化；时间窗口过大影响在线指标。

​ 在线学习算法篇(一) 样本延迟反馈 KM

​ CVR 预估中的转化延迟反馈问题概述 知乎

最近发表

《Dual Learning Algorithm for Delayed Conversions 2020》

用两个模型：CVR 预测模型和 + CVR Bias 预测模型；提出 a dual learning algorithm，在已观测的数据集上，交替训练这两个模型。

注：用合成数据集评估效果，无在线效果对比。

《Addressing Delayed Feedback for Continuous Training with Neural Networks in CTR prediction RecSys19》

在 LR 和 W&D模型基础上，比较 5 种 loss：LogLoss / DelayedFeebackLoss 加入延迟反馈信息 / PULoss 未标记样本作为负样本 / FNWeighted / FNCalibration 的 CE / RCE / PR-AUC 指标，其中 FNCali 较好。

Twitter 提出 PDF，旨在解决深度 CTR 模型中，训练样本时间窗口延时很小（推特 pCTR 需要小于 5min 达到近实时）导致 FN 样本干扰的问题，在 Wide&Deep 模型损失函数的基础上：

argminθ,wdLDF(θ,wd)+α(∣∣θ∣∣22+∣∣wd∣∣22)\arg \min_{\theta, w_d} L_{DF}(\theta, w_d) + \alpha(||\theta||_2^2+||w_d||_2^2)

对比 5 个 损失函数的效果：

  • Log Loss

    LCE=−∑x,y=1logfθ(x)−∑x,y=0log[1−fθ(x)]\begin{aligned} L_{CE}=&-\sum_{x,y=1}\log f_\theta(x)\\ &-\sum_{x,y=0}\log[1-f_\theta(x)] \end{aligned}

  • Fake Negative Weighted Loss

    基于 importance sampling 推导，负样本在用户参与后立即用正标签复制到数据集。

    假设

    b(x∣y=0)=p(x),b(x∣y=1)=p(x∣y=1)b(x|y=0)=p(x),b(x|y=1)=p(x|y=1)

    其中 b 是样本数据分布与真实数据分布的 bias，我们知道 b(y=0)=11+p(y=1)b(y=0)=\frac{1}{1+p(y=1)}，因为所有样本标签初始化为 0。

    损失函数是

    LIS(θ)=−Ep[logfθ(y∣x)]=−∑x,yp(x,y)logfθ(y∣x)=−Eb[p(x,y)b(x,y)logfθ(y∣x)]=−1N∑np(xn,yn)b(xn,yn)logfθ(yn∣xn)\begin{aligned} L_{IS}(\theta)&=-\mathbb{E}_p[\log f_\theta(y|x)]=-\sum_{x,y}p(x,y)\log f_\theta(y|x)\\ &=-\mathbb{E}_b[\frac{p(x,y)}{b(x,y)} \log f_\theta(y|x)] = -\frac{1}{N} \sum_n \frac{p(x_n,y_n)}{b(x_n,y_n)} \log f_\theta(y_n|x_n) \\ \end{aligned}

    LIS(θ)=−∑x,yp(y=1∣x)1+p(y=1∣x)[1+fθ(x)]logfθ(x)+11+p(y=1∣x)[(1−fθ(x)(1+fθ(x)))]log(1−fθ(x))\begin{aligned} L_{IS}(\theta)=-\sum_{x,y}&\frac{p(y=1|x)}{1+p(y=1|x)}[1 + f_\theta (x)] \log f_\theta(x) \\ &+ \frac{1}{1+p(y=1|x)}[(1-f_\theta(x)(1+f_\theta(x)))] \log(1-f_\theta(x)) \end{aligned}

    其中 [⋅][\cdot] 不参与梯度计算。

  • Fake Negative Calibration Loss

  • Positive Unlabeled Loss

    LPU=−∑x,y=1[logfθ(x)−log(1−fθ(x))]−∑x,y=0log[1−fθ(x)]\begin{aligned} L_{PU}=&-\sum_{x,y=1}[\log f_\theta(x)-\log(1-f_\theta(x))]\\ &-\sum_{x,y=0}\log[1-f_\theta(x)] \end{aligned}

    推导见 overview

  • Delayed Feedback Loss

    LDF(θ,wd)=−∑x,y=1logfθ(x)+logλ(x)−λ(x)d−∑x,y=0log[1−fθ(x)+fθ(x)exp(−λ(x)e)]\begin{aligned} L_{DF}(\theta, w_d)=&-\sum_{x,y=1} \log f_\theta(x)+\log\lambda(x)-\lambda(x)d \\ &-\sum_{x,y=0}\log[1-f_\theta(x) + f_\theta(x)\exp(-\lambda(x)e)] \end{aligned}

    其中 d 是正例的曝光-点击时长，e 是负例曝光-至今时间，fθ(x)f_\theta(x) 是模型。

    假设延迟转化概率服从指数分布

    λ(x)=exp(wd⋅x)\lambda(x)=\exp(w_d\cdot x)

    其中 wdw_d 是延时反馈模型参数，θ\theta 是深度模型参数。

    另一个数值稳定的版本是

    LDF(θ,wd)=−∑x,ylogfθ(x)−∑x,y=1wd⋅x−λ(x)d−∑x,y=0log[exp(−fθ(x))+exp(−λ(x)e)]\begin{aligned} L_{DF}(\theta,w_d)=&-\sum_{x,y}\log f_\theta(x)\\ & -\sum_{x,y=1}w_d\cdot x - \lambda(x)d \\ & - \sum_{x,y=0}\log[\exp(-f_\theta(x))+\exp(-\lambda(x)e)] \end{aligned}

    通过延迟反馈大的样本辅助模型参数学习。

    推导参考论文《Modeling Delayed Feedback in Display Advertising》

发现：在线性模型表现好的损失函数，在深度模型不一定好。

《A Nonparametric Delayed Feedback Model for Conversion Rate Prediction 2018》

PDF 认为延迟的反馈分布可能和广告/用户/上下文都有关系，因此对延迟反馈的时间建模成一个可以学习的模型，和下一篇文章的方式与 CVR 进行联合建模。

《Learning from Delayed Outcomes via Proxies with Applications to Recommender Systems, ICML19》 PDF 引入 proxy

《Modeling Delayed Feedback in Display Advertising SIGKDD14》

Criteo PDF 发表，提出了两步模型：pCVR 最终转化概率 & pCVR 最终转化所需时间，通过后者延迟大的数据辅助前者的学习。

文中分析了分别进行 pCTR CVR 模型的优势：pCTR 样本多，通过在线训练框架优化；pCVR 样本稀疏，延时反馈长达 30 天。在转化样本稀疏时，pCTR 更准便于优化 CPC。

定义 X 特征，Y 转化是否已发生，C 是否最终会转化，D 点击到转化的延时（不转化为 -1），E 自点击的流逝时间。

定义两个概率模型， 是否最终转化 Pr(C∣X)Pr(C|X) 和 Pr(D∣X,C=1)Pr(D|X,C=1)，线上使用前者（LR 模型，也可用其他）：

Pr(C=1∣X=x)=p(x)=11+exp(−wcx)Pr(C=1|X=x) = p(x)=\frac{1}{1+\exp(-w_cx)}

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)=exp(wdx)\lambda(x)=\exp(w_dx) ，共有两个参数 wc,wdw_c,w_d

Label 定义：1 最终转化；0 未观察到转化

Y=0→C=0 or E<DY = 0 \rightarrow C= 0 \text{ or }E < D

Y=1⟹C=1Y=1 \Longrightarrow C=1

训练样本：由转化样本 (yi=1,xi,ei,di)(y_i=1,x_i,e_i,d_i) 和未观察到转化样本 (yi=0,xi,ei)(y_i=0,x_i,e_i) 组成。

假设：给定 XX，元组 (C,D)(C,D) 与 EE 独立，既 Pr(C,D∣X)=Pr(C,D∣X,E)\Pr(C,D|X)=\Pr(C,D|X,E)

模型定义：对于转化样本有

P(Y=1,D∣X,E)=Pr(C=1,D∣X,E)=Pr(C=1,D∣X)=Pr(D∣X,C=1)Pr(C=1∣X)=exp(−λ(x)ei)\begin{aligned} P(Y=1,D|X,E) &= \Pr(C=1,D|X,E) \\ &=\Pr(C=1,D|X) \\ &=\Pr(D|X,C=1)\Pr(C=1|X)\\ &=\exp(-\lambda(x)e_i) \end{aligned}

对于未转化样本有

P(Y=0∣X,E)=Pr(Y=0∣C=0,X,E)Pr(C=0∣X)+Pr(Y=0∣C=1,X,E)Pr(C=1∣X)\begin{aligned} P(Y=0|X,E) = & \Pr(Y=0|C=0,X,E)\Pr(C=0|X)+ \\ & \Pr(Y=0|C=1,X,E)\Pr(C=1|X)\\ \end{aligned}

其中以上第二项 Pr(C∣X)\Pr(C|X) 已定义，第一项定义为

Pr(Y=0∣C=0,X,E)=Pr(D>E∣C=1,X,E)=∫ei+infλ(x)exp(−λ(x)t)dt=exp(−λ(x)ei)\begin{aligned} \Pr(Y=0|C=0,X,E)&=\Pr(D>E|C=1,X,E) \\ &=\int_{e_i}^{+\inf}\lambda(x)\exp(-\lambda(x)t)dt \\ &=\exp(-\lambda(x)e_i) \end{aligned}

Pr(Y=0∣C=1,X,E)=1\Pr(Y=0|C=1,X,E)= 1

综上，得到模型定义

Pr(Y=0∣X,E)=1−p(xi)+p(xi)exp(−λ(xi)ei)Pr(Y=1,D∣X,E)=exp(−λ(x)ei)\begin{aligned} \Pr(Y=0|X,E) &= 1-p(x_i)+p(x_i)\exp(-\lambda(x_i)e_i)\\ \Pr(Y=1,D|X,E) &= \exp(-\lambda(x)e_i) \end{aligned}

模型训练：EM 方法

损失函数：

argminwc,wdLDF(wc,wd)+μ2(∣∣wc∣∣2+∣∣wd∣∣2)\arg \min_{w_c,w_d}L_{DF}(w_c,w_d)+\frac{\mu}{2}(||w_c||^2+||w_d||^2)

LDF(wc,wd)=−∑x,y=1logp(x)+logλ(x)−λ(x)d−∑x,y=0log[1−p(x)+p(x)exp(−λ(x)e)]\begin{aligned} L_{DF}(w_c, w_d)=&-\sum_{x,y=1} \log p(x)+\log\lambda(x)-\lambda(x)d \\ &-\sum_{x,y=0}\log[1-p(x) + p(x)\exp(-\lambda(x)e)] \end{aligned}

其中 p(x)=11+exp(−wc⋅x),λ(x)=exp(wd,x)p(x)=\frac{1}{1+\exp(-w_c\cdot x)}, \lambda(x)=\exp(w_d,x)

Importance Sampling

是通过从一个数据分布的采样，估算另一个数据分布的采样的方法。

关于模型 fθf_\theta 和数据分布 pp ，交叉熵的定义是

L(θ)=−Ep[logfθ(y∣x)]=−∑x,yp(x,y)logfθ(y∣x)L(\theta)=-\mathbb{E}_p[\log f_\theta(y|x)]=-\sum_{x,y}p(x,y)\log f_\theta(y|x)

在线采样有偏导致数据分布为 bb，而我们无法从数据分布 pp 中采样，通过恰当的 weighting scheme 我们能获得无偏估计：

Ep[logfθ(y∣x)]=Eb[p(x,y)b(x,y)logfθ(y∣x)]=1N∑nw(xn,yn)logfθ(yn∣xn)\mathbb{E}_p[\log f_\theta(y|x)]=\mathbb{E}_b[\frac{p(x,y)}{b(x,y)} \log f_\theta(y|x)] = \frac{1}{N} \sum_n w(x_n,y_n) \log f_\theta(y_n|x_n)

其中 w(x,y)=p(x,y)b(x,y)w(x,y)= \frac{p(x,y)}{b(x,y)} 是 importance weight

此方法的挑战，是需要对 ww 作出合理估计。

此方法广泛用于反事实分析（counterfactual analysis）：微软 Bottou et. al. 在《Counterfactual reasoning and learning systems: The example of computational advertising JMLR13》 PDF 讨论了如何在计算广告应用此方法估算 counterfactual expectation。

例子：https://zhuanlan.zhihu.com/p/41217212

Inverse Propensity Weighting

《Moving towards best practice when using inverse probability of treatment weighting (IPTW) using the propensity score to estimate causal treatment effects in observational studies》PDF

在临床药理研究中，通常治疗组（Y = 1）的指派不是随机的，建模倾向分数（propensity score） p(x)=P(Y=1∣X=x)p(x)=P(Y=1|X=x) ，即某个样本 x 被指派为治疗组的概率；然后通过逆倾向分数对样本加权。

在 pCTR 问题中，Y=1 表示点击样本。

此方法的挑战，是需要对倾向分数单独建模。

例子：https://en.wikipedia.org/wiki/Inverse_probability_weighting

Delayed Bandits

《Markov decision processes with delays and asynchronous cost collection》

《Stochastic Bandit Models for Delayed Conversions》

《Learning and planning in environments with delayed feedback》

本文有帮助？