1 of 52

CS255 Fundamentals of Information Retrieval

Lecture 12

IR Evaluation

Krishnendu Ghosh

Department of Computer Science & Engineering

Indian Institute of Information Technology Dharwad

2 of 52

Situation

Thanks to your stellar performance in CS468, you quickly rise to VP of Search at internet retail giant TEMU. Your boss brings in her nephew Sergey, who claims to have built a better search engine for TEMU. Do you

Laugh derisively and send him to rival Tramlaw Labs?
Counsel Sergey to go to IIIT Dharwad and take CS468?
Try a few queries on his engine and say “Not bad”?
… ?

3 of 52

What could you ask Sergey?

How fast does it index?

Number of documents/hour
Incremental indexing – TEMU adds 10K products/day

How fast does it search?

Latency and CPU needs for nozama’s 5 million products

Does it recommend related products?

This is all good, but it says nothing about the quality of Sergey’s search

You want TEMU’s users to be happy with the search experience

4 of 52

How do you tell if users are happy?

Search returns products relevant to users

How do you assess this at scale?

Search results get clicked a lot

Misleading titles/summaries can cause users to click

Users buy after using the search engine

Or, users spend a lot of $ after using the search engine

Repeat visitors/buyers

Do users leave soon after searching?
Do they come back within a week/month/… ?

5 of 52

Happiness: Elusive to Measure

Most common proxy: relevance of search results

Pioneered by Cyril Cleverdon in the Cranfield Experiments

But how do you measure relevance?

6 of 52

Measuring Relevance

Three elements:

A benchmark document collection
A benchmark suite of queries
An assessment of either Relevant or Nonrelevant for each query and each document

7 of 52

Want to Measure Quality of a New Search Algo?

Benchmark documents – TEMU’s products

Benchmark query suite – more on this

Judgments of document relevance for each query

8 of 52

Relevance Judgments

Binary (relevant vs. non-relevant) in the simplest case

More nuanced relevance levels also used(0, 1, 2, 3 …)

What are some issues already?

5 million times 50K takes us into the range of a quarter trillion judgments

If each judgment took a human 2.5 seconds, we’d still need 1011 seconds, or nearly $300 million if you pay people $10 per hour to assess

10K new products per day

9 of 52

What else?

Present query-document pairs to low-cost labor on online crowd-sourcing platforms

Hope that this is cheaper than hiring qualified assessors

Lots of literature on using crowd-sourcing for such tasks

You get fairly good signal, but the variance in the resulting judgments is quite high

10 of 52

Crowd Source Relevance Judgments?

till need test queries

Must be germane to docs available
Must be representative of actual user needs
Random query terms from the documents are not a good idea
Sample from query logs if available

Classically (non-Web)

Low query rates – not enough query logs
Experts hand-craft “user needs”

11 of 52

Early Public Test Collections (20th Century)

Recent datasets: 100s of million web pages (GOV, ClueWeb, …)

12 of 52

Benchmark

Let’s review some evaluation measures

Precision
Recall
DCG
…

13 of 52

Evaluating an IR system

Note: user need is translated into a query
Relevance is assessed relative to the user need, not the query
E.g., Information need: My swimming pool bottom is becoming black and needs to be cleaned.
Query: pool cleaner
Assess whether the doc addresses the underlying need, not whether it has these words

14 of 52

Unranked Retrieval Evaluation: Precision and Recall

Binary assessments

Precision: fraction of retrieved docs that are relevant = P(relevant|retrieved)
Recall: fraction of relevant docs that are retrieved
= P(retrieved|relevant)

Precision P = tp/(tp + fp)
Recall R = tp/(tp + fn)

15 of 52

Rank-Based Measures

Binary Relevance

Precision@K (P@K)
Mean Average Precision (MAP)
Mean Reciprocal Rank (MRR)

Multiple levels of relevance

Normalized Discounted Cumulative Gain (NDCG)

16 of 52

Precision@K

Set a rank threshold K

Compute % relevant in top K

Ignores documents ranked lower than K

Ex:

Prec@3 of 2/3

Prec@4 of 2/4

Prec@5 of 3/5

In similar fashion we have Recall@K

17 of 52

A precision-recall curve

18 of 52

Average Precision

19 of 52

Average Precision

where rel⁡(k) is an indicator function equaling 1 if the item at rank k is a relevant document, zero otherwise. Note that the average is over relevant documents in top-k retrieved documents and the relevant documents not retrieved get a precision score of zero.

20 of 52

MAP

21 of 52

Mean Average Precision

If a relevant document never gets retrieved, we assume the precision corresponding to that relevant doc to be zero

MAP is macro-averaging: each query counts equally

Now perhaps most commonly used measure in research papers

Good for web search?

MAP assumes user is interested in finding many relevant documents for each query

MAP requires many relevance judgments in text collection

22 of 52

R-Precision

R-precision requires knowing all documents that are relevant to a query. The number of relevant documents, R, is used as the cutoff for calculation, and this varies from query to query.

Note that the R-Precision is equivalent to both the precision at the R-th position (P@R) and the recall at the R-th position.

23 of 52

Discounted Cumulative Gain

Popular measure for evaluating web search and related tasks

Two assumptions:

Highly relevant documents are more useful than marginally relevant documents

the lower the ranked position of a relevant document, the less useful it is for the user, since it is less likely to be examined

24 of 52

Discounted Cumulative Gain

Uses graded relevance as a measure of usefulness, or gain, from examining a document

Gain is accumulated starting at the top of the ranking and may be reduced, or discounted, at lower ranks

Typical discount is 1/log(rank)

With base 2, the discount at rank 4 is 1/2, and at rank 8 it is 1/3

25 of 52

Summarize a Ranking: DCG

What if relevance judgments are in a scale of [0,r]? r>2

Cumulative Gain (CG) at rank n

Let the ratings of the n documents be r1, r2, …rn (in ranked order)

CG = r1+r2+…rn

Discounted Cumulative Gain (DCG) at rank n

DCG = r1 + r2/log22 + r3/log23 + … rn/log2n

We may use any base for the logarithm

26 of 52

Discounted Cumulative Gain

DCG is the total gain accumulated at a particular rank p:

Alternative formulation:

used by some web search companies

emphasis on retrieving highly relevant documents

27 of 52

DCG Example

10 ranked documents judged on 0–3 relevance scale:

3, 2, 3, 0, 0, 1, 2, 2, 3, 0

discounted gain:

3, 2/1, 3/1.59, 0, 0, 1/2.59, 2/2.81, 2/3, 3/3.17, 0

= 3, 2, 1.89, 0, 0, 0.39, 0.71, 0.67, 0.95, 0

DCG:

3, 5, 6.89, 6.89, 6.89, 7.28, 7.99, 8.66, 9.61, 9.61

28 of 52

NDCG for Summarizing Rankings

Normalized Discounted Cumulative Gain (NDCG) at rank n

Normalize DCG at rank n by the DCG value at rank n of the ideal ranking

The ideal ranking would first return the documents with the highest relevance level, then the next highest relevance level, etc

Normalization useful for contrasting queries with varying numbers of relevant results

NDCG is now quite popular in evaluating Web search

29 of 52

NDCG for summarizing rankings

4 documents: d₁, d₂, d₃, d₄

i	Ground Truth		Ranking Function₁		Ranking Function₂
i	Document Order	r_i	Document Order	r_i	Document Order	r_i
1	d4	2	d3	2	d3	2
2	d3	2	d4	2	d2	1
3	d2	1	d2	1	d4	2
4	d1	0	d1	0	d1	0
	NDCG_GT=1.00		NDCG_RF1=1.00		NDCG_RF2=0.9203

30 of 52

NDCG for summarizing rankings

31 of 52

What if the results are not in a list?

Suppose there’s only one Relevant Document

Scenarios:

known-item search
navigational queries
looking for a fact

Search duration ~ Rank of the answer

measures a user’s effort

32 of 52

Mean Reciprocal Rank

Consider rank position, K, of first relevant doc
Could be – only clicked doc
Reciprocal Rank score =
MRR is the mean RR across multiple queries

Where ranki refers to the rank position of the first relevant document for the i-th query.

33 of 52

Mean Reciprocal Rank

Given those three samples, we could calculate MRRS as (1/3+1/2+1)/3=11/18, or approximately 0.61.

34 of 52

Human Judgments

Expensive
Inconsistent

Between raters
Over time

Decay in value as documents/query mix evolves
Not always representative of “real users”

Rating vis-à-vis query, don’t know underlying need
May not understand meaning of terms, etc.

So – what alternatives do we have?

35 of 52

User Behavior

Search Results for “CIKM” (in 2009!)

# of clicks received

36 of 52

User Behavior

Adapt ranking to user clicks?

# of clicks received

37 of 52

What do clicks tell us?

Tools needed for non-trivial cases

# of clicks received

38 of 52

Eye-tracking User Study

39 of 52

Click Position-bias

Higher positions receive more user attention (eye fixation) and clicks than lower positions.

This is true even in the extreme setting where the order of positions is reversed.

“Clicks are informative but biased”.

Normal Position

Percentage

Reversed Impression

Percentage

40 of 52

Relative vs Absolute Ratings

User’s click sequence

41 of 52

Evaluating Pairwise Relative Ratings

Pairs of the form: DocA better than DocB for a query

Doesn’t mean that DocA relevant to query

Now, rather than assess a rank-ordering wrt per-doc relevance assessments …
Assess in terms of conformance with historical pairwise preferences recorded from user clicks
BUT!
Don’t learn and test on the same ranking algorithm

i.e., if you learn historical clicks from nozama and compare Sergey vs nozama on this history …

42 of 52

Comparing Two Rankings via Clicks

Kernel machines

SVM-light

Lucent SVM demo

Royal Holl. SVM

SVM software

SVM tutorial

Kernel machines

SVMs

Intro to SVMs

Archives of SVM

SVM-light

SVM software

Query: [support vector machines]

Ranking A

Ranking B

43 of 52

Interleave the Two Rankings

Kernel machines

SVM-light

Lucent SVM demo

Royal Holl. SVM

Kernel machines

SVMs

Intro to SVMs

Archives of SVM

SVM-light

This interleaving�starts with B

…

44 of 52

Remove Duplicate Results

Kernel machines

SVM-light

Lucent SVM demo

Royal Holl. SVM

Kernel machines

SVMs

Intro to SVMs

Archives of SVM

SVM-light

…

45 of 52

Count User Clicks

Kernel machines

SVM-light

Lucent SVM demo

Royal Holl. SVM

Kernel machines

SVMs

Intro to SVMs

Archives of SVM

SVM-light

…

Clicks

Ranking A: 3�Ranking B: 1

A, B

A

46 of 52

Interleaved Ranking

Present interleaved ranking to users

Start randomly with ranking A or ranking B to even out presentation bias

Count clicks on results from A versus results from B

Better ranking will (on average) get more clicks

47 of 52

A/B testing at Web Search Engines

Purpose: Test a single innovation
Prerequisite: You have a large search engine up and running.
Have most users use old system
Divert a small proportion of traffic (e.g., 0.1%) to an experiment to evaluate an innovation

Interleaved experiment
Full page experiment

48 of 52

Facts/Entities

49 of 52

Recap

Benchmarks consist of

Document collection
Query set
Assessment methodology

Assessment methodology can use raters, user clicks, or a combination

These get quantized into a goodness measure – Precision/NDCG etc.
Different engines/algorithms compared on a benchmark together with a goodness measure

50 of 52

User Behavior

User behavior is an intriguing source of relevance data

Users make (somewhat) informed choices when they interact with search engines
Potentially a lot of data available in search logs

But there are significant caveats

User behavior data can be very noisy
Interpreting user behavior can be tricky
Spam can be a significant problem
Not all queries will have user behavior

51 of 52

Incorporating User Behavior into Ranking Algorithm

Incorporate user behavior features into a ranking function like BM25F

But requires an understanding of user behavior features so that appropriate Vj functions are used

Incorporate user behavior features into learned ranking function

Either of these ways of incorporating user behavior signals improve ranking

52 of 52

Thank You