Lecture
The search engine used for running experiments along the tracks was developed within the company as part of the Search project and is currently successfully used on the company's web projects and those of our partners.
When developing the system, one of the main goals was to make it flexible and easily adaptable, by means of a convenient set of settings, to a wide variety of search tasks that differ significantly from each other both in the nature of the indexed collection and in the typical search needs of users. On the other hand, it was necessary to ensure high search quality over a complex collection containing various types of documents, a typical example of which is a web collection covering a fairly large set of sites. In addition, an important requirement was high performance, allowing the system to be used for searching large volumes of data under heavy user load.
The structure of the search index is close to the classical one, described many times in the literature [3, 4]. The foundation consists of inverted lists of word occurrences, used for finding relevant documents, and forward indexes of terms for generating the fragments returned to the user (snippets). A number of techniques are also applied that reduce memory requirements and increase performance, both during indexing and while serving user queries.
To ensure high quality of the returned results, the first requirement is the correct choice of a relevance function that determines the degree of correspondence between a document and a query. Let us look at this in more detail.
When calculating relevance, we take into account both the frequency of occurrence of individual query words in the document and the co-occurrence of words together with their mutual position. Unlike most known systems, we use two different ways of accounting for the mutual position of words in a document: the co-occurrence of word pairs and the presence of relevant passages in the document. Each of these methods has its own advantages: the word-pair method makes it possible to handle well not only queries that form a single phrase, but also queries with varying degrees of connectedness between groups of words within the query. At the same time, the passage closest to the query, better than other methods, makes it possible to assess whether there is a formal correspondence between the query and the document, that is, whether the document contains at least a simple mention of the object specified in the query. Used together, these two methods, in our view, complement each other well and make it possible to achieve good search quality for the widest possible range of queries.
Thus, the weight of a document for a query in our system consists of three components:
W = kfWf + kpW p+ kp5 Wp5 (1)
where:
Wf – the document weight computed on the basis of the TF*IDF algorithm;
W p – the document weight computed on the basis of co-occurrences in the document of word pairs that are adjacent in the query;
Wp5 – the weight of the document's passage closest to the query;
kf kp kp5 – coefficients.
It should also be noted that, in order to obtain a nonzero weight, a document does not have to contain all of the query words. Documents are also included in the ranking for which the ratio of the total IDF of the query words occurring in them to the total IDF of all query words exceeds a given threshold. Such documents are additionally «penalized» for missing words; however, the weight of some of them may in general still exceed the weight of documents containing all the query words.
Let us examine each of the weights in formula (1) in more detail.
The formula we use to calculate the TF*IDF weight for each query term is a modification of the standard BM25 formula, and looks as follows
(2)
where:
fterm– the weight of the term in the document, calculated on the basis of the number of occurrences, taking into account a number of additional factors;
IDFterm– the inverse frequency of the term in the collection, calculated using the standard logarithmic formula;
L– the normalized document length;
k1, b– coefficients.
The overall TF*IDF weight of a document is obtained by summing the weights obtained for all query terms.
A distinctive feature of applying this formula in our search engine is that, for documents whose size exceeds the constant k2 (corresponding, in the standard BM25 formula, to the average document length in the collection, and set in the configuration in our system), instead of length normalization, a method of splitting the document into overlapping fragments is used. Using this method makes it possible to avoid unjustifiably lowering the weight of long documents that contain a small fragment with high relevance.
The fragments have a fixed size, set in the configuration, smaller than k2, and are taken with overlap across the entire text of the document.
The weight of each fragment for each query term is estimated using formula (2) without length normalization, i.e., with L=1.
As a result, the document fragment with the highest weight is selected, and its weight is used as the Wf weight of the document in (1).
As a feature not found in the works on this topic known to us, it can be noted that we additionally include in each fragment a small section of text from the beginning of the document, substantially shorter than the length of the fragment, since the words found at the very beginning of a long document often describe its content as a whole.
For documents with a length shorter than k2, length normalization is used, according to the formula
(3)
where:
Lw – the length of the document in words;
k3 k4– coefficients set in the configuration.
Another significant feature of TF*IDF ranking in our search engine is the use of a fairly large value of the coefficient 
in formula (1): for the runs, a value considerably larger than the usually accepted one was used. Our choice here is related to the fact that a small value of this coefficient is meant to give an advantage to documents with a fairly even occurrence of the various query words in the document, which is relevant in the case where TF*IDF is the sole ranking criterion and the co-occurrence of words is not otherwise taken into account. Since we account for word co-occurrence separately, here we chose a coefficient value that makes it possible to give a sufficiently high weight to documents with a high occurrence of only some (and even, in particular, one) of the query words.
When calculating this weight, an occurrence of a term in the document is taken into account only if it is located in the document at a distance not exceeding a given value from at least one of the query terms adjacent to it (special handling is provided for stop words).
For the run on the web collection, we chose the distance as 2 (adjacent or with one word in between) for the case where the word order in the query and the document matches, and 1 (adjacent only) for the case where it does not match.
Word occurrences satisfying this condition are processed using the TF*IDF algorithm described above; only the set of coefficients differs.
By a passage we mean a fragment of the document, of a size not exceeding a given limit, in which all query terms occur, or a significant portion of the query terms whose total IDF exceeds a given threshold.
When selecting the best passage of a document, the main factors are its completeness (the presence of all query terms), length, word order (whether it matches the word order in the query), the zone of the document (heading, highlighted text, regular text) in which the passage was found, and the proximity of the passage to the beginning of the document. A number of additional factors are also taken into account.
The weight of a passage for each factor is scored in points based on rules specific to each factor, after which the weights are summed. The total weight is the weight of the passage. Of the resulting passage weights, the maximum is chosen for calculating the overall weight using formula (1).
The effectiveness of the algorithms described was verified during the system's participation in the Russian Information Retrieval Evaluation Seminar (ROMIP) in 2005.
The seminar established 3 tracks for comparing the performance of search engine algorithms:
One experimental run was submitted for each of these tracks. The flexibility of the system's settings proved sufficient to unambiguously select, for each track, the parameters desired for building a harmonious system tuned to the given collection, and, as a result, to limit ourselves to a single run. Of course, the global optimum might not have been reached, but the results in each case turned out to be quite satisfactory.
For the web collection search track (web-adhoc), participants were offered a fairly extensive collection of web pages, representing part of the sites on the narod.ru domain (more than 700,000 pages, 6.3GB). Under the conditions of the track, a large number (more than 24,000) of queries, specially selected from search logs, had to be run against this collection. The first 100 documents from the search results were considered the system's answer to the query, ordered by decreasing document significance in the results. For the final evaluation, 75 were selected from the entire set of queries after the results were obtained. A fairly detailed description of the evaluation methods used and the standard parameters is given, for example, in the description of the ROMIP seminar.
Below is a table of results for the track participants using the web-adhoc-or-pd50-all evaluation method (at least one expert rating exceeds the minimum relevance threshold; the systems' answers are considered narrowed to a pool depth of 50 documents; for the 2004 and 2005 queries) and an 11-point TREC graph using the same evaluation method.
Table 1. Comparative results of the web search track participants with the web-adhoc-or-pd50-all evaluation.
Figure 1. 11-point TREC graphs for participants of the web search track with the web-adhoc-or-pd50-all evaluation.
Roughly the same ratio, both for the Average Precision parameter and for the points of the TREC graph, between our results and those of the other participants also holds for the remaining evaluation methods.
Table 2 shows the parameter values achieved by the Poisk system for various types of evaluation. In the first two columns the metrics are calculated for all documents in the search results, while in the last two – only for the first 50 (pd50). Accordingly, in the first and third – strict relevance requirements (all expert ratings exceed the minimum relevance threshold), and in the second and fourth – loose relevance requirements (at least one of the expert ratings exceeds the minimum relevance threshold).
Table 2. Results of the Poisk@Mail.Ru run for evaluations of the web-adhoc-*-*-all type.
For the legal document search track (Legal-adhoc), the company «Kodeks» provided participants with a collection of about 67,000 documents. Just as with the web search track, the task consisted of running a large number (12,900) of queries against this collection. The system's response was likewise considered to be up to 100 of the most relevant documents in the results.
For the mixed search track, it was necessary to run the combined set of queries provided for the Web-adhoc and Legal-adhoc tracks against the combined collection of web and legal documents. The goal was to test the ability of systems to function on a highly heterogeneous collection, since web and legal documents differ significantly in their characteristics.
The same search system was used to carry out the tasks of these two tracks; the only difference was in the parameter settings for the particular task.
For example, in legal documents the title is likely to contain words directly related to the document's subject matter. At the same time, in the web collection, junk in page titles is a fairly common occurrence. Accordingly, the weight for words and passages located in important zones of the document was changed.
Legal documents also more often contain complex syntactic structures, as a result of which words related in meaning end up separated by a larger number of unrelated words. To account for this, the maximum possible passage length and a number of bonuses and penalties charged for the connectedness of query words in the document were changed. Etc.
The results of these tracks are, for the most part, similar to the results of the web-adhoc track. They can be studied in detail in the paper .
Let us try to analyze the relevance of the algorithms described above and the results obtained to the task of Internet search, as solved by large search engines.
Let us give the main differences between the task of Internet search and the task of full-text search in its classical formulation, as used (with some modifications) at the ROMIP workshop:
This list is certainly incomplete; we have listed only the most important differences.
Let us now look at how each of these differences will affect the value of the algorithms we used and the representativeness of the experimental results obtained.
The need to ensure high system performance with a large volume of indexed information often makes it impossible to apply algorithms in Internet search that have proven themselves well in experimental research. In our case, however, high performance requirements were placed on the system from the outset and were met during its development. As in other search engines, this is achieved both through direct optimization of the described algorithms and through optimization that takes ranking into account, that is, one that allows resource-intensive precise ranking operations to be performed only for documents that have a chance of ending up at sufficiently high positions in the results, based on a coarser assessment of their relevance..
The main consequences of the enormous difference in data volume between the Internet (even just the Russian-language segment) and test collections (in particular, the collection used at ROMIP) are:
The first of these features is largely compensated for by applying off-page ranking factors to such queries. The effect of the second shows up primarily in the increased importance of algorithms that account for the mutual arrangement of words. Since it was precisely these that we paid special attention to, we accordingly expected from the outset that a significant increase in data volume would not have a negative effect on the quality of our system's performance. At the same time, one usually cannot speak of this with full confidence prior to experimental verification.
Link-based ranking, citation index, site descriptions in directories, the relevance of the site as a whole to the query, and other off-page criteria are of decisive importance for relevance for a significant share of queries in Internet search. The relevance of the page text also matters for such queries, but a coarse assessment of it is usually sufficient, since subtle differences have practically no effect on the relevance of results for such queries. At the same time, no less significant is the share of queries for which off-page information is practically absent and on-page ranking turns out to be decisive. Thus, one can say that although the relevance of results in Internet search is determined not only by the quality of on-page ranking algorithms, their influence on search quality is quite substantial.
Of course, it must be kept in mind here that the relevance of Internet search results depends not only on ranking quality but also on other factors. The size and update frequency of the database, near-duplicate detection, spam filtering - all of this also has a significant impact on search quality.
Page-level relevance criteria are comparatively easy to fake, since the page is entirely under the control of its author. However, all on-page factors are subject to spam to roughly the same degree, because the author has an equal degree of control over the textual information on which these criteria are built. Consequently, it makes sense not to dwell on the question of the extent of this vulnerability, but to shift the main burden of fighting spam onto specialized anti-spam algorithms that are not directly related to ranking.
A meaningful measure of relevance in real search engines is the degree of user satisfaction with the results obtained. Naturally, this criterion does not lend itself to precise formal definition, unlike the criteria used in information retrieval experiments. The question of how applicable traditional formal criteria are to real Internet search remains little studied. For example, criteria that are significant in experimental research, such as Precision, Recall, and Average Precision, are oriented toward a situation in which the user is interested in all relevant documents and views the entire search results page. In real Internet search, however, such a model of user behavior is only one of many and does not occur all that often. Perhaps in the future relevance-assessment systems will be developed that take into account the probable behavior model of the user for the query being assessed and select an appropriate ranking criterion, although even this would only be a partial solution to the problem.
On the other hand, there is undoubtedly a correlation between formal criteria and search quality from the user's point of view. Moreover, as our own research, among others, has shown, various formal relevance criteria as a rule correlate fairly well with one another, which is also an argument in favor of their applicability to Internet search, despite the diversity of user behavior models.
Thus, on the whole, one can say that the algorithms described are applicable, among other things, to building a full-fledged Internet search system. At the same time, many questions cannot be considered clear until they have been verified experimentally.
Comments