Learning-to-Rank (LtR) techniques leverage machine learning algorithms and large amounts of training data to induce high-quality ranking functions. Given a set of documents and a user query, these functions are able to predict a score for each of the documents that is in turn exploited to induce a relevance ranking. e eectiveness of these learned functions has been proved to be signicantly aected by the data used to learn them. Several analysis and document selection strategies have been proposed in the past to deal with this aspect. In this paper we review the state-of-the-art proposals and we report the results of a preliminary investigation of a new sampling strategy aimed at reducing the number of not relevant query-document pairs, so to signicantly decrease the training time of the learning algorithm and to increase the nal eectiveness of the model by reducing noise and redundancy in the training set.
Ranking is one of the most important problems in information
retrieval. Modern Web search engines exploit and combine hundreds
of features modelling the relevance between the user query and
the candidate documents. A specic area of machine learning, i.e.,
learning to rank, has been developed to deal with the ranking
problem. Given a training set of feature vectors and relevance pairs, a
learning to rank algorithm learns how to combine the query and
the document features so to optimize a specic eectiveness
ranking metric. In the last years important eorts have been spent on
feature engineering/extraction and the development of
sophisticated learning to rank algorithms while lile research has been
conducted on how to choose queries and documents for learning
to rank datasets nor on the eect of these choices on the ability
of learning to rank algorithms to learn eectively and eciently.
Yilmaz and Robertson aack the problem by observing that the
number of judgments in the training set directly aects the quality
of the learned system [
Asham et al. propose several document selection
methodologies, i.e., depth-k pooling, sampling (infAP, statAP), active-learning
(MTC), and on-line heuristics (hedge) [
In a later contribution, Kanoulas et al. propose a large-scale
study on the eect of the distribution of labels across the dierent
grades of relevance in the training set on the performance of trained
ranking functions [
In this paper, we investigate a new technique to sample documents in order to improve both eciency and eectiveness of learning to rank models. Indeed, the improved eciency is a consequence of a reduced size of the sampled dataset, with the ranking algorithm that have to learn from a lower number of query-document pairs. On the other hand, an eective sampling technique may lead to improve the eectiveness of the resulting model by ltering out noise and reducing the redundancy of the query-document pairs.
We present preliminary experimental results proving the benets of the new proposed sampling methodology. 2
We propose a sampling methodology that acts in two steps: i) we train a ranking model on the full dataset and we use it to rank the query-document pairs of the same dataset; ii) we select a given fraction of the top-ranked negative samples, i.e., label = 0, together with all the positive ones, i.e., label> 0. e rationale is that the top-ranked negative samples by the learned model are the most likely to be mis-ranked. Consequently, we reduce the dataset to such positive and negative examples to let the learning algorithm focuses on the most critical and discriminating examples. Moreover, by sampling only negative documents we indirectly reduce the unbalance between positive and negative classes and reduce the redundancy in the negative class.
We evaluate the eectiveness of our proposed technique on the
Istella1 [
We built several sampled datasets by varying the fraction of negatives sampled to f5%; 10%; 20%; 40%g. We trained a λ-Mart model on each of these sampled datasets and we evaluated their performance on the full test set. As shown in Figure 1, the best performing model is the one trained on the dataset where only the top 10% negatives were selected. is model signicantly outperforms the model trained on the full training set by a large margin. Moreover, when the fraction of documents selected is lowered to 5%, we observe a drop in performance, while in the rst iterations (up to 200 trees) results are in line with other models. is behavior suggests that the use of 5% of the negative instances does not fully represent the negative class of query-document pairs. As a (a) Model trained on Full Dataset (b) Model trained on 10% Sample consequence the resulting model is not able to correctly identify them and this harm the ranking accuracy.
e proposed sampling strategy has been showed to provide a signicant boost to the eectiveness of the ranking model. To understand the reasons that lead to this gain, we investigate the similarity distribution between pairs of documents in the negative class. Figure 2 reports such instance analysis, where the similarity between a pair of documents is computed by counting the number of exit leaves in common in scoring the two documents using the given ensemble-based ranking model. e x-axis corresponds to the number of leaves in common (1,000 is the max for two documents exiting in the same leaves for all the trees), while the y-axis corresponds to the number of pairs with the given similarity. e negative examples in the full dataset were analyzed with the models trained on the full dataset and on the 10% sample. According to the model trained on the sampled dataset, the document pairs distribution is signicantly skewed towards dissimilar pairs, i.e., with a few common exit leaves. is not only signies that the initial dataset was redundant in the negative class, but it also implies that the model trained on the sampled dataset is much more eective in discriminating among the negative examples and thus resulting in an improved ranking accuracy.
e preliminary experimental evaluation conrms the validity of the proposed sampling technique. As future work we intend to investigate in depth for a robust and systematic sampling technique that is able to provide benets independently from the classdistribution of the dataset and where the best sampling ratio is automatically chosen accordingly to the dataset properties. We believe that sampling strategies can both improve the quality of the training data generate and the eectiveness of the learning algorithms.