23.1.6 Improving User Queries

One of the most effective ways to improve retrieval performance is to find a way to improve user queries. The techniques presented in this section have been shown to varying degrees to be effective at this task.

The single most effective way to improve retrieval performance in the vector space model is the use of relevance feedback (Rocchio, 1971). In this method, a user presents a query to the system and is presented with a small set of retrieved documents. The user is then asked to specify which of these documents appears relevant to their need. The user's original query is then reformulated based on the distribution of terms in the relevant and non-relevant documents that the user examined. This reformulated query is then passed to the system as a new query with the new results being shown to the user. Typically an enormous improvement is seen after a single iteration of this technique.

The formal basis for the implementation of this technique falls out directly from some of the basic geometric intuitions of the vector model. In particular, we would like to push the vector representing the user's original query toward the documents that have been found to be relevant, and away from the documents judged not relevant. This can be accomplished by adding an averaged vector representing the relevant documents to the original query, and subtracting an averaged vector representing the non-relevant documents.

More formally, let's assume that $ \vec{q}_i $ represents the user's original query, $ R $ is the number of relevant documents returned from the original query, $ S $ is the number of non-relevant documents, and documents in the relevant and non-relevant sets are denoted as $ \vec{r} $ and $ \vec{s} $, respectively. In addition, assume that $ \beta $ and $ \gamma $ range from 0 to 1 and that $ \beta + \gamma = 1 $. Given these assumptions, the following represents a standard relevance feedback update formula:

$$ \vec{q}_{i+1}=\vec{q}_{i}+\frac{\mathrm{p}}{R}\sum_{j=1}^{R}\vec{r}_{j}-\frac{\gamma}{S}\sum_{k=1}^{S}\vec{s}_{k} $$

The factors $ \beta $ and $ \gamma $ in this formula represent parameters that can be adjusted experimentally. Intuitively, $ \beta $ represents how far the new vector should be pushed towards

the relevant documents, and $ \gamma $ represents how far it should be pushed away from the non-relevant ones. Salton and Buckley (1990) report good results with $ \beta = .75 $ and $ \gamma = .25 $.

We should note that evaluating systems that use relevance feedback is rather tricky. In particular, an enormous improvement is often seen in the documents retrieved by the first reformulated query. This should not be too surprising since it includes the documents that the user told the system were relevant on the first round. The preferred way to avoid this inflation is to only compute recall and precision measures for what is called the residual collection, the original collection without any of the documents shown to the user on any previous round. This usually has the effect of driving the system's raw performance below that achieved with the first query, since the most highly relevant documents have now been eliminated. Nevertheless, this is an effective technique to use when comparing distinct relevance feedback mechanisms.

An alternative approach to query improvement focuses on terms that comprise the query vector. In query expansion, the user's original query is expanded by adding terms that are synonymous with or related to the original terms. Query expansion is thus a technique for improving recall, perhaps at the expense of precision. For example the query Steve Jobs could be expanded by adding terms like Apple, Macintosh, and personal computer.

The terms to be added to the query are taken from a thesaurus. It is possible to use a hand-built resource like WordNet or UMLS as the thesaurus for query expansion, when the domain is appropriate. But often these thesauruses are not suitable for the collection, and instead, we do thesaurus generation, generating a thesaurus automatically from documents in the collection. We can do this by clustering the words in the collection, a method known as term clustering. Recall from our characterization of the term-by-document matrix that the columns in the matrix represent the documents and the rows represent the terms. Thus, in the thesaurus generation, the rows can be clustered to form sets of synonyms, which can then be added to the user's original query to improve its recall. The distance metric for clustering can be simple cosine, or any of the other distributional methods for word relatedness discussed in Ch. 20.

The thesaurus can be generated once from the document collection as a whole (Crouch and Yang, 1992), or sets of synonym-like terms can be generated dynamically from the returned set for the original query (Attar and Fraenkel, 1977). Note that this second approach entails far more effort, since in effect a small thesaurus is generated for the documents returned for every query, rather than once for the entire collection.

23.2 FACTOID QUESTION ANSWERING

There are many situations where the user wants a particular piece of information rather than an entire document or document set. We use the term question answering for the task of returning a particular piece of information to the user in response to a question. We call the task factoid question answering if the information is a simple fact, and particularly if this fact has to do with a named entity like a person, organization, or location.

The task of a factoid question answering system is thus to answer questions by finding, either from the Web or some other collection of documents, short text segments that are likely to contain answers to questions, reformatting them, and presenting them to the user. Fig. 23.7 shows some sample factoid questions together with their answers.

Since factoid question answering is based on information retrieval techniques to find these segments, it is subject to the same difficulties as information retrieval. That is, the fundamental problem in factoid question answering is the gap between the way that questions are posed and the way that answers are expressed in a text. Consider the following question/answer pair from the TREC question answering task:

User Question: What company sells the most greeting cards?

Potential Document Answer: Hallmark remains the largest maker of greeting cards.

Here the user uses the verbal phrase sells the most while the document segment uses a nominal the largest maker. The solution to the possible mismatches between question and answer form lies in the ability to robustly process both questions and candidate answer texts in such a way that a measure of similarity between the question and putative answers can be performed. As we'll see, this process involves many of the techniques that we have introduced in earlier chapters including limited forms of morphological analysis, part-of-speech tagging, syntactic parsing, semantic role labelling, named-entity recognition, and information retrieval.

Because it is impractical to employ these relatively expensive NLP techniques like parsing or role labeling on vast amounts of textual data, question answering systems generally use information retrieval methods to first retrieve a smallish number of potential documents. The most expensive techniques then used in a second pass on these smaller numbers of candidate relevant texts.

Fig. 23.8 shows the three phases of a modern factoid question answering system: question processing, passage retrieval and ranking, and answer processing.