阿里在《Real Negatives Matter: Continuous Training with Real Negatives for Delayed Feedback Modeling》中提出了一种延迟建模方式：
抽要
CVR预估的一个难点是：转化会有延迟，并且在点击完较长时间后才发生。这种延迟反馈会提出一个新挑战：新数据会对连续训练（continuous training）有益，但在训练时并不会具有完整的label信息。为了平衡模型的新鲜度（freshness）和label确定性（label certainty），之前的方法会设置一个较短的等待窗口(waiting window)，或者甚至不用等转化信号。如果转化发生在等待窗口外，该样本将被复制，带上一个postive label，并被吸收到training pipeline中。然而，这种方法具有一些问题：
- 首先，他们假设：观察到的feature分布仍与实际分布是相同的。但该假设不会成立，因为有重复样本
- 第二，转化动作的确定度(certainty)在商业系统中是稀疏的。
这些问题会在延迟反馈建模期间引入bias。在本paper中，我们提出了DElayed FEedback modeling with Real negatives（DEFER）方法来解决这些问题。提出的方法会吸收真负样本到training pipeline中。真负样本能确保观察到的feature分布与实际分布等价，从而减少bias。真负样本的加入，也会带来更多关于转化的确定信息。为了纠正分布偏移（distribution shift），DEFFR会采用importance sampling来对loss function进行加权。工作数据集上的实验结果，验证了DEFFR的优越性。DEFFR会在阿里的展示广告系统上部署，并在多个场景下在CVR上获得了6%的提升。本paper中的代码和数据是开源的。
1.介绍
2.相关工作
一些之前的工作主要关注于delayed feedback问题【13】，这些方法并不是连续训练的，会忽略掉被错误标记的负样本。例如，如果模型在30天数据上进行训练，归属窗口（attribution window）是7天（在一个点击和一个转化间的延迟可能从不会超过7天），接着最近7天中的负样本的labels可能会不正常，因为转化可能发生在未来。注意，如果点击刚发生，negative label很有可能是不正确的。
2.1 Delayed Feedback Models
在展示广告中，因为活跃的advertisers、ad campaigns和users的变化，分布是动态变化的。例如，当新的ad campaigns被添加到系统中时，基于过去数据构建的模型可能会对其它新的ad campaigns表现不好。为了捕获数据中的变化，机器学习模型会持续进行更新来保持新鲜。最终，在训练期间，会设置一个等待窗口（waiting window）：转化被归属到在该等待窗口中发生的一个点击。接着，新的样本会被持续训练（continuous training）的训练算法所吸收。然而，由于窗口较短，持续学习方法可能会引入许多被错误标记的负样本（假负：fake negatives）。为了纠正由fake negatives引入的bias，【2，26】提出了delayed feedback models。延迟反馈建模（delayes feedback modeling）首先由DFM[2]提出。在DFM中，一个负样本会被看成是一个unlabeled样本，因为转化还未发生。除了预估CVR以外，CFM也会引入第二个模型，它会捕获在点击和转化间的期望延迟（expected delay），假设延迟分布遵循指数分布。这两个模型的训练是联合训练的（jointly）。注意，delayed feedback modeling也与存活时间分析（survival time analysis）紧密关联，它会研究存活时间的分布。在实际上，可能违反指数假设。为了解决该问题，Yoshikawa等【26】提出了一个无参数的delayed feedback model来进行CVR预估，它可以在没有假设一个参数分布的情况下，表示time delay的分布。
Ktena【12】采用一个持续训练的模式，通过初始使用一个负样本来包含所有样本。如果一个正向的engagement发生，该样本会复制上正标记（postive label），并在第二次时被包含在训练算法中。这里，这种有偏观察数据分布包含了来自实际数据分布会被标记为负样本的所有样本，以及原始正样本。为了学习来自bias分布的模型，ktena[12]提出了两个loss function FNW和FNC，它会利用importance sampling来处理分布偏移（distribution shift）。除了在初始将所有样本标记成负样本外，Yasui[25]提出了一种feedback shift importance weighting算法，在该算法中，模型会在一个特定时间间隔中的真实转化。然而，它不会允许数据纠正（data correction），例如，重复的正样本（当未来发生一个转化时）。为了发现在模型训练中的延迟与假负样本率（fake negative rate）间的一个tradeoff，ESDFM【24】会建模在观察到的转化分布和真实化分布间的关系。
图2 真负样本、假负样本、正样本的图示。这里，waiting window指的是在点击时间和在样本被取到训练pipeline间的时间间隔。
- 一个真负样本指的是：样本没有发生转化。
- 一个假负样本指的是：样本的转化发生在waiting window外，但仍在attribution window内。
- 一个正样本指的是：样本的转化发生在waiting window内
2.2 Delayed Bandits
存在一些bandit算法[10,18,22]，它们会研究延迟反馈建模。这些bandit算法的目标是，做出顺序决策，以便最小化累积遗忘（cumulative regret）。Joulani[10]分析了在在线学习算法的regret的延迟影响，并表明：延迟会以乘法方式增加在对抗问题（adversarial problems）中的regret，以加法方式增加在随机问题（stochastic problems）的regret。Pike【18】研究了带延迟的bandits问题，会聚合anonymous feedback。Vernade【22】则研究了随机延迟bandit设置，并提供了一个在假设延迟分布是已知下的完全分析。
3.前提
我们首先给出一个关于在线CVR建模的简单介绍。接着我们会引入之前的方法是如何解决CVR预估的延迟反馈的。
3.1 背景
在CVR预估中，模型会将输入看成是：\((x,y) \sim (X, Y)\)，
其中：
- x是feature，
- $y \in \lbrace 0, 1\rbrace $是转化标签（conversion label）
CVR预估的目标是：学习一个具有参数$\theta$的函数f，它会最小化从数据分布中抽样的样本的泛化错误（genrealization error）：
\[E_{(x,y) \sim (X,Y)} [l(x,y; f_{\theta}(x))]\]…(1)
其中：
- l是loss function。
由于转化可能延迟，一些样本会通过传统的监督学习方法被不正确标记成负样本。
- z：在转化和点击期间的duration我们将它标记为z。如果该样本没有实际转化，$z = +\infty$。
- $w_1, w_2$分别分别是等待窗口和归属窗口的长度，并且$w_2 > w_1$。
如图2所示，在延迟反馈建模中存在三种类型的样本：
- 真负样本（Real negatives）：$z > w_2$。真负样本是没有发生转化的样本
- 假负样本（Fake negatives）：$w_1 < z < w_2$。假负样本是在训练时没有发生转化并且被误标记为负样本的样本，因为它的等待时间（waiting window）太短了。
- 正样本（Positives）：$z < w_1$。正样本指的是在等待窗口中具有转化动作的样本
注意，假负样本也是正样本，但转化并没有发生在等待窗口中。一种naive strategy是，等待一个足够长的窗口来确保大多数labels会是正确，来减小假负样本的数目。然而，在展示广告系统中，数据分布是动态变化的，例如：新的ad campaigns会添加到系统中。为了捕获数据的最新变化，CVR模型会持续更新。这样，它需要对模型新鲜度（model freshness）和标签确定度（label certainty）间进行权衡。之前的方法会通过设置一个短的等待窗口等待立即转化（immediate conversions）来解决该问题。为了纠正label噪声，假负样本会在当engagement发生时会复制一个正标记（postive label）【12】。这个重复的样本会被包含到训练管线中（training pipeline）。这里如图1(a)所示，观察到的分布包含了4部分：真负样本、正样本、假负样本、重复样本（带正标签的假复样本拷贝）。由于直接使用假负样本训练，会误导最优化的方向，之前的方法开发了多种方式来纠正分布偏移问题。
图1 (a) 之前的在线延迟反馈方法的data pipeline，它会复制具有positive labels的假负样本 (b) 提出的方法的data pipeline。提出的方法会复制正样本和真负样本。在复制后，特征分布与实际分布仍保持一致
3.2 假负样本加权（Fake Negative Weighted）
由于在观察分布与实际分布间的不一致（disparity），会采用importance sampling来纠正分布偏移（distribution shift）。Ktena【12】提出了假负样本加权（FNW：fake negative weighted）方法。
CVR预估的loss function可以被写成：
\[\begin{align} L = E_{(x,y) \sim p} l(x,y; f_{\theta}(x)) \\ = \int \int p(x) q(y | x) \frac{p(y|x)}{q(y|x)} l(x,y; f_{\theta}(x)) dxdy \\ \approx \int \int q(x) q(y | x) \frac{p(y|x)}{q(y|x)} l(x,y; f_{\theta}(x)) dxdy \\ = E_{(x,y) \sim q} \frac{p(y|x)}{q(y|x)} l(x,y; f_{\theta}(x)) \end{align}\]…（2）
其中：
- q是有偏观察分布（biased observed distribution）
由于包含重复正样本，观察到的特征分布q(x)不等于实际特征分布p(x)。FNW假设：\(p(x) \approx q(x)\)，它会引入额外的bias到延迟反馈建模中。
在FNW中，没有设置waiting window，样本会立即看成是带负标签的负样本。一旦用户与ad有交互，相同的数据点使用一个正标签传给模型。这里，我们可以获得：
\[q(x \mid y = 0) = p(x), q(x \mid y = 1) = p(x \mid y = 1)\]其中：
- $q(y=0) = \frac{1}{1+p(y=1)}$
在有偏分布中观察到的一个转化的概率为：
\[q(y = 1 | x) = \frac{q(y = 1)q(x | y = 1)}{q(y = 1)q(x | y = 1) + q(y = 0)q(x | y = 0)} \\ = \frac{p(y=1)}{1+p(y=1)} \cdot \frac{p(x | y = 1)}{p(x | y = 1) + \frac{1}{1+p(y=1)}p(x)} \\ = \frac{p(y = 1|x)}{1 + p(y = 1|x)}\]同样，观察到负样本在有偏分布中的概率可以计算为：
\[q(y=0 | x) = \frac{1}{1+p(y=1|x)}\]…(4)
通过替换在等式(2)中的等式3和等式4，loss function可以重写为：
\[L = -\sum\limits_{x,y} y(1+p(y=1|x))log f_{\theta}(x) + (1-y)p(y=0|x) ((1+p(y=1|x)) log(1-f_{\theta}(x))\]…(5)
由于\(p(y=1 \mid x)\)不能被访问，FNW会将它替代为模型估计\(f_{\theta}\)，并在训练期间通过它对梯度传播进行stop。
3.3 假负样本校准（Fake Negative Calibraiton）
Fake negative calibration（FNC）会学习一个函数，它直接估计有偏分布q。接着FNC会通过以下calibration来获得函数\(p(y=1 \mid x)\)：
\[p(y=1 | x) = \frac{q(y=1 | x)}{1 - q(y=1 | x)}\]…(6)
4.使用真负样本进行延迟反馈建模
在本节中，我们会详细介绍DEFER：DElayed FEedback modeling with Real negatives。我们：首先引入在DEFER中的数据流，它会复制真负样本（real negatives）来纠正分布漂移。基于设计好的数据流，DEFER会使用importance sampling来纠正分布漂移。其它方法也会使用真负样本进行训练，我们会派生出相应的loss function。最终，我们会共享我们的商业平台的部署经验，以及不同的转化归属机制、生产环境预算等。
4.1 数据流
如上所述，之前的持续训练方法会包含假负样本，以便在有噪声信号开销下捕获新鲜度（freshness）。为了引入更多确定的转化信息，会包含重复样本，我们使用importance sampling来纠正分布漂移。然而，这些方法都具有一些问题：
- 首先，重复样本会改变特征分布。该近似\(q(x) \approx p(x)\)会引入额外偏差。
- 再者，所有关于转化动作的特定信息会来自于正样本，这在CVR预估中是不足的。这使得模型很难学习并且仍表现良好。
为了减少bias，并且不伤害新鲜度，我们会包含重复正样本以及重复真负样本到训练pipeline中。
具体的，在重新设计过的数据pipeline中，我们让每个样本都具有一个waiting window $w_1$来等待转化信号。waiting window对于所有样本或者指定样本(sample-specific)来说是相同的。使用一个指定样本的窗口(sample-specific window)的原因是，不同的商品具有不同的延迟分布。例如，对比起便宜商品，昂贵的商品会具有较长的期望转化次数（expected conversion times），因而需要一个更长的窗口来等待转化信号。设置sample-specific window的一个策略是：定义多个window长度，来训练一个multi-class分类模型 $P_{length}(w_1 \mid x)$并预测waiting window长度：
\[w_1 = \underset{w}{argmax} P_{waiting} (w | x)\]…(7)
在该窗口中具有转化的样本，会被标记成正样本；没有转化的样本会是假负样本或者真负样本。对于那些假负样本，如果之后在归属窗口中发生转化，我们会将这些样本带上正标签包含到pipeline中。对于那些最终不会发生转化的真负样本，我们也会进行复制，并将它们包含到训练pipeline中。这种重复会带来关于转化信号的更多确定信息。因而，在提出的方法中存在4种样本，如图1(b)所示，真负样本、正样本、假负样本、带真实label的重复样本（可以是正label，也可以是负label）。
4.2 Loss function
由于在观测到的分布与实际分布间的不一致，提出的方法会使用importance sampling来纠正分布偏移。有了重复样本的包含，我们可以获得：\(q(x) = p(x)\)，以及联合概率 \(q(x,y=0)\)可以被计算为：
\[q(x,y = 0) = p(x, y=0) + \frac{1}{2} p (x, y=1, z > w_1)\]…(8)
条件概率$q(y=0 \mid x)$可以被写成：
\[q(y=0 | x) = \frac{q(x,y=0)}{q(x)} \\ = \frac{p(x,y=0)+\frac{1}{2} p(x,y=1, z > w_1)}{p(x)} \\ = p(y=0 | x) + \frac{1}{2} p_{dp}(x)\]其中：
- $p_{dp}(x) = p(x, y=1, z>w_1 \mid x)$是x是一个假样本的概率。
相似的，$q(y=1 \mid x)$可以被写成：
\[q(y=1 | x) = p(y=1 | x) - \frac{1}{2} p_{dp}(x)\]…(10)
接着，根据等式(2)，我们可以为x计算importance sampling：
\[\frac{p(y=0 | x)}{q(y=0 | x)} = \frac{p(y=0 | x)}{p(y=0|x) + \frac{1}{2} p_{dp}(x)} \\ \frac{p(y=1 | x)}{q(y=1 | x)} = \frac{p(y=1 | x)}{p(y=1|x) + \frac{1}{2} p_{dp}(x)}\]…(11)
因而，importance weighed CVR loss funciton可以被公式化为：
\[L = - \sum\limits_{x,y} y \frac{p(y=1 | x)}{p(y=1|x) - \frac{1}{2}p_{dp}(x)} log f_{\theta}(x) \\ + (1-y) \frac{p(y=0 | x)}{p(y=0 | x) + \frac{1}{2} p_{dp}(x)} log(1-f_{\theta}(x))\]…(12)
由于\(p(y=1 \mid x), p(y=0 \mid x)\)不能被访问，我们可以使用模型估计\(f_{\theta}(x)\)和\(1 - f_{\theta}(x)\)来分别替代\(p(y=1 \mid x), p(y=0 \mid x)\)。对于\(p_{dp}(x)\)，我们会训练一个分类器\(f_{dp}\)来预测x是一个假负样本的概率。如【12】所示，我们会通过importance weight来停止梯度传播。因此，等式(13)可以被重写成：
\[L = -\sum_{x,y} y [\frac{f_{\theta}(x)}{f_{\theta}(x) - \frac{1}{2} f_{dp}(x)}] log f_{\theta}(x) \\ + (1-y) [\frac{1 - f_{\theta}(x)}{1 - f_{\theta}(x) + \frac{1}{2} f_{dp}(x)}] log(1 - f_{\theta}(x))\]其中\([\cdot]\)意味着停止梯度操作。
4.3 变种
对于其它方法（像FNW和FNC），重复的真负样本可以被包含来提升学习。我们为FNW和FNC来派生相应的loss function。
4.3.1 FNW
对于FNW，我们有：
\[q(y=1 | x) = \frac{p(y=1 | x)}{1 + p(y=1 | x) + p(y=0 | x)} = \frac{p(y=1 | x)}{2} \\ q(y=0 | x) = \frac{1 + p(y=0 | x)}{1 + p(y=1 | x) + p(y=0 | x)} = \frac{1 + p(y=0 | x)}{2}\]…(14)(15)
接着我们有：
\[\frac{p(y=1 | x)}{q(y=1 | x)} = 2 \\ \frac{p(y=0 | x)}{q(y=0 | x)} = \frac{2 p(y=0 | x)}{1 + p(y=0 | x)}\]…(16)
最终，loss function可以重新公式化为：
\[L = - \sum\limits_{x,y} 2y log f_{\theta}(x) + (1-y) p(y=0 | x) (\frac{2p(y=0|x)}{1+p(y=0|x)}) log(1 - f_{\theta}(x))\]…(17)
4.3.2 FNC
相似的，对于FNC，我们有：
\[p(y = 1 | x) = 2q(y=1 | x)\]…(18)
4.4 真负样本的生产环境设定
在展示公告中，不同的商业场景根据不同的用户行为，经常会设置不同的归属窗口。例如，在阿里巴巴，一些业务场景会将归属窗口设置为1天，而一些业务场景则会将归属窗口设置为7天。需要注意的是，真负样本的延迟时间等于正样本的最大延迟时间，并且模型新鲜度不可能受真负样本所大大影响，但会带来更多的确定label来训练算法。对于一个长转化窗口的业务场景，重复样本的引入，会增加维持数据缓存的额外的基础设施开销。因而，对于长转化窗口场景，我们会通过设置一个较短的窗口\(w_3 (w_1 < w_3 < w_2)\)。在\(w_3\)之前没有转化的样本，可以被近似为真负样本并直接放到训练算法中。对于具有短归属窗口的业务场景，我们不会采用近似，会包含真负样本。换句话说，我们将在线延迟反馈建模划分成2个settings：短的归属窗口和长归属窗口。对于首者，我们直接使用模型。对于第二个，我们假设：真负样本会在一个时间窗口\(w_3(w_1 < w_3 < w_2)\)之后被获取。相似的，\(w_3\)对于所有样本来说都是固定的，或者通过一个多分类模型进行预测：
\[w_3 = argmax_w P_{attribution} (w | x)\]…(19)
4.5 离线训练方法
对于商业平台来说会使用离线训练，我们也提出了一个方法，它在许多场景被证明是有用的。
图3
如图3所示，我们提出的离线方法，会使用多任务学习（multi-task learning）通过利用在转化时间内包含的信息来提升泛化性。具体的，模型在shared bottom layers的top上具有N+1个heads。其中的一个head会预测：点击是否会被实际转化的概率，表示为\(p(y=1 \mid x)\)。其它heads会预测转化是否会在预定义的time window \(w_1, w_2, \cdots, w_N\)内发生：
\[p(z < w_n, y=1 | x) = p(z < w_n | y=1, x) * p(y=1 | x)\]…(20)
\(y_n\)表示样本在\(w_n\)是否具有转化的概率，loss function可以被写成：
\[L = - \sum_n \sum_x y_n log p(z < w_n, y=1 | x) \\ - \sum_n \sum_x (1-y_n) log(1 - p(z < w_n, y=1 | x)) \\ - \sum_x y log p(y=1|x) - \sum_x (1-y) log(1-p(y=1 | x))\]由于接近训练天数末尾的样本，可能具有所有的N+1个labels，我们只会根据观察到的labels更新相应的参数。对于一个样本来说，如果预定义的\(w_n, \cdots, w_N\)窗口还未到达，我们只会通过\(p(y=1, z<w_1 \mid x), \cdots, p(y=1, z<w_{n-1} \mid x)\)，当其它heads的参数在阻断时使用观察到的labels来来更新参数。注意，\(p(y=1 \mid x)\)也会通过\(p(y=1, z<w_1 \mid x), \cdots, p(y=1, z< w_{n-1} \mid x)\)的梯度进行更新。例如，5天作为第三个时间窗口。如果在从过去的第4天有样本点击，我们只会从\(p(z < w_1, y=1 \mid x), p(z<w_2, y=1\mid x)\)来更新参数。对于从过去的第7天前有过样本点击，那所有参数会同时更新。