Ranking Training

In relation to search engines , each list is a set of documents that satisfy a certain search query.

A training sample consists of a selection of search queries, a subset of the documents that correspond to them, and assessments of the relevance of each document to the query. They can be prepared either manually, by specially trained people (search quality evaluators or assessors ), or automatically, based on an analysis of user clicks ^[2] or search engine tools such as Google’s SearchWiki .

Ranking features

During the training of the ranking model and during its operation, each document-query pair is translated into a numerical vector of ranking features (also called ranking factors or signals) that characterize the properties of the document, query and their relationship. Such signs can be divided into three groups:

• Query-independent or static characteristics - depending only on the document, but not on the request. For example, PageRank or document length. Such features are usually calculated at the stage of indexing documents and are often used to build an indicator of the static quality of a document, which is used to increase the efficiency of search engines. ^{[3] [4]}
• Signs that depend only on the request. For example, "query about porn or not."
• Query-dependent or dynamic characteristics - depending on both the document and the request. For example, a measure of TF-IDF matching a document to a query.

The following are some examples of ranking features used in the LETOR dataset widely known in the art: ^[5]

• Values ​​of measures TF, TF-IDF , BM25 , and the language model of matching the request of different areas of the document (title, URL, body text, link text);
• Lengths and IDFs - sums of document zones;
• Document ranks obtained by various variations of such link ranking algorithms as PageRank and HITS .

There are several metrics by which the quality of the performance of ranking algorithms in a sample is evaluated and compared with assessors. Often the parameters of the ranking model tend to be adjusted in such a way as to maximize the value of one of these metrics.

Examples of metrics:

• DCG and NDCG ;
• Accuracy @ n , NDCG @ n (@ n means that the metric value is considered only according to n best issuing documents);
• MAP
• average inverse rank ;
• pfound is a development by Yandex . ^[6]

In his article “Learning to Rank for Information Retrieval” ^[1] and speeches at thematic conferences, Tai-Yang Lew from Microsoft Research Asia analyzed the methods existing at that time for solving the task of ranking training and proposed their classification into three approaches, depending on the input data representation used and the penalty function:

Pointwise

In the pointwise approach ( English pointwise approach ) it is assumed that each pair of request-document is assigned a numerical rating. The task of ranking training comes down to building a regression : for each individual query-document pair, it is necessary to predict its assessment.

As part of this approach, many machine learning algorithms can be applied to regression problems. When estimates can take only a few values, algorithms for ordinal regression and classification can also be used.

Pairwise Approach

In a pairwise approach ( English pairwise approach ) ranking training is reduced to building a binary classifier, which receives two documents that correspond to the same query, and it is necessary to determine which one is better.

Examples of algorithms: ^[1] RankNet, FRank, RankBoost, RankSVM, IR-SVM.

List approach

The list approach ( English listwise approach ) is to build a model, at the input of which all the documents matching the request are received at once, and the output is their rearrangement. Model parameters are adjusted to directly maximize one of the ranking metrics listed above. But this is often difficult, since the ranking metrics are usually not continuous and non-differentiable with respect to the parameters of the ranking model, therefore they resort to maximizing some of their approximations or lower bounds.

Examples of algorithms: ^[1] SoftRank, SVM ^map , AdaRank, RankGP, ListNet, ListMLE.

Large Search Engines

Search engines of many modern search engines on the Internet, including Yandex , Yahoo ^[7] and Bing , use ranking models built using machine learning methods. Bing's search uses the RankNet algorithm. ^[8] The latest machine learning ranking algorithm developed and applied in the Yandex search engine is called MatrixNet; ^[9] Yandex itself sponsored the Internet Mathematics 2009 contest ^[10] to build a ranking algorithm on a set of its own data.

In an interview in early 2008, Peter Norvig , director of research at Google , said that their search engine is not yet ready to completely entrust ranking to machine learning algorithms, motivating it by the fact that, firstly, automatically created models can behave unpredictably on new query classes that are not similar to queries from the training set, compared to models created by expert people. Secondly, the creators of the current Google ranking algorithm are confident that their model is able to solve problems more efficiently than machine learning. ^[11] The first reason is of much greater interest to us, since it not only goes back to such a well-known problem of inductive logic formulated by the German mathematician K. G. Hempel and contradicting intuition (the statement "all crows are black" is logically equivalent to the fact that "all non-black objects are not crows"), but it also forces us to return to a number of unresolved issues by F. Rosenblatt, who created the world's first neural network capable of to perception and the formation of a response to the perceived stimulus - a single-layer perceptron. ^[12] Based on criticism of the elementary Rosenblatt perceptron , we can understand the vulnerability of this rating model, which Google experts tell us about: are artificial systems able to generalize their individual experience to a wide class of situations for which the response was not communicated to them in advance? No, the individual experience of artificial systems in practice is always limited and never complete. One way or another, machine learning tools can solve the problem of spamming with a fairly high degree of efficiency. ^[13]