Non-Clicks Mean Irrelevant? Propensity Ratio Scoring As a Correction

Without loss of generality, we are given a set of i.i.d. queries $\bm{Q}$, where each query $q$ is associated with a list of candidate ranking documents $\{x_{i}\}^{|q|}_{i=1}$. The goal of LTR is to optimize a ranker $\pi$ on $\bm{Q}$ under ranking metrics of interest (e.g., ARP, NDCG, etc). Formally, the empirical risk of $\pi$ incurred on $\bm{Q}$ can be obtained as,

where $r_{q}(x_{i})$ is the ground-truth relevance label of document $x_{i}$ to query $q$ (assuming binary relevance for simplicity), $\pi_{q}$ denotes the ranking of documents under query $q$, and $\Delta(x_{i}|\pi_{q})$ measures the contribution from a relevant document $x_{i}$ to the ranking metric, e.g., the $rank$ of $x_{i}$ in ARP or the discounted gain of $x_{i}$ in NDCG.

Unlike the full-information setting where the relevance labels of all documents in $\pi_{q}$ are known, $r_{q}$ is only partially observed in the implicit click feedback, due to various click biases (Richardson et al., 2007). Simply using clicked documents to realize Eq (1) leads to a biased estimate of the ranking metric.

IPS addresses the bias issue via weighing each clicked document in Eq (1) by the inverse of its observation propensity in the logged ranking $\tilde{\pi}_{q}$ (Joachims et al., 2017b). To be more specific, denote $o_{q}$ as a binary vector indicating whether the documents’ relevance labels in $r_{q}$ are observed in $\tilde{\pi}_{q}$. For each element of $o_{q}$, the marginal probability $P(o_{q}(x_{i})=1|\tilde{\pi}_{q})$ is referred to as the observation propensity of document $x_{i}$. Consider the deterministic noise-free setting in (Joachims et al., 2017b), a document is clicked if and only if it is examined (thus observed) and relevant, i.e., $c_{q}(x_{i})\Leftrightarrow o_{q}(x_{i})\wedge r_{q}(x_{i})$. We can then get an unbiased estimate of $R(\pi_{q}|q)$ for any new ranking $\pi_{q}$ via IPS (Imbens and Rubin, 2015; Rosenbaum and Rubin, 1983),

where we introduce another binary vector $c_{q}$ to denote whether a document is clicked under $q$ in $\tilde{\pi}_{q}$.

Although Eq (2) has been proved to be an unbiased estimate of $R(\pi_{q}|q)$ for any new ranking $\pi_{q}$: $E_{o_{q}}\big{[}R_{IPS}(\pi_{q}|q,\tilde{\pi}_{q},o_{q})\big{]}=R(\pi_{q}|q)$ (Joachims et al., 2017b), a direct optimization of Eq (2) is intractable, due to the non-continuous nature of most ranking metrics. Approximations are thus necessary for optimization (Agarwal et al., 2019a), which however introduce a gap from the estimated metric to the induced loss. Next we rigorously examine and analyze the consequence caused by this gap.

In Eq (2), it is important to realize that the individual contribution $\Delta(x_{i}|\pi_{q})$ of a relevant document $x_{i}$ has to be obtained from its comparisons to other documents in the ranking list $\pi_{q}$, as the ranking position of $x_{i}$ in $r_{q}$ depends on how many other documents are predicted to be more relevant than it by the ranker. As shown in (Wang et al., 2018b), this is achieved via pairwise comparisons for a set of popular ranking metrics in practice. For instance, to get the $rank$ of a relevant document $x_{i}$ in $\pi_{q}$, we need to compare its predicted relevance $\hat{r}_{q}(x_{i})$ to all other documents’ $\hat{r}_{q}(x_{j})$. One key property in such a pairwise formulation is that only comparisons between two documents of different ground-truth relevance labels have influence on the ranking metric evaluation and can thus contribute to the optimization. The comparisons between two documents of the same relevance label will only form a constant term, agnostic to their positions or predicted relevance (Wang et al., 2018b).

The gap thus emerges when using continuous approximations on the pairwise comparisons, such as logistic loss (Arias-Nicolás et al., 2008), hinge loss (Joachims, 2002) or LambdaRank loss (Burges et al., 2006): the induced loss on comparisons between same-labeled documents become an irreducible term in the total loss that distorts the optimization and leads to sub-optimal results. To theoretically and more explicitly illustrate the issue, we revisit the optimization of Average Relevance Position (ARP), which is analyzed in the first IPS-based LTR solution (Joachims et al., 2017b) (but termed as $rank$). The same analysis can be easily applied to the optimization of other ranking metrics, such as NDCG (Wang et al., 2018b).

Assume there are $n$ documents in $\pi_{q}$ and the rank of documents starts from 0. Use $r_{q}^{i}$ and $\hat{r}_{q}^{i}$ to replace $r_{q}(x_{i})$ and $\hat{r}_{q}(x_{i})$ for simplicity. We have the APR evaluated on $\pi_{q}$ as:

where $C_{1}=\frac{1}{2n}\sum_{i=1}^{n}\sum_{j:r_{q}^{i}=r_{q}^{j}}r_{q}^{j}$ and $C_{2}=\frac{1}{n}\sum_{i=1}^{n}\sum_{j:r_{q}^{j}<r_{q}^{i}}r_{q}^{j}$ ($C_{2}=0$ in binary case) are constants. As shown in the step $*$, we should only impose pairwise loss to bound the comparison indicator $\mathbb{I}_{\hat{r}_{q}^{i}<\hat{r}_{q}^{j}}$ on document pairs with different ground-truth relevance labels, for optimizing the metric (i.e., relevant-irrelevant pairs in this binary case). Comparisons from pairs with the same label form a constant $C_{1}$ that does not contribute to the optimization.

More concretely, in $C_{1}$, a pair of documents with the same label $r$ count $r\mathbb{I}_{\hat{r}_{q}^{i}<\hat{r}_{q}^{j}}+r\mathbb{I}_{\hat{r}_{q}^{j}<\hat{r}_{q}^{i}}=r$ in the metric, independent of how they are ranked in $\pi_{q}$. If we introduce pairwise loss on such pairs, we are forcing the pair of documents to have the same predicted relevance values. Using pairwise logistic loss as an example, the loss $r\cdot\big{[}\log\big{(}1+e^{-(\hat{r}_{q}^{i}-\hat{r}_{q}^{j})}\big{)}+\log\big{(}1+e^{-(\hat{r}_{q}^{j}-\hat{r}_{q}^{i})}\big{)}\big{]}$ is minimized only when $\hat{r}_{q}^{i}=\hat{r}_{q}^{j}$. In other words, the loss on a pair of documents with the same label impose unnecessary constraints that distort the optimization.

Eq (3.2) reveals the root cause to the issue of IPS in practical ranker optimization using implicit feedback. We are now prepared to present our general deficiency diagnosis of existing IPS-based LTR solutions. Consider a general pairwise loss $\delta(x_{i},x_{j}|\pi_{q})$ defined on two different documents $x_{i}$ and $x_{j}$ in $\pi_{q}$, which indicates how likely $x_{i}$ is more relevant than $x_{j}$. Following the IPS estimator in Eq (2), the individual contribution of a relevant document $x_{i}$ to the ranking metric is thus upper bounded by the total pairwise loss of comparing $x_{i}$ to all other documents in $\pi_{q}$:

where we assume minimizing the loss will optimize the metric.

In click data, where only the relevant and observed documents are indicated by clicks, the local loss on $q$ can be derived from Eq (2) with pairwise loss. There are currently two strategies for imposing the pairwise loss. The first one is to compare each clicked document to all other documents as in Propensity SVM-Rank (Joachims et al., 2017b) or its generalizations (Agarwal et al., 2019a); but in expectation, it contains loss on all relevant-relevant pairs. To avoid explicitly comparing two relevant documents indicated by clicks, the second strategy restricts the loss on comparisons between clicked and non-clicked ones (Rendle et al., 2009; Hu et al., 2019):

But as relevant and unobserved documents are also non-clicked, this strategy still cannot address the problem of including loss on relevant-relevant pairs that only distracts the optimization:

In expectation, besides the pairwise loss on relevant-irrelevant pairs that we need, this strategy also includes pairs on relevant documents versus relevant but unobserved documents (the second sum in the bracket). The negative effect can also be perceived from an intuitive perspective: as the relevant but unobserved documents are mistakenly used as negative examples, it will degrade the new ranker’s ability to recognize these missed relevant documents, making the ranker still unfavorably biased against them.

In order to verify our theoretical analysis, in Figure 2, we demonstrate the empirical influence of including pairwise loss on relevant-relevant pairs in LTR model training with clicks. Specifically, we synthesize clicks on the Yahoo and Web10K LTR datasets with the propensity model ($\eta=1$) described in Section 5. To better illustrate the effect, we adopt the noise-free setting and sampled 128,000 clicks. To learn new rankers from the clicks, we apply IPS on the pairwise logistic loss, and include pairs from different comparison strategies. The NDCG@10 results are reported on fully labeled test sets in the two benchmarks accordingly. As clearly shown, including relevant-relevant document comparisons seriously hurt ranker optimization. Therefore, we should remove the relevant-relevant pairs to eliminate such adverse effects for LTR model learning, which will be the focus of next section.

The insight of identifying truly irrelevant documents in non-clicked documents comes from the decomposition of click data in Figure 1. In a noise-free setting, if a document is observed (the first column in Figure 1), click is equivalent to relevance, i.e., $o_{q}(x_{i})=1\rightarrow[c_{q}(x_{i})=r_{q}(x_{i})]$. Consequently, if a document is observed and non-clicked, it is irrelevant, i.e., $[o_{q}(x_{i})=1\wedge c_{q}(x_{i})=0]\rightarrow r_{q}(x_{i})=0$ (the I&O part in Figure 1). The problem of identifying truly irrelevant documents from non-clicked ones is thus reduced to finding the observed documents in the non-clicked ones.

Note that for a non-clicked document $x_{j}$, we do not have its true observation $o_{q}(x_{j})$. However, by weighting the loss on each non-clicked document with its conditional observation probability $P(o_{q}(x_{j})=1|c_{q}(x)=0,\tilde{\pi}_{q})$, we can restrict the loss on non-clicked documents to those that are non-clicked but observed, in expectation. But this conditional probability is not easy to estimate: As shown in Figure 1, this probability corresponds to the ratio of the $I\&O$ part in the non-clicked documents, which depends on both the position and relevance of the documents. Therefore, we need to estimate $P(o_{q}(x_{j})=1|c_{q}(x)=0,\tilde{\pi}_{q})$ on all positions under every single query. Without sufficient observations under the same query, the estimation quality can hardly be guaranteed. Instead, we propose to directly use the position-based observation propensity $P(o_{q}(x_{j})=1|\tilde{\pi}_{q})$ as an approximation for the purpose of reweighing the loss on each non-clicked document,

where $\Omega(\cdot)$ represents any general loss on a non-clicked document $x_{j}$, including the pairwise loss used in Section 3.2. Due to the approximation, the second term of Eq (7) still contains relevant documents; but $P(o_{q}(x_{j})=1|\tilde{\pi}_{q})$ for relevant but non-clicked documents is expected to be small. For example, under a position-based examination model (Joachims et al., 2017b), the examination probability shrinks fast over positions; and thus the impact from relevant but non-clicked documents can be quickly eliminated when moving down the ranked list. We refer to this weighting on non-cliked documents as the Propensity-weighted Negative Samples (PNS).

As the observation of documents are position-based and independent (Craswell et al., 2008; Wang et al., 2018a), treatments on clicked and non-clicked documents will not interfere with each other. Therefore, we can integrate the inverse propensity weighting on the clciked documents and propensity weighting on the non-clicked ones to reweigh the pairwise losses incurred when comparing them:

which leads to a weight on each pairwise loss term defined by the propensity ratio between the non-clicked and clicked documents in it. We name this new weighting scheme Propensity Ratio Scoring, or PRS in short. In expectation, the PRS estimator largely removes the relevant-relevant comparisons, and focus on comparing each relevant document to irrelevant ones for ranker optimization:

where the first step is the same as Eq (6); and the second step is derived from Eq (7) by substituting $\Omega(x_{j}|\pi_{q})$ with $\delta(x_{i},x_{j}|\pi_{q})$. As discussed in Section 4.1, the second term that consists relevant-relevant comparisons is small and can be safely ignored in practice. In this way, the total loss is merely obtained from valid relevant-irrelevant pairs that contribute to ranker optimization. Notice that besides removing relevant documents from non-clicked documents, Eq (9) also excludes the irrelevant and unobserved documents, i.e., the I&U part in Figure 1. But as the ranking metrics are defined on relevant documents, we only need to correct the errors introduced by including relevant documents as negative examples, and keep the total loss unbiased to all relevant documents. As demonstrated in the expectation, PRS can properly promote all the relevant documents against irrelevant ones.

Besides the correction effect, we next show that by imposing a more careful use of the non-clicked documents, the variability of the PRS estimator can be reduced comparing to the IPS estimator, which is very important for LTR with real-world click data (Swaminathan and Joachims, 2015b). Let us first rewrite the PRS estimator in Eq (8) as follows:

The complete proof will be elaborated with details in a longer version of this paper. The above tail bound of the PRS estimator depicts its variability. Intuitively, this tail bound provides the range that the estimator can vary with a high probability; and a smaller range means a lower variability. Similarly, we can get the tail bound of the IPS estimator in Eq (5) as:

where $\tau_{i}=\frac{1}{P(o_{q}(x_{i})=1|\tilde{\pi}_{q})}\cdot\sum_{x_{j}:c_{q}(x_{j})=0}\delta(x_{i},x_{j}|\pi_{q})$ if $0<P(o_{q}(x_{i})=1|\tilde{\pi}_{q})<1$; and $\tau_{i}=0$, otherwise. As the propensity of each non-clicked document is smaller than 1, $0\leq\rho_{i}\leq\tau_{i}$ always holds. Thus, the PRS estimator enjoys a reduced variability than IPS, which is vital for the convergency of ranker estimation in practice.

In addition to providing an unbiased estimate of pairwise comparisons on click data, another obvious advantage of PRS is its general applicability: it does not require any additional statistics or procedures than those already used in IPS (e.g., we can use any existing methods for propensity estimation (Joachims et al., 2017b; Craswell et al., 2008; Wang et al., 2018a; Agarwal et al., 2019b; Qin et al., 2020a)). As a result, it can be seamlessly applied to all existing unbiased LTR settings or other scenarios (e.g., recommendation (Schnabel et al., 2016)) where IPS is used, and guaranteed for better performance.

So far, we have assumed a noise-free setting, i.e., a document is clicked if and only if it is observed and relevant: $c_{q}(x_{i})=1\Leftrightarrow[o_{q}(x_{i})=1\wedge r_{q}(x_{i})=1]$. However, in reality this may not hold: a user can possibly misjudge and miss a relevant document, or mistakenly click on an irrelevant document. Fortunately, PRS is order-preserving under the same noise assumption made by IPS (Joachims et al., 2017b). Due to space limit, we decide not to include the proof, which can be obtained similarly as in (Joachims et al., 2017b) but based on Eq (9). We will present the influence of noisy clicks empirically in Section 5.3.

As shown in Eq (8), the proposed PRS estimator generally applies to any pairwise LTR algorithms. To test the performance of PRS on different ranking models, we include two popularly used yet significantly different pairwise LTR algorithms for experiments. One is pairwise logistic regression (Rendle et al., 2009; Arias-Nicolás et al., 2008), and the other one is LambdaMART (Burges, 2010), the state-of-the-art pairwise LTR algorithm.

We primarily compare the PRS estimator against the IPS estimator, and also a Naive estimator. The Naive estimator simply treats clicks as relevance and non-clicks as irrelevance. The two baseline estimators can be viewed as special cases of our PRS estimator: IPS always sets the observation propensity of a non-clicked document to $1$; and Naive simply sets the PRS weight to $1$ in all pairs. All three estimators are applied to the two base ranking algorithms to learn new rankers from click data. We also include the Full-Info ranker trained with fully-labeled ground-truth data as the skyline.

We adopt three benchmark LTR datasets, including Yahoo Learning to Rank Challenge (set1), MSLR-WEB10K and MQ2007.
$\bullet$ Yahoo. One of the largest and most popularly used benchmark dataset for LTR. It contains around $30K$ queries with $710K$ documents. Each query-document pair is depicted with a 700-dimension feature vector (519 valid features) and a five-grade relevance label. Following (Joachims et al., 2017b), we binarize the relevance by assigning $r_{q}(x)=1$ to documents with relevance label $3$ or $4$, and $r_{q}(x)=0$ for others.
$\bullet$ WEB10K. It contains $10K$ queries and a 136-dimension feature vector for each query-document pair. We binarize the relevance labels in the same way as in the Yahoo dataset.
$\bullet$ MQ2007. It contains about $1,700$ queries and a 46-dimension feature vector for each query-document pair, with relevance label in $\{0,1,2\}$. We assign $r_{q}(x)=1$ to documents with relevance label $1$ or $2$, and $r_{q}(x)=0$ to documents with relevance label $0$.

For all three datasets, we keep the partition of the train, validation, test set from the corpus and report the performance on the binarized fully labeled test sets with five-fold cross-validation. We follow the procedure in (Joachims et al., 2017b) to derive click data from each fully labeled dataset. To generate clicks, we first train an initial ranker with 1 percent of the queries in the training set, which is referred to as the production ranker $\pi_{0}$. Then we randomly select a query $q$ from the rest of the training set, for which we use $\pi_{0}$ to compute the ranking $\tilde{\pi}_{q}$ for this query. With the ranked list, we can generate clicks according to a position-based click model,

where $e_{q}(x_{i},k)$ denotes whether the document at position $k$ is examined, and examination equals the observation of the relevance label: $e_{q}(x_{i})=o_{q}(x_{i})$. Thus the observation propensity is equivalent to the position-based examination probability $P(e_{q}(x_{i},k)=1|\tilde{\pi}_{q})$, which is defined as follows,

where $\eta$ represents the severity of position bias. The propensity $P(o_{q}(x_{i})=1|\tilde{\pi}_{q})$ of each document (regardless of clicked or non-clicked) is recorded based on their positions in the presented ranking. We also add click noise as in (Joachims et al., 2017b). Denote $\mu\in[0,0.5)$ as the noise level, we have $P\big{(}c_{q}(x_{i})=1\big{|}r_{q}(x_{i})=1,o_{q}(x_{i})=1\big{)}=1-\mu$ and $P\big{(}c_{q}(x_{i})=1\big{|}r_{q}(x_{i})=0,o_{q}(x_{i})=1\big{)}=\mu$. When not mentioned otherwise, we use $\eta=1$ and $\mu=0.1$ as the default setting. In the following sections, we investigate the influence of each component.

We use NDCG@10 as the main performance metric. We also computed other metrics such as MAP and ARP. But as the performance on these metrics was consistent with each other and the space limit, we only report NDCG@10 to include more experiments. We tune the hyper-parameters via cross-validation. Each result is averaged over five runs and the standard deviation is displayed as the shadow areas in the figures.

We further evaluate PRS on data from one of the world’s largest personal search engines, GMail search, to prove PRS’ applicability in real-world large-scale industrial settings. Specifically, we collected the click-through data from Gmail search logs between June and July 2020 for experiments, resulting in hundreds of millions of queries with clicks. The ranking order of documents in each query was determined by the actual deployed production model, and other factors such as (the unknown) click noise are without any synthetic interventions. Among all the queries, 80% are used for training, 10% for validation and parameter tuning, and the remaining for testing. On average, each GMail query has six candidate documents based on its search interfaces and one of the documents is clicked.

The dataset contains a rich set of features, including query-document matching features such as BM25, situational features (e.g. time of the day), user features (e.g. user’s previous click behavior), and document attributes (e.g. document age), etc. The observation propensities are estimated from randomized online experiments (Wang et al., 2016). We use weighted mean reciprocal rank (WMRR) as our primary metric, since it has been found to be predictive of online gains (Wang et al., 2018a). In particular, WMRR is calculated as follows:

where $w_{i}$ denotes the bias correction weight that corresponds to the inverse propensity of the clicked document, $N$ denotes the number of testing queries, $\mathrm{rank}_{i}$ denotes the rank position of the clicked document for the i-th query. As explained in Section 3.1, WMRR is an unbiased estimate of MRR metric. Hence, the higher WMRR is, the better a model performs.

We conduct experiments with linear rankers, LambdaMART, and deep neural network (DNN) rankers to demonstrate PRS’ robust performance on real-world datasets with different families of ranking models. We include the following specific models for comparison: a baseline logistic regression model using Naive estimator, an IPS-trained logistic regression, a PRS-trained logistic regression, Unbiased LambdaMART (based on IPS) (Hu et al., 2019), PRS-LambdaMART, an IPS-trained DNN model, and a PRS-trained DNN model. For all compared models, we use the same set of input features. For DNN models, we use a 3-layer fully connected architecture with 256 hidden dimensions, pairwise logistic loss, and SGD for optimization. All results are reported comparatively to the base logistic regression model, to avoid reporting the absolute performance that is proprietary. As a large portion of testing queries are already clicked at the top (position 0), which are considered as easier queries, we also report the results on other queries separately to better illustrate the performance improvement. The results are shown in Table 2. Note that in large commercial search systems, an approach with an improvement around 0.2% is considered as substantial (Wang et al., 2016; Qin et al., 2020b).

All relative differences between PRS and baseline in each family of algorithms are statistically significant under paired t-test with $p$-value$<$0.05. We can find that PRS not only performs the best among all solutions, it is also robust under different queries, including those more difficult ones (i.e., clicked on lower ranked positions). IPS tends to over-emphasize difficult queries (e.g., give them larger weights in training), while sacrificing performance on easier ones. LambdaMART and DNN rankers outperform linear rankers by a large margin due to their model capacity in leveraging feature non-linearity. Unbiased LambdaMART shows competitive performance, but is still inferior to PRS-LambdaMART on this large-scale real-world dataset. The results also strongly support PRS for real-world deployments: it only requires a simple modification of the instance weighting schema during training, without any other changes (e.g., logging or optimization).