Learning to rank


Learning to rank or machine-learned ranking is the application of machine learning, typically supervised, semi-supervised or reinforcement learning, in the construction of ranking models for information retrieval systems. Training data consists of lists of items with some partial order specified between items in each list. This order is typically induced by giving a numerical or ordinal score or a binary judgment for each item. The ranking model purposes to rank, i.e. producing a permutation of items in new, unseen lists in a similar way to rankings in the training data.

Applications

In information retrieval

Ranking is a central part of many information retrieval problems, such as document retrieval, collaborative filtering, sentiment analysis, and online advertising.
A possible architecture of a machine-learned search engine is shown in the accompanying figure.
Training data consists of queries and documents matching them together with relevance degree of each match. It may be prepared manually by human assessors,
who check results for some queries and determine relevance of each result. It is not feasible to check the relevance of all documents, and so typically a technique called pooling is used — only the top few documents, retrieved by some existing ranking models are checked. Alternatively, training data may be derived automatically by analyzing clickthrough logs, query chains, or such search engines' features as Google's SearchWiki.
Training data is used by a learning algorithm to produce a ranking model which computes the relevance of documents for actual queries.
Typically, users expect a search query to complete in a short time, which makes it impossible to evaluate a complex ranking model on each document in the corpus, and so a two-phase scheme is used. First, a small number of potentially relevant documents are identified using simpler retrieval models which permit fast query evaluation, such as the vector space model, boolean model, weighted AND, or BM25. This phase is called top- document retrieval and many heuristics were proposed in the literature to accelerate it, such as using a document's static quality score and tiered indexes. In the second phase, a more accurate but computationally expensive machine-learned model is used to re-rank these documents.

In other areas

Learning to rank algorithms have been applied in areas other than information retrieval:
For the convenience of MLR algorithms, query-document pairs are usually represented by numerical vectors, which are called feature vectors. Such an approach is sometimes called bag of features and is analogous to the bag of words model and vector space model used in information retrieval for representation of documents.
Components of such vectors are called features, factors or ranking signals. They may be divided into three groups :
Some examples of features, which were used in the well-known dataset:
Selecting and designing good features is an important area in machine learning, which is called feature engineering.

Evaluation measures

There are several measures which are commonly used to judge how well an algorithm is doing on training data and to compare the performance of different MLR algorithms. Often a learning-to-rank problem is reformulated as an optimization problem with respect to one of these metrics.
Examples of ranking quality measures:
DCG and its normalized variant NDCG are usually preferred in academic research when multiple levels of relevance are used. Other metrics such as MAP, MRR and precision, are defined only for binary judgments.
Recently, there have been proposed several new evaluation metrics which claim to model user's satisfaction with search results better than the DCG metric:
Both of these metrics are based on the assumption that the user is more likely to stop looking at search results after examining a more relevant document, than after a less relevant document.

Approaches

Tie-Yan Liu of Microsoft Research Asia has analyzed existing algorithms for learning to rank problems in his paper "Learning to Rank for Information Retrieval". He categorized them into three groups by their input representation and loss function: the pointwise, pairwise, and listwise approach. In practice, listwise approaches often outperform pairwise approaches and pointwise approaches. This statement was further supported by a large scale experiment on the performance of different learning-to-rank methods on a large collection of benchmark data sets.

Pointwise approach

In this case, it is assumed that each query-document pair in the training data has a numerical or ordinal score. Then the learning-to-rank problem can be approximated by a regression problem — given a single query-document pair, predict its score.
A number of existing supervised machine learning algorithms can be readily used for this purpose. Ordinal regression and classification algorithms can also be used in pointwise approach when they are used to predict the score of a single query-document pair, and it takes a small, finite number of values.

Pairwise approach

In this case, the learning-to-rank problem is approximated by a classification problem — learning a binary classifier that can tell which document is better in a given pair of documents. The goal is to minimize the average number of inversions in ranking.

Listwise approach

These algorithms try to directly optimize the value of one of the above evaluation measures, averaged over all queries in the training data. This is difficult because most evaluation measures are not continuous functions with respect to ranking model's parameters, and so continuous approximations or bounds on evaluation measures have to be used.

List of methods

A partial list of published learning-to-rank algorithms is shown below with years of first publication of each method:
Regularized least-squares based ranking. The work is extended in
to learning to rank from general preference graphs.20073 listwise2008pairwise/listwiseWinning entry in the recent Yahoo Learning to Rank competition used an ensemble of LambdaMART models. Based on MART “LambdaSMART”, for Lambda-submodel-MART, or LambdaMART for the case with no submodel 3 listwiseBased on ListNet.20083 listwise20083 listwise20082 pairwiseA semi-supervised approach to learning to rank that uses Boosting.20082 pairwiseAn extension of RankBoost to learn with partially labeled data 20082 pairwiseSortNet, an adaptive ranking algorithm which orders objects using a neural network as a comparator.20092 pairwiseMagnitude-preserving variant of RankBoost. The idea is that the more unequal are labels of a pair of documents, the harder should the algorithm try to rank them.20093 listwiseUnlike earlier methods, BoltzRank produces a ranking model that looks during query time not just at a single document, but also at pairs of documents.20093 listwiseA method combines Plackett-Luce Model and neural network to minimize the expected Bayes risk, related to NDCG, from the decision-making aspect.20103 listwiseA boosting approach to optimize NDCG.20102 pairwiseExtends GBRank to the learning-to-blend problem of jointly solving multiple learning-to-rank problems with some shared features.20102 pairwise & listwise20102 pointwise & pairwiseCombined Regression and Ranking. Uses stochastic gradient descent to optimize a linear combination of a pointwise quadratic loss and a pairwise hinge loss from Ranking SVM.2015pairwiseRanks face images with the triplet metric via deep convolutional network.2016pairwiseSupports various ranking objectives and evaluation metrics.2017listwiseEvolutionary Strategy Learning to Rank technique with 7 fitness evaluation metrics2018pairwiseLearns simultaneously the ranking and the underlying generative model from pairwise comparisons.2018listwiseEnd-to-end trainable architectures, which explicitly take all items into account to model context effects.2019listwiseOptimizes Average Precision to learn deep embeddings2019listwise & hybridLearns ranking policies maximizing multiple metrics across the entire dataset
Note: as most supervised learning algorithms can be applied to pointwise case, only those methods which are specifically designed with ranking in mind are shown above.

History

introduced the general idea of MLR in 1992, describing learning approaches in information retrieval as a generalization of parameter estimation; a specific variant of this approach had been published by him three years earlier. Bill Cooper proposed logistic regression for the same purpose in 1992 and used it with his Berkeley research group to train a successful ranking function for TREC. Manning et al. suggest that these early works achieved limited results in their time due to little available training data and poor machine learning techniques.
Several conferences, such as NIPS, SIGIR and ICML had workshops devoted to the learning-to-rank problem since mid-2000s.

Practical usage by search engines

Commercial web search engines began using machine learned ranking systems since the 2000s. One of the first search engines to start using it was AltaVista, which launched a gradient boosting-trained ranking function in April 2003.
Bing's search is said to be powered by algorithm, which was invented at Microsoft Research in 2005.
In November 2009 a Russian search engine Yandex announced that it had significantly increased its search quality due to deployment of a new proprietary MatrixNet algorithm, a variant of gradient boosting method which uses oblivious decision trees. Recently they have also sponsored a machine-learned ranking competition "Internet Mathematics 2009" based on their own search engine's production data. Yahoo has announced a similar competition in 2010.
As of 2008, Google's Peter Norvig denied that their search engine exclusively relies on machine-learned ranking. Cuil's CEO, Tom Costello, suggests that they prefer hand-built models because they can outperform machine-learned models when measured against metrics like click-through rate or time on landing page, which is because machine-learned models "learn what people say they like, not what people actually like".
In January 2017 the technology was included in the open source search engine Apache Solr™, thus making machine learned search rank widely accessible also for enterprise search.

Vulnerabilities

Similar to recognition applications in computer vision, recent neural network based ranking algorithms are also found to be susceptible to covert adversarial attacks, both on the candidates and the queries. With small perturbations imperceptible to human beings, ranking order could be arbitrarily altered. In addition, model-agnostic transferable adversarial examples are found to be possible, which enables black-box adversarial attacks on deep ranking systems without requiring access to their underlying implementations.
Conversely, the robustness of such ranking systems can be improved via adversarial defenses such as the Madry defense.