ƒery-level Ranker Specialization

Abstract

Traditional Learning to Rank models optimize a single ranking function for all available queries. Œis assumes that all queries come from a homogenous source. Instead, it seems reasonable to assume that queries originate from heterogenous sources, where certain queries may require documents to be ranked di‚erently. We introduce the Specialized Ranker Model which assigns queries to di‚erent rankers that become specialized on a subset of the available queries. We provide a theoretical foundation for this model starting from the listwise PlackeŠ-Luce ranking model and derive a computationally feasible expectation-maximization procedure to infer the model's parameters. Furthermore we experiment using a noisy oracle to model the risk/reward tradeo‚ that exists when deciding which specialized ranker to use for unseen queries.

INTRODUCTION

Search engines have long been the predominant way to navigate the World Wide Web. As the amount of available content continues to grow and the popularity of search engines increases, the necessity of quality search systems is ever increasing. One of the most vital parts of any search system is the Learning to Rank (LTR) model, it considers hundreds of relevance signals and decides in what order documents should be displayed to the user [ 9 ].

Existing work has mainly focused on algorithms that optimize a single ranking model for all available queries [ 1, 2, 7, 9 ]. In contrast it seems reasonable to assume that not all queries should be ranked the same. For instance the queries ICTIR 2017 Home Page and Python require very di‚erent rankers. Œe former requires a ranker that focusses on retrieving a single relevant result and is thus navigational where the laŠer needs a ranker which provides documents relevant to di‚erent aspects of python and is more informational. In theory non-linear models could recognize this distinction and rank accordingly, however in practice the algorithms have limited capability of recognizing such query level paŠerns [ 11 ]. Œe main research question we address in this paper is: Main RQ Can a mixture of rankers e‚ectively recognize di‚erent ranking paŠerns in LTR data? We propose a mixture of rankers approach that assigns queries to di‚erent rankers, thus these rankers become specialized on a subset of the available queries. Assignment is based on how the documents of a query should be ranked, thus we do not make assumptions about anything like query intent but let the model €nd such paŠerns implicitly. 2 Combining relevance signals to rank documents is the central problem in the €eld of learning to rank. Listwise methods have seen the greatest success [ 1, 2 ]. Œese approaches treat entire lists of ranked documents as learning instances. It is so successful because it can directly optimize the objective of ranking. Œe traditional learning to rank methods, however, learn a single ranking function or model with which all queries are ranked. In our work we capture heterogeneous ranking paŠerns and build a mixture of rankers based on a listwise approach.

Œe closest related work is the PlackeŠ-Luce Regression Mixture Model [ 14 ]. Œere, the authors deal with item preferences, where users are assigned to so-called “preference groups”. Œese groups contain users that have similar preferences in the way that they rank items. Our method bears a lot of similarity to their method, but there are two major di‚erences that set our work apart. First, our work applies to the LTR seŠing, where we model queries and unique document sets for each query. Second is the fact that we deal with incomplete preferences for ranking. We consider the scenario where relevance labels are shared across documents resulting in multiple correct rankings. 3

MODEL

In this section we discuss the Specialized Rankers Model (SRM) and provide a formal de€nition. We contrast with existing work [ 14 ] by considering the predominant LTR scenario in Information Retrieval (IR). Here a query qn is provided by a user at each time step and the system responds by displaying a result list of documents r .

Œe idea of this paper is to €nd several specialist rankers that work very well for a subset of queries. Œe main assumption is that there are K query groups. ‹eries within a group agree with each other on how documents should be ranked whilst disagreeing with queries from other groups. Each of the query groups has a ranking function modeled by PLk which determines the preferred order of documents. No assumptions are made about what characterizes such groups or what the reasons for their disagreement are; instead, SRM recognizes them solely based on their ranking preferences.

For this paper we assume that the ranking functions are PlackeŠLuce (PL) models, thus the ranking function is a probabilistic distribution over all possible rankings of fd gn . For brevity we will denote the feature representation of a query-document pair Φ(qn ; d ) = d, the PlackeŠ-Luce probability [ 10, 12 ] of a ranking r is then de€ned by:

PLk (r ) = jr j Y Pk (ri j fri ; ri+1; :::; r jr j g) i=1 (1) d jD j σ w r

K α π z

N where Pk (di j D) gives the probability that document di is sampled out of the set of remaining documents D:

Pk (di j D) = Pdj 2D exp( fk (dj )) : exp( fk (di )) Here, fk (d ) is a scoring function that predicts a relevance score for each document d. In the €eld of IR the PL model is the basis for the Listwise approach introduced by Cao et al. [ 2 ]. With this model a result list is generated stepwise, where at each step a document is sampled from the remaining documents based on Pk . Since this probability depends on both the individual document as the remaining documents this approach is considered Listwise. Furthermore, in practice the PL model is only used for optimization, since nondeterministic ranking models are o‰en avoided in production. A‰er optimization the production ranker simply orders the documents on their fk (d ) values, thus giving the ranking that maximizes the PL model [ 2 ]. Œe original PL model did not include a exponent and only requires every object to have a positively associated score. However, the exponent allows any scoring function fk to be valid and is thus the prominent approach [ 2, 14 ]. For simplicity we will assume fk is the linear model:

fk (d ) = wkT d; where the weights wk have to be learned for each of the K ranking groups. We note, however, that any function that is di‚erentiable with respect to its weights can be used here.

Figure 1 displays the plate notation for SRM, the generative process of the graphical model can be described as follows: (1) Œe mixture proportions of the K ranking groups π is sampled from a Dirichlet distribution with the prior α : (2) Œe weights wk for each of the K ranking groups is sampled from the multivariate Gaussian distribution with zero mean and σ 2 variance: π

Dirichlet (α ): wk

N (0; σ 2): (3) For all queries fqn j n = 1 : : : N g (2) (3) (4) (5) (6) (7) (8) (9) (a) A ranking group zn is sampled (b) A ranking of its corresponding documents Dn is sampled from the PL model belonging to its ranking group zn : zn rn

Multinomial(π ):

PL(r j Dn ; wzn ) Accordingly, this gives us the following likelihood:

L (R; Z ;W ; π j D) = P (π j α )

K Y P (wk j 0; σ 2) k=1 N Y P (zn j π )PL(rn j wzn ; Dn ) n=1 where R = fr1; : : : ; rN g is the set of all N rankings, W = fw1, . . . , wK g the set of K weights, and Z = fz1; : : : ; zN g the set of all ranking group assignments.

Œe novelty of this model w.r.t. previous IR methods comes from the existence of multiple rankers which producing the preferred rankings. In contrast with the PL Regression Model [ 14 ] the SRM models queries and unique document sets for each query. Furthermore, if K = 1 is chosen this method reduced to the Listwise approach [ 2 ] where a single ranker produced all preferred rankings. However there is a mismatch between LTR data and the assumption that a single preferred ranking per query exists. Because most LTR datasets are based on relevance labels, some ambiguity exists since there is no preference in the order of documents with the same level of relevance. To the best of our knowledge, this ambiguity has been ignored in previous work regarding the Listwise approach, thus we contrast further by introducing a method that can handle such ambiguity. 4

OPTIMIZATION PROCESS

In order to optimize our mixture model the Expectation Maximization (EM) algorithm is used. EM is an iterative algorithm for maximizing the likelihood of a model that contains latent variables. In our case the group assignments zn can not be observed, during optimization EM considers the expected values of the zn and chooses the parameters wk and π accordingly. By iteratively estimating zn and then maximizing the remaining parameters, the procedure recognizes the K ranking groups while simultaneously €nding the optimal rankers wk for each group. Œe following sections will discuss the derivation of the expectation and maximization steps separately. 4.1

Ambiguity in LTR datasets

Unlike previous Listwise LTR work [ 2 ], we do not assume that there is just one preferred ranking r . Instead we consider many di‚erent possible rankings that are correct. Œis generalization is appropriate because LTR datasets are usually graded on an ordinal scale, where many documents can share the same relevance label. Any permutation of the documents that corresponds to these relevance labels can be considered a correct ranking.

Each query has a corresponding set of documents fd gq and a set of correct rankings of these documents Ωq = frq1; rq2; : : :g. For notational simplicity we de€ne the probability that a correct ranking is sampled:

P (Ωn j wzn ; Dn ) =

PL(rn j wzn ; Dn )

X rn 2Ωn 4.2

Expectation

To formulate the EM algorithm, we de€ne the Q function as the conditional expectation of the log-likelihood:

Q (W ; π ;W 0; π 0) = EZ jR;W ; π; D [log L (R; Z ;W ; π j D)] = log P (π j α ) +

K X log P wk j 0; σ 2 k=1

N K + X X Tnk (log P (zn = k j π ) + log P (Ωn j wk ; Dn )) : n=1 k=1 Œus, the output of the expectation step are the membership probabilities Tnk , which can be computed as follows:

Tnk = PK k0=1 P (zn = k 0 j π )P (Ωn j wk0; Dn )

P (zn = k j π )P (Ωn j wk ; Dn ) Œis resembles a weighted and L2-regularized SGD step, where the regularization strength is σ12 and where each query is weighted according to Tnk . Œe major challenge that remains is computing @ log P (Ωn j wk ; Dn ). Using the chain the stochastic gradient @wk rule and product rule we end up with the following formula: X r 2Ωn P (Ωn j wk ; Dn ) i=1

Pk (ri j fri ; : : : ; r jr j g) (10) (11) (13) (14) In order to compute @w@k Pk (ri j fri ; : : : ; r jr j g), we use the quotient rule and get the following result: (15) (16) Pk (ri j fri ; : : : ; r jr j g)

Pjjx=ij efk (dj ) fk0(di )

fk0(dj ) Pjjx=ij efk (dj ) Plugging equation 15 into equation 14, gives us the gradient: X

PL(r j wk ; Dn ) Xjrj Pjjr=ji efk (dj ) fk0(di ) fk0(dj ) r 2Ωn P (Ωn j wk ; Dn ) i=1 Pjjr=ji efk (dj ) With this gradient, we can now €nd the optimal values for wk using SGD. Note, however, that computing the gradient still requires computing a sum over all rankings r in Ωn , which is prohibitively expensive for datasets with many documents per query. In the next section, we will discuss how to tackle this large computational cost. 4.4

Dealing with the complexity of ambiguity

Œe size of the set of correct rankings Ωn is on the order of O (jDn j!). As a result, computing the EM steps quickly becomes infeasible when there are many documents to be ranked per query. To solve this problem we use several techniques: Top-m. Similar to the original Listwise method [ 2 ] we use the top-m approach to reduce computational complexity. Œe set of correct top-m rankings is de€ned as: Ωn = r j 9r 0 2Ωn r0 = r00 ^ : : : ^ rm = r m0 ) ˆ ( Accordingly the likelihood that the top m documents are correct is: P ( Ωˆn j wzn ; Dn ). Œe derivation for the E-step and M-step remain the same, but use Ωˆ n instead of Ωn .

Dynamic programming. An important property of the PL model is that the probability of a document being sampled only depends on the set of remaining documents. Œus the order of the previously sampled documents does not maŠer, as a result the E-step and Mstep can be computed by iterating over all subsets of documents instead of all their permutations. Using Dynamic Programming this reduces the computational complexity of our method to O 2jDn j . Importance sampling. Despite the large gains achieved with dynamic programming, there are queries where the number of relevant documents is so great that exact computations are still intractable. For these cases we have a €nal sampling method that approximates the gradient but can be computed in constant time. Œis approach samples a subset of rankings from Ωn and then performs calculations as if this is the complete set of correct rankings. However since there is no way to directly sample Ωn , we sample rankings from the current ranker and using importance sampling weigh them so that every ranker in Ωn has the same weight. Œis approach works well because generally a small subset of Ωn has almost all the probability mass (PL(r j wk ; Dn )). 5

EXPERIMENTS

We evaluate our model and method on two widely used learning to rank datasets: MSLR-WEB10k [ 13 ]. Œis dataset contains 10,000 queries. It represents query-document pairs as 136-dimensional feature vector 0.65 0.60 0.40 0.35

MSLR-10k 10 Rankers 5 Rankers 2 Rankers 1 Ranker LambdaMART and grades them on a scale from 0 (irrelevant) to 4 (perfectly relevant). 6,000 queries are used for training, 2,000 for validation and 2,000 for testing.

Webscope [ 3 ]. Œis dataset contains 29,921 queries. Œe querydocument pairs are represented using 519-dimensional feature vector and graded on a scale from 0 (irrelevant) to 4 (perfectly relevant). 19,944 queries are used for training, 2,994 for validation and 6,983 for testing.

We evaluate the rankings produced by our models using nDCG [ 6 ]. Given a test query, we assign one of K specialist rankers. In this paper we choose an oracle setup so that we can systematically control the number of mistakes we make in assigning a specialist ranker to a given query. An oracle’s accuracy ranges from 0% (choosing a ranker uniformly at random) to 100% (choosing the best ranker every time). Œis allows us to study the risk/reward tradeo‚ associated with selecting a specialist ranker for unseen test queries.

We train the SRM model for di‚erent number of rankers (K = 1; 2; 5; 10) using hyperparameters α = 1:01 and σ = 0:1. In our implementation we use Adam [ 8 ] as the SGD optimizer with a minibatch size of 128 and the default Adam seŠings β1 = 0:9, β2 = 0:999 and ϵ = 1 10 7. We compare our work with LambdaMART, a state-of-the-art non-linear model [ 1 ]. Œe LambdaMART model’s hyper-parameters (sampling rate, feature sampling rate, learning rate, maximum number of leaf nodes and minimum number of observations per leaf) are tuned on a held-out validation set.

We evaluate our model’s performance on the test set using the aforementioned oracle setup. Œe results are shown in Figure 2. As expected, when the oracle becomes more accurate, the performance gains become greater. However, if one were to only select the best ranker less than 30% of the time, the model would perform worse than just using a single ranker. Œis makes sense, as selecting a suboptimal ranker for a query can have adverse e‚ects on its ranking performance. If the oracle selects the best specialized ranker about 60% of the time, we already see a statistically signi€cant performance gain over using a single ranker. An 80% accurate oracle outperforms LambdaMART if at least 5 to 10 specialized rankers are used.

An oracle function could in theory be realized by using querylevel features. Such features occur very rarely in public LTR datasets, thus this falls outside our experimental possibilities. Previous work that uses datasets obtained from commercial search engines has shown that classifying queries, especially for specialization purposes, is possible [ 4, 5 ]. 6

CONCLUSION

In this paper we introduce SRM, a model that uses a mixture of ranking functions to recognize di‚erent ranking paŠerns in LTR data. We describe an ecient expectation-maximization algorithm for inferring the model’s parameters. Our €ndings show that the model picks up on latent paŠerns in LTR datasets.

We evaluated SRM by making use of an oracle setup, where an oracle select the best specialized ranker for the query at hand. Depending on the dataset our experiments show that a 60% accurate oracle can already signi€cantly outperform a single linear ranker. We require an at least 80% accurate oracle to signi€cantly outperform a state-of-the-art LambdaMART model.

Œere are several directions for future work: (1) In our experimental setup we use a linear function fk (d ), but our model can easily be extended to non-linear functions such as deep neural networks, which are worth investigating. (2) Assigning test queries to specialized rankers based on query-level features has previously been shown to be possible [ 4 ] and would be an interesting continuation.

Acknowledgements

Œis research was supported by Ahold Delhaize, Amsterdam Data Science, the Bloomberg Research Grant program, the Criteo Faculty Research Award program, Elsevier, the European Community’s Seventh Framework Programme (FP7/2007-2013) under grant agreement nr 312827 (VOX-Pol), the Microso‰ Research Ph.D. program, the Netherlands Institute for Sound and Vision, the Netherlands Organisation for Scienti€c Research (NWO) under project nrs 612.001.116, HOR-11-10, CI-14-25, 652.002.001, 612.001.551, 652.001.003, and Yandex. All content represents the opinion of the authors, which is not necessarily shared or endorsed by their respective employers and/or sponsors.

References

[1] Christopher JC Burges . 2010 . From ranknet to lambdarank to lambdamart: An overview . Learning 11 , 23 - 581 ( 2010 ), 81 .

[2] Zhe Cao , Tao Qin, Tie-Yan Liu , Ming-Feng Tsai , and Hang Li . 2007 . Learning to rank: from pairwise approach to listwise approach . In ICML. ACM.

[3] Olivier Chapelle and Yi Chang . 2011 . Yahoo! learning to rank challenge overview .. In Yahoo! Learning to Rank Challenge. 1 - 24 .

[4] Xiubo Geng , Tie-Yan Liu , Tao Qin, Andrew Arnold, Hang Li , and Heung-Yeung Shum . 2008 . ‹ery dependent ranking using k-nearest neighbor . In SIGIR. ACM , 115 - 122 .

[5] Ahmed Hassan , Ryen W White, and Yi-Min Wang . 2013 . Toward self-correcting search engines: Using underperforming queries to improve search . In SIGIR. ACM , 263 - 272 .

[6] Kalervo Ja ¨rvelin and Jaana Keka¨la¨inen . 2002 . Cumulated gain-based evaluation of IR techniques . TOIS 20 , 4 ( 2002 ), 422 - 446 .

[7] Œorsten Joachims. 2002 . Optimizing search engines using clickthrough data . In SIGKDD. ACM , 133 - 142 .

[8] Diederik Kingma and Jimmy Ba . 2014 . Adam: A method for stochastic optimization . arXiv preprint arXiv:1412.6980 ( 2014 ).

[9] Tie-Yan Liu and others. 2009 . Learning to rank for information retrieval . Foundations and Trends® in Information Retrieval 3 , 3 ( 2009 ), 225 - 331 .

[10] R Duncan Luce . 2005 . Individual Choice Behavior: A Šeoretical Analysis . Courier Corporation.

[11] Craig Macdonald , Rodrygo LT Santos, and Iadh Ounis . 2012 . On the usefulness of query features for learning to rank . In Proceedings of the 21st ACM international conference on Information and knowledge management. ACM , 2559 - 2562 .

[12] Robin L Placke Š . 1975 . Œe analysis of permutations . Applied Statistics 24 , 2 ( 1975 ), 193 - 202 .

[13] Tao Qin and Tie-Yan Liu . 2013 . Introducing LETOR 4.0 Datasets. CoRR abs/1306 .2597 ( 2013 ). hŠp://arxiv.org/abs/1306.2597

[14] Maksim Tkachenko and Hady W Lauw. 2016 . PlackeŠ -Luce Regression Mixture Model for Heterogeneous Rankings . In CIKM. ACM , 237 - 246 .