Measure retrieval recall

Learn it

Words to know

evaluation set

A fixed list of test questions with their correct answers or documents, used to measure a system the same way every time.

relevant document

A document that holds the answer to a test question.

recall at k

The share of the relevant documents that appear in the first k results.

How it works

1. With no relevant ids there is nothing to find. Return 0 instead of dividing by zero.
2. Take the first k results. Anything after that does not count, and a repeated result still uses up a place.
3. Count how many of the relevant ids are among them. Each relevant id counts once, however often it was retrieved.
4. Divide by the number of distinct relevant ids.

Worked example

Input
retrieved = ["d4", "d1", "d7", "d2"]
relevant = ["d1", "d2", "d3"]
k = 2

Output
0.333333

One of the three relevant documents is in the first two results, so recall at 2 is 1 / 3. With k raised to 4, d2 would count too, and recall would be 2 / 3.

Why it matters

The first portfolio project reports this number before and after each change, and once at the end on questions it kept aside. It measures the search only: an answer can still be wrong when recall is 1.

Your turn

Compute recall at k: the share of the relevant documents that appear in the first k results.

retrieved

the ids the search returned, best first; an id can appear twice

relevant

the ids that hold the answer; an id can appear twice

k

how many results count; 0 or more

Returns

A number from 0 to 1: the distinct relevant ids found in the first k results, divided by the number of distinct relevant ids. Do not round it. With no relevant ids, 0.

Input
retrieved = ["d4", "d1", "d7", "d2"]
relevant = ["d1", "d2", "d3"]
k = 2

Output
0.333333

Input
retrieved = ["a", "b", "c"]
relevant = ["a", "c"]
k = 2

Output
0.5

Input
retrieved = ["a", "a"]
relevant = ["a", "b"]
k = 2

Output
0.5

Input
retrieved = ["a"]
relevant = []
k = 1

Output
0

The checks also try

• a relevant id listed twice
• k is 0
• the same search with k raised to 4
• k larger than the result list
• a relevant id listed twice, and one missing
• a repeated result uses up a place

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Where to start

   Only the first k results count, so cut the list first. Then the question is how many relevant ids are in that cut.

2. Hint 2: The key step

   Use sets for both sides. A set holds each id once, so repeats on either side cannot change the count.

3. Hint 3: The outline

   Make a set targets from relevant. If it is empty, return 0. Make a set top from the first k items of retrieved. Count the ids in targets that are also in top, and return that count divided by the size of targets.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Step by step

1. The distinct relevant ids. A set removes repeats, so an id listed twice in relevant is still one document to find.
2. With nothing to find, recall is zero. Dividing by the size of an empty set would be a division by zero. Returning 0 is the rule this exercise uses for that case.
3. The first k results, each id once. Results after position k do not count, and a set keeps a document that was retrieved twice from being counted twice.
4. The share of the relevant ids that were found. The division is by the number of relevant ids, not by k. Dividing by k would measure precision at k: the share of the first k results that are relevant.

The same numbered steps are the comments in the solution.

function solve(retrieved, relevant, k) {
  // 1. The distinct relevant ids
  const targets = new Set(relevant);
  // 2. With nothing to find, recall is zero
  if (targets.size === 0) return 0;
  // 3. The first k results, each id once
  const top = new Set(retrieved.slice(0, k));
  // 4. The share of the relevant ids that were found
  let found = 0;
  for (const id of targets) {
    if (top.has(id)) found++;
  }
  return found / targets.size;
}

def solve(retrieved, relevant, k):
    # 1. The distinct relevant ids
    targets = set(relevant)
    # 2. With nothing to find, recall is zero
    if len(targets) == 0:
        return 0
    # 3. The first k results, each id once
    top = set(retrieved[:k])
    # 4. The share of the relevant ids that were found
    found = 0
    for doc_id in targets:
        if doc_id in top:
            found += 1
    return found / len(targets)

Watch out

• Divide by the number of relevant ids, not by k and not by the number of results. Dividing by k gives precision at k.
• Recall says nothing about the answer. A search can find every document and the model can still answer wrongly; measure that separately.
• Do not adjust the search on the same questions you report. Keep some questions aside and look at them only at the end.
• In JavaScript: A JavaScript Set has no length and no filter. Use set.size, and loop over it with for (const id of set).

Check yourself