Computationally Efficient Optimization of Plackett-Luce Ranking Models for Relevance and Fairness (Extended Abstract)

1 Introduction

Learning to Rank (LTR) is a branch of machine learning that covers methods for optimizing ranking systems for search and recommendation applications [Liu, 2009]. Traditionally, scoring function are used to assigns an individual score to each item, and subsequently, produce rankings by sorting items according to their assigned scores [Fuhr, 1989; Joachims, 2002]. The main difficulty in LTR is that there is no gradient w.r.t. the sorting procedure. Solutions to this difficulty can be divided into two categories: optimizing a heuristic function that bounds or approximates the ranking performance [Burges, 2010; Wang et al., 2018; Bruch et al., 2019]; or optimizing a probabilistic ranking system [Cao et al., 2007; Xia et al., 2008; Ustimenko and Prokhorenkova, 2020].

In recent years, the popularity of the Plackett-Luce (PL) ranking model has increased [Singh and Joachims, 2019; Diaz et al., 2020]. It models ranking as a succession of decision problems where each individual decision is made by a PL model [Plackett, 1975; Luce, 2012]. Previous research from the industry indicates that the probabilistic nature of the PL model leads to more robust performance [Bruch et al., 2020]. In online LTR, it appears the PL model is very good at exploration because it explicitly quantifies its uncertainty [Oosterhuis and de Rijke, 2018]. Recent work has also posed that the PL model is well suited to address fairness aspects of ranking [Singh and Joachims, 2019; Diaz et al., 2020].

In this paper, we introduce PL-Rank: a novel method that can efficiently optimize both relevance and exposure-based fairness ranking metrics. Our work contributes novel estimators that unbiasedly estimate the gradient of a PL ranking model w.r.t. a ranking metric, and the PL-Rank algorithm to compute them efficiently. To the best of our knowledge, PLRank is the first LTR method that utilizes specific properties of ranking metrics and the PL-ranking model. Our experimental results show that compared to existing LTR methods, PL-Rank has increased sample-efficiency and increased timeefficiency: PL-Rank requires less computational time to converge at optimal performance. The introduction of PL-Rank makes the optimization of PL ranking models more practical by greatly reducing its computational costs, additionally, these gains also help in the further promotion of fairness aspects of ranking models [Diaz et al., 2020].

2 Background

Let ρq,d = ρd denote the relevance of item d for a query q (for brevity we omit q in notation), let y be a ranking and yk denote the kth item in ranking y: y = [y1, y2, . . . , yK]. Furthermore, π(y | q) = π(y) indicates the probability that ranking y is sampled for query q by ranking model π. The performance of π for a single query is determined by the weights per rank θ and an expectation over the ranking behavior of π:

By choosing θk accordingly, R(q) can represent the most common relevance ranking metrics: e.g. top-K Discounted Cumulative Gain (DCG): θDCG@K k = 1[k ≤K]/ log2(k+1), or precision at K: θPREC@K k = 1K 1[k ≤ K]. The overall performance of a π is the expected performance over the natural distribution of user-issued queries:

Accordingly, LTR for relevance optimizes π to maximize R, given relevances ρd and the chosen metric represented by θk.

In the PL ranking model [Bruch et al., 2020], an item is chosen from a pool of available items based on the individual scores each item has. For our ranking problem, a learned prediction model m predicts the log score of an item d w.r.t. to query q as m(q, d) = m(d) ∈ R. The probability that an unplaced item d is chosen to be the kth item in ranking y from the set of items D is the score of d: em(d) , divided by the sum of scores for the items that have not been placed yet:

where y1:k-1 indicates the ranking up to rank k - 1, i.e., y1:k-1 = [y1, y2, . . . , yk-1]. We note the large similarity with the Soft-Max function commonly used in deep learning. Accordingly, the probability of a ranking is simply the product of the placement probabilities of each individual item:

An advantage of the PL ranking model is that rankings can be sampled quite efficiently, by applying the Gumbel Softmax trick [Gumbel, 1954]: for each item a sample from the Gumbel distribution is taken: γ (i) d ∼ Gumbel(0, 1), i.e. by first sampling uniformly from the [0, 1] range: ζ (i) d ∼ Uniform(0, 1), and then applying: γ (i) d = -log(-log(ζ (i) d )). Subsequently, per item we take the sum of their Gumbel sample and their log score: ˆm(i) d = m(d) + γ (i) d . Finally, sorting according to the ˆm(i) values provides a sampled ranking:

This sampling procedure follows the PL distribution of π [Gumbel, 1954; Bruch et al., 2020]. In practice, rankings can thus be sampled as quickly as top-K sorting, which translates to a computational complexity of O(|D| +K log(|D|)).

Previous work have used policy-gradients to optimize PL ranking models [Singh and Joachims, 2019; Bruch et al., 2020], they utilize the famous log-trick from the REINFORCE algorithm [Williams, 1992]:

By applying the log-trick to Eq. 1, its derivate can be expressed as an expectation over the ranking distribution π:

We see that this policy gradient is composed of two parts: a gradient w.r.t. the log probability of a complete ranking multiplied by the reward for that ranking. Luckily, to avoid iterating over all possible rankings the gradient can approximated by a simple sampling strategy; If we sample N rankings from π with y(i) denoting the ith sample, then the following estimates the gradient unbiasedly:

A straightforward implementation could use a machine learning framework to compute the gradient w.r.t. the log probabilities: [ δ δm log(π(y(i) ))], e.g. PyTorch [Paszke and others, 2019] or Tensorflow [Abadi and others, 2016]. The downside of this approach is that it delegates the most difficult computation to a framework, which generally do not make use of the fact that π is a PL model and that a ranking metric is optimized. In contrast, the remainder of this paper will introduce methods that make use of specific PL properties, and as a result, show better computational efficiency in our experimental results.

3 Method: PL-Rank for Relevance

In this section, we will derive three novel methods for estimating the gradient of a PL-ranking model.

3.1 RankingMetric Based Approximation

By rewriting Eq. 1 we can see that ρd only need to be multiplied with the probability of the ranking up to their rank:

where ∑y1:k∈π is a summation over all possible (sub)rankings of length k. Intuitively this makes sense because the placement of any item after k will not affect the relevance of previously placed items.

Let us first consider that the derivate of the log probability of a ranking can be decomposed as a sum over log probabilities of the individual item placements, using Eq. 4:

Eq. 9 & 10 allow us to get the following derivative of R(q):

Again, this gradient can be estimated using sampled rankings:

We will call this estimator the placement policy gradient estimator, in contrast with the basic policy gradient estimator (Eq. 8), this estimator weights the gradients of placement probabilities with the observed following relevances. By doing so, it uses of the structure of ranking metrics and thus is more tailored towards these metrics than the basic estimator.

3.2 Computationally Efficient Estimation

Next, we will use the knowledge that π is a PL model to propose an estimator that can be computed with greater computational efficiency. We start by taking the derivative of an item placement probability:

We note that the probability of placing an item that has already been placed is zero: d ∈ y1:k-1 → π(d | y1:k-1) = 0. Combining Eq. 11 & 13 results in the following gradient:

risk imposed by placement probability

We see that the derivative can seen as a summation over items with two parts per item: the first part represents the expected reward to follow the placement of d; the second part can be interpreted as a the risk imposed by an item d. We view it as representing a risk since if d is not placed at k then π(d | y1:k-1) indicates how likely d would have been placed instead of yk and in which case the following reward ∑Kx=k θxρyx may not have occurred. For cases where d is the item at rank k: d = yk, the risk stops the log score m(d) from increasing too far as the placement probability π(d | y1:k-1) may already be very great.

Based on Eq. 14, we introduce the PL-Rank-1 estimator:

To the best of our knowledge, PL-Rank-1 is the first gradient estimation method that is specifically designed for optimizing PL-ranking models w.r.t. ranking metrics. Importantly, it can be computed with a time-complexity of O(N · K · D).

3.3 Improving Sample-Efficiency

In Eq. 14 we see that an item receives a positive weight from the expected following reward. Therefore, even when an item has a low probability of being placed it can compensate with a high relevance (ρd) to get a positive weight. However, the N samples may not include a ranking where such an item is placed at all and thus these items will nevertheless receive a negative weight in the estimated gradient. We propose one last estimator to mitigate this potential issue.

First, we rewrite the expected reward following placement to separate the reward obtained from d:

Combining this result with Eq. 14 we get:

expected direct reward minus the risk of placement

In this formulation the gradient w.r.t. an item's log score m(d) is weighted by the relevance after placement (excluding ρd) plus the expected direct reward (θkρd) minus the expected risk imposed by d before its placement. From Eq. 17 we can derive the novel PL-Rank-2 estimator:

We will call this estimator: PL-Rank-2. Unlike PL-Rank-1 (Eq. 15), PL-Rank-2 can provide a positive weight to items that were not in the top-K of any of the N sampled rankings. While this is expected to increase the sample-efficiency, it does not come at the cost of computational complexity as both PL-Rank-1 and PL-Rank-2 have a complexity of O(N ·K·D).

3.4 PL-Rank for Fairness

Importantly, PL-Rank can also estimate the gradient of a PL ranking model w.r.t. exposure-based fairness metrics [Diaz et al., 2020; Biega et al., 2018] Exposure represents the expected number of people that will examine an item, let θk be the probability that a user examines an item at rank k, then the exposure an item d receives under π is:

where again for brevity we denote Ed = E(q, d). Most fairness metrics for rankings consider whether exposure is distributed fairly over items, regardless of the exact metric, PLRank can be applied to a fairness metric F if the chain-rule can be applied as follows:

To derive this gradient, we first note that the Ed (Eq. 19) and R(q) (Eq. 1) are equivalent if ∀d′ ρd′ = 1[d′ = d], therefore if we replace ρ in PL-Rank-2 (Eq. 17) accordingly, it will provide us the gradient δEd δm . If we combine this fact with Eq. 20 we obtain the following PL-Rank-2 based gradient:

In other words, we can apply PL-Rank by simply replacing the item relevances with the gradients: δF(q) δEd before computation. This potentially makes PL-Rank the first LTR method that is suited for optimizing both relevance and fairness.

4 Experimental Setup

Our experiments evaluate whether PL-Rank can reach higher performance in less computational time than policy gradients or LambdaLoss [Wang et al., 2018]. We use the three largest publicly-available LTR industry datasets: Yahoo! Webscope [Chapelle and Chang, 2011], MSLR-WEB30k [Qin and Liu, 2013], and Istella [Dato et al., 2016]. As a metric to optimize, we chose the commonly-used top-5 Discounted Cumulative Gain (DCG@5). To compare the computational costs of each method, we ran repeated experiments under identical circumstances on a single Intel Xeon Silver 4214 CPU. We optimize neural networks with two hidden layers of 32 sigmoid activated nodes using standard stochastic gradient descent with a 0.01 learning rate. For calculating gradients we utilize Tensorflow [Abadi and others, 2016] with two exceptions: the sampling of rankings and δR(q) δm with the PLRank algorithm are computed using Numpy [Harris and others, 2020]. The number of sampled ranked are scaled with epochs according to: N = 10 + 90 · epoch 40 . 1

1 Code: https://github.com/HarrieO/2021-SIGIR-plackett-luce.

5 Results

Figure 1 shows the performance of PL ranking models trained with PL-Rank, Policy Gradients and LambdaLoss over training time in minutes. We see that LambdaLoss, a method designed for deterministic ranking models, converges quickly but on suboptimal performance. The standard policy gradient (Eq. 7) appears to learn slowly, as we do not observe it to converge in our results. The placement policy gradient outperforms both baselines within 20 minutes of training across all three datasets. On all datasets, we see an improvement of PLRank-1 over the placement policy gradient which is very large on Yahoo and MSLR but smaller on Istella. This improvement can be attributed to the reduced computational costs of PL-Rank-1, as a result, it is capable of completing more epochs in the same amount of time and can therefore reach a higher performance in less computational time. Finally, compared to PL-Rank-1, PL-Rank-2 has an even higher performance on the Yahoo and Istella datasets but not on MSLR. It appears that its increased sample-efficiency helps PL-Rank2 initially, when N is low, except on the MSLR dataset. To conclude, it thus appears that Pl-Rank-2 reaches higher performance faster when compared to the other methods in all tested cases, with the single exception of PL-Rank-1 on the MSLR dataset. Therefore, our results support the conclusion that PL-Rank-2 is the most time-efficient method when compared with policy gradients and LambdaLoss.

6 Conclusion

This paper addressed the optimization of PL-ranking models for both relevance and fairness ranking metrics. To alleviate the large computational costs of existing methods, we introduced three new estimators for efficiently estimating the gradient of a ranking metric w.r.t. a PL ranking model: the placement policy gradient and two PL-Rank methods. Our experimental results indicate that our novel methods considerably reduce the computational time required to reach optimal performance compared to existing methods. Compared to the popular basic policy gradient, PL-Rank-2 converges several hours earlier, thus immensely alleviating the computational costs of optimization.

With the introduction of PL-Rank, we hope that the usage of stochastic ranking models is made more attractive in realworld scenarios. Finally, we think PL-Rank is also an important theoretical contribution to the LTR field, as it proves that PL ranking models can be optimized with computational efficiency, without relying on heuristic methods.