Combining Document Representations for Known-Item Search | Paul Ogilvie and Jamie Callan

@information_retrieval

Mandatory reading for for IR: section 1-3.

This paper investigates the pre-conditions for successful combination of document representations formed from structural markup for the task of known-item search. (1)

known-item-search: in this task, the user has a very specific document in mind but does not know where it is.

Usually, such specific document would have a single document representation. The idea of this paper is to use structural information of that document (e.g. markup) to form various document representations to use for information retrieval.

The idea borrows from meta-search in that it performs a "data fusion" of the results based on multiple document representations (cf. 1).

But the paper actually does not do a meta-search, rather:

An alternative to meta-search techniques is to use the document representations to modify term weights directly within a single search engine. We present a technique for this using generative language modeling. Rather than using the language model estimated from a single document representation, this approach estimates a mixture language model based on a combination of language models created from the various document representations.

Q: What's a mixture language model?

Criteria for individual search engines for effectiveness of meta-search (multiple sources; cf. 1):

  1. compatible output; scoring on the same scale
  2. each be accurate
  3. be independent

Do these requirements (the paper says: hypotheses) also apply in this case?

W.r.t. 1: do ranking using "Okapi and language modeling systems across different document representations" (1)

Paper mentions "Okapi": that refers to Okapi BM25, a language modeling system.

W.r.t. 2: regular relevance criteria are not that applicable, because we are not interested in one particular topic, but in the one document. It is correct or incorrect. Instead, a measure is used to check whether multiple document representations "tend to give higher weight to the correct document than to incorrect documents." (2)

W.r.t. 3: "Applied to known-item finding, an appropriate hypothesis is that the representations would give widely varying scores for the incorrect documents, but tend to score the correct document highly, with lower variance." (2)

Combining representations

Two approaches (2):

  1. "Meta-search" approach: do retrieval using a single representation, for multiple representations, and then combine the results in one ranked list.

  2. "combine the document representations into one mixture language model that estimates the query generation process, and then perform retrieval using the mixture language model." (2)

Advantages of the mixture approach:

  • "With the mixture-based language modeling approach we have guidance on how to combine the probability distributions." (2)
  • "The mixture-based language model also combines evidence at the query term level, rather than after performing retrieval."

Data fusion

This paper will use the language model approach, but will compare with the alternative meta-search algorithms.

"There are two main classes of meta-search algorithms: ones that use scores from systems and ones that do not. (2)

Q: What does that mean?

Algorithms:

  • combMNZ
  • combSUM
  • Condorcet fuse
  • Borda fuse
  • Reciprocal rank fusion strategy

Last three do not use "scores from the systems" (2). What systems?

"These approaches assume that the scores from the different retrieval systems are not directly comparable." (2)

Aha, so the meta-search algorithm does not use ranking scores from the individual systems.

In this application, "we can assume that the search engines use the same ranking function. This may or may not lead to comparable scores, depending on the ranking function" (2) The latter remark is slightly vague still. But I guess what the authors mean is that we are now testing the effect of different document representations. However, they then conceit that the ranking method still matters, so this issue is not entirely resolved at this point.

This section contains a summary of these algorithms. Note that I've encountered Condorcet and Borda in the context of elections , see RI-Multi_Agent_Systems.md .

Combining Language models

Basic working of a language model:

A unigram language model defines a multinomial probability distribution over all words in the vocabulary of the corpus. These probabilities are interpreted as word generation probabilities, and documents are ranked by their probability of generating the query (3)

Given a language model, how likely is it that this document will give rise to the query?

$$P(Q|\theta_D)=\prod_{i=1}^{|Q|}P(q_i|\theta_D)$$

A language model is usually a linear interpolation between a language model specific to one document, and a general language model of the whole corpus:

$$P(w|\theta_D)=\lambda_1 P_{MLE}(w|D)+\lambda_2 P_{MLE}(w|C)$$

With C being the whole corpus.

The maximum likelihood estimate is in this case equal to the empirical distribution:

$$P_{MLE}(w|D)= \frac{ count(w;D)}{|D|}$$

The lambda's are usually set using Dirichlet prior smoothing with parameter mu usually being the average document length of the collection.

But how do we combine language models then? Approach:

Create language models for the different document representations, and then linearly interpolate them. The weights used for this interpolation should sum up to one, so that we end up with a probability distribution.

Another detail is that corpus C now refers to all documents with the same document representation.

Note:

The main difference between the language modeling approach presented here and the meta-search techniques is that it combines the document representations on the query term level, rather than as a post-retrieval score combination. (3)

Q: What's the main difference between a mixed language modelling approach to fielded retrieval, rather than a "meta-search" approach?

Experimental methods

Six different document representations were tested in our experiments: (i) the full document text, (ii) in-link text, (iii) title text, (iv) image alternate text, (v) large font text (including headings), and (vi) meta tag keywords and descriptions.