Lecture
So far we have treated a document as a sequence of terms. In
fact, most documents have additional structure. Electronic documents are usually accompanied by metadata, which is encoded in a form
that computers can recognize. By metadata we mean specific kinds of data about a document, such as the author's name, the title, and the publication date. This metadata usually contains metadata fields, such as the creation date and the document format3
, as well as the author's name and, possibly, the document title. The set of possible values of these fields should be considered finite — for example, the set of all document
creation dates is bounded.
Consider the query “Find documents authored by William Shakespeare in 1601
that contain the words alas poor Yorick”. In this case, processing the query reduces, as
usual, to finding the intersection of postings lists, except that we
can merge term positions from both standard inverted indexes and parametric indexes4
. For each field (for example, for the creation date) there is one parametric index; it allows selecting only those documents that match the date specified in the query. Figure 6.1 shows the user
interface for parametric search. Some fields imply ordered values (for example, dates); in the query above, one such value
is the year “1601”. A search engine may support queries that specify ranges of such ordered values; data structures such as B-trees can be used to store the set of values of a field.
Zones resemble fields, but the content of a zone can be arbitrary
text. Whereas a field may have a relatively small set of values,
a zone can contain an arbitrary and unbounded amount of text. For example, document titles and abstracts are usually treated as zones. In order to support
3 In Russian and foreign practice, “metadata field” or “field”
is very often replaced by “attribute” or “document attribute”. — Editor's note. 4 Also “attribute index”, “document attribute index”, and “attribute search”. — Editor's note.
the processing of queries of the form “Find documents with the word merchant in the title and William in the author list, as well as the phrase gentle rain in the text”, a standard inverted index can be built for each zone of the document. Such an index looks
roughly like the one shown in Figure 6.2. Whereas the dictionary for a parametric
index is built from a fixed list of values (a set of languages, a set of dates), the dictionary for a zone index is built from the texts located
in that zone
Figure 6.1. Parametric search. In this example we have a collection with fields that allow selecting publications by zones, such as Author or Language
Figure 6.2. A basic zone index; zones are encoded as extensions of the dictionary entries
In fact, the dictionary size can be reduced by encoding the zone in which a term occurs in the term position instead. For example, Figure 6.3 shows how the occurrence of the word william in the title and in the author zone of various documents is encoded. Such encoding is useful when the size of the dictionary matters (since we require the dictionary to be stored in main memory). However, there is another reason why the encoding shown in Figure 6.3 turns out to be useful: efficient weighted zone scoring
Figure 6.3. A zone index in which the zone is encoded in the term position rather than in the dictionary
So far in Section 6.1 we have focused on finding documents based on Boolean queries against fields and zones. Let us now move on to the second application of zones
and fields.
Denote the Boolean query by the letter q, and the document by the letter d. The weighted zone scoring method assigns the pair (q, d) a relevance value from the interval [0,1], computing a linear combination of zone scores, to which each zone
of the document contributes a Boolean value. More specifically, consider a set of documents, each of which has l zones. Let 
, so that
. Let si, where 1 ≤ i ≤ l, be a Boolean value indicating whether there is a match (or no match)
between the query q and the i-th zone. For example, if all the query terms belong to a particular
zone, then its Boolean value should equal one, and if not — zero. Indeed, this mapping can be performed by any Boolean function that maps the presence of query terms in a zone to the set {0, 1}. Thus, weighted zone
relevance can be defined as
Weighted zone scoring is sometimes called ranked Boolean retrieval.
Example 6.1. Consider the query shakespeare against a collection in which each document has three zones: author, title, and body.
The Boolean score function for a zone takes the value one if the query term shakespeare belongs to that zone,
and zero if not. Weighted zone scoring in such a collection involves using three weights, g1, g2, and g3, corresponding to the zones author,
title, and body. Suppose that g1 = 0.2, g2 = 0.3, and g3 = 0.5 (so that the sum of all three weights equals one); this corresponds to an application in which
a match in the author zone is less important compared to all the other zones,
a match in the title zone is more important, and a match
in the body zone is most important of all.
Thus, if the term shakespeare appears in the title and body zones but is absent from the author zone, then the relevance of the document will equal 0.8.
How is weighted zone relevance computed? To do this, one can simply compute the relevance for each document in turn, summing the contributions of the different zones.
However, weighted zone relevance can be computed directly from the inverted indexes. The algorithm shown in Figure 6.4 is intended for the case in which the query q contains two terms, q1 and q2, and the Boolean function AND: 1 — if both query terms are present in the zone, and 0 — if not. After the algorithm we describe its extension to more complex queries and Boolean functions
Readers may have noticed a strong similarity between the algorithms shown in Figures 6.4 and 1.6. Indeed, they implement the same pass over the term positions, except that instead of simply adding the document to the result set for the Boolean AND query, in this case we compute the relevance of each document. In some works the array of current relevance values scores[] is called the set of accumulators. This is because, for Boolean functions more complex than AND, the relevance of a document can be nonzero even if it does not contain all the query terms
Figure 6.4. Algorithm for weighted zone scoring over two inverted lists. The function WeightedZone (not shown here) is computed in the inner loop of formula (6.1)
How are the weights gi determined in weighted zone scoring? They can be specified by experts (or by the user). However, much more often the weights are determined based on training examples assessed in advance. This method belongs to the general class of ranking methods in information retrieval known as “machine-learned relevance”. In this section we give a brief introduction to this topic, since weighted zone scoring is good material for such an exposition. A more complete description requires an understanding of the principles of machine learning,
1. We have at our disposal a set of training examples, each of which is a tuple consisting of a query q, a document d, and a relevance judgment for d and q. In the simplest case, each relevance judgment is binary, i.e. relevant or not relevant. More sophisticated implementations of this methodology use finer-grained judgments.
2. The weights gi are determined by “training” on these examples so that the resulting
scores approximate the relevance judgments of the training examples.
In weighted zone scoring, this process can be viewed as fitting the coefficients of a linear function of the Boolean features of occurrence in the corresponding zones. The costly part of this methodology is the labor-intensive collection of relevance
judgments on which the training is based, especially if the collection changes frequently (as the web does). Let us describe a simple example showing how the problem of determining the weights gi via training can be reduced to a simple optimization problem.
Consider a simple variant of weighted zone scoring in which each
document has title and body zones. Apply to a given query q and document d a Boolean
matching function and compute the Boolean values sT(d, q) and sB(d, q), indicating whether the title (respectively, the body) of document d matches query q. For example, the algorithm shown in Figure 6.4 uses the AND function applied to the
query terms for this purpose. Let us compute a value between zero and one for each
(document, query) pair, using the values sT(d, q) and sB(d, q) and a constant g∈[0,1]:
(6.2)
Now let us describe how to determine the constant g from training examples, each of which is a triple of the form Φj = (dj, qj, r(di, qj)). Each training example, containing document di and query qi, is given a relevance judgment r(di, qj) by a human editor, taking the value relevant or not relevant. This process is illustrated in Figure 6.5, which shows seven examples.
Figure 6.5. An example of training examples. For each training example Φj we have the Boolean values sT(dj, qj) and sB(dj, qj), used for scoring according to formula (6.2).
(6.3)
Now let us compare this computed relevance with the relevance judgment for the same pair (dj, qj) made by a human; for this, each relevant judgment is coded as one, and not relevant as zero. Suppose the error of the weighting function with weight g is defined by the following formula
. 
Here the editor's judgment r(dj,qj) is coded as one or zero. Thus, the total error corresponding to the set of training examples equals
Now the problem of determining the constant g from the training examples reduces to finding the value of g that minimizes the total error (6.4). Determining the best value of g from formula (6.4) as formulated in Section 6.1.3 reduces to the problem of minimizing a quadratic function of g on the interval [0,1]. This topic is discussed in Section 3.
Note that for any training example Φj such that sT(dj, qj) = 0 and sB(dj, qj) = 1, the relevance computed by formula (6.2) equals 1–g. Similarly, one can write down the relevance computed by formula (6.2) for the three other possible combinations of values of sT(dj, qj) and sB(dj, qj); these combinations are shown in Figure 6.6.
Figure 6.6. The four possible combinations of sT and sB
Denote by n01r (respectively, n01n) the number of training examples for which sT(dj, qj) = 0 and sB(dj, qj) = 1, and for which the expert judgment is relevant (respectively, not relevant). Then the contribution to the total error in expression (6.4) from the training examples for which sT(dj, qj) = 0 and sB(dj, qj) = 1 equals
Writing down in a similar manner the contributions to the error from the training examples for the three other combinations of values of sT(dj, qj) and sB(dj, qj) (and extending the notation in the obvious way), we arrive at the conclusion that the total error, as defined by formula (6.4), equals
. (6.5)
Differentiating expression (6.5) with respect to g and setting the result equal to zero, we obtain that the optimal value of g equals
. (6.6)
Exercise 6.1. Is it necessary that, when using the weighted
zone scoring method, all zones use the same Boolean matching function?
Exercise 6.2. In Example 6.1, take the following weights: g1 = 0.2, g2 = 0.31, and g3 = 0.49. List all the distinct values that a document can have.
Exercise 6.3. Rewrite the algorithm shown in Figure 6.4 for the case where the query contains more than two terms.
Exercise 6.4. Write pseudocode for the function WeightedZone for the case of two inverted lists, as in Figure 6.4.
Exercise 6.5. Apply formula (6.6) to the set of training examples shown in Figure 6.5, and estimate the best value of g.
Exercise 6.6. For the value of g found in Exercise 6.5, compute the relevance of the document using the weighted zone scoring method for
each (query, document) example. How does this relevance compare to the expert judgments shown in Figure 6.5 (judgments coded as 0 and 1)?
Exercise 6.7. Why does the expression for the quantity g in formula (6.6) not take into account training examples for which the values of sT(dj, qj) and sB(dj, qj) are the same?
Comments