{'fraction_non_alphanumeric': 0.033664906198360496, 'fraction_numerical': 0.010433204808346563, 'mean_word_length': 4.564088696592753, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Noise tolerance of learning to rank under class-conditional label noise

Often, the data used to train ranking models is subject to label noise. For example, in web-search, labels created from clickstream data are noisy due to issues such as insufficient information in item descriptions on the SERP, query reformulation by the user, and erratic or unexpected user behavior. In practice, it is difficult to handle label noise without making strong assumptions about the label generation process. As a result, practitioners typically train their learning-to-rank (LtR) models directly on this noisy data without additional consideration of the label noise. Surprisingly, we often see strong performance from LtR models trained in this way. In this work, we describe a class of noise-tolerant LtR losses for which empirical risk minimization is a consistent procedure, even in the context of class-conditional label noise. We also develop noise-tolerant analogs of commonly used loss functions. The practical implications of our theoretical findings are further supported by experimental results.

on noisy data. Specifically, we describe a class of noise-tolerant losses, which we refer to as order-preserving, for which empirical risk minimization (ERM) is a consistent procedure even in the presence of class-conditional label noise. Further, we show that classical statistical learning theory results go through, almost without modification. We also identify a sufficient condition for a loss function to be considered order-preserving. While not all commonly used loss functions satisfy this condition, we introduce order-preserving analogs of these losses. The applicability of these losses to practical applications is explored in the experimental results section. The results developed here provide further theoretical justification for the use of weak supervision methods in learning to rank [6,10,17].
Our results also have implications for training classification models. In practice, we can train a ranking model using the available noisy data, and separately collect a small subset of clean data for determining the classification threshold. In critical applications, we can use ideas from distribution-free risk control to identify a cutoff point that guarantees a limited level of risk, with high probability [2,3].

RELATED WORK
It is well known that optimal classifiers learned in the presence of class-conditional noise differ from the optimum under the clean distribution only in terms of the classification threshold. Natarajan et al. build their method of label dependent costs based on this observation [13]. Zhang et al. uses a similar observation to design their post-processing based approach [18]. As they are primarily interested in learning a classifier, neither of these works considers the ranking problem, or the implications of this observation on empirical risk minimization of ranking objectives. In this work, we consider the same class-conditional label noise condition as [13,18] and study it's implications for learning to rank.
It is immediate from the above observation on the role of the classification threshold, that the optimum for noisy class probability estimation is optimal for both the noisy ranking problem and the clean ranking problem. This fact suggests that minimization of ranking objectives has certain noise tolerance properties. In our analysis, we do not necessarily assume that the optimum of the noisy risk is obtained. Instead, we are interested in the more practical case where we may face optimization difficulties over our model class or be limited by the size of the training set available.
Zamani and Croft study the behavior of so-called symmetric loss functions under noise conditions which they refer to as uniform and non-uniform noise [16]. They find that these symmetric losses are noise tolerant in the sense that the global optimum of the noisy empirical risk is also a global optimum of the clean empirical risk. As it turns out, symmetry of the loss function alone is not sufficient to ensure their noise tolerance condition. Indeed, they implicitly require that the corrupted labels be selected uniformly at arXiv:2208.02126v2 [cs.IR] 17 Aug 2022 random over the set of incorrect labels (see their equation 17 and the first equality in equation 21). This assumption is particularly strong, especially when treating the set of labels as a single label over {0, 1} as is the case in their setup. Accordingly, although NDCG and other learning to rank metrics satisfy the symmetry condition, their theorems 2 and 3 do not apply in the general class conditional noise regime which we consider in this work. Further, their results are concerned only with the global optima, while our results are more general and have strong implications for empirical risk minimization with finite samples. Finally, it is worth noting that the proofs of their theorems 2 and 3 deal with the expected empirical risk (the expectation taken over the noise), rather than the empirical risk which we can compute in practice.
The notion of noise tolerance we explore in this work (which we refer to as order preservation) is reminiscent of the property of consistent distinguishability explored by Wang et al. in [15]. However, their analysis is purely concerned with the behavior of NDCG@k losses as → ∞, with no consideration of the effects of label noise.

BACKGROUND AND NOTATION
Define X, Y, Q as the feature space, label space and query space, respectively. Let P be a distribution over X × Y associated with a query, ∈ Q, from which we have access to noisy iid samples ( ,˜) where˜is a corrupted version of . Assume further that there exists a distribution over queries, so that query is issued with probability , or formally P( = ) = where is the random variable associated with the issued query. We drop references to the query where the additional specificity is not needed.
Similar to previous work, we restrict ourselves to the case of binary relevance, Y = {0, 1}. From a practical information retrieval perspective, we can consider as indexing the instances, so that represents the features of document and its relevance label. To accommodate pairwise losses, we define = ( − + 1)/2 so that ties are indicated by 1/2.
In this work, we assume that our dataset has been corrupted with class-conditional label noise: corruptions to the labels that are independent of the features, conditioned on the true class. Further, for simplicity of exposition, without loss of generality, the derivations assume that the probability of corruptions are the same for each class, P(˜= 1 | = 0) = P(˜= 0 | = 1). 1 Putting this together, the corrupted label is given by: where the corruptions are determined by which are iid Bernoulli random variables with parameter ∈ [0, 1] and are independent of the features, conditioned on the true class: Note that when = 1 we receive the correct value of , so larger values of imply less noise.
In our setup, we assume that the noise is constant across queries. In the case where the label noise can vary arbitrarily for query 1 Note that the results in this work go through almost without modification if we do not make this assumption. to query, we don't have any guarantees (without other additional assumptions) since the noise can be chosen such that the expected noisy risk incorrectly prefers one scoring function to another.
Let F = { | : X → R} be the class of scoring functions over which we are optimizing the risk ℓ : F → R for a given margin based loss ℓ : R → R + . If ℓ is a pointwise loss, then If ℓ is a pairwise loss then We use˜ℓ to indicate the noisy risk, so for pointwise losses: and for pairwise losses: Notice that in both the clean and the noisy case, the pairwise risk is computed only over pairs of documents with different labels. When the choice of loss function is clear from context, we use to indicate the risk ℓ . We indicate the empirical versions of the risk with the subscript ; the clean and noisy risk, respectively: The key results of this work are concerned with the class of loss functions with the following noise tolerance property.
Definition 3.1 (order-preserving loss functions). A loss function ℓ is order-preserving if the following condition holds for all , ∈ F and distributions over X × Y for which ℎ( ) has a density with respect to Lebesgue measure for every ℎ ∈ F : The order preserving property implies that when the noise level is not too high, then scoring functions that are preferred by the clean risk are also preferred by the noisy risk and vice versa. This is a powerful property that (as we will see in section 4.4) allows us to derive finite-sample guarantees on the convergence of empirical risk minimization of order-preserving loss functions. Note that the order-preserving property is distinct from (but reminiscent of) the notion of noise tolerance considered by Zamani and Croft [16].
Remark. In the definition of order-preserving losses, we require that ℎ( ) has a density for each ℎ ∈ F to avoid the possibility of ties in the predictions. Note that this requirement is satisfied whenever itself has a density with respect to Lebesgue measure and ℎ is continuous. Alternatively, ℎ( ) can always be made to be absolutely continuous with respect to Lebesgue measure by convolving it's distribution with that of a smooth approximation of a delta function.
For convenience, we deal with the loss equivalents of metrics such as AUC, DCG and NDCG. Specifically, define DCG@k : F → R as: where : [ ] → [ ] is the permutation of the documents determined by the scoring function and is the discount applied to rank ; a typical choice is log(1 + ). We define NDCG@k accordingly: where maxDCG@k( ) is the DCG@k obtained by the arranging the items in decreasing order of their true relevance. This is the best achievable DCG@k in query, . The loss equivalents of the remaining metrics are defined by similarly taking their negation.
Next we define a subset of the order-preserving losses which we show contains several commonly used loss functions.

Definition 3.2 (label-symmetric loss functions). A loss function
This class of losses is identical to the class of symmetric losses introduced in [16], but restricted to the case of binary relevance.

ORDER PRESERVATION
In this section, we identify a sufficient condition for a loss to be considered order-preserving and further show that there are losses which do not satisfy this condition, but are still order-preserving. Building on this, we present order-preserving versions of commonly used losses that are not themselves order-preserving. Finally, we show that the order preservation property gives us a mechanism to apply results from statistical learning theory to the class conditional noise regime.

Label-symmetric losses
First, we show that both pointwise and pairwise label-symmetric losses are order-preserving. The key observation is that label-symmetry allows us to relate the risk due to incorrectly labeled instances to the risk due to correctly labeled instances. The proofs for the two types of losses are similar, with the main difference for pairwise losses being in handling the loss terms incurred by instances of the same class, but with different noisy labels.
Proof. We show this result for pointwise losses and pairwise losses separately.
First, consider the pointwise case. Let , ∈ F and consider the noisy risk: where the second equality follows from the tower property of expectation and the class-conditional noise assumption. Now, by the definition of a label-symmetric loss: which is simply an affine transform of the clean risk. The difference in their noisy risk: So ℓ is order-preserving. Consider now the pairwise risk.
Let us denote by 1 , 2 ( ) the quantity: where the equality comes from the class-conditional noise assumption. Then expand the noisy risk as: where we've used that the noise magnitude is constant over queries. When ℓ is label-symmetric, we have that: The first two equalities are immediate. To see the remaining two, expand the , ( ) terms as: where := ( ) and we apply the assumption that the event { ( 1 ) = ( 2 )} occurs with probability 0 when both items have the same relevance label. Using this same assumption and by symmetry, we have that P( 1 > 2 | 1 = 2 = ) = P( 1 < 2 | 1 = 2 = ) = 1/2. Now, since ℓ is label-symmetric we have that the quantity in the previous display is: But this reduces to simply /2.
Putting it all together, we see that: So ℓ is order preserving. □ It is straightforward to check that a loss function is label-symmetric. However, recall that this condition is not required for order-preservation.
Proof. For the 0-1 loss: which is equal to 1 for all ≠ 0. The proof for AUC is identical. See [16] for the proof of the hinge loss and ℓ 1 loss. □ Although AUC and 0-1 loss are non-differentiable, their use as loss functions is still practical when selecting from a finite collection of scoring functions, such as during hyperparameter optimization.
Next we show examples of commonly used loss functions that are not label-symmetric. Proposition 4.3. The exponential and binary cross-entropy losses are not label-symmetric. Similarly the ranknet and lambdarank losses [4,5] are not label-symmetric.
Proof. To show the binary cross entropy loss is not label-symmetric: which is a finite constant when is 1, and goes to ∞ as goes to ∞. Recall that the lambdarank loss is simply a scaled version of the logistic loss (applied in a pairwise setting) so the same counterexample shows that it is also not label-symmetric. The ranknet loss is a specific kind of lambdarank loss.
Similarly, for the exponential loss: which is a finite constant when is 1, and goes to ∞ as goes to ∞. □ Label-symmetry of a loss function is not necessary for it to be order preserving. We can, however, show that some commonly used non-label-symmetric losses are indeed not order preserving. Proof. For general pointwise losses: . When ℓ ( ) = log(1 + exp(− )) we have the logistic loss. Let ( ) = P( = 1 | ) for some positive . Taking → ∞ drives ( ) to 0 but − ( ) goes to ∞, so the perfect scorer will have a noisy loss that is larger than a bounded but random scorer. So the logistic loss is not order preserving. The same argument applies to the exponential loss, given by ℓ ( ) = exp(− ).
For pairwise losses, using the decomposition in (2): To show that the ranknet loss is not order preserving, consider the same scorer as before: ( ) = P( = 1 | ). Recall the ranknet loss ℓ ( ) = log(1 + exp(− )). Similar to the pointwise case, while 1,0 ( ) → 0 as → ∞, 0,1 ( ) is unbounded as → ∞ which is eventually larger than the noisy risk for a bounded but random scoring function. □ As we will see in section 4.2, it is possible to develop non-convex but smooth and label-symmetric analogs of the logistic and ranknet losses.
Remark. The lambdarank loss does not fit into the framework defined here since it also takes as input the permutation induced by the scores under consideration. However, we expect the lambdarank loss to exhibit similar (lack of) order preservation behavior to the ranknet loss.

Symmetric versions of non-label-symmetric losses
It is possible to define symmetric but non-convex versions of the cross-entropy and ranknet losses. The non-convexity of a loss, although potentially intimidating, does not exclude its viability as an objective function. Recent results show that empirical risk minimization of non-convex losses can be practical, even with classical optimization algorithms such as gradient descent with a fixed step size [12]. Given certain conditions on the data distribution and function class, Mei et al. show that the set of critical points of the empirical risk converges to the set of critical points of the true risk, with local minima converging to local minima, saddles to saddles and the global minima to the global minima; see their theorem 2 [12]. So, in the case of order preserving losses with class-conditional label noise, the noisy empirical local minima converge to the noisy expected local minima, which are also local minima of the clean loss, and similarly for the global optima.
While the log-loss is not an order preserving loss, we can define a label-symmetric analog.  Proof. For both the symmetrized logistic and the symmetrized ranknet losses: So they are label-symmetric and hence order-preserving. □ Our experimental results show that the order preserving property of these losses justifies the additional complexity resulting from the non-convexity.

DCG is order-preserving
Since DCG, NDCG and other listwise ranking losses are computed over a collection of instances (not individuals or simply pairs), they do not fit into the framework of label-symmetric functions defined previously. Recall that although DCG and NDCG losses satisfy the definition proposed in [16], their results do not apply unless additional assumptions are made. Nevertheless, DCG losses still exhibit the same order-preservation property introduced in section 4.1. Proof. Expanding the noisy DCG loss: Taking the expectation we have: This is simply an affine transform of E [DCG@k( ; )], so DCG losses are order preserving. □ While both AUC and DCG losses are order preserving, AUC has a further property that makes it suitable as a metric in practice. In the proof of proposition 4.7, we consider the expectation over the query distribution. In practice, the same query is issued many times in order to form a high quality estimate of the DCG loss, appealing to the law of large numbers. If each query is issued only a single time, estimates of the DCG could be dominated by noise. In contrast, the samples used in the estimation of AUC are exchangeable, so that estimates of the query-wise AUC are close to the true AUC given a single issue of a query and enough labels for that query.

Finite sample results
The results presented so far deal primarily with the expected risk, rather than the empirical risk. In particular, the order-preservation property is a property of the expected risk, so the relationship in (1) will not necessarily hold for all finite . To formulate analogous finite sample results, we can leverage concentration inequalities, with the goal of showing that order preservation holds with high probability for most pairs under consideration.
However, in practice, we are typically interested in the simpler task of identifying a single scoring function that achieves the optimal risk. The following results show that ERM over the noisy risk enjoys the same classical convergence guarantees as the clean case. In particular, minimization of the empirical risk over a class of finite VC dimension is consistent, achieving the same convergence rate as in the clean problem, scaled by a factor related to the noise magnitude.
Lemma 4.8. Let ℓ be an order-preserving loss. If ∈ (0.5, 1] then we have the following equality for each > 0: where is the function selected by empirical risk minimization with samples.
Proof. The proof is immediate from the definition of order preserving losses. □ Corollary 4.9. Assume that for the function class F and a loss ℓ we have the following uniform law of large numbers: Then running empirical risk minimization on the noisy estimates of the risk is equivalent (up to constant scaling factors of the convergence rate) to running ERM using clean estimates.
The above corollary is a direct consequence of classical results from statistical learning theory [7,14] and lemma 4.8. Note that the deviation on the RHS of (4) is simply scaled by a term related to the magnitude of the noise, so the convergence rate is accordingly scaled. For example, for the 0-1 loss, by applying Devroye et al.'s theorem 12.6 [7] to the RHS of (4) we can bound the excess risk of the model selected using ERM, with high probability: Theorem 4.10. For each > 0 and number of samples : where S(F , ) gives the ℎ shatter coefficient of the function class F .
Theorem 4.10 shows that if the function class is not too complex (in terms of the growth rate of it's shatter coefficient), then ERM is a consistent procedure. In particular, the risk of the selected scoring function, , converges to the optimal risk achievable by any function in the class, F .
Inverting the deviation bound gives us a bound on the difference between the expected risk and the optimal risk when we only have access to noisy data: where the expectation is taken over the randomness in the dataset used for empirical risk minimization. Notice that these bounds are non-asymptotic and are valid for every value of . Similar bounds can be derived for other order-preserving losses from their classical analogs, see [1] and [9].

Noise tolerance of almost-optima.
We can also develop similar deviation bounds in the case where empirical risk minimization does not succeed. Since an empirical minimizer may be computationally difficult to obtain in practice, we now assume that our noisy empirical risk is only almost-minimized, in the sense that our selected function is close to the optimum with high probability. More formally, assume that given samples, the noisy excess empirical risk is bounded above by with probability as least 1 − for some constants , > 0: Then we have the following non-asymptotic result: Theorem 4.11. Let ℓ be an order-preserving loss. Assume that we almost-minimize the noisy empirical risk, as in (6). Then, for each , > 0 we have that: where, as before, is the function selected by minimization of the noisy empirical risk.
Proof. First, since ℓ is order preserving, we have that: Now, rewrite˜( ) − inf ∈ F˜( ) as: which with probability at least 1 − is bounded above by: So, by a union bound, we have the claimed inequality. □ Now, as before, applying classical results from statistical learning theory, we can derive deviation bounds for symmetric loss functions when the risk is only almost-minimized. For example, in the case of the 0-1 loss we have the following result: Theorem 4.12. Let ℓ be the 0-1 loss. Assume that we almostminimize the noisy empirical risk, as in (6). Then, for each , > 0 we have that: Proof. The result is immediate from theorem 4.11 and Devroye et al. theorem 12.6 [7]. □

EXPERIMENTAL RESULTS
To better understand the behavior of order preserving and nonorder preserving losses, we conduct two sets of experiments. The first verifies the order preservation properties that were demonstrated in section 4. The second investigates the practical implications of these theoretical results.

Simulating order preservation
We explore the order preservation properties of commonly used loss functions, as well as the symmetrized losses introduced in section 4.2. We simulate the behavior of 100 scoring functions of varying quality over 1000 draws of 100 queries and compare the noisy risk to the clean risk. The scoring functions are created by adding an increasing amount of noise to a perfect scorer. Further, the predictions of half of the scorers constructed in this way are scaled by 10, to produce the effect of the counterexamples presented in proposition 4.4. The prevalence across simulated queries varies over a range from 0.1 to 0.9 while the noise level is kept constant, 1 − = 0.1. We plot the noisy risk vs the clean risk for each loss function in figure 1.
We expect the plots corresponding to order preserving losses to have all their points lying along a line with positive slope, showing that the noisy risk is an affine transform of the clean loss. Figure  1 supports the findings in this work, showing that AUC is order preserving. Interestingly, MAP does not appear to be exactly order preserving, although the plotted points show a high rank correlation. In contrast, as demonstrated by proposition 4.4, the logistic and exponential losses are not order preserving; note that not all points lie along the same line.

Performance of ERM for label-symmetric losses
In practice, we are primarily interested in selecting the optimal scorer, rather than ordering the full collection of scorers. Motivated by the results in section 4.2, we explore the practicality of the nonconvex symmetrized losses introduced in section 4.2. We compare the performance of linear models trained using various learningto-rank loss functions on four datasets. The first dataset is a synthetic learning-to-rank dataset inspired by the experiments of [12]. The second is the simple 20-Newsgroups dataset which is a collection of message board posts where the originating group is treated as the query. The last two are the popular LETOR datasets, MQ2007 and MQ2008, freely available from Microsoft 2 .
We inject class-conditional label noise over a range of values for each dataset. ranges over [1, 0.9, 0.8, 0.7, 0.6, 0.51]. We avoid ≤ 0.5 since we do not have any theoretical justification for the selection of one loss function over another in this regime.
The synthetic datasets are generated by first sampling a at random from an isotropic gaussian in dimensions for each query. The document features are also sampled from an isotropic gaussian in dimensions and the labels for each query are generated by sampling from P( = 1 | ) = (⟨ , ⟩) where is the logistic Figure 1: Simulation of the order preservation properties of various loss functions. The x-axis represents the clean risk, while the y-axis represents the noisy risk. For visual purposes, the line of best fit is overlayed. The exponential loss and the logistic loss are not order preserving, which can be seen in subfigures 1d and 1e; notice that not all the points lie along the same line. The relationship between the noisy and true risk for MAP does not appear to be linear.
function. The theoretical results in [12] justify empirical risk minimization of certain non-convex losses in this context (see their theorem 4). In our experiments, the number of samples is 500 with 5 features. The 20-Newsgroups dataset is preprocessed by considering a bag of words representation of the documents, removing all headers and footers to avoid leaking relevance labels into the content of the document.
We use the query-normalized versions of the MQ2007 and MQ2008 datasets and limit the labels to binary relevance. The features are further normalized to allow for faster convergence.
We train a linear model for each dataset and each choice of using four different loss functions, the commonly used logistic and ranknet losses, in addition to their symmetrized analogs introduced in section 4.2. We train each model until convergence (determined based on the estimated loss over a holdout set of the noisy data) using the Adam optimizer [11]. The learning rate and weight decay are selected by running a grid search, with the learning rate selected from [1e-1, 1e-2, 1e-3, 1e-4, 1e-5] and the weight decay selected from [1e-5, 1e-4, 1e-3]. The performance of the models over the varying noise levels are shown in figure 2. 3 As suggested by our theoretical results, models trained with the symmetrized ranknet loss tend to perform better than the other models at higher noise rates. Models trained with the more traditional losses are competitive at the lower noise rates. For the 3 Other optimizers led to similar results, but converged slower. MQ2007 and MQ2008 data sets, models trained with the symmetrized logistic loss perform poorly (substantially worse than models trained with the other methods) across all noise levels. The distributional assumptions of Mei et al.'s theorem 2 and theorem 4 may not be satisfied in this case or may be satisfied only with unfavorable constants, leading to vacuous bounds. In particular, the gradient of the loss may not in fact be subgaussian. Another possiblity is that the increased difficulty of the optimization problem is not made up for by the benefit from noise tolerance for this dataset.
Despite certain loss functions not being exactly order preserving, the performance of the trained models in this section suggest that they may be approximately order preserving, in some sense. If the logistic and ranknet losses did not at all preserve the order of scoring functions in the context of class-conditional label noise, then we would see much worse performance than we see in this section for models trained using these objective functions.

CONCLUSION
In this work, we showed that certain loss functions commonly used in learning to rank applications are noise tolerant in the sense that they are order-preserving in the context of class-conditional label corruptions. We further developed a sufficient condition for a pairwise or pointwise loss to be considered order-preserving and introduce order-preserving analogs of commonly used loss functions. In addition, we show that empirical risk minimization of (a) Synthetic dataset (b) 20-Newsgroups dataset (c) MQ2007 LETOR dataset (d) MQ2008 LETOR dataset Figure 2: NDCG@10 of models trained using various loss functions across four datasets and a range of noise conditions. 1 − is the label flip probability, so as decreases, the noise level increases. The symmetrized ranknet tends to perform best at the higher noise levels, while the more traditional loss functions are competitive at the lower noise levels. The symmetrized logistic loss performs poorly on the MQ2007 and MQ2008 datasets, likely due to optimization difficulties or misspecified assumptions from [12]. MAP and AUC had similar behavior to NDCG@10.
these losses enjoys the same properties as in the classical no-noise case; in particular, ERM in the context of class-conditional noise is consistent and satisfies the same convergence rate as the no-noise case, but scaled by a constant related to the magnitude of the noise. Experimental results support our theoretical findings while also suggesting that some metrics that are more difficult to analyze theoretically, NDCG and MAP, may be order preserving.
We leave it to future work to more closely analyze additional learning to rank losses such at MAP, NDCG and ERR. One possible route is to apply the analysis techniques of Wang et al. [15] to investigate the noise tolerance properties of NDCG. In particular, they introduce a pseudo-expectation of NDCG which is close to the empirical NDCG with high probability, but is easier to analyze. A limitation of this approach is that it cannot be used to analyze NDCG losses with a finite and fixed cutoff point .
Our analysis only considered the case where the noise level is constant across queries. In some applications, this assumption is not likely to hold. It might be possible to show that similar results to the ones shown here hold when we instead assume that ratio between the noise level and the prevalence is constant across queries. We also leave it to future work to analyze the behavior of learning-to-rank losses in the case of multiple relevance labels.