VL02 Ranking and Evaluation

Organisation and Exercise Sheet 2#

Feedback on ES1 showed typical ranking failures (Slide 4): specific queries (oppenheimer, indiana jones, gothic horror burton) worked well, but bomb returned Dr. Strangelove instead of Oppenheimer, toy story returned Finding Nemo first (it mentions Toy Story), british western matched westerns that won British awards, and in 12 years a slave the “12” was ignored (only letters are word characters), the rest is unspecific and word order is ignored. Tutor feedback appears as feedback-tutor.md in the SVN repository; individual timeslots with the tutor can be booked via Daphne (Slide 5).

ES2 (Slide 6): (1) compute BM25 scores, extending ES1; (2) write an automatic evaluation script for a benchmark; (3) tune the BM25 parameters on a training set, then evaluate once on the test set.

Ranking: Basic Idea#

A keyword query formulates a search desire, and not every document containing some or all keywords is relevant for it. We want the most relevant documents first; for web search with millions of hits this is crucial (Slide 7).

Basic idea (Slide 8):

1. In the inverted lists, store with each doc ID a score that captures how much the document is “about” that word.
2. While merging the lists, aggregate (sum) the scores of the same doc ID.
3. Sort by score.

university  17 0.5, 53 0.2, 97 0.3, 127 0.8
freiburg    23 0.1, 34 0.8, 53 0.1, 127 0.7

MERGED      17 0.5, 23 0.1, 34 0.8, 53 0.3, 97 0.3, 127 1.5
SORTED      127 1.5, 34 0.8, 17 0.5, 53 0.3, 97 0.3, 23 0.1

Top-k results#

A full sort of the merged list takes $\Theta(n \log n)$, with $n$ the number of postings. Usually only the top-$k$ hits are displayed, so a partial sort (the $k$ largest elements) suffices (Slide 9):

• possible in $\Theta(n + k \log k)$;
• $k$ rounds of HeapSort give $\Theta(n + k \log n)$;
• for constant $k$ both are $\Theta(n)$.

Scores: tf, df, idf#

Goal (Slide 10): the score of the posting for document $D_i$ in the inverted list of word $w$ should reflect the relevance of $w$ in $D_i$; the larger, the more relevant. Relevance is somewhat subjective, but it has to be done somehow anyway.

Problem: some words are frequent in many documents regardless of the content. With tf alone, of dominates the score:

university  …, 57 5,  …, 123 2,  …
of          …, 57 14, …, 123 23, …
freiburg    …, 57 3,  …, 123 1,  …
SCORE SUM   …, 57 22, …, 123 26, …

Document 123 wins only because it contains of more often. A word like of should count little for relevance.

The more frequent a word, the smaller its idf, so idf is a good proxy for the rarity of a word. Without the $\log_2$, small differences in $\mathrm{df}$ would have too much effect.

tf.idf#

The tf.idf score of $w$ in $D$ is $\mathrm{tf} \cdot \mathrm{idf}_w$ (Slide 13). In the example above:

university  …, 57 30 (=5·6),  …, 123 12 (=2·6),  …
of          …, 57 14 (=14·1), …, 123 23 (=23·1), …
freiburg    …, 57 30 (=3·10), …, 123 10 (=1·10), …
SCORE SUM   …, 57 74,         …, 123 45,         …

Now document 57, which mentions university and freiburg more often, ranks first.

BM25#

BM25 is a tf.idf-style formula that became famous for outperforming other formulas on standard benchmarks over many years.

• Standard setting: $k = 1.75$, $b = 0.75$.
• $k = 0$, $b = 0$: binary, $\mathrm{tf}^* = 1$ for every $\mathrm{tf} > 0$ (score = idf).
• $k \to \infty$, $b = 0$: normal tf.idf, since $\alpha = 1$ and $\mathrm{tf}^* \to \mathrm{tf}$.

Plausibility argument#

Part 1: $\mathrm{tf} \to \mathrm{tf}^*$ (Slide 16). Start from $\mathrm{tf} \cdot \mathrm{idf}$ and replace $\mathrm{tf}$ by $\mathrm{tf}^*$ such that

• $\mathrm{tf}^* = 0$ if and only if $\mathrm{tf} = 0$;
• $\mathrm{tf}^*$ increases as $\mathrm{tf}$ increases;
• $\mathrm{tf}^* \to$ a fixed limit as $\mathrm{tf} \to \infty$ (fixes problem 2).

The “simplest” formula with these properties is $\mathrm{tf}^* = \mathrm{tf} \cdot (k+1) / (k \cdot \alpha + \mathrm{tf})$, for any $\alpha > 0$; its limit is $k + 1$.

Part 2: choice of $\alpha$ (Slide 17). $\alpha$ acts as a normalization of $\mathrm{tf}$:

BM25 normalizes by document length (fixes problem 1):

• full normalization $\alpha = \mathrm{DL}/\mathrm{AVDL}$ is too extreme;
• some normalization: $\alpha = (1-b) + b \cdot \mathrm{DL}/\mathrm{AVDL}$, interpolating between none ($b = 0$) and full ($b = 1$).

Implementation advice#

(Slide 18)

1. Compute the inverted lists with tf scores (implicitly done in Lecture 1, where IDs were appended once per occurrence).
2. Along with that, compute $\mathrm{DL}$ for each document and $\mathrm{AVDL}$ (number of words).
3. Make a second pass over the inverted lists and replace each tf by $$\frac{\mathrm{tf} \cdot (k+1)}{k \cdot \left(1 - b + b \cdot \mathrm{DL}/\mathrm{AVDL}\right) + \mathrm{tf}} \cdot \log_2 \frac{N}{\mathrm{df}}.$$

Further refinements and other methods#

(Slides 19–20)

• Tune $k$ and $b$ (ES2).
• Boost results that match every query word at least once.
• Take the popularity of a movie into account. Some scores are already normalized (e.g. IMDb rating), others are not (e.g. IMDb #votes); a common heuristic for scores with huge differences is the logarithm, as for idf.
• Query logs and click-through data (who searched what and clicked on what): an important signal for big search engines.
• Learning to rank: for a query, compute a feature vector of many different scores for a subset of candidate documents, then rank these vectors with machine learning.

Evaluation: Ground Truth#

Example: query matrix movies, relevant: 10, 582, 877, 10003. The ES2 benchmark has 56 queries. Building high-quality benchmarks of sufficient size is an important and time-consuming part of research.

Precision at k#

Average Precision#

Mean Precisions over a Benchmark#

(Slide 24) Given a benchmark with several queries, capture the quality of a system by the mean of a measure over all queries:

• $\mathrm{MP@}k$ = mean of the $\mathrm{P@}k$ values over all queries;
• $\mathrm{MP@R}$ = mean of the $\mathrm{P@R}$ values over all queries;
• MAP = mean of the AP values over all queries.

These are very common measures in research papers on ranking.

Discounted Cumulative Gain#

Sometimes relevance comes in shades, e.g. 0 = not relevant, 1 = somewhat relevant, 2 = very relevant. Very relevant documents ranked above only somewhat relevant ones should get a bonus (Slide 25, DCG and nDCG).

Binary Preference (bpref)#

Sometimes relevance judgments exist only for a subset of the documents, typically for very large datasets where checking all documents is infeasible. A common approach in competitions is pooling: judge only the top-$k$ results of each participant (Slide 27, BPref).

Finer points (Slide 29):

• Why $|NR(d)| / \min(|R|, |N|)$ and not $|NR(d)| / |N|$? By definition $|NR(d)| \le |R|$ and $|NR(d)| \le |N|$, so the fraction lies in $[0,1]$. The score of $d$ already drops to zero when $|R|$ non-relevant documents come before it, so a high bpref is harder to achieve than with $|N|$.
• Why $1/|R|$ and not $1/|RR|$? A relevant document missing from the result list must be punished, for the same reason that AP takes $\mathrm{P@}R_i = 0$ for relevant documents not in the list.

Overfitting#

Extreme case: for each benchmark query, output the relevant documents from the ground truth. In a realistic setting (a real search engine or a competition) one develops on a training set, and the actual evaluation is on a test set that must not be used, or is not available, during development. ES2 provides a training benchmark for tuning and a test benchmark to measure quality once tuning is done.

Set vs. Ranked List#

The ground truth is a set, but the evaluated results are ranked lists (Slides 31–32). Why not evaluate differently?

1. Output a set and compare it with the ground truth? There is no natural cut-off value.
2. Make the ground truth a ranked list and compare rankings? The relevant documents usually have no full order (though there may be levels of relevance, cf. nDCG).
3. Evaluate the accuracy of the scores themselves? The absolute score values mean little; they only serve to rank the documents.

References#

Manning/Raghavan/Schütze, Section 6 (Scoring and Term Weighting) and Section 8 (Evaluation in IR); papers Probabilistic Relevance: BM25 and Beyond (FnTIR 2009) and Test Collection Based Evaluation of IR Systems (FnTIR 2010); Wikipedia: Okapi BM25, Information retrieval (Slide 33).

Concepts#

• Inverted Index — extended with scored postings; merging aggregates scores
• term frequencies — tf as the first, naive posting score
• TF-IDF — tf weighted by $\mathrm{idf} = \log_2(N/\mathrm{df})$ to discount common words
• BM25 — tf.idf with saturating, length-normalized $\mathrm{tf}^*$; implemented and tuned in ES2
• Ground Truth — relevant-document sets per query; with the queries it forms a benchmark
• Precision at k — P@k and P@R, fraction of relevant hits in the top $k$
• Average Precision — mean of $\mathrm{P@}R_i$ over all relevant documents, 0 for missing ones
• MAP — mean AP over a benchmark (with MP@k, MP@R)
• DCG and nDCG — evaluation with graded relevance, normalized by the ideal ranking
• BPref — evaluation with incomplete relevance judgments
• Overfitting (IR Evaluation) — tuning on the benchmark; avoided by a training/test split
• Posting — entry of an inverted list (doc ID, score, optionally positions)
• Document Frequency — number of documents containing a word, equal to the inverted list length
• Partial Sort (Top-k) — get the $k$ best hits in $\Theta(n + k \log k)$
• Pooling — judging only the top-$k$ results of each participant
• Learning to Rank — ranking feature vectors of candidate documents with machine learning