Learning to Rank (LtR) techniques leverage assessed samples of query-document relevance to learn ranking functions able to exploit the noisy signals hidden in the features used to represent queries and documents. In this paper, we explore how to enhance the state-ofthe-art LambdaMart algorithm by integrating in the training process an explicit knowledge of the underlying user-interaction model and the possibility of targeting di erent objective functions, that can e ectively drive the algorithm towards promising areas of the search space. We enrich the learning algorithm in two ways: (i) by considering complex query-based user dynamics instead than simply discounting the gain by the rank position; (ii) by designing a learning path across di erent loss functions that can capture di erent signals in the training data. Our extensive experiments, conducted on publicly available datasets, show that the proposed solution permits to improve various ranking quality measures by statistically signi cant margins.
In [
Copyright c 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). This volume is published
and copyrighted by its editors. SEBD 2020, June 21-24, 2020, Villasimius, Italy.
{ modelling user dynamics into LambdaMart: instead of proposing new
features to account for user behavior and then training the LtR model on this
extended set of features, we: (1) explicitly model the user dynamics in
scanning a ranked result list with Markov chains trained on query log data; (2)
de ne a novel measure which embeds this trained Markov chain
(Normalized Markov Cumulated Gain (nMCG)), and modify the LambdaMart loss
function to rely on this measure instead of the usual Normalized Discounted
Cumulated Gain (nDCG) [
An LtR algorithm exploits a ground-truth set of training examples in order to
learn a document scoring function [
LambdaRank can be summarized as follows. Given a query q and two
candidate documents di and dj in the training set with relevance labels li and lj
respectively, si and sj are the scores currently predicted for the documents. The
lambda gradient of any given Information Retrieval (IR) quality function Q, as
de ned in [
Qij
1
1 + esi sj
where, the sign is determined by the document labels only, the rst factor Q
is the quality variation when swapping scores si and sj , and the second factor is
the derivative of the RankNet cost [
0.25
0.2
4Rank Positions 8
6
10
4Rank Positions 8
6
100.2
We summarize here our methodology [
Figure 1(a) plots the stationary distributions obtained from the Yandex query log described in Section ??. We focus on two distinct macroscopic behavior types, and, for the sake of simplicity, we call navigational the queries where users concentrated on just the rst item, and we consider all the other queries as informational since users tend to visit more documents. On the basis of the above experimental observations, we claim that the user dynamics can be described as a mixture of the navigational and informational behavior. The navigational component is represented by the inverse of the rank position 1i , while the informational component is linear with respect to the rank position i. Therefore, we model the user dynamics as
(i) = i 1 + i + where the parameters , and are calibrated in order to t the estimated stationary distributions computed on the Yandex dataset.
Figures 1(b) and 1(c) show the stationary distributions together with the tted curves for the navigational and informational cases, respectively. In Figure 1(b) the stationary distribution is the same reported in the red line of Figure 1(a), i.e. queries with just 1 relevant document, while to compute the stationary distribution reported in Figure 1(c) we aggregate all the user dynamics corresponding to the other queries, i.e. queries without relevant documents or with more than one relevant document.
We enhance the existing LambdaMart algorithm by replacing the above Q with a new quality measure which integrates the proposed user dynamics . This new measure is called Normalized Markov Cumulated Gain (nMCG) and it is de ned as follows:
Pi k 2li 1 c(i) 1) c(h) where li is the relevance label of the i-th ranked document and c(i) is the user dynamics function at rank i relative to the query class c, either navigational or informational. Basically, nMCG can be seen as an extension of nDCG, where the discount function is de ned by the user dynamic and depends on the query class. Moreover, since c depends on the query class, i.e. depends on the query q, we are optimizing two di erent variants of the same quality measure nMCG across the training dataset. Finally, nMCG@kij can be computed e ciently as follows: Hereinafter, we use nMCG-MART to refer to the described variant of LambdaMart aimed at maximizing nMCG. 2.2
Applying a Continuation Methods (CM) to a cost function C means to de ne a sequence of cost functions C with 2 [0; 1], such that by increasing , the complexity of the function increases. Therefore, C0 represents a highly smoothed version of the original cost function corresponding to C1.
We implement CMs in the contest of forests of decision trees as a two steps learning process, where the initial trees are trained by minimizing a cost function C0 and the remaining trees are trained by optimizing C1. We did not explore in this work more complex multi-stage scenarios, which can trivially extend this work. We denote continuation methods as C0T0 C1T1, meaning that the rst T0 trees of the ensemble minimize C0, while the remaining T1 trees minimize C1, additively re ning the prediction of the rst T0 trees.
In order to apply a CM to LambdaMart we need to smooth the
LambdaMart loss function. Smoother variants of nDCG have been previously
proposed, e.g. SoftNDCG [
The rst option we consider is to use as C0 the Mean Square Error (MSE) as a smooth variant of the target nDCG measure. Even if MSE is easily di erentiable and an MSE equal to 0 corresponds to the maximum nDCG value, the MSE cost cannot be considered a smooth approximation of nDCG. Nevertheless, Gradient Boosted Regression Trees that minimize MSE are known to perform well, even at optimizing nDCG. The rationale of using C0 equal to MSE is that of using a smooth function that alone exhibits good performance as a good seed for the re nement that the optimization of nDCG or nMCG may provide.
The second option we consider is to use Recall@k as C0. Recall is not a di erentiable function either, as it su ers the same issues as nDCG. Still, it is an easier function to be optimized because it considers binary relevance instead of graded, and it discriminates between documents above or below the cut-o k without further discounting according to document ranks. The rationale is to train the rst portion of the forest in order to place the most relevant documents above the cut-o , and then to complete the training with the target metric nDCG or nMCG to adjust their relative ranking.
Since Recall is not di erentiable, we devised a LambdaMart-based approach similar to nMCG-MART. We de ne nRecall@kij as the normalized change in Recall@k when swapping the i-th and j-th documents in the current ranking. Given a relevance binarization thresholds , nRecall@kij is de ned as follows: 1li 1lj Ph 1lh (1i k 1j k) ; where 1p is the indicator function evaluating to 1 if predicate p is true and 0 otherwise.
Finally, in addition to C1 being equal to nDCG, we also consider the case where nMCG-MART is used as C1. Our goal is to evaluate the added value of exploiting the user dynamics in producing the nal ranking, even when the rst trees of the forest where built by optimizing a di erent metric.
In conclusion, we compare the e ectiveness of LambdaMart and nMCGMART and we asses the bene t they can receive by a pre-training on a di erent metric, which allows the two algorithms to initiate their search process from a di erent point in the solution space, possibly leading to a better nal solution. 3
We remark that since there is no publicly available dataset providing, at the same
time, user session data, document relevance and query-document pairs features,
we have to use two di erent datasets in our analysis. Therefore, we calibrate the
user model on the click log dataset provided by Yandex [
We used LambdaMart as the reference LtR algorithm. Speci cally, we used (and modi ed) the open source implementation of LambdaMart provided in the LightGBM gradient boosting framework and swiped the hyper parameters
Available at https://github.com/Microsoft/LightGBM. with cross-validation so as to maximize the average performance over the validation folds.
As signi cance test, we computed Fisher's randomization test with 100 000
random permutations and = 0:05, which is the most appropriate statistical
test to evaluate whether two approaches di er signi cantly [
As name convention, all the CM approaches are referred with the name of
the rst objective function C0, the corresponding number of trees used during
the rst training phase T0, followed by the name of the second objective function
C1 with the corresponding number of trees T1. Therefore, recallT300 ndcgT200
means that the model is trained with Recall@10 for the rst 300 trees and then
with nDCG@10 for the following 200 trees. Moreover, we exploit as reference
models for CM approaches nMCG-MART and mseT200 ndcgT300, which is the
best performing model proposed in [
In this section we summarize the main ndings without reporting any gure or
table, the complete results can be found in the original paper [
First, we evaluate the performance of the proposed models against the baselines on MSLR-WEB10K and MSLR-WEB30K: { With nDCG@10, CM approaches combining Recall and nMCG, namely recallT300 nmcgT200 and recallT400 nmcgT100, achieve the best performance on each fold. They are signi cantly di erent from both the baseline and the corresponding CM approaches which combine Recall followed by nDCG. This supports our hypothesis that the combination of CM and the user dynamics integrated by nMCG can boost LambdaMart performance. { With nDCG@100, CM approaches using nMCG are less e ective and mseT200 ndcgT300 is the best performing model, signi cantly improving over the baseline both on each fold and on the average across folds. Moreover, CM approaches using nMCG are not signi cantly di erent from those using nDCG. However, they are still signi cantly improving over the baseline. { With Recall@10, the results are somehow in between nDCG@10 and nDCG@100. mseT200 ndcgT300 is the best performing model when the average across each fold is considered. However, if we break down the results on each fold, recallT400 nmcgT100 is the best performing model on three folds out of ve for MSLR-WEB30K. Moreover, recallT400 nmcgT100 is signi cantly better than the baseline and than recallT400 ndcgT100. { With Recall@100, CM approaches using nDCG, i.e. mseT200 ndcgT300, recallT300 ndcgT200 and recallT400 ndcgT100 perform better than those using nMCG. When considering the score across all the folds, mseT200 ndcgT300 is still the best performing model. Thus, when using Recall@100 as evaluation measure, we reach conclusions similar to those inferred with nDCG@100. { With Expected Reciprocal Rank (ERR)@10, recallT300 nmcgT200 is the best performing model and it is the only approach which is signi cantly better than the baseline. Moreover, CM approaches using nMCG are also signi cantly better than those using nDCG, with respect to both each separate fold and the average across folds.
To summarize, CM approaches exploiting the user dynamics perform better at lower rank positions, while CM approaches using nDCG, as mseT200 ndcgT300, are somehow better in retrieving a higher number of relevant documents in the rst 100 rank positions.
Second, we repeated the previous analysis by considering the query type, i.e. we compared the proposed models on navigational and informational queries separately. On a high level the experimental results show that: { With navigational queries, there are just a few models which are signi cantly better than the baselines, independently of the measure or the fold. Furthermore, none of the model performs markedly better than the others, there is instead a lot of variability depending on the measure and the fold under consideration. We argue that with navigational queries the number of relevant documents is limited and systems have little room for manoeuvre: they need to place the most relevant document at the top of the ranked list and, when doing this properly, they all perform equally well in achieving this task. { The experimental comparison of models on informational queries provides more insights on the performance of CM approaches combined with the user dynamics. The exploitation of the user dynamics together with CM boosts the ranking of queries for which several relevant documents are available. Indeed, it helps in identifying those documents that are more relevant than others and in placing them at the beginning of the ranked list.
Finally, we analyse the tree-wise performance of the proposed models: we compare the performance of di erent models with a varying number of trees. All CM approaches leveraging the user dynamics results to be always better than the baselines as the number of trees increases. Moreover, each boosting of the performance corresponds exactly to the switching point T0, showing that replacing the objective function from Recall to nMCG is bene cial for the learning algorithm at any switching point. 4
This paper investigated whether integrating in LtR the knowledge of the userinteraction model and the possibility of targeting di erent objective functions is pro table and allows us to train more e ective ranking functions. The results of the experiments, measured with di erent metrics and cut-o s, gave us a more clear understanding of the problem addressed and con rmed our initial intuitions. We showed, by also breaking down the analysis to di erent classes of queries, that the proposed continuation methods exploiting our user-aware nMCG measure consistently outperform the baselines by statistically signi cant margins.
As future work we will study di erent methods for applying click models to
LtR datasets. A possibility suggested in [