23.1.4 Evaluating Information Retrieval Systems

The basic tools used to measure the performance of ranked retrieval system are the precision and recall measures we employed in earlier settings. Here we assume that the returned items can be divided into two categories: those relevant to our purposes and those that are not. Therefore, precision is the fraction of the returned documents that are relevant, while recall is the fraction of all possible relevant documents that are contained in the return set. More formally, let's assume that we have been given a total of T ranked documents in response to a given information request, a subset of these documents, R, consists of relevant documents, and a disjoint subset, N, consists of the remaining irrelevant documents, and finally let's assume that there are U documents in the collection as a whole that are relevant to this particular request. Given all this we can define our precision and recall measures to be:

$$ Precision=\frac{|R|}{|T|} $$

$$ Recall=\frac{|R|}{|U|} $$

Unfortunately, these metrics are not quite sufficient to measure the performance of a system that ranks the documents it return. That is, if we are comparing the performance of two ranked retrieval systems, we require a metric that will prefer the one that ranks the relevant documents higher. Simple precision and recall as defined above are not dependent on rank in any way; we need to adapt them to capture how well a system does at putting relevant documents higher in the ranking. The two standard methods in information retrieval for accomplishing this are based on plotting precision/recall curves and on averaging precision measures in various ways.

Let's consider each of these methods in turn using the data given in the table in Fig. 23.4. This table provides rank-specific precision and recall values calculated as we proceed down through a set of ranked items. That is, the precision numbers are the fraction of relevant documents seen at a given rank, and recall is the fraction of relevant documents found at the same rank. The recall measures in this example are based on this query having 9 relevant documents in the collection as a whole. Note that recall is non-decreasing as we proceed, when relevant items are encountered recall increases and when non-relevant documents are found it remains unchanged. Precision on the other hand hops up and down, increasing when relevant documents are found and decreasing otherwise.

One common way to get a handle on this kind of data is to plot precision against recall on a single graph using data gathered from across a set of queries. To do this we'll need a way to average the recall and precision values across a set of queries. The standard way to do this is to plot averaged precision values at 11 fixed levels of recall (0 to 100, in steps of 10). Of course, as is illustrated by our earlier table we're not likely to have datapoints at these exact levels for all (or any) of the queries in our evaluation

| Rank | Judgment | Precision $ _{Rank} $ | Recall $ _{Rank} $ |

| --- | --- | --- | --- |

| 1 | R | 1.0 | .11 |

| 2 | N | .50 | .11 |

| 3 | R | .66 | .22 |

| 4 | N | .50 | .22 |

| 5 | R | .60 | .33 |

| 6 | R | .66 | .44 |

| 7 | N | .57 | .44 |

| 8 | R | .63 | .55 |

| 9 | N | .55 | .55 |

| 10 | N | .50 | .55 |

| 11 | R | .55 | .66 |

| 12 | N | .50 | .66 |

| 13 | N | .46 | .66 |

| 14 | N | .43 | .66 |

| 15 | R | .47 | .77 |

| 16 | N | .44 | .77 |

| 17 | N | .44 | .77 |

| 18 | R | .44 | .88 |

| 19 | N | .42 | .88 |

| 20 | N | .40 | .88 |

| 21 | N | .38 | .88 |

| 22 | N | .36 | .88 |

| 23 | N | .35 | .88 |

| 24 | N | .33 | .88 |

| 25 | R | .36 | 1.0 |

set. We'll therefore use interpolated precision values for the 11 recall values from the data points we do have. This is accomplished by choosing the maximum precision value achieved at any level of recall at or above the one we're calculating. In other words,

$$ IntPrecision(r)=\max_{i>=r}Precision(i) $$

Note that this interpolation scheme not only provides us with the means to average performance over a set of queries, but it also provides a sensible way to smooth over the irregular precision values in the original data. This particular smoothing method is designed to give systems the benefit of the doubt by assigning the maximum precision value achieved at higher levels of recall from the one being measured. The interpolated data points for our earlier example are given in the following table and plotted in Fig. 23.5.

Given curves such as this we can compare two systems or approaches by comparing their curves. Clearly curves that are higher in precision across all recall values are

preferred. However, these curves can also provide insight into the overall behavior of a system. Systems that are higher in precision towards the left may favor precision over recall, while systems that are more geared towards recall will be higher at higher levels of recall (to the right).

A second popular way way to evaluate ranked retrieval systems is known as mean average precision(MAP). In this approach, we again descend through the ranked list

of items and note the precision only at those points where a relevant item has been encountered. For a single query, we average these individual precision measurements over the return set up to some fixed cutoff. More formally, if we assume that $ R_{r} $ is the set of relevant documents at or above r, then the average precision for a single query is:

$$ \frac{1}{\left|R_{r}\right|}\sum_{d\in R_{r}}Precision_{r}(d) $$

where $ Precision_{r}(d) $ is the precision measured at the rank where document d was found. For an ensemble of queries, we then average over these averages, giving us our mean average precision measure. Applying this technique to the data in Fig. 23.5 yields a MAP measure of 0.6 for this single retrieval.

MAP has the advantage of providing a single crisp metric that can be used to compare competing systems or approaches. Note, that MAP will tend to favor systems that provide relevant documents at high ranks. Of course, this isn't really a problem since that is a big part of what we're looking for in a retrieval system. But since the measure essentially ignores recall, it can favor those systems that are tuned to return small sets of documents in which they are highly confident, at the expense of systems that attempt to be more comprehensive by trying to attain higher levels of recall.

The U.S. government-sponsored TREC (Text REtrioval Conference) evaluations, run annually since 1992, provide a rigorous testbed for the evaluation of a variety of information retrieval tasks and techniques. TREC provides large document sets for both training and testing, along with a uniform scoring system. Training materials consist of sets of documents accompanied by sets of queries (called topics in TREC) and relevance judgments. TREC subtasks over the years have included question answering, IR in Chinese and Spanish, interactive IR, retrieval from speech and video, and others. See Voorhees and Harman (2005). Details of all of the meetings can be found at the TREC page on the National Institute of Standards and Technology website.