Delayed Feedback Modeling for the Entire Space Conversion Rate Prediction

The target of conversion model is to estimate the probability of $pCVR=P(C=1|Y=1,X=x,E=e)$. Similar to many previous work like (Chapelle 2014; Su et al. 2020), we assume that:

$\displaystyle P(C|Y=1,X,E)=P(C|Y=1,X)$

(1)

This makes sense because the elapsed time since the click usually does not make any influence on the final conversion. To eliminate the sample selection bias and data sparsity problem, we refer to the idea of ESMM and ESM²  (Ma et al. 2018; Wen et al. 2020). By making use of the sequential pattern of user actions ”impression $\rightarrow$ click $\rightarrow$ pay”, we construct CTR and post-view click-through & conversion rate (CTCVR) tasks together. Here, we use $pCTR$ and $pCTCVR$ to represent the probability of CTR and CTCVR respectively, where $pCTR=P(Y=1|X=x)$ and $pCTCVR=P(C=1,Y=1|X=x)$. The CVR prediction of the $i$th sample can then be formulated as:

$$P(c_{i}=1|y_{i}=1,x_{i})=\frac{P(c_{i}=1,y_{i}=1|x_{i})}{P(y_{i}=1|x_{i})}$$

(2)

As can be seen from the equation 2, $P(c_{i}=1,y_{i}=1|x_{i})$ and $P(y_{i}=1|x_{i})$ can all be modeled on the entire input space $X$, which greatly helps relieve the problem of sample selection bias. In most situations, the click rate is small, so $P(c_{i}=1|y_{i}=1,x_{i})$ may be larger than 1 and may cause numerical instability. Hence, we model $pCTR$ and $pCTCVR$ at the same time. This helps us avoid the problem of numerical instability. Besides, we are able to model with all CTR samples which helps us get more stable training process and better performance, because the size of CTR samples is much larger than the size of CVR samples. In our neural network framework, the embedding layer is shared which enables CVR network to learn from huge volume of CTR samples and alleviate the data sparsity trouble a lot. Different from  (Ma et al. 2018; Wen et al. 2020), we add time delay model attempting to solve the problem of feedback delay problem.

To address the problem of feedback delay, we model the time delay with reference to the idea of survival analysis(Jr. 2011). Survival analysis is originally used to analyze the expected duration of time until one or more events happen. Corresponding to our problem, conversion can be considered as an ”event” here. We use $f(t)$ to denote the probability density function, which represents the probability that the conversion will happen at time $t$. Then we can get our survival function:

$\displaystyle S(t)=1-\int_{0}^{t}f(t)dt$

(3)

To make our model more general and suitable for different scenarios. We do not make any special assumptions of the distribution, like exponential distribution (Chapelle 2014) or Weibull distribution  (Ji, Wang, and Zhu 2017). Instead, we choose to make use of the features of users, items and context to construct the time delay model, which is more reasonable and easy to generalize to other scenarios. In our algorithm, we first transform the delayed time via day slots. Concretely, the delayed time are divided into $T+2$ bins. The $i$th bin where $i\leq T$ represents that the conversion happens at $i$ days later after the click and $T+1$ indicates that the delay time of conversion is bigger than $T$ days. This is quite reasonable because when $T$ is large, the conversions only occupy a small part and can be recognized as noise. Hence, we put all conversions happened after $T$ days later since the click into the $T+1$ bin. The probability that the conversion happens at the $t$ days since the click can be described as:

$\displaystyle P(D=t|C=1,Y=1,E=e,x)=F(g(x,e),t)$

(4)

where $g(x,e)$ represents the softmax output of the time delay model and $F(\cdot,t)$ is the $t$th value of $g(x,e)$, $t\in[0,T+1]$. For simplicity, we will use $f(t,x,e)$ to represent $F(g(x,e),t)$ in the following content.

By combining the two models of conversion and time delay, we can get the final ESDF. Concrete relations within ESDF can be summarized as below:

• •

  If a conversion has already happened, we have $Z=1$, then $C$ must be 1 and the delay time $D$ can be observed.

  $$Z=1\rightarrow C=1~{}and~{}E>D=d$$

  (5)

• •

  If a conversion has not happened, we have $Z=0$. It is either because the user will not convert or because he will convert later, in other words,

  $$Z=0\rightarrow C=0~{}or~{}E<D$$

  (6)

For the sake of convenience, we define three sets of sample indices:

	$\displaystyle I_{1,1}$	$\displaystyle=\{i|z_{i}=1\&y_{i}=1,i=1,2...,N\}$		(7)
	$\displaystyle I_{0,1}$	$\displaystyle=\{i|z_{i}=0\&y_{i}=1,i=1,2...,N\}$
	$\displaystyle I_{0,0}$	$\displaystyle=\{i|z_{i}=0\&y_{i}=0,i=1,2...,N\}$

We respectively refer to $I_{1,1},I_{0,1},I_{0,0}$ as the observed conversions, unobserved conversion and unclicked samples. Given parameters $\Theta=\{\theta_{ctr},\theta_{ctcvr},\theta_{delay}\}$, the likelihood of ESDF $P(\mathcal{D};\Theta)$ can be factorized as:

	$\displaystyle P(\mathcal{D};\Theta)$	$\displaystyle=\mathop{\Pi}\limits_{i\in I_{1,1}}P(z_{i}=1,y_{i}=1|x_{i},e_{i})$		(8)
		$\displaystyle\times\mathop{\Pi}\limits_{i\in I_{0,1}}P(z_{i}=0,y_{i}=1|x_{i},e_{i})$
		$\displaystyle\times\mathop{\Pi}\limits_{i\in I_{0,0}}P(z_{i}=0,y_{i}=0|x_{i},e_{i})$

Under the assumption (1) and the equivalence (5), the probability $P(z_{i}=1,y_{i}=1|x_{i},e_{i})$ can by written as:

		$\displaystyle P(z_{i}=1,y_{i}=1|x_{i},e_{i})$		(9)
	$\displaystyle=$	$\displaystyle P(c_{i}=1,D=d_{i},y_{i}=1|x_{i},e_{i})$
	$\displaystyle=$	$\displaystyle P(c_{i}=1,y_{i}=1|x_{i},e_{i})P(D=d_{i}|c_{i}=1,y_{i}=1,x_{i},e_{i})$
	$\displaystyle=$	$\displaystyle P(c_{i}=1,y_{i}=1|x_{i})P(D=d_{i}|c_{i}=1,y_{i}=1,x_{i},e_{i})$
	$\displaystyle=$	$\displaystyle q_{i}f(d_{i},x_{i},e_{i})$

where $q_{i}=P(c_{i}=1,y_{i}=1|x_{i})$ and $f(d_{i},x_{i},e_{i})=P(D=d_{i}|c_{i}=1,y_{i}=1,x_{i},e_{i})$ in the last equation. The first equation comes from the relation (5), while the third equation comes from the conditional independence (1). Note that when a conversion has been observed, $e_{i}$ has to be greater or equal to $d_{i}$ here. Furthermore, the probability that sample $i$ has been clicked and the conversion has not been observed yet can be formulated as:

		$\displaystyle P(z_{i}=0,y_{i}=1|x_{i},e_{i})$		(10)
	$\displaystyle=$	$\displaystyle P(z_{i}=0,c_{i}=0,y_{i}=1|x_{i},e_{i})$
	$\displaystyle+$	$\displaystyle P(z_{i}=0,c_{i}=1,y_{i}=1|x_{i},e_{i})$
	$\displaystyle=$	$\displaystyle P(c_{i}=0,y_{i}=1|x_{i})$
	$\displaystyle+$	$\displaystyle P(z_{i}=0,c_{i}=1,y_{i}=1|x_{i},e_{i})$
	$\displaystyle=$	$\displaystyle P(y_{i}=1|x_{i})-P(c_{i}=1,y_{i}=1|x_{i})$
	$\displaystyle+$	$\displaystyle P(c_{i}=1,y_{i}=1|x_{i})P(z_{i}=0|c_{i}=1,y_{i}=1,x_{i},e_{i})$
	$\displaystyle=$	$\displaystyle P(y_{i}=1|x_{i})-q_{i}+q_{i}P(z_{i}=0|c_{i}=1,y_{i}=1,x_{i},e_{i})$

The second equation comes from the conditional independence (1) and the truth $P(z_{i}=0|c_{i}=0,y_{i}=1,x_{i},e_{i})=1$. The probability of delayed conversion is:

		$\displaystyle P(z_{i}=0|c_{i}=1,y_{i}=1,x_{i},e_{i})$		(11)
	$\displaystyle=$	$\displaystyle P(D>e_{i}|c_{i}=1,y_{i}=1,x_{i},e_{i})$
	$\displaystyle=$	$\displaystyle\sum_{t=e_{i}+1}^{T+1}f(t,x_{i},e_{i})$

Finally, the probability that sample $i$ is not clicked is:

		$\displaystyle P(z_{i}=0,y_{i}=0|x_{i},e_{i})$		(12)
	$\displaystyle=$	$\displaystyle P(y_{i}=0|x_{i})P(z_{i}=0|y_{i}=0,x_{i})$
	$\displaystyle=$	$\displaystyle 1-P(y_{i}=1|x_{i})$

The second equation comes from the truth: $P(z_{i}=0|y_{i}=0,x_{i})=1$. By substituting the formula (9),(10), (11),(12) into the likelihood function, we can get the following result. Note that for simplicity, we use $p_{i}$ to represent $P(y_{i}=1|x_{i})$

	$\displaystyle P(\mathcal{D};\Theta)$	$\displaystyle=\mathop{\Pi}\limits_{i\in I_{1,1}}q_{i}f(d_{i},x_{i},e_{i})$		(13)
		$\displaystyle\times\mathop{\Pi}\limits_{i\in I_{0,1}}[p_{i}-q_{i}+q_{i}\sum_{t=e_{i}+1}^{T+1}f(t,x_{i},e_{i})]$
		$\displaystyle\times\mathop{\Pi}\limits_{i\in I_{0,0}}(1-p_{i})$

In this subsection, we explain the learning algorithm for ESDF derived on the basis of Expectation-Maximization (EM) algorithm. EM algorithm is widely used to optimize the maximum likelihood estimation of probabilistic models that depend on hidden variables. Due to the time delay issue, the variable $C$ can not be observed immediately after click occurred. Hence, we treat variable $C$ as the hidden variable. Specifically, we calculate the expectation of $C$ with current model in the expectation step, and maximize the expected log-likelihood according to the expectation of $C$ in the maximization step.

Expectation Step For a given sample, we need to calculate the posterior probability of the hidden variable. We denote the expectation for sample $i$ as $w_{i}$. It is trivial to get the following equations:

	$\displaystyle w_{i}$	$\displaystyle=1,\forall i\in I_{1,1}$		(14)
	$\displaystyle w_{i}$	$\displaystyle=0,\forall i\in I_{0,0}$

The first equation comes from the relation (5). For $i\in I_{0,1}$, we can not observe the conversion directly and need to estimate the expectation of $C$ given $Z=0~{}\&~{}Y=1$.

	$\displaystyle w_{i}$	$\displaystyle=P(c_{i}=1|z_{i}=0,y_{i}=1,x_{i},e_{i})$		(15)
		$\displaystyle=\frac{P(c_{i}=1|y_{i}=1,x_{i})P(z_{i}=0|c_{i}=1,y_{i}=1,x_{i},e_{i})}{P(z_{i}=0|y_{i}=1,x_{i},e_{i})}$
		$\displaystyle=\frac{q_{i}\sum_{t=e_{i}+1}^{T+1}f(t,x_{i},e_{i})}{p_{i}-q_{i}+q_{i}\sum_{t=e_{i}+1}^{T+1}f(t,x_{i},e_{i})}$

Maximization Step In maximization step, we maximize the expected log-likelihood according to the distribution computed during the expectation step. Based on equations of (13) and (14), the expected log-likelihood loss for $I_{1,1}$ and $I_{0,0}$ can be formulated as:

	$\displaystyle\mathcal{L}_{1,1}$	$\displaystyle=\sum_{i\in I_{1,1}}{w_{i}[~{}log(q_{i})+log(f(d_{i},x_{i},e_{i}))~{}]}$		(16)
		$\displaystyle=\sum_{i\in I_{1,1}}{[~{}log(q_{i})+log(f(d_{i},x_{i},e_{i}))~{}]}$
	$\displaystyle\mathcal{L}_{0,0}$	$\displaystyle=\sum_{u\in I_{0,0}}{(1-w_{i})log(1-p_{i})}$
		$\displaystyle=\sum_{u\in I_{0,0}}{log(1-p_{i})}$

For the expected log-likelihood of $I_{0,1}$, we split it into two parts with $C=0$ and $C=1$, corresponding to the $p_{i}-q_{i}$ and $q_{i}\sum_{t=e_{i}+1}^{T+1}{f(t,x_{i},e_{i})}$ of (13) respectively. The expected log-likelihood can be formulated as:

	$\displaystyle\mathcal{L}_{0,1}$	$\displaystyle=\sum_{i\in I_{0,1}}{w_{i}[~{}log(q_{i})+log(\sum_{t=e_{i}+1}^{T+1}{f(t,x_{i},e_{i})})~{}]}$		(17)
		$\displaystyle+\sum_{i\in I_{0,1}}{(1-w_{i})~{}log(p_{i}-q_{i})}$

Combining the equations of (16) and (17), the quantity to be maximized during maximization step can finally be summarized as:

		$\displaystyle\mathcal{L}(\mathcal{D};\Theta)=\sum_{i}{w_{i}log(q_{i})}$		(18)
		$\displaystyle+\sum_{i}{(1-w_{i})[y_{i}log(p_{i}-q_{i})+(1-y_{i})log(1-p_{i})]}$
		$\displaystyle+\sum_{i}{w_{i}z_{i}log(f(t_{i},x_{i},e_{i}))}$
		$\displaystyle+\sum_{i}{w_{i}(1-z_{i})log(\sum_{t=t_{i}+1}^{T+1}{f(t,x_{i},e_{i})})}$

with

$\displaystyle t_{i}=\left\{\begin{array}[]{rcl}e_{i}&if&z_{i}=0\\ d_{i}&if&z_{i}=1\\ \end{array}\right.$

(19)

According to our survey, it’s the first time to model the CVR prediction with delayed feedback on the entire space. Most of the related datasets are collected during the post-click stage like the classical criteo dataset used in  (Chapelle 2014), or lack of the delayed information as  (Ma et al. 2018). No public datasets consist of impression, click and conversion labels simultaneously in CVR modeling area. To evaluate the proposed method and better study this problem in the future, we collect traffic logs from our E-commerce search system and opensource a simplified random sampling version of the whole dataset. In the rest of this paper, we refer to the released dataset as Public Dataset and the whole dataset as Product Dataset. The statistics of the two datasets are summarized in Table 2. The training data is made of logs from 2020-05-30 to 2020-06-05, while the testing data consists of data on 2020-06-06. For the delayed conversion samples, we set the attribution window to 7 days. So the conversion labels of testing data have been attributed up to 2020-06-12, while labels of the training data can only be attributed up to 2020-06-05. This is consistent with the actual production environment since we can not observe the future information. As shown in figure 2, about 80$\%$ conversions occur on the first day, but the rest of them occur much later. It means that we may mistake 20% positive samples for negative if we adopt the traditional label collection paradigm within one day. There exits a slight difference of the distribution between training and testing data. It is because the testing data is labeled with the ground truth conversion. More detailed descriptions of the dataset can be found in the website of $URL$¹¹footnotemark: 1.

Metric ROC AUC  (Fawcett 2006) is a widely used metric in CVR prediction task, it denotes the probability of ranking a random positive sample higher than a negative sample. A variation of group AUC (GAUC) is introduced in (He and McAuley 2016; Zhu et al. 2017) which measures the items of intra-user order by averaging AUC over users and is shown to be more relevant to online performance on CVR prediction. In this paper, we group the impressions by each request of users to compute the GAUC:

$$GAUC=\frac{\sum_{i=1}^{N}{\#impression_{i}\times AUC_{i}}}{\sum_{i}^{N}\#impression_{i}}$$

where $N$ is the number of user requests and $AUC_{i}$ corresponds to the performance of ranking model for the $i$th request. It’s worth noting that the value of GAUC is 0.5 for a group of samples with the same label. When computing GAUC, we just only consider groups comprising both positive and negative samples in practice. Besides, we follow  (Yan et al. 2014) to introduce RelaImpr to measure the relative improvement over models. The RelaImpr is defined as below:

$$RelaImpr=(\frac{AUC(measuredmodel)-0.5}{AUC(basemodel)-0.5}-1)\times 100\%$$

Compared Methods To verify the effectiveness of our delayed feedback framework, we choose the following baselines for comparison. To assure fairness, we re-implement all methods with deep neural work. All baselines share embeddings between CTR and CVR tasks.

• •

  ESMM  (Ma et al. 2018): ESMM eliminates the data sparsity and selection bias problems by modeling CVR on the entire space. Here we use it as the baseline framework. Following the baseline method in  (Chapelle 2014), samples for which the conversion is unobserved in the first day are treated as negative. It is a traditional paradigm to process industrial data in practice.

• •

  NAIVE: To evaluate the impact of false negative samples, we remove them from training set and build a naive competitor with the same model of ESMM.

• •

  SHIFT: SHIFT extends the attribution window from one day to seven days. False negative samples are gradually corrected day by day limited to the newest date we can observe. This method partially fixes the false negative labels but doesn’t consider the elapsed time and delay distribution.

• •

  DFM (Chapelle 2014): As a strong competitor, DFM considers the delayed feedback with an exponential distribution assumption for the time delay. A lot of methods based on hazard function approximation finally degenerate into DFM after assuming that the hazard function is independent with the elapsed time. For a fairness compare, we replace the logistic regression of DFM with deep neural network and also add the embedding share between CTR and CVR network. The new version of DFM has the same network backbone with our method.

Parameter Settings For all experiments, the dimension of embedding is set to 8 and the batch size is 1024. We use Adam  (Kingma and Ba 2014) solver with an initial learning rate of 0.0001. Both CTR and CVR branches share the same MLP architecture of $512\times 256\times 128\times 1$ for all models. ReLU is used to be the activation function. The number of slots for the time delay discretization is set to 7. We report all results on public and product datasets with the same hyperparameters.

Experimental results on public and product datasets are reported in Table 3. Remind that, for the public dataset, impressions from the same request are sparse due to the random sampling, and GAUC by individual request will collapse to 0.5. So we adopt the ROC AUC as the metric on public dataset and GAUC on product dataset. As can be seen from Table 3, ESDF outperforms the other competitors both in public and product datasets and achieves almost 0.08 absolute GAUC gain and 6.68% RelaImpr over the ESMM baseline, which is considered substantial for our application.

We can observe that the baseline method ESMM achieves the worst performance because it contains many false negative samples. By simply removing these noise samples, NAIVE gets a better result, around 0.52% and 0.45% improvement of RelaImpr on the public and product datasets respectively. SHIFT makes a further improvement by partially correcting the false negative samples and achieves 2.28 % and 2.62% improvements compared with simple ESMM. However, due to the lack of consideration of the feedback delay distribution, SHIFT can not compete against DFM. As a strong competitor, DFM makes a significant improvement compared with above three methods. There are two main factors that restrict DFM after our re-implementation with deep neural network: First, it ignores the user sequential behavior pattern which can relieve the impact of sample selection bias; Second, the exponential distribution assumption limits the hypothesis space of feedback delay model. ESDF makes an improvement from these two aspects and achieves 0.82% and 3.16% improvement of RelaImpr over DFM on the public and product datasets respectively.

In this subsection, we focus on the performance of different models on the delayed samples. For comparison, we adopt log loss as the metric which is more attentive to the precision of models. We try to get an insight into the impact of delayed feedback samples to different methods. As shown in Figure 3, all models, as expected, perform better on data of the first day. The feedback delay hides the original distribution and makes the prediction imprecise. Time delay methods of DFM and ESDF outperform the others on both public and product datasets, but DFM is a bit unstable on the public dataset. We believe it is related to the inconsistency between true distribution of data and the assuming exponential one. An interesting fact is that, unlike the observations of GAUC, the naive method performs worse than ESMM, especially on the public dataset. A possible reason is that removing delayed feedback samples increases the difference between positive and negative classes, reducing the difficulty of model learning around the classification boundary. But on the other side, it expands the gap between training and testing datasets, making the model tend to give an imprecise prediction on the unseen data.