Search Quality Metrics: What They Mean And How They Work

Let's start with the main point in the question - ranking. Ranking is a way of sorting items (sites, videos, images, news posts, etc.) based on their relevance.

By relevance, we mean the degree to which an object is related to a specific query. Suppose we have a request and several objects that correspond to it in one way or another. The higher the degree of compliance of the object with the request, the higher its relevance. The task of ranking is to return the most relevant object in response to a request. The higher the relevance, the higher the likelihood that the user will take the targeted action (go to the page, buy a product, watch a video, etc.).

With the development of information retrieval systems, the topic of ranking becomes more and more relevant. This problem arises everywhere: when distributing search results pages, recommending videos, news, music, goods, and more. Learning to Rank exists for this purpose.

Learning to Rank or machine-learned ranking (MLR) is a branch of machine learning that studies and develops self-learning ranking algorithms. Its main task is to determine the most effective algorithms and approaches based on their qualitative and quantitative assessment. Why did the problem of teaching ranking arise?

For example, let's take a page of an information resource - an article. The user enters a query into a search engine that already contains a set of files. In accordance with the request, the system extracts the corresponding files from the collection, ranks them, and gives them the highest relevance.

Ranking is performed based on the sorting model f (q, d), where q is the user's request, d is the file. The classical f (q, d) model works without self-learning and doesn't consider the connection between words (for example, Okapi BM25, Vector space model, BIR models). It calculates the file's relevance to the request based on the occurrence of the request words in each document. Obviously, with the current volume of files on the Internet, search results based on simple models may not be accurate enough.

Therefore, the trends have changed. Machine learning has replaced the simple classical model to improve the quality of search. The use of machine learning methods made it possible to build a ranking model automatically. It considers many relevancy factors that previously could not be considered — for example, anchor texts, page authority, natural language analysis, keyword analysis of competitors, and page user experience.

Learning to Rank is currently one of the critical tasks of modern web search. Over time, the most common metrics for assessing the search quality have already been formed in this area.

Learning to Rank is a complete learning task that includes training and testing.

Training data includes request, files, the degree of relevance.

Each request is associated with several files. It is not possible to check the relevance of all files, so the merge method is usually used - only a few top documents retrieved by existing ranking models are checked. Also, training data can be obtained automatically from Google SearchWiki or by analyzing the transition log, query chains.

The degree of compliance is determined by the file request in several ways. The most common approach assumes that the relevance of a document is based on several metrics. The higher the correspondence of one indicator, the higher the score for it. Relevance scores are derived from a set of search engine labeling that takes 5 values from 0 (irrelevant) to 5 (completely relevant). The estimates for all indicators are summed up.

As a result, the most relevant is the file, the sum of the ratings for all indicators being the highest. The learning data is used to create ranking algorithms that calculate the relevance of documents to real queries.

However, there is an important nuance here: user requests must be processed at high speed. And it is impossible to use complex scoring schemes in this variant (for each request). Therefore, the check is carried out in two stages:

During the training and operation of MLR, the file-request pair is translated into a numerical vector from ranking factors and other signals. They characterize the relationship between the request and the file, as well as their properties.

Signs are divided into three groups:

This approach allows you to provide the user with the most accurate results on the SERP. Ranking features are collected in LETOR, a collection of benchmarks for research in learning to rank in information retrieval.

Both binary (relevant/irrelevant) and multilevel (for example, relevance 0 to 5) scales are used to evaluate each file returned in response to a request. In practice, queries can be incorrect and have different shades of relevance. For example, in the query "dog" there is an ambiguity: the machine doesn't know if the user is looking for the planet Dog, an album by Blink-182, or the rapper Snoop Dogg.

In information retrieval theory, there are many metrics for assessing the performance of an algorithm with training data and comparing different ranking training algorithms. Open source states that they are created in relevance scoring sessions where judges evaluate search results' quality. However, common sense tells us that such an option is hardly possible, and here's why:

Nevertheless, in information retrieval theory, there are well-established indicators of assessment described by authoritative sources. Here are some of them.

It is a statistical measure of evaluating any process that generates a list of possible responses to a sample of queries ordered by the probability of being correct. The mean reciprocal rank is defined as the average of the inverse ranks for all Q queries:

Where ranki is the position of the first relevant document for query i.

This is the simplest metric of the three: it tries to measure where is the first relevant item. It is closely linked to the binary relevance family of metrics.

This method is simple to compute and is easy to interpret; it focuses on the first relevant element of the list. It is best suited for targeted searches, such as users asking for the "best item for me." Suitable for known-item search such as navigational queries or looking for a fact.

The MRR metric doesn't evaluate the rest of the list of recommended items. It focuses on a single item from the list.

It gives a list with a single relevant item just a much weight as a list with many relevant items. It is okay if that is the target of the evaluation.

This might not be a fair evaluation metric for users that want a list of related items to browse. The goal of the users might be to compare multiple associated items.

MAP, or mean average precision, computes an entire query set's average relevance and ranks all the top ones highly. So, rather than assuming there is only one winner, MAP asks whether this is relevant and lists all the queries with a "yes" response.

MAP is ideal for ranking results when you are looking at five or more results. That makes it ideal for evaluating related recommendations, like on an eСommerce platform.

If we want to understand the NDCG metric, we must first understand the CG (Cumulative Gain) and DCG (Discounted Cumulative Gain), and also understand the two assumptions we make when using DCG and related metrics:

If each recommendation has a relevance score associated with it, the CG is the sum of the relevance scores of all results in the list:

The cumulative gain at a specific position in the p ranking, where rel_i is an assessment of the relevance of the result at position i. Each relevance score is associated with a document.

The problem with CG is that it doesn't consider the position of the result set when determining its usefulness. In other words, if we change the order of the relevance scores, we won't be able to understand better the usefulness of the result set as the CG will remain the same.

For example:

Obviously, Metric Set B returns a much more useful result than Metric Set A, but the CG measure says they return equally good results.

To overcome this, we are introducing DCG. DCG punishes highly relevant documents that appear lower in the search results by decreasing the ranked relevance value, which is logarithmically proportional to the position of the result:

But with DCG, a problem arises when we want to compare search engines' performance from one query to another because the list of search results can vary in length depending on the query provided. Therefore, by normalizing the cumulative gain in each position for the selected value by queries, we arrive at NDCG.

We accomplish this by sorting all the relevant documents in the corpus according to their relative relevance, getting the largest possible DCG through the p-position (also known as c).

Where, the ideal discounted cumulative gain is:

The topic of metrics for assessing search quality is relevant and important today. But, unfortunately, we can talk about it only from the point of view of theorizing. Metrics for evaluating the quality of search, in our case, are mostly fantasies. Here's why: we can't have all the data we have on Google.

This means that choosing a methodology that would make it possible to determine the instrument is more of fortune-telling since we cannot check anything here.

Yes, you can try to rely on patents or words published by this or that official. But 90% of all patents are rubbish that has nothing to do with programming. And phrases are only part of the puzzle, which is aggravated by the fact that all these people are tied by such a severe NDA that even the phrases that were supposedly accidentally thrown out are written in the contract.

And all we can do is analyze and combine data from various sources, resulting in a document that tells about the theoretical foundations of how search quality can be assessed.

Good luck and high positions to everyone!