Seq2Slate: Re-ranking and Slate Optimization with RNNs

Introduction

Ranking a set of candidate items is a central task in machine learning and information retrieval. Many existing ranking systems are based on pointwise estimators, where the model assigns a score to each item in a candidate set and the resulting slate is obtained by sorting the list according to item scores Liu et al. (2009). Such models are usually trained from click-through data to optimize an appropriate loss function Joachims (2002). This simple approach is computationally attractive as it only requires a sort operation over the candidate set at test (or serving) time, and can therefore scale to large problems. On the other hand, in terms of modeling, pointwise rankers cannot easily express dependencies between ranked items. In particular, the score of an item (e.g., its probability of being clicked) often depends on the other items in the slate and their joint placement. Such interactions between items can be especially dominant in the common case where display area is limited or when strong position bias is present, so that only a few highly ranked items get the user’s attention. In this case it may be preferable, for example, to present a diverse set of items at the top positions of the slate in order to cover a wider range of user interests. Conversely, presenting multiple items with similar attributes may create “synergies” by drawing attention to the collection, amplifying user response beyond that of any individual item.

A significant amount of work on learning-to-rank does consider interactions between ranked items when training the model. In pairwise approaches a classifier is trained to determine which item should be ranked first within a pair of items (e.g., Herbrich et al., 1999; Joachims, 2002; Burges et al., 2005). Similarly, in listwise approaches the loss depends on the full permutation of items (e.g., Cao et al., 2007; Yue et al., 2007). Although these losses consider inter-item dependencies, the ranking function itself is pointwise, so at inference time the model still assigns a score to each item which does not depend on scores of other items (i.e., an item’s score will not change if it is placed in a different set).

There has been some work on trying to capture interactions between items in the ranking scores themselves (e.g., Qin et al., 2008, 2009; Zhu et al., 2014; Rosenfeld et al., 2014; Dokania et al., 2014; Borodin et al., 2017; Ai et al., 2018b). Such approaches can, for example, encourage a pair of items to appear next to (or far from) each other in the resulting ranking. Approaches of this type often assume that the relationship between items takes a simple form (e.g., submodular Borodin et al. (2017)) in order to obtain tractable inference and learning algorithms. Unfortunately, this comes at the expense of the model’s expressive power. Alternatively, greedy or approximate procedures can be used at inference time, though this often introduces approximation errors, and many of these procedures are still computationally expensive (e.g., Rosenfeld et al., 2014).

More recently, neural architectures have been used to extract representations of the entire set of candidate items for ranking, thereby taking into consideration all candidates when assigning a score for each item Mottini and Acuna-Agost (2017); Ai et al. (2018a). This is done by an encoder which processes all candidate items sequentially and produces a compact representation, followed by a scoring step in which pointwise scores are assigned based on this joint representation. This approach can in principle model rich dependencies between ranked items, however its modeling requirements are quite strong. In particular, all the information about interactions between items needs to be stored in the intermediate compact representation and extracted in one-shot when scoring (decoding).

Instead, in this paper we propose a different approach by applying sequential decoding, which assigns item scores conditioned on previously chosen items. Our decoding procedure lets the score of an item change depending on the items already placed in previous positions. This in turn allows the model to account for high-order interactions in a natural and scalable manner. Moreover, our approach is purely data-driven so the model can adapt to various types of inter-item dependencies, including synergies—where items appearing together contribute to their joint appeal, and interference—where items decrease each other’s appeal. In particular, we apply a sequence-to-sequence (seq2seq) model Sutskever et al. (2014) to the ranking task, where the input is the list of candidate items and the output is the resulting ordering. Since the output sequence corresponds to ranked items on the slate, we call this approach sequence-to-slate, or in short seq2slate.

To address the seq2seq problem, we build on the recent success of recurrent neural networks (RNNs) in a wide range of applications (e.g., Sutskever et al., 2014). This allows us to use a deep model to capture rich dependencies between ranked items, while keeping the computational cost of inference manageable. More specifically, we use pointer networks, which are seq2seq models with an attention mechanism for pointing at positions in the input Vinyals et al. (2015b). We show how to train the network end-to-end to optimize several commonly used ranking measures. To this end, we adapt RNN training to use weak supervision in the form of click-through data obtained from logs, instead of relying on ground-truth rankings, which are much more expensive to obtain. Finally, we demonstrate the usefulness of the proposed approach in a number of learning-to-rank benchmarks and in a large-scale, real-world recommendation system.

Ranking as Sequence Prediction

In the seq2seq framework, the probability of an output permutation, or slate, given the inputs is expressed as a product of conditional probabilities according to the chain rule:

This expression is completely general and does not make any conditional independence assumptions. In our case, the conditional $p(\pi_{j}|\pi_{<j},x)\in\Delta^{n}$ (a point in the $n$-dimensional simplex) models the probability of any item being placed at the $j$’th position in the ranking given the items already placed at previous positions. For brevity, we have denoted the prefix permutation $\pi_{<j}=(\pi_{1},\ldots,\pi_{j-1})$. Therefore, this conditional can exactly capture all high-order dependencies between items in the ranked list, including those due to diversity, similarity or other interactions.

Our setting is somewhat different than a standard seq2seq setting in that the output vocabulary is not fixed. In particular, unlike in e.g., machine translation, the same index (position) is populated by different items in different instances (queries). The vocabulary size $n$ itself may also vary per instance in the common case where the number of items to rank can change. This is precisely the problem addressed by pointer networks, which we review next.

We employ the pointer-network architecture of Vinyals et al. (2015b) to model the conditional $p(\pi_{j}|\pi_{<j},x)$. A pointer network uses non-parametric softmax modules, akin to the attention mechanism of Bahdanau et al. (2015), and learns to point to items in its input sequence rather than predicting an index from a fixed-sized vocabulary.

We note the following. (i) Our formulation using sequential decoding lets the score of items (i.e., $p_{i}^{j}$) change depending on items previously placed on the slate, thereby allowing the model to account for high-order interactions in a natural way. (ii) The model makes no explicit assumptions about the type of interactions between items. If the learned conditional in Eq. (2) is close to the true conditional in Eq. (1), then the model can capture rich interactions—including diversity, similarity or others. Hence, our approach is data-driven rather than modeling specific types of interactions (such as multinomial logit), which is a key advantage. We demonstrate the benefits of this flexibility in our experiments (Section 4). (iii) The probability $p_{\theta}(\pi|x)$ is differentiable (in $\theta$) for any fixed permutation $\pi$, which allows gradient-based learning (see Section 3). (iv) The computational cost of inference, dominated by the sequential decoding procedure, is $O(n^{2})$, which is standard in seq2seq models with attention. We also consider a computationally cheaper single-step decoder with linear cost $O(n)$, which outputs a single vector $p^{1}=p_{\theta}(\pi_{1}=\cdot|x)$ (see Eq. (2)), from which we obtain $\pi$ by sorting the values—similar to the approach taken in Mottini and Acuna-Agost (2017); Ai et al. (2018a)); we compare both approaches below.

Previous studies have shown that the order in which the input is processed can significantly affect the performance of sequential models Vinyals et al. (2016); Nam et al. (2017); Ai et al. (2018a). For this reason, we will assume here the availability of a base (or “production”) ranker with which the input sequence is ordered (e.g., a simple pointwise method that ignores the interactions we seek to model), and view the output of our model as a re-ranking of the items. In many real systems such base ranker is readily available. For example, the candidate set may be chosen from a huge item repository by an upstream model. Often candidate generator scores are available and can be used to obtain a base ranking via a simple sort. In this case we obtain the base ranking almost for free, as byproduct of candidate generation. Importantly, using a base ranker and focusing on re-ranking allows our seq2slate model to direct its modeling capacity at interactions between items rather than individual items.

Training with Click-Through Data

We now turn to the task of training the seq2slate model from data. A typical approach to learning in ranking systems is to run an existing ranker “in the wild” and log click-through data, which are then used to train an improved ranking model. This type of training data is relatively inexpensive to obtain, in contrast to human-curated labels such as relevance scores, ratings, or full rankings Joachims (2002).

In the standard seq2seq setting, models are trained to maximize the likelihood of a target sequence of tokens given the input, which can be done by maximizing the likelihood of each target token given the previous target tokens using Eq. (1). In this case, the model is typically fed the ground-truth tokens as inputs to the next prediction step during training, an approach known as teacher forcing Williams and Zipser (1989). Unfortunately, this approach cannot be applied in our setting since we only have access to weak supervision in the form of labels $y$ (e.g., clicks), rather than ground-truth permutations. Instead, we next show how the seq2slate model can be trained directly from the labels $y$.

One viable approach, which has been applied successfully in related tasks (Bello et al., 2017; Zhong et al., 2017), is to use reinforcement learning (RL) to directly optimize for the ranking measure ${\mathcal{R}}(\pi,y)$. In this setup, the objective is to maximize the expected ranking metric obtained by sequences sampled from our model:

One can use policy gradients and stochastic gradient ascent to optimize $\theta$. The gradient is formulated using the popular reinforce update (Williams, 1992):

This can be approximated via Monte-Carlo sampling as follows:

where $k$ indexes ranking instances in a batch of size $B$, the $\pi[k]$ are permutations drawn from the model $p_{\theta}$, and $b_{\mathcal{R}}(x)$ denotes a baseline function that estimates the expected rewards in order to reduce variance.

2 Supervised Training

Policy gradient methods like reinforce are known to induce challenging optimization problems and can suffer from sample inefficiency and difficult credit assignment. As an alternative, we propose supervised learning using the labels $y$. In particular, rather than waiting until the end of the output sequence as in RL above, we can give feedback to the model at each decoder step.

We note that the loss above differs from the actual ranking measures used in evaluation (i.e., MAP, NDCG@k, etc.). On the other hand, any permutation that places the positive labels at the first positions gets 0 loss and optimizes all ranking measures, so in that sense the losses are aligned. This situation is quite common for surrogate losses in machine learning.

Using the definition of the sequence loss above, our goal is to optimize the expected loss:

This corresponds to sampling the permutation $\pi$ according to the model, where $\pi_{j}$ is drawn from $p_{\theta}(\cdot|\pi_{<j},x)$ for each position $j$. For completeness, we derive the expected loss as a function of the model scores $S$ in Appendix A.

Notice that the expected loss in Eq. (7) is differentiable everywhere since both $p_{\theta}(\pi|x)$ and ${\mathcal{L_{\pi}}}(\theta)$ are differentiable for any permutation $\pi$. In this case, the gradient is formulated as:

which can be approximated from samples by:

Here $b_{\mathcal{L}}(x[k])$ is a baseline that approximates ${\mathcal{L}}_{\pi[k]}(\theta)$, introduced for variance reduction. This gradient is analogous to the reinforce update from Eq. (3)–(4), but where the loss ${\mathcal{L}}$ subsumes the role of the reward ${\mathcal{R}}$. Notice, however, that since the loss depends on the model parameters $\theta$ while the reward does not, the resulting update is quite different. Specifically, applying stochastic gradient descent intuitively decreases the probability of drawing samples with high losses (left term in Eq. (8)), as in reinforce, but in addition also reduces the loss of any sample (right term in Eq. (8)), which differs from reinforce (see also Schulman et al., 2015, Eq. (4)).

In many seq2seq applications, using greedy decoding at test time performs better than sampling from the model (e.g., Ranzato et al., 2016; Leblond et al., 2018). Therefore, it makes sense to also consider training the model using a greedy decoding policy, which is an alternative approach to sampling (cf. Eq. (9)). The greedy policy consists of selecting the item that maximizes $p_{\theta}(\cdot|\pi_{<j},x)$ at every step $j$. The resulting permutation $\pi^{*}$ then satisfies $\pi_{j}^{*}=\operatorname*{argmax}_{i}~{}p_{\theta}(\pi_{j}=i|\pi^{*}_{<j},x)$ and our loss simply becomes ${\mathcal{L}}_{\pi^{*}}(\theta)$. Unlike the sampling-based loss in Eq. (7), the greedy policy loss is not continuous everywhere since a small change in the scores $S$ may result in a jump between permutations $\pi^{*}$, and therefore a jump in the value of ${\mathcal{L}}_{\pi^{*}}(\theta)$. Specifically, the loss is non-differentiable when any $s^{j}$ has multiple maximizing arguments. Outside this measure-zero subspace, the loss is continuous (almost everywhere), and the gradient is well-defined.

For both training policies (sampling and greedy), we minimize the loss via stochastic gradient descent over mini-batches in an end-to-end fashion.

Experimental Results

We evaluate the performance of our seq2slate model on a collection of ranking tasks. In Section 4.1 we use learning-to-rank benchmark data to study the behavior of the model. We then apply our approach to a large-scale commercial recommendation system and report the results in Section 4.2.

1 Learning-to-Rank Benchmarks

To understand the behavior of the proposed model, we conduct experiments using two learning-to-rank datasets. We use two of the largest publicly available benchmarks: the Yahoo Learning to Rank Challenge data (set 1),https://webscope.sandbox.yahoo.com/catalog.php?datatype=c and the Microsoft Web30k dataset.https://www.microsoft.com/en-us/research/project/mslr/ These datasets only provide feature vectors for each query-document pair, so all context (query) features are embedded within the item feature vectors themselves.

We adapt the procedure proposed by Joachims et al. (2017) to generate click data. The original procedure is as follows: first, a base ranker is trained from the raw data. We select this base ranker by training all models in the RankLib package,https://sourceforge.net/p/lemur/wiki/RankLib/ and choosing the one with the best performance on each data set (MART for Yahoo and LambdaMART for Web30k). We generate an item ranking using the base model, which is then used to generate training data by simulating a user “cascade” model: a user observes each item with decaying probability $1/i^{\eta}$, where $i$ is the base rank of the item and $\eta$ is a parameter of the generative model. This simulates a noisy sequential scan by the user. An observed item is clicked if its ground-truth relevance score is above a threshold (relevant: $\{2,3,4\}$, irrelevant: $\{0,1\}$), otherwise no click is generated.

Unfortunately, the original datasets only include a per-item relevance score, which is independent of the other items. This means that there are no direct high-order interactions between the clicks, and therefore the joint probability in Eq. (1) is just $p(\pi|x)=\prod_{j=1}^{n}p(\pi_{j}|x)$. In this case a pointwise ranker is optimal so there would be no need for seq2slate. Therefore, in order to introduce high-order dependencies, we augment the above procedure as follows, creating a generative process dubbed diverse-clicks. When observing a relevant item, the user will only click if it is not too similar to previously clicked items (i.e, diverse enough), thus reducing the total number of clicks. Similarity is defined as being in the smallest $q$ percentile (i.e., $q=0.5$ is the median) of Euclidean distances between pairs of feature vectors within the same ranking instance: $D_{ij}=\|x_{i}-x_{j}\|$. We use $\eta=0$ (no decay, since clicks are sparse anyway due to the diversity term) and $q=0.5$. We also discuss variations of this model below. Since our focus is on modeling high-order interactions, all results reported in this section are w.r.t. the generated binary labels and not the original relevance scores.

Using the generated training data, we train both our seq2slate model and baseline rankers from the RankLib package: AdaRank Xu and Li (2007), Coordinate Ascent Metzler and Croft (2007), LambdaMART Wu et al. (2010), ListNet Cao et al. (2007), MART Friedman (2001), Random Forests Breiman (2001), RankBoost Freund et al. (2003), RankNet Burges et al. (2005). Some of these baselines use deep neural networks (e.g., RankNet, ListNet), so they are strong state-of-the-art models with comparable complexity to seq2slate. The results in Table 1 show that seq2slate significantly outperforms all the baselines, suggesting that it can better capture and exploit the dependencies between items in the data.

To better understand the behavior of the model, we visualize the probabilities of the attention from Eq. (2) for one of the test instances in Fig. 2. Interestingly, the model produces slates that are close to the input ranking, but with some items demoted to lower positions, presumably due to the interactions with previous items.

We next consider several variations of the generative model and of the seq2slate model itself. Results are reported in Table 2. The rank-gain metric per example is computed by summing the positions change of all positive labels in the re-ranking, and this is averaged over all examples (queries).

In Table 2, we compare the different training variants outlined in Section 3, namely, cross entropy with the greedy or sampling policy, a smooth hinge loss with $\gamma=1.0$, and reinforce. We find that supervised learning with cross entropy generally performs best, with the smooth hinge loss doing slightly worse. Our weakly supervised training methods have positive rank gain on all datasets, meaning they improve over the base ranker. The results from Table 2 suggest that training with reinforce yields comparable results on Yahoo but significantly worse results on the more challenging Web30k dataset. In terms of training time, reinforce needed 4X more time till convergence. We find no significant difference in performance between relying on the greedy and sampling policies during training.

We compare seq2slate to the model which uses a single decoding step, referred to as one-step decoder (see Section 2). In Table 2 we see that this model has comparable performance to the sequential decoder. One possible explanation for the comparable performance of the one-step decoder is that the interactions in our generated data are rather simple and can be effectively learned by the encoder. By contrast, in Section 4.2 we show that on more complex real-world data, sequential decoding can perform significantly better than one-step decoding. In terms of runtime, we observed a 4X decrease in training time and a 3X decrease in inference time for the one-step decoder compared to sequential decoding (for the real-world data in Section 4.2 below, one-step decoding was 2.5X faster per iteration in both training and inference). This suggests that when inference time is crucial, as in many real-world systems, one might prefer the faster single-shot option. Having said that, we point out that even with sequential decoding the runtime was not a bottleneck in our case and we were able to train a seq2slate model on millions of examples in a couple of hours, and serve live traffic in $O(10)$ milliseconds. For this reason we also did not make an effort to optimize the code, so the numbers above can probably be reduced significantly.

Previous work suggests that the performance of seq2seq models is often sensitive to the order in which the input is processed Vinyals et al. (2016); Nam et al. (2017); Ai et al. (2018a). To test the sensitivity of seq2slate to the order in which items are processed, we consider the use of seq2slate without relying on the base ranker to order the input. Instead, items are fed to the model in random order. Since learning the correct ranking from a single example may be hard, we generate multiple copies of each training example, each with a different randomly shuffled input order. Specifically, in Table 2 we show results for 10 generated examples per original example under ‘shuffled data’. The results show that the performance is indeed significantly worse in this case, which is consistent with previous studies. It suggests that reranking is an easier task than ranking from scratch.

To demonstrate the flexibility of seq2slate, we generate data using a variant of the diverse-clicks model above. Specifically, in the similar-clicks model, the user also clicks on observed irrelevant items if they are similar to previously clicked items (increasing the number of total clicks). As above, we use the pairwise distances in feature space $D_{ij}$ to determine similarity. For this model we use $q=0.5$, and $\eta=0.3$ for Web30k, $\eta=0.1$ for Yahoo, to keep the proportion of positive labels similar.The value of $\eta$ was chosen such that the percentage of examples with no positive labels (clicks) at all remained small enough and roughly the same in all datasets (around 1.15% of all examples). The results in Table 3 show that seq2slate has comparable performance to the baseline rankers, with slightly lower performance on Yahoo and significantly better performance on the harder Web30k data. This demonstrates that our model can adapt to various types of interactions in the data. Notice that no changes to the model or training algorithm were necessary for seq2slate. In contrast, if one used a specific interaction model for ‘diverse-clicks’, then a different model would be required for the ‘similar-clicks’ data, a distinction not needed with seq2slate.

2 Real-World Data

We also apply seq2slate to a ranking problem from a large-scale commercial recommendation system. We train the model using massive click-through logs (comprising roughly $O(10^{7})$ instances) with cross-entropy loss, the greedy policy, L2-regularization and dropout. The data has item sets of varying size, with an average $n$ of 10.24 items per example. We learn embeddings of the raw inputs as part of training.

Table 5 shows the performance of seq2slate and the one-step decoder compared to the production base ranker on test data (of roughly the same size as the training data). Significant gains are observed in all performance metrics, with sequential decoding outperforming the one-step decoder. This suggests that sequential decoding may more faithfully capture complex dependencies between the items.

Finally, we let the learned seq2slate model run in a live experiment (A/B testing) and re-rank the result of the current production recommender system. We compute the click-through rate (CTR) in each position (#clicks/#examples) for seq2slate. The production base ranker serves traffic outside the experiment, and we compute CTR per position for this traffic as well. Fig. 3 shows the difference in CTR per position, indicating that seq2slate has significantly higher CTR in the top positions. This suggests that seq2slate indeed places items that are likely to be chosen higher in the ranking.

Related Work

In this section we discuss additional related work. We build on the recent impressive success of seq2seq models in complex prediction tasks, including machine translation Sutskever et al. (2014); Bahdanau et al. (2015), parsing Vinyals et al. (2015a), combinatorial optimization Vinyals et al. (2015b); Bello et al. (2017), multi-label classification Wang et al. (2016); Nam et al. (2017), and others. Our work differs in that we explicitly target the ranking task, which requires a novel approach to training seq2seq models from weak feedback (click-through data).

Most of the work on ranking mentioned above uses shallow representations. However, in recent years deep models have been used for information retrieval, focusing on embedding queries, documents and query-document pairs Huang et al. (2013); Guo et al. (2016); Palangi et al. (2016); Wang and Klabjan (2017); Pang et al. (2017) (see also recent survey by Mitra and Craswell (2017)). Rather than embedding individual items, in seq2slate a representation of the entire slate of items is learned and encoded in the RNN state. Moreover, learning the embeddings ($x$) can be easily incorporated into the training of the sequence model to optimize both simultaneously end-to-end.

Closest to ours are the recent works of Mottini and Acuna-Agost (2017) and Ai et al. (2018a), where an RNN is used to encode a set of items for ranking. There are some differences between the approach of Ai et al. (2018a) and ours, including using GRU cells instead of LSTM cells, reversing the input order (the highest ranking item is fed to the encoder last), and training from relevance scores instead of click-through data. More importantly, both works Mottini and Acuna-Agost (2017); Ai et al. (2018a) use a single decoding step. In contrast, we apply sequential decoding, which directly allows item scores to change based on previously chosen items. We believe that this significantly simplifies modeling and inference with complex high-order interactions between items, and indeed show that it performs much better in practice (see Section 4.2).

Finally, Santa Cruz et al. (2017) recently proposed an elegant deep learning framework for learning permutations based on the so called Sinkhorn operator, building on prior work by Adams and Zemel (2011). Their approach uses a continuous relaxation of permutation matrices (i.e., the set of doubly-stochastic matrices, or the Birkhoff polytope). Followup work has focused on improved training and inference procedures, including a Gumbel softmax distribution to enable efficient learning Mena et al. (2018), a reparameterization of the Birkhoff Polytope for variational inference Linderman et al. (2018), and an Actor-Critic policy gradient training procedure Emami and Ranka (2018). However, these works are focused on reconstruction of scrambled objects (i.e., matchings), and it is not obvious how to extend it to our ranking setting, where no ground-truth permutation is available.

Conclusion

We presented a novel approach to ranking sets of items called seq2slate. We found the formalism of pointer-networks particularly suitable for this setting. We emphasized the modeling and computational advantages of using sequential decoding, which allowed the model to dynamically adjust placement of items on the slate given previous choices. We addressed the challenge of training the model from weak user feedback (click-trough logs) to improve the ranking quality. To this end, we proposed new sequence losses along with corresponding gradient-based updates. Our experiments show that the proposed approach is highly scalable and can deliver significant improvements in ranking results.

Our work can be extended in several directions. In terms of architecture, we aim to explore the Transformer network Vaswani et al. (2017); Dehghani et al. (2019) in place of the RNN. Several algorithmic variants can potentially improve the performance of our model. For inference, beam-search has been shown to improve predictions of several seq2seq models Wiseman and Rush (2016), and we believe can do the same for seq2slate. For training, several approaches have been recently proposed for seq2seq models, including Actor-Critic Bahdanau et al. (2017) and more recently SeaRNN Leblond et al. (2018), and it will be interesting to test their performance in the ranking setting.

Finally, an interesting future direction is to study off-policy correction for seq2slate Joachims et al. (2018); Chen et al. (2019). In this setting, training examples are assigned importance weights in order to account for the fact that the labels were obtained using a different policy than the one we wish to evaluate during training. In particular, the expected sequence loss is adjusted to account for this mismatch as follows:Substituting $\mathcal{L}_{\pi}(\theta)$ by $\mathcal{R}(\pi,y)$ yields an equivalent formulation for the expected reward from Section 3.1.

where $p_{\text{base}}$ is the probability of $\pi$ under the base ranker (i.e., logging policy). This expectation can then be approximated from logged samples as in Section 3. We leave this extension to future work.

Appendix A Derivation of the Expected Loss

Here we show the expected loss as a function of the model scores $S$,

References