Learning to rank

A possible architecture of a machine-learned search engine.

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 the relevance degree of each match. It may be prepared manually by human assessors (or raters, as Google calls them), 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. This technique may introduce selection bias. Alternatively, training data may be derived automatically by analyzing clickthrough logs (i.e. search results which got clicks from users),[3] query chains,[4] or such search engines' features as Google's (since-replaced) SearchWiki. Clickthrough logs can be biased by the tendency of users to click on the top search results on the assumption that they are already well-ranked.

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 (such as a few hundred milliseconds for web search), which makes it impossible to evaluate a complex ranking model on each document in the corpus, and so a two-phase scheme is used.[5] 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,[6] or BM25. This phase is called top-${\displaystyle k}$ 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.[7] In the second phase, a more accurate but computationally expensive machine-learned model is used to re-rank these documents.

Learning to rank algorithms have been applied in areas other than information retrieval:

• In machine translation for ranking a set of hypothesized translations;[8]
• In computational biology for ranking candidate 3-D structures in protein structure prediction problems.[8]
• In recommender systems for identifying a ranked list of related news articles to recommend to a user after he or she has read a current news article.[9]

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. Formally speaking, the pointwise approach aims at learning a function ${\displaystyle f(x)}$ predicting the real-value or ordinal score of a document ${\displaystyle x}$ using the loss function ${\displaystyle L(f,x_{j},y_{j})}$.

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.

In this case, the learning-to-rank problem is approximated by a classification problem — learning a binary classifier ${\displaystyle h(x_{u},x_{v})}$ that can tell which document is better in a given pair of documents. The classifier shall take two documents as its input and the goal is to minimize a loss function ${\displaystyle L(h;x_{u},x_{v},y_{u,v})}$. The loss function may reflect the average number of inversions in ranking.

In many cases, the binary classifier ${\displaystyle h(x_{u},x_{v})}$ is implemented with a scoring function ${\displaystyle f(x)}$. As an example, RankNet [15] adapts a probability model and defines ${\displaystyle h(x_{u},x_{v})}$ as the estimated probability of the document ${\displaystyle x_{u}}$ has higher quality than ${\displaystyle x_{v}}$:

${\displaystyle P_{u,v}(f)={\text{CDF}}(f(x_{u})-f(x_{v})),}$

where ${\displaystyle {\text{CDF}}(\cdot )}$ is a cumulative distribution function, for example, the standard logistic CDF, i.e.

${\displaystyle {\text{CDF}}(x)={\frac {1}{1+\exp \left[-x\right]}}.}$

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.

A partial list of published learning-to-rank algorithms is shown below with years of first publication of each method:

Year	Name	Type	Notes
1989	OPRF [16]	2 pointwise	Polynomial regression (instead of machine learning, this work refers to pattern recognition, but the idea is the same)
1992	SLR [17]	2 pointwise	Staged logistic regression
1994	NMOpt [18]	2 listwise	Non-Metric Optimization
1999	MART (Multiple Additive Regression Trees)	2 pairwise
2000	Ranking SVM (RankSVM)	2 pairwise	A more recent exposition is in,[3] which describes an application to ranking using clickthrough logs.
2002	Pranking[19]	1 pointwise	Ordinal regression.
2003	RankBoost	2 pairwise
2005	RankNet	2 pairwise
2006	IR-SVM	2 pairwise	Ranking SVM with query-level normalization in the loss function.
2006	LambdaRank	pairwise/listwise	RankNet in which pairwise loss function is multiplied by the change in the IR metric caused by a swap.
2007	AdaRank	3 listwise
2007	FRank	2 pairwise	Based on RankNet, uses a different loss function - fidelity loss.
2007	GBRank	2 pairwise
2007	ListNet	3 listwise
2007	McRank	1 pointwise
2007	QBRank	2 pairwise
2007	RankCosine	3 listwise
2007	RankGP[20]	3 listwise
2007	RankRLS	2 pairwise	Regularized least-squares based ranking. The work is extended in [21] to learning to rank from general preference graphs.
2007	SVMmap	3 listwise
2008	LambdaSMART/LambdaMART	pairwise/listwise	Winning entry in the Yahoo Learning to Rank competition in 2010, using an ensemble of LambdaMART models. Based on MART (1999)[22] “LambdaSMART”, for Lambda-submodel-MART, or LambdaMART for the case with no submodel.
2008	ListMLE	3 listwise	Based on ListNet.
2008	PermuRank	3 listwise
2008	SoftRank	3 listwise
2008	Ranking Refinement[23]	2 pairwise	A semi-supervised approach to learning to rank that uses Boosting.
2008	SSRankBoost[24]	2 pairwise	An extension of RankBoost to learn with partially labeled data (semi-supervised learning to rank)
2008	SortNet[25]	2 pairwise	SortNet, an adaptive ranking algorithm which orders objects using a neural network as a comparator.
2009	MPBoost	2 pairwise	Magnitude-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.
2009	BoltzRank	3 listwise	Unlike earlier methods, BoltzRank produces a ranking model that looks during query time not just at a single document, but also at pairs of documents.
2009	BayesRank	3 listwise	A method combines Plackett-Luce Model and neural network to minimize the expected Bayes risk, related to NDCG, from the decision-making aspect.
2010	NDCG Boost[26]	3 listwise	A boosting approach to optimize NDCG.
2010	GBlend	2 pairwise	Extends GBRank to the learning-to-blend problem of jointly solving multiple learning-to-rank problems with some shared features.
2010	IntervalRank	2 pairwise & listwise
2010	CRR	2 pointwise & pairwise	Combined 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.
2014	LCR	2 pairwise	Applied local low-rank assumption on collaborative ranking. Received best student paper award at WWW'14.
2015	FaceNet	pairwise	Ranks face images with the triplet metric via deep convolutional network.
2016	XGBoost	pairwise	Supports various ranking objectives and evaluation metrics.
2017	ES-Rank	listwise	Evolutionary Strategy Learning to Rank technique with 7 fitness evaluation metrics
2018	DLCM [27]	2 listwise	A multi-variate ranking function that encodes multiple items from an initial ranked list (local context) with a recurrent neural network and create result ranking accordingly.
2018	PolyRank[28]	pairwise	Learns simultaneously the ranking and the underlying generative model from pairwise comparisons.
2018	FATE-Net/FETA-Net [29]	listwise	End-to-end trainable architectures, which explicitly take all items into account to model context effects.
2019	FastAP [30]	listwise	Optimizes Average Precision to learn deep embeddings
2019	Mulberry	listwise & hybrid	Learns ranking policies maximizing multiple metrics across the entire dataset
2019	DirectRanker	pairwise	Generalisation of the RankNet architecture
2019	GSF [31]	2 listwise	A permutation-invariant multi-variate ranking function that encodes and ranks items with groupwise scoring functions built with deep neural networks.
2020	RaMBO[32]	listwise	Optimizes rank-based metrics using blackbox backpropagation[33]
2020	PRM [34]	pairwise	Transformer network encoding both the dependencies among items and the interactions between the user and items
2020	SetRank [35]	2 listwise	A permutation-invariant multi-variate ranking function that encodes and ranks items with self-attention networks.
2021	PiRank [36]	listwise	Differentiable surrogates for ranking able to exactly recover the desired metrics and scales favourably to large list sizes, significantly improving internet-scale benchmarks.
2022	SAS-Rank	listwise	Combining Simulated Annealing with Evolutionary Strategy for implicit and explicit learning to rank from relevance labels
2022	VNS-Rank	listwise	Variable Neighborhood Search in 2 Novel Methodologies in AI for Learning to Rank
2022	VNA-Rank	listwise	Combining Simulated Annealing with Variable Neighbourhood Search for Learning to Rank
2023	GVN-Rank	listwise	Combining Gradient Ascent with Variable Neighbourhood Search for Learning to Rank

Note: as most supervised learning to Rank algorithms can be applied to pointwise, pairwise and listwise case, only those methods which are specifically designed with ranking in mind are shown above.

Commercial web search engines began using machine learned ranking systems since the 2000s (decade). One of the first search engines to start using it was AltaVista (later its technology was acquired by Overture, and then Yahoo), which launched a gradient boosting-trained ranking function in April 2003.[39][40]

Bing's search is said to be powered by RankNet algorithm,[41] which was invented at Microsoft Research in 2005.

In November 2009 a Russian search engine Yandex announced[42] 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.[43] Recently they have also sponsored a machine-learned ranking competition "Internet Mathematics 2009"[44] based on their own search engine's production data. Yahoo has announced a similar competition in 2010.[45]

As of 2008, Google's Peter Norvig denied that their search engine exclusively relies on machine-learned ranking.[46] 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".[47]

In January 2017, the technology was included in the open source search engine Apache Solr.[48] It is also available in the open source OpenSearch and the source-available Elasticsearch.[49][50] These implementations make learning to rank widely accessible for enterprise search.