Learning to rank

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.

[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: For the convenience of MLR algorithms, query-document pairs are usually represented by numerical vectors, which are called feature vectors.

Examples of ranking quality measures: DCG and its normalized variant NDCG are usually preferred in academic research when multiple levels of relevance are used.

In this case, it is assumed that each query-document pair in the training data has a numerical or ordinal 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.

The classifier shall take two documents as its input and the goal is to minimize a loss function

The loss function typically reflects the number and magnitude of inversions in the induced ranking.

is a cumulative distribution function, for example, the standard logistic CDF, i.e.

These algorithms try to directly optimize the value of one of the above evaluation measures, averaged over all queries in the training data.

[16] LambdaMART is a pairwise algorithm which has been empirically shown to approximate listwise objective functions.

[17] 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.

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.

Norbert Fuhr introduced the general idea of MLR in 1992, describing learning approaches in information retrieval as a generalization of parameter estimation;[49] a specific variant of this approach (using polynomial regression) had been published by him three years earlier.

[18] Bill Cooper proposed logistic regression for the same purpose in 1992 [19] and used it with his Berkeley research group to train a successful ranking function for TREC.

Manning et al.[50] 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 NeurIPS, SIGIR and ICML have had workshops devoted to the learning-to-rank problem since the mid-2000s (decade).

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.

In November 2009 a Russian search engine Yandex announced[54] 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.

[55] Recently they have also sponsored a machine-learned ranking competition "Internet Mathematics 2009"[56] based on their own search engine's production data.

[57] As of 2008, Google's Peter Norvig denied that their search engine exclusively relies on machine-learned ranking.

[59] In January 2017, the technology was included in the open source search engine Apache Solr.

[61][62] These implementations make learning to rank widely accessible for enterprise search.

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.

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.