Lecture
Learning to rank (or machine-learned ranking, MLR) — is a class of supervised machine learning problems concerned with automatically fitting a ranking model to a training set consisting of a number of lists and given partial orders on the elements within each list. The partial order is usually specified by assigning a score to each element (for example, «relevant» or «not relevant»; more than two grades may also be used). The goal of the ranking model is to best (in some sense) approximate and generalize the ranking method from the training set to new data.
Learning to rank is still a fairly young, rapidly developing field of research that emerged in the 2000s with the growth of interest, within information retrieval, in applying machine learning methods to ranking problems.
As applied to search engines, each list represents a set of documents satisfying some search query.
The training set consists of a sample of search queries, a subset of documents matching them, and relevance scores for each document with respect to the query. These can be prepared either manually, by specially trained people (search-quality evaluators, or assessors), or automatically, based on an analysis of user clicks or on tools of search engines such as Google's SearchWiki system.
During the training of a ranking model, and while it operates, each document-query pair is converted into a numeric vector of ranking features (also called ranking factors or signals) that characterize the properties of the document, the query, and their relationship. Such features can be divided into three groups:
Below are some examples of ranking features used in LETOR, a dataset widely known in this field of research:
There are several metrics used to evaluate and compare the quality of ranking algorithms on a set with assessor scores. The parameters of a ranking model are often tuned to maximize the value of one of these metrics.
Examples of metrics:
In his article «Learning to Rank for Information Retrieval» and in talks at topical conferences, Tie-Yan Liu of Microsoft Research Asia analyzed the methods existing at the time for solving the learning-to-rank problem and proposed classifying them into three approaches, depending on the input data representation and loss function used:
In the pointwise approach (pointwise approach), it is assumed that each query-document pair is assigned a numerical score. The learning-to-rank task reduces to building a regression: for each individual query-document pair, its score must be predicted.
Within this approach, many machine learning algorithms for regression problems can be applied. When the scores can take only a few values, algorithms for ordinal regression and classification can also be used.
In the pairwise approach (pairwise approach), learning to rank reduces to building a binary classifier that takes as input two documents corresponding to the same query and must determine which of them is better.
Examples of algorithms: RankNet, FRank, RankBoost, RankSVM, IR-SVM.
The listwise approach (listwise approach) consists of building a model that takes as input all the documents corresponding to a query at once, and outputs their permutation. The model's parameters are fitted to directly maximize one of the ranking metrics listed above. But this is often difficult, since ranking metrics are usually not continuous and not differentiable with respect to the ranking model's parameters, so one resorts to maximizing certain approximations or lower bounds of them.
Examples of algorithms: SoftRank, SVMmap, AdaRank, RankGP, ListNet, ListMLE.
A possible architecture of a search engine using machine learning.
The search engines of many modern web search systems, including Yandex, Yahoo and Bing, use ranking models built with machine learning methods. Bing's search uses the RankNet algorithm. The newest machine-learning ranking algorithm, developed and used in the Yandex search engine, was named MatrixNet; Yandex itself sponsored the «Internet Mathematics 2009» contest for building a ranking algorithm on its own dataset.
In an interview in early 2008, Peter Norvig, director of research at Google, said that their search engine was not yet ready to fully entrust ranking to machine learning algorithms, citing two reasons: first, that automatically created models could behave unpredictably on new classes of queries unlike those in the training set, compared with models created by human experts. Second, the creators of Google's current ranking algorithm are confident that their model can solve problems more effectively than machine learning can. The first reason is of much greater interest to us, since it not only goes back to a well-known problem of inductive logic, formulated by the philosopher C. G. Hempel, which runs counter to intuition (the statement "all ravens are black" is logically equivalent to "all non-black objects are not ravens"), but also forces us to return to a number of unresolved questions raised by F. Rosenblatt, who created the world's first neural network capable of perception and of forming a response to a perceived stimulus – the single-layer perceptron.[ Drawing on the critique of Rosenblatt's elementary perceptron, we can understand the full vulnerability of this rating model that Google's specialists tell us about: are artificial systems able to generalize their individual experience to a broad class of situations for which the response was not communicated to them in advance? No, the individual experience of artificial systems is in practice always limited and is never complete. Either way, machine learning tools make it possible to solve the problem of spamdexing with a fairly high degree of effectiveness.
Ranking is a central part of many information retrieval tasks, such as document retrieval , collaborative filtering , sentiment analysis , and online advertising .
A possible architecture of a machine-learning search engine is shown in the accompanying figure.
Training data consist of queries and their corresponding documents, together with a relevance degree for each match. It can be prepared manually by human testers (or assessors , as Google calls them), who review the results for some queries and determine the relevance of each result. It is impossible to check the relevance of all documents, so a method called pooling is normally used - only a few top documents retrieved by some existing ranking models are checked. Alternatively, training data can be obtained automatically by analyzing click-through logs (i.e., search results that received clicks from users), query chains , or such search-engine features as Google's SearchWiki .
The training data is used by the learning algorithm to build a ranking model that computes the relevance of documents for real queries.
Users typically expect a search query to complete in a short time (e.g., a few hundred milliseconds for web search), which makes it infeasible to evaluate a complex ranking model for every document in the corpus, so a two-stage scheme is used. First, a small number of potentially relevant documents is identified using simpler retrieval models that allow queries to be scored quickly, such as the vector space model , the Boolean model , weighted AND, or BM25 . This phase is called top-{\ displaystyle k}
document retrieval and many heuristic methods have been proposed in the literature to speed it up, for example using static document-quality scoring and multi-level indexes. In the second stage, a more accurate but computationally expensive machine learning model is used to re-rank these documents.
Learning-to-rank algorithms have been applied not only in information retrieval:
Commercial search engines began using machine-learned ranking systems in the 2000s (decade). One of the first search engines to start using it was AltaVista (its technology was later acquired by Overture , and then by Yahoo ), which in April 2003 launched a ranking function using gradient boosting . [32] [33]
Bing search is believed to be based on the RankNet algorithm [ 34] [ when? ], which was invented at Microsoft Research in 2005.
In November 2009, the Russian search engine Yandex announced [35], that it had significantly improved search quality by introducing its new proprietary MatrixNet algorithm, a variant of gradient boosting that uses oblivious decision trees. [36] Recently they also sponsored a machine-learned ranking competition, «Internet Mathematics 2009» [37], based on production data from their own search engine. Yahoo announced a similar competition in 2010. [38]
In 2008, Google's Peter Norvig denied that their search engine relies exclusively on machine-learned ranking. [39] The CEO of Cuil , Tom Costello, suggests that they prefer manually built models because they can outperform machine-learned models when compared using metrics such as CTR or time on landing page, because machine-learned models " learn what people say they like, rather than what they actually like ". [40]
In January 2017 this technology was incorporated into the open-source search engine Apache Solr™ [41], making machine-learned search ranking widely available for enterprise search as well.
Below is a partial list of published learning-to-rank algorithms, indicating the year of the first publication of each method:
| Year | Name | Type | Notes |
|---|---|---|---|
| 1989 | OPRF [16] | pointwise | Polynomial regression (instead of machine learning this work belongs to pattern recognition, but the idea is the same) |
| 1992 | SLR [17] | pointwise | Stepwise logistic regression |
| 1994 | NMOpt [18] | listwise | Nonmetric optimization |
| 1999 | MART (Multiple Additive Regression Trees) | pairwise | |
| 2000 | Ranking SVM (RankSVM) | pairwise | A later exposition is given in , which describes an application to ranking using click-through logs. |
| 2002 | PRanking [19] | pointwise | Ordinal regression. |
| 2003 | RankBoost | pairwise | |
| 2005 | RankNet | pairwise | |
| 2006 | IR-SVM | pairwise | Ranking SVM with query-level normalization in the loss function. |
| 2006 | LambdaRank | pairwise / listwise | RankNet in which the pairwise loss function is multiplied by the change in the IR metric caused by a swap. |
| 2007 | AdaRank | listwise | |
| 2007 | FRank | pairwise | Based on RankNet, uses a different loss function - fidelity loss. |
| 2007 | GBRank | pairwise | |
| 2007 | ListNet | listwise | |
| 2007 | McRank | pointwise | |
| 2007 | QBRank | pairwise | |
| 2007 | RankCosine | listwise | |
| 2007 | RankGP [20] | listwise | |
| 2007 | RankRLS | pairwise |
Ranking based on regularized least squares. In [21] this work is extended to learning to rank on preference graphs. |
| 2007 | Map SVM | listwise | |
| 2008 | LambdaSMART / LambdaMART | pairwise / listwise | An ensemble of LambdaMART models was used in the winning entry of the recent Yahoo Learning to Rank Challenge. Based on MART (1999) [22] «LambdaSMART» stands for Lambda-submodel-MART, or LambdaMART for the case without a submodel (https://www.microsoft.com/en-us/research/wp-content/uploads /2016/02/tr-2008-109.pdf ). |
| 2008 | ListMLE | listwise | Based on ListNet. |
| 2008 | PermuRank | listwise | |
| 2008 | SoftRank | listwise | |
| 2008 | Rank refinement [23] | pairwise | A semi-supervised approach to learning to rank using Boosting. |
| 2008 | SSRankBoost [24] | pairwise | Extension of RankBoost for training with partially labeled data (semi-supervised learning to rank) |
| 2008 | SortNet [25] | pairwise | SortNet, an adaptive ranking algorithm that orders objects using a neural network as a comparator. |
| 2009 | MPBoost | pairwise | A magnitude-preserving variant of RankBoost. The idea is that the more unequal the labels of a pair of documents are, the harder the algorithm should try to rank them. |
| 2009 | BoltzRank | listwise | Unlike earlier methods, BoltzRank builds a ranking model that, at query time, looks not only at individual documents but also at pairs of documents. |
| 2009 | BayesRank | listwise | The method combines the Plackett-Luce model and a neural network to minimize the expected Bayes risk associated with NDCG from a decision-theoretic perspective. |
| 2010 | NDCG Boost [26] | listwise | A boosting approach to optimizing NDCG. |
| 2010 | GBlend | pairwise | Extends GBRank to a multi-task learning setting, jointly solving several learning-to-rank tasks that share some features. |
| 2010 | IntervalRank | pairwise and listwise | |
| 2010 | CRR | pointwise and pairwise | Combined Regression and Ranking. Uses stochastic gradient descent to optimize a linear combination of pointwise squared loss and pairwise hinge loss from ranking SVM. |
| 2015 | FaceNet | pairwise | Ranks face images by a triplet metric using a deep convolutional network. |
| 2016 | XGBoost | pairwise | Supports various ranking objectives and evaluation metrics. |
| 2017 | ES-Rank | listwise | An evolutionary-strategy technique for learning to rank with 7 fitness evaluation metrics |
| 2018 | PolyRank [27] | pairwise | Simultaneously learns a ranking and an underlying generative model from pairwise comparisons. |
| 2018 | FATE-Net / FETA-Net [28] | listwise | End-to-end trainable architectures that explicitly take all items into account to model context effects. |
| 2019 | FastAP [29] | listwise | Optimizes average precision for learning deep embeddings |
| 2019 | Mulberry | listwise and hybrid | Learns ranking policies by maximizing several metrics across the entire dataset |
| 2019 | DirectRanker | pairwise | Generalization of the RankNet architecture |
Note: since most supervised learning algorithms can be applied to pointwise cases, only methods specifically designed with ranking in mind are shown above.
Similar to recognition applications in computer vision , recent neural-network-based ranking algorithms have also been found vulnerable to covert adversarial attacks on both candidates and queries. [42] With small perturbations imperceptible to a human, the ranking order can be arbitrarily altered. Furthermore, it has been found that transferable, model-independent adversarial examples are possible, enabling black-box adversarial attacks on deep ranking systems without the need to access their underlying implementations. [42] [43]
Conversely, the robustness of such ranking systems can be improved with adversarial defenses, such as Madry's defense
Comments