Search Engine Evaluation | Zhai, Chapter 9 of "Text Data Management and Analysis A Practical Introduction to Information Retrieval and Text Mining"
Measures:
- Effectiveness/accuracy
- Efficiency
- Usability
Efficiency and usability are requirements for any software system. This chapter focuses on effectiveness because search engines require their own evaluation methodology in this case.
Cranfield Evaluation Methodology
This Cranfield paradigm is not limited to search engines but can be applied to any empirical test. The core idea is:
- Build a reusable test collection similar to a real document collection
- Define measures using this collection
Because we reuse the same collection, we can meaningfully compare several algorithms and systems. We also use the same relevance judgements (see below). For evaluation we additionally need:
- Queries that simulate a user's information need
- Relevance judgement for those queries by the users who formulated those queries (because the queries express their information need)
- We construct an ideal ranking based on the relevance judgements.
When evaluating a system, it is likely most appropriate to use different measures that suit users with different information needs. E.g. whether precision or recall is an appropriate measure highly depends on the information need of the user (for example get a few accurate results, or many results to make sure no potentially relevant results are missed).
Set retrieval
Do not take ranking into account.
- Precision
- Recall
- F-measure balances precision and recall
The ideal scenario is precision=1, recall=1. However, in practice a high recall is correlated with a low precision. The more documents we include just so that we do not overlook potentially relevant documents, the more irrelevant documents we will include.
p7: Why do we not use the arithmetic mean between precision and recall? Arithmetic mean is heavily dominated by large values. This means the mean would be high with a very large recall value, independent of the precision value; and it's trivial to have a perfect recall, namely by returning all documents.
$$F_1 = \frac{ 2PR }{ P+R }$$
Ranked list
Text retrieval problem is a ranking problem rather than a classification problem.
If a user inspects ranked results in a linear fashion, the user will stop inspecting results at some point. We do not however know where this cutoff point lies exactly.
- Compute precision each time the recall increases in the ranking
- Pessimistic assumption we assume precision of 0 for recall values that are not a strict increase within the top-k returned documents.
- This assumption is used to easily compute MAP; every irrelevant document (where the recall does not improve) will receive precision 0 and is thus disregarded. This way you can just sum all precisions without worrying about "skipping" irrelevant documents.
Key takeaway:
This is the most important point to keep in mind: when you compare different algorithms, the key is to avoid any bias toward a particular method. As long as you can avoid that, it’s perfectly fine to do a transformation of these measures that preserves the order. (9)
We can compute a precision-recall curve for various cutoffs, given an output ranking. This helps us see for which recall we can score a certain precision value. Because we made the pessimistic assumption, we'll likely have a precision of 0 on the right side of the plot.
from Zhai p.176.
p.175-176 discusses a scenario in which the curves for two systems cross each other. In this case, there is no single best system to choose. We have to think about the information need of the user again, given the task the user is performing.
Well, the difference is just that—in the low level of recall, system B is better, but in the high recall region, system A is better. That means it depends on whether the user cares about high recall, or low recall with high precision. (10)
Average Precision
If we want to compare many systems, doing that manually based on a curve is tedious. Instead, we'd like to have a single number to use for the comparison.
Idea 1: Compute the area under the precision-recall curve, i.e. the average precision
Important: this measure is defined on the set of relevant documents only. This is also why we only compute and consider the precision when the recall increases, i.e. when another relevant document is retrieved.
This also means that the denominator of the average is the set of all relevant documents and not the set of retrieved relevant documents.
Q: Why do we not divide by the set of retrieved relevant documents?
A: Then the measure would favor systems that return fewer relevant documents. (see p.11)
This measure is sensitive to the position of a particular item. If we shift relevant documents up, the average precision increases! Let's say p(7)=3/7 and we move the relevant document at rank 7 one up. Then we have p(6)=3/6. And obviously 3/6 > 3/7.
So we use this instead of regular precision, because precision alone is not sensitive to ranking.
Also, because only the precision of relevant documents is used, recall is still taken into account.
Mean average precision (MAP)
Because the average precision is only computed for one query, we can compute the arithmetic mean of average precisions over a set of queries. This is the mean average precision (MAP).
Again, we may want to avoid large values biasing the results. If we have a large average precision, what does this mean? A large AP may mean that the query was simply quite easy. Conversely, a low AP may mean the query is very difficult. So if we want a system to perform decent on all kinds of queries (easy to hard)
Instead, the geometric mean weighs very low average precision values heavily. So this would mean this measure heavily prioritizes difficult queries.
$$gMAP(\L)=( \prod_{i=1}^m) avp(L_i))^(\frac{1}{m})$$
Or:
$$gMAP(\L)=\exp (\frac{1}{m} \sum_{i=1}^m)ln avp(L_i))$$
Mean Reciprocal rank
If we know there is only one relevant document, average precision is essentially 1/r where r is the rank of the final relevant document in the final ranking.
Then MAP becomes the Mean Reciprocal Rank (MRR).
r can be directly interpreted as the effort a user has to make to find the single relevant document (when traversing from top to bottom).
But... why do we then not use r? Again, the problem is that the mean is dominated by large values. But now large values are the worse results.
The difference appears when there are many topics. Just like MAP, this sum will be dominated by large values of r. So what are those values? Those are basically large values that indicate lower ranked results. That means the relevant items rank very low down on the list. The average would then be dominated by the relevant documents that are ranked in the lower portion of the list. From a user’s perspective we care more about the highly ranked documents, so by taking this transformation by using reciprocal rank we emphasize more on the difference on the top. Think about the difference between rank one and rank two and the difference between rank 100 and 1000 using each method. Is one more preferable than the other? (14)
Multi-level judgements
All measures based on average precision assume binary relevance judgements. But this doesn't work with multi-level relevance judgements e.g. from 1 (non-relevant) to 3 (highly relevant).
The gain for a user when reading a highly relevant document is 3, whereas the gain of reading an irrelevant document is 1.
Assuming users only look at top-10 results, the cumulative gain is
$$CG(L)=\sum_{i=1}{n}r_i$$
But because three relevant documents in the top-3 are more valuable than the same relevant documents at the bottom of the top-10, we discount the gain by the rank of the document.
The first document is not discounted, meaning: there is no additional cost to inspecting this result because the user always at least looks at the first result. So we get the following discounted cumutative gain:
$$DCG(L)=r_1 + \sum_{i=2}{n} \frac{r_i}{log_2 i}$$
Now the score is sensitive to ranking. If highly relevant documents appear higher in the ranking, they will offer more gain than when they would appear lower in the ranking because they will be discounted less.
There is only one issue left. The DCG willl have different scales for different queries/topics. For example, for one query we may have 6 highly relevant documents, whereas for another query we may have only 2. This will obviously influence the scale of the DCG.
So if we want to meaningfully compare the DCG of two queries, we need to both normalize them (in the range [0,1]) relative to their ideal ranking.
The ideal ranking is just the ranking sorted on the known relevance judgements. I was wondering whether we need tie-breaking, but we don't as only the gain counts in this case.
It makes sense that the result will be in [0,1] because the DCG is discounted and thus will never be larger than the ideal ranking.
$$N DCG(L) = \frac{DCG(L)}{Ideal DCG}$$
Now the query difficulty etc. is taken into account, because performance is measured relative to how good we could have done for the current query.
Normalization does not affect the performance comparison because the ideal DCG is the same for each system. It's the same for a given query, independent of the retrieval system.
Practical challenges
- Representativeness of documents and queries
- Have enough queries and documents to avoid bias
- For high-recall task, you can't have one relevant document only
- Have enough queries for statistical testing between measured results
- Sign test (p. 19)
- Wilcoxon signed-rank test
- t-test
W.r.t. significance testing:
A particularly interesting test is the Wilcoxon signed-rank test. It’s a nonparametric test, and we not only look at the signs, but also consider the magnitude of the difference in scores. Another is the (parametric) t-test where a normal distribution is assumed. (19)