阿里在《Asymptotically Unbiased Estimation for Delayed Feedback Modeling via Label Correction》提出一种通过 Label Correction的方式对Delayed Feedback Modeling的渐近无偏估计建模:Defuse。
摘要
缓解延迟反馈问题是在线广告转化率(CVR)预测中至关重要的一环。以往的延迟反馈建模方法使用一个观察窗口(observation window)来平衡等待准确标签和利用新鲜反馈之间的权衡。此外,为了在观察到的但有偏的分布中估计CVR,广泛使用重要性采样来减少分布偏差。虽然有效,但我们认为以往的方法在重要性加权过程中错误地将假负样本视为真实负样本,并且没有充分利用观察到的正样本,导致性能次优。
在这项工作中,我们提出了一种新的方法,即带有无偏估计的延迟反馈建模(DEFUSE),旨在更细致地分别校正即时正样本、假负样本、真实负样本和延迟正样本的重要性权重。具体来说,我们提出了一种两步优化方法:
- 首先在应用重要性采样之前推断观察到的负样本中假负样本的概率。
- 为了充分利用观察到的分布中的真即时正样本,我们进一步开发了一个双分布建模框架,联合建模无偏即时正样本和有偏延迟转化。
实验结果在公共和我们的工业数据集上验证了DEFUSE的优越性。代码可在 https://github.com/ychen216/DEFUSE.git 获取。
1.引言
在线广告已成为智能电子商务的主要商业模式,帮助广告商锁定潜在客户[3, 4, 14]。一般来说,每次行动成本(CPA)和每次点击成本(CPC)是两种广泛使用的支付选项,它们直接影响平台的收入和所有广告商的投资回报率(ROI)。作为两种定价竞价的基本部分,转化率(CVR)预测,专注于以ROI为导向的优化,始终是一个不可替代的组成部分,以确保一个健康的广告平台[12]。
流式学习(streaming learning)作为一种广泛使用的训练框架,会根据实时反馈不断微调模型,已在点击率(CTR)预测任务中显示出有希望的性能[13, 18, 21, 22]。然而,如表1所示,由于CVR预测普遍存在的延迟和长尾转化反馈,通过流式学习实现更好的结果并非易事。更具体地说,如图1所示,发生在时间 $ t_0 $ 的点击需要等待足够长的归因窗口 $ w_a $ 才能确定其实际label——只有在 $ t_0 + w_a $ 之前转化的样本才被标记为正样本。通常,不同商业场景中 $ w_a $ 的设置范围从一天到几周不等。问题在于,即使是一天这样短的归因窗口也太长,无法确保样本的新鲜度,这仍然是实现有效的流式CVR预测的主要障碍。
图1 不同标签类型的说明。观察窗口 $ w_0 $表示点击时间和流式训练时间之间最小的时间间隔;而归因窗口 $ w_a $ 决定了实际的标签。
为了解决这一挑战,现有的努力集中在引入一个更短的观察窗口 $ w_o $,例如30分钟,允许在 $ t_0 + w_o $ 之后立即收集有观察到标签的点击并将其分发到训练流程中。优化 $ w_o $ 提供了利用更多新鲜样本和接受不太准确标签之间的权衡能力。这极大地提高了样本的新鲜度,同时在观察窗口内可接受地覆盖了转化,代价是暂时将长时间延迟的反馈标记为假负样本。因此,当前的工作主要集中在对观察到的但有偏的分布中的假负样本进行CVR估计。
由于使用标准的二元分类损失(例如交叉熵)很难实现无偏估计,当前的努力实施各种辅助任务来模拟转化延迟,以减轻由假负样本引起的偏差。早期方法[2, 29]尝试通过联合优化CVR预测与一个预测延迟时间 $ d $ 的延迟模型来解决延迟反馈问题,假设从延迟分布中。然而,这些方法直接在有偏的观察分布上进行训练,并且没有充分利用稀有且稀疏的延迟正反馈。意识到这些缺点后,最近的研究主要关注在转化发生时将延迟转化重新用作正样本。设计了各种样本复制机制来充分利用每次转化。例如:
- FNC/FNW[10]:将 $ w_o $ 设置为0,并在转化到达时重新发送所有正样本。
- ES-DFM[27]:仅复制之前被错误标记为假负样本的延迟正样本;
- DEFER[5]:重新利用所有在完成标签归因后具有实际label的样本,以保持特征分布的平等,并利用真实的负样本。此外,为了弥合分布偏差,采用重要性采样[1]来纠正真实情况与观察到的但有偏的分布之间的差异。
尽管有效,我们认为当前方法仍存在一些限制。首先,它们主要侧重于设计适当的训练流程以减少特征空间中的偏差,并通过重要性采样仅对观察到的正样本和负样本的损失进行加权。问题是,观察到的负样本可能是假负样本,这些方法错误地将它们视为真实负样本,导致次优性能。其次,观察到的正样本可以进一步细分为即时正样本(IP)和延迟正样本(DP),这意味着两个潜在的改进:
- (1)直观上,由于复制,IP和DP对CVR模型的贡献不同。
- (2)通过排除DP,可以基于与实际IP分布一致的观察数据集直接建立IP预测的无偏估计。
在本文中,我们提出了一种用于流式CVR预测的带有无偏估计的延迟反馈建模(DEFUSE),它研究了假负样本的影响,并充分利用了DP在重要性采样上的作用。与以往仅对观察到的正样本和负样本进行建模的方法不同,我们正式将样本识别为四种类型,即即时正样本(IP)、假负样本(FN)、真实负样本(RN)和延迟正样本(DP)。
由于在观察到的负样本中采用了FN,我们提出了一个两步优化方法,首先在对每种类型的样本进行重要性采样之前,推断观察到的负样本是假负样本的概率,然后通过重要性采样进行无偏CVR预测。此外,我们设计了一个双分布框架,充分利用即时正样本。全面的实验表明DEFUSE在公共和工业数据集上都比最先进的方法表现更好。
我们的主要贡献可以总结如下:
- 我们强调了以更细粒度划分观察样本的重要性,这对于准确的的重要性采样建模至关重要。
- 我们提出了一种无偏重要性采样方法DEFUSE,并采用两步优化来解决延迟反馈问题。此外,我们在流式学习中实现了双分布建模框架,充分利用即时正样本。
- 我们在公共和工业数据集上进行了广泛的实验,证明了我们的DEFUSE的最先进的性能。
2.相关工作
2.1 延迟反馈模型
在预测转化率(CVR)的研究中,学习延迟反馈已经受到了相当大的关注。Chapelle [2] 假设延迟分布是指数的,并提出了两个广义线性模型,分别用于预测CVR和延迟时间。然而,这种强假设可能在实践中难以模拟延迟分布。为了解决这个问题,[29] 提出了一种非参数延迟反馈模型用于CVR预测,该模型利用核密度估计并将多个高斯分布结合起来近似实际的延迟分布。此外,一些近期的工作[23, 25] 通过按天slot离散化延迟时间,实现了对延迟反馈问题的细粒度生存分析。然而,上述方法的一个显著缺点是它们都只尝试优化观察到的转化信息,而不是实际的延迟转化,这无法充分利用稀疏的正反馈。
2.2 无偏CVR估计
与以前的方法不同,当前的主流方法采用重要性采样方法来估计真实的期望 $ w_{\text{r}} $。Ktena 等人 [10] 假设所有样本最初都被标记为负样本,然后在它们转化时复制带有正标签的样本并将它们引入训练流程。为了进一步从有偏分布中建模CVR预测,他们提出了两种假负样本加权(FNW)和假负样本校准(FNC),利用重要性采样[1]。然而,它只关注样本的及时性,忽略了标签的准确性。为了解决这个问题,ES-DFM [12] 引入了一个观察窗口来研究在窗口内等待更准确标签与利用窗口外更新鲜训练数据之间的权衡。Gu 等人 [5] 进一步复制观察窗口中的真实负样本和稀疏正样本,以消除通过复制延迟正样本引入的特征分布偏差。
2.3 延迟摇臂赌博机
延迟反馈在摇臂赌博机方法中引起了很多关注[17, 20, 20]。以前的方法是将延迟反馈建模视为一个顺序决策问题,并最大化长期奖励[6, 8, 24]。Joulani 等人 [8] 提供了将为非延迟开发的算法转换为延迟的元算法,并分析了延迟反馈在流式学习问题中的影响。[24] 提供了一个随机延迟摇臂赌博机模型,并在已知延迟分布的假设下证明了在审查和未审查设置下的算法。[6] 试图检查连续动作空间中的摇臂赌博机流式学习,并引入了一个带有延迟奖励和摇臂赌博机反馈的无梯度学习策略。
3 预备知识
在本节中,我们首先阐述带有延迟反馈的流式CVR预测问题。然后,我们简要介绍以前方法中使用的标准重要性采样算法。本文中使用的所有符号在表2中进行了总结。
3.1 问题阐述
在标准的CVR预测任务中,输入可以正式定义为 $ (x, y) \sim p(x, y) $,其中:
- $x$ 表示特征,$ y \in \lbrace 0, 1 \rbrace $ 是转化标签
一个通用的CVR预测模型的目标是:通过优化以下理想的损失来学习二元分类器函数 $f$ 的参数 $\theta$:
\[L_{\text{ideal}} = \mathbb{E}_{(x, y) \sim p} \left[ \ell(y, f_{\theta}(x)) \right]\]
…(1)
其中:
- $ (x, y) $ 是从真实分布 $ p(x, y) $ 中抽取的训练样本,
- $ \ell $ 表示分类损失,例如广泛使用的交叉熵损失。
然而,如上所述,由于引入了观察窗口,发生在观察窗口之外的转化点击将首先被视为假负样本。因此,观察分布 $ q(x, y) $ 总是与真实分布 $ p(x, y) $ 有偏。
更具体地说,如图1所示,在在线广告系统中有四种类型的样本:
- 即时正样本(IP),例如 $ d < w_o $。在观察窗口内转化的样本被标记为即时正样本。
- 假负样本(FN),例如 $ w_o < d < w_a $。假负样本指的是由于延迟转化而在训练时被错误标记为负的样本。
- 真实负样本(RN),例如 $ d > w_a $ 或 $ d = \infty $。在等待足够长的归因窗口 $ w_a $ 后仍未转化的样本被标记为真实负样本。
- 延迟正样本(DP)。这些样本在转化时被复制,并带有正标签被引入到训练流程中。
3.2 重要性采样
重要性采样已经在许多近期任务中得到了广泛的研究和应用,例如反事实学习[26]和无偏估计[5, 27]。通常,以前的方法使用重要性采样来估计从观察到的分布中训练损失的期望,并重新编写理想的CVR损失函数如下:
\[L = \mathbb{E}_{(x, y) \sim p} \left[ \ell(y, f_{\theta}(x)) \right] \\
= \mathbb{E}_{(x, y) \sim q} \left[ w(x, y) \ell(y, f_{\theta}(x)) \right]\]
…(2)(3)
其中:
- $ f_{\theta} $ 是追求无偏CVR预测的期望CVR模型
- $ p(x, y) $ 和 $ q(x, y) $ 分别表示真实情况和观察到的及复制的分布的联合密度函数,
- $ w(x, y) $ 是由重要性采样引入的真实情况分布相对于观察到的及复制的分布的似然比率,追求无偏的 $ f^*_{\theta}(x) $。
目前,通过假设或确保 $ p(x) \approx q(x) $ 并精心设计样本复制机制,所有发布的方法[5, 10, 27]都应用了首次在[10]中发表的 $ w(x, y) $ 的公式推导,如下所示:
\[L = \mathbb{E}_{(x,y) \sim q(x,y)} \left[ w(x, y) \ell(y, f_{\theta}(x)) \right] \\
= \int q(x) dx \int \frac{q(y | x)}{p(x, y)} \ell(x, y; f_{\theta}(x)) dy \\
= \int \frac{q(x)}{p(x)} dx \int \frac{q(y | x)}{q(y | x)} \ell(x, y; f_{\theta}(x)) dy \\
\approx \int q(x) dx \int \frac{p(y | x)}{q(y | x)} \ell(x, y; f_{\theta}(x)) dy \\
\approx \sum_{(x_i, y_i) \in D} \left[ y_i \frac{p(y_i = 1 | x_i)}{q(y_i = 1 | x_i)} \log f_{\theta}(x_i) + (1 - y_i) \frac{p(y_i = 0 | x_i)}{q(y_i = 0 | x_i)} \log (1 - f_{\theta}(x_i)) \right],\]
…(4)(5)(6)(7)(8)
其中 D 是观察到的数据集。这些发布方法之间的差异主要在于:
- 不同的训练流程设计,例如 $ w_o $ 的选择和图 2 所示的复制样本的定义,这最终导致了 $ q(y \mid x) $ 的不同公式。
- 对 $ p(d > w_o \mid x, y = 1) $ 或 $ p(d > w_o \mid y = 1)p(y = 1 \mid x) $ 等的不同建模选择。
图2 在线延迟反馈建模旧方法的数据分布
如图2 所示:
- FNW/FNC [10]:首先将 $w_o=0$,并在点击时将所有点击标记为负样本,所有正样本在转化时被收集并作为DP重放(replay);
- ES-DFM[27]和DEFER[5]:保持合理的观察时间$w_o$,因此,在$t_0+w_o$ 内发生的转化的点击可以被正确标记为IP。
- ES-DFM和 DEFER之间的唯一区别:在于 ES-DFM 仅重放(replay)延迟的正样本,而 DEFER则复制所有点击(包括IP和RN)。
- ES-DFM和DEFER都选择将 $ f_{\text{dp}}(x) = p(d > w_o, y = 1 \mid x) = p(d > w_o \mid x, y = 1)p(y = 1 \mid x) $ 作为一个整体来建模。
这些方法在样本复制机制上的这些差异最终导致了它们在公式(9)、(10)和(11)中 $q(y \mid x)$的不同公式:
\[q_{\text{fnw}}(y = 0 | x) = \frac{1}{1 + p(y = 1 | x)} \\
q_{\text{esdfm}}(y = 0 | x) = \frac{p(y = 0 | x) + f_{\text{dp}}(x)}{1 + f_{\text{dp}}(x)} \\
q_{\text{defer}}(y = 0 | x) = \frac{p(y = 0 | x) + 1}{2f_{\text{dp}}(x)}\]
…(9)(10)(11)
3.2.1 局限性
尽管这些发布的方法在减少偏差方面取得了成功,我们注意到由于在推导 $ w(x, y) $ 的公式时引入了一个隐藏的缺陷,这些方法仍然未能实现无偏的CVR预测。通常,重要性采样假设在从 $ p(x, y) $ 过渡到 $ q(x, y) $ 过程中没有值的修改,然而在第3.1节提到的CVR预测中,即使是相同的点击,从 $q(x,y)$ 观察到的标签可能会暂时偏离来自$p(x,y)$ 的真实标签(ground-truth label)。更具体和严格地说,如果我们将观察到的标签(observed label)区分为v,将有偏分布重新表示为$q(x,v)$,我们有:
\[y = y(v, d) =
\begin{cases}
1, & \text{if } v = 1 \\
0, & \text{if } v = 0 \text{ and } d = +\infty \\
1, & \text{if } v = 0 \text{ and } d > w_o.
\end{cases}\]
…(12)
结果,本应被标记为 $ \frac{p(d>w_o, y=1 \mid x)}{q(y=0 \mid x)} $ 的假负样本,在公式(8)中被错误地当作真实的负样本处理,导致性能次优和CVR预测的偏差。
4.方法
在本节中,我们详细地介绍了我们提出的方法:带有无偏估计(UnbiaSed Estimation)的延迟反馈建模(DEFUSE:DElayed Feedback modeling with UnbiaSed Estimation)。我们:
- 首先介绍我们的无偏估计校正,它分别对四种类型的样本的重要性进行加权。
- 然后,我们为DEFUSE提出了一个两步优化方法。
- 最后,为了进一步减少由观察到的有偏分布造成的影响,我们设计了一个双分布(bi-distribution)建模框架,充分利用在实际分布下即时转化的情况。
请注意,我们的DEFUSE适用于不同的训练流程,但为了便于描述,我们将在ES-DFM的训练流程设计之上介绍我们的方法。
4.1 无偏延迟反馈建模
如我们在3.2.1节中所描述的,我们的目标是:通过进一步优化假负样本的损失来实现无偏的延迟反馈建模。根据公式(5,12),我们可以获取无偏估计如下:
\[L_{\text{ub}} = \int q(x) dx \int q(v|x) \frac{p(x)}{q(x)} \frac{p(y(v, d) |x )}{q(v|x)} \ell(x, y(v, d); f_{\theta}(x)) dv\]
…(13)
其中:
- $\ell(x, y(v, d); f_{\theta}(x))$ 是带有标签 $ \tilde{y}(v, d) $ 的观察样本的损失函数。
- 通常,之前的方法通过假设 $ p(x) \approx q(x) $ [10, 27] 或设计适当的训练流程来保证特征分布的一致性来消除 $ \frac{p(x)}{q(x)} $。
4.1.1 DEFUSE的重要性加权。
在这项工作中,与之前侧重于复制机制的工作不同,我们通过正确评估 $ \ell(x, y(v, d); f_{\theta}(x)) $ 的重要性权重来实现无偏CVR估计。如表3所示,观察到的样本可以正式地分为四个部分。直观地说,如果我们拥有每个部分的所有标签,公式(13)可以重写为:
\[L_{\text{ub}} = \int q(x) [\sum\limits_{v_i} q(v_i | x) w_i(x, y(v_i, d)) \ell(x, y(v_i, d); f_{\theta}(x))] dx\]
…(14)
其中:
- $w_i=\frac{p(x, y(v_i, d))}{q(x, v_i)}$ 且 $i \in \lbrace \text{IP}, \text{FN}, \text{RN}, \text{DP} \rbrace$,遵循 $\sum {v_i}=1$ 且 $v_i \in \lbrace 0, 1 \rbrace $。
请注意,当前的工作仅仅在公式(8)中对观察到的正样本和负样本进行建模,这忽略了假负样本(FN)的影响,导致标签分布的偏差。
为了求解公式(14),我们首先引入一个隐变量z,用来推断观察到的负样本是否是FN,然后分别对这四种观察样本的重要性权重$w_i$进行建模。因此,公式(14)等同于:
\[\underset{\theta}{min} L_{\text{ub}} \\
\Leftrightarrow \underset{\theta}{min} \int q(x) \left[ v \left( w_{\text{DP}} \log f_{\theta}(x) + I_{\text{IP}} (w_{\text{IP}} - w_{\text{DP}}) \log f_{\theta}(x) \right) \\
+ (1 - v)(w_{\text{FN}} \log f_{\theta}(x) z + w_{\text{RN}} \log(1 - f_{\theta}(x)) (1 - z)) \right] dx\]
…(15)
其中:
\[w_{\text{IP}}(x) = w_{\text{RN}}(x) = 1 + f_{\text{dp}}(x)\]
\[w_{\text{DP}}(x) + w_{\text{FN}}(x) = 1 + f_{\text{dp}}(x)\]
其中:
- $ w_{\text{IP}}(x) $、$ w_{\text{DP}}(x) $、$ w_{\text{FN}}(x) $、$ w_{\text{RN}}(x) $ 表示重要性权重;
- $ I_{\text{IP}} $ 是观察到的即时正样本的指示器。
经验上,我们设置: $ w_{\text{DP}}(x) = 1 $ 和 $ w_{\text{FN}}(x) = f_{\text{dp}}(x) $,因为 $ \text{DP} $ 可以被观察到。详细的证明在补充材料中给出。
与标准cross entropy-loss相比,我们集成了一个辅助任务 $f_{\text{dp}}(x)$来对每种类型的样本的重要性权重$w_i$进行建模,而不是直接使用观察到的标签。
4.1.2 优化
此后,剩下的问题是如何选择优化无偏损失函数。由于公式(15)中的 $z$ 是不可获得的,我们通过引入另一个辅助模型 $z(x)$来预测隐藏的$z$,进一步将观察到的负样本分解为真实负样本和假负样本,实现两步优化:
\[L_{\text{neg}} = z(x) w_{\text{FN}} \log f_{\theta}(x) + (1 - z(x)) w_{\text{RN}} \log(1 - f_{\theta}(x))\]
…(16)
其中:
\[z(x) = \frac{p(y = 1, d > w_o | x)}{p(y = 0 | x) + p(y = 1, d > w_o | x)}\]
- $ z(x) $ 是假负样本(FN)概率,表示观察到的负样本是真实正样本的概率。
在实践中,我们实现了两种方式来建模 $ z(x) $:
- $ z_1(x) = 1 - f_{\text{rn}}(x) $。这采用二元分类模型 $ f_{\text{rn}}(x) $ 来预测观察到的负样本是真实负样本的概率。对于 $ f_{\text{rn}} $ 模型的训练,排除了观察到的正样本,然后将负样本标记为1,延迟正样本标记为0。
- $ z_2(x) = \frac{f_{\text{dp}}(x)}{f_{\text{dp}}(x) + 1 - f_{\theta}(x)} $。这采用CVR模型 $ f_{\theta}(x) $ 和延迟模型 $ f_{\text{dp}}(x) $ 来间接建模假负样本概率。对于 $ f_{\text{dp}}(x) $ 的学习,将延迟正样本标记为1,其他的标记为0。
4.2 双分布建模
尽管理论上是无偏的,但我们的DEFUSE一个潜在的缺点是:重要性权重 $ w $、隐藏模型 $ z(x) $ 尤其是乘法项 $ z(x)w_{\text{FN}} $ 和 $ (1-z(x))w_{\text{RN}} $ 的估计可能会导致高方差。这通常意味着收敛速度慢,并导致次优性能,尤其是在反馈相对稀疏的情况下。因此,我们努力构建一个可以充分利用观察到的分布中的样本的替代学习框架。
回想一下,与之前的方法仅使用观察到的正样本和负样本不同,我们将样本分为四种类型。IP和DP分别表示即时转化和延迟转化。
因此,我们采用多任务学习 [11, 15, 19, 26] 框架来联合优化以下子任务:
- 1) 窗口内(Inw)模型:预测观察窗口 $ w_o $ 内的IP概率 $ F_{\text{IP}}(x) = p(y = 1, d \leq w_o \mid x) $。
- 2) 窗口外(Outw)模型:预测 $ w_o $ 之外的DP概率 $ F_{\text{DP}}(x) $。然后,整体转化概率可以形式化为:
\[p(y = 1 | x) = F_{\text{IP}}(x) + F_{\text{DP}}(x).\]
…(18)
图3 双分布模型的示意图,其中Exp(专家网络),Share Exp(共享专家网络),Outw Exp(外部专家网络)分别表示单层的窗口内(in_window)、共享(shared)和窗口外(out_window)专家网络。
值得一提的是,如图3b所示,
- 对于任务1,使用样本是非重复且正确标记的,因此 $ F_{\text{IP}}(x) $ 模型可以直接在无偏的真实分布上进行训练。
- 对于任务2,$ F_{\text{DP}}(x) $ 模型必须在与FNW [10]相同的有偏观察分布上进行训练,其中 $ w’_o = 0 $。
因此,我们将我们的DEFUSE实现到 $ F_{\text{DP}}(x) $ 模型中,以通过重要性采样实现无偏估计。类似于公式(15)的推导,我们有:
\[L_{\text{IP}} = \int p(x, y_{\text{IP}}) \left[ y_{\text{IP}} \log f_{\text{IP}}(x) + (1 - y_{\text{IP}}) \log(1 - f_{\text{IP}}(x)) \right] dx\]
…(19)
\[L_{\text{DP}} = \int q(x, v_{\text{DP}}) \left[ v_{\text{DP}}w'_{\text{DP}}(x) \log f_{\text{DP}}(x) \\
+ (1 - v_{\text{DP}})w'_{\text{FN}}(x)z'(x) \log f_{\text{DP}}(x) \\
+ (1 - v_{\text{DP}})w'_{\text{RN}}(x)(1 - z'(x)) \log(1 - f_{\text{DP}}(x)) \right] dx,\]
…(20)
其中:
- $ p(x, y_{\text{IP}}) $,$ q(x, v_{\text{DP}}) $ 分别表示子任务的训练数据集的分布,
- $w’{\text{DP}}(x), w’{\text{FN}}(x), w’_{\text{RN}}(x) $ 是重要性权重,
- $ z’(x) $ 作为进一步推断假负样本的隐藏模型。
最后,我们设计了如图3a所示的多任务学习架构,通过联合优化联合损失来学习所需的CVR模型:
\[L = L_{\text{IP}} + L_{\text{DP}}.\]
…(21)
通过这样做,我们将延迟反馈建模分为一个无偏的 $ \text{in_window} $ 预测和一个基于重要性采样的 $ \text{out_window} $ 预测任务。注意,只有第二部分需要用重要性权重和隐藏变量z进行训练,这意味着通过推断 $ w $ 和 $ z $ 引入的高方差负面影响可以有效地限制。
附录: