./ahmedhashim

In Layered Search Ranking, I created a ranker for a furniture catalog. Of course you can tune your ranker on a few example queries, but at some point you want a number that will tell you if your ranker is improving or degrading.

Offline evaluation will give you this number. Once you have a list of judged queries, you can evaluate your ranker against them and see how the score changes as you make changes to your ranker. Here are some metrics you can use to quantify how “good” your results are.

Judgments

All of the offline metrics below take the same input: some queries and their associated documents, judged for relevance.

The most basic form is binary relevance. For a query like walnut record cabinet, you’d have some set of products that you label relevant, and the rest would be non-relevant. You can also use graded relevance, where each judgment has an integer associated with how relevant the document is. Typically the grades go from 0 to 3, with 3 being a very relevant result. Grades allow a metric to prefer a highly relevant result over a somewhat relevant one.

Where the judgments come from depends on what you have access to. Editorial review will give you the highest quality labels, but it doesn’t scale. Most likely you’re going to have click logs and downstream conversions that give you noisier labels at a much higher volume. Most people end up with a mix of both.

Let’s assume the following judgments:

judgments = {
    "walnut record cabinet": {
        "vinyl_record_cabinet_v3": 3,
        "walnut_storage_console": 2,
        "oak_record_stand": 1,
    },
    # ...more queries
}

Precision

Precision is how many of the documents that are returned are relevant.

Using precision on the entire list of results isn’t too helpful when trying to evaluate rankings. Search engines return a lot of results, and the precision decreases as you go down the list. We use precision at k (P@k) to help with this problem. It only measures the top $k$ results:

P@5 and P@10 are used the most, as these are the top results the user will see.

def precision_at_k(retrieved: list[str], relevant: set[str], k: int) -> float:
    top_k = retrieved[:k]
    return sum(1 for doc in top_k if doc in relevant) / k

Recall

Recall is how many of the relevant documents are actually retrieved.

There’s always a trade-off between recall and precision. If you retrieve more documents, your recall will go up but your precision will decrease. This is because all the relevant documents are still there, but now there are more non-relevant documents mixed in.

def recall(retrieved: list[str], relevant: set[str]) -> float:
    if not relevant:
        return 0.0
    return sum(1 for doc in retrieved if doc in relevant) / len(relevant)

If users are only looking at the first 10 results, recall over all items won’t be very helpful. Recall at $k$ just looks at the top $k$ results, similar to P@k.

F-measure

The F-measure, or $F_1$, is the harmonic mean of precision and recall:

Since the harmonic mean skews towards the smaller of the two values, you’re not able to have a high $F_1$ if you’re really good at one and bad at the other. This can be changed using the generalized form:

$\beta > 1$ will weight recall higher and $\beta < 1$ will weight precision higher.

def f1(precision: float, recall: float) -> float:
    if precision + recall == 0:
        return 0.0
    return 2 * precision * recall / (precision + recall)

$F_1$ is used more in classification tasks. When it comes to ranking, MAP and nDCG are better choices, since they both take the rank into consideration.

Mean Average Precision

P@k doesn’t take into consideration where a relevant document lands within the top $k$. If the relevant document is at rank 1 or 5, you’ll get the same score. Average Precision (AP) fixes that by taking the average of the precision at each rank where a relevant document was found:

where $P(k)$ is the precision at cutoff $k$, and $\text{rel}(k)$ is 1 if the document at rank $k$ is relevant and 0 otherwise. Mean Average Precision calculates the average of AP for a set of queries:

MAP favors rankers that place relevant documents higher. Each relevant document adds the precision value at its rank, so bumping a relevant document from rank 9 to rank 1 helps its contribution substantially.

def average_precision(retrieved: list[str], relevant: set[str]) -> float:
    if not relevant:
        return 0.0
    hits = 0
    score = 0.0
    for k, doc in enumerate(retrieved, start=1):
        if doc in relevant:
            hits += 1
            score += hits / k
    return score / len(relevant)


def mean_average_precision(per_query: list[tuple[list[str], set[str]]]) -> float:
    return sum(average_precision(r, j) for r, j in per_query) / len(per_query)

MAP operates on yes/no judgments. If your judgments have levels of relevance, then nDCG is a better choice.

Normalized Discounted Cumulative Gain

Discounted Cumulative Gain (DCG) sums up the relevance grades of the top documents. The contribution of a grade is reduced the further down the list it occurs:

where $\text{rel}_i$ is the grade of the document at rank $i$, on a scale from 0 to 3 in our judgments.

The numerator is the grade, and the logarithm in the denominator is the discount. Consider vinyl_record_cabinet_v3, which has a grade of 3. At rank 1 it contributes $3 / \log_2 2 = 3$, its full grade. At rank 5 it contributes $3 / \log_2 6 \approx 1.16$, a little less than 40% of it. This drop-off approximates how user attention dwindles down a page.

Raw DCG doesn’t allow you to compare results between queries, because the maximum achievable value varies according to how many relevant documents there are for that query. Normalizing by the ideal ranking resolves that:

where $\text{IDCG}_p$ is the DCG you would achieve if you ordered the judged documents for that query by grade, highest first. For walnut record cabinet, this means grades 3, 2, 1, so $\text{IDCG}_3 = 3/1 + 2/1.58 + 1/2 \approx 4.76$. nDCG is guaranteed to range from 0 to 1, allowing you to compare runs and aggregate over queries.

from math import log2


def dcg(retrieved: list[str], judgments: dict[str, int], k: int) -> float:
    return sum(
        judgments.get(doc, 0) / log2(i + 1)
        for i, doc in enumerate(retrieved[:k], start=1)
    )


def ndcg(retrieved: list[str], judgments: dict[str, int], k: int) -> float:
    ideal = sorted(judgments.values(), reverse=True)[:k]
    idcg = sum(rel / log2(i + 1) for i, rel in enumerate(ideal, start=1))
    return dcg(retrieved, judgments, k) / idcg if idcg else 0.0

nDCG is the default offline evaluation measure for graded relevance.

Mean Reciprocal Rank

MRR calculates the average of the reciprocal rank of the first relevant document:

If the first relevant result is at rank 1, you get a score of 1.0. If it’s at rank 5, you get a score of 0.2. Notice how steep that drop-off is. That’s intentional: MRR doesn’t care how many other useful answers you give, only whether you gave the user’s first useful answer at the very top.

def reciprocal_rank(retrieved: list[str], relevant: set[str]) -> float:
    for k, doc in enumerate(retrieved, start=1):
        if doc in relevant:
            return 1 / k
    return 0.0


def mean_reciprocal_rank(per_query: list[tuple[list[str], set[str]]]) -> float:
    return sum(reciprocal_rank(r, j) for r, j in per_query) / len(per_query)

MRR mainly helps for things like known-item search and Q&A, where there tends to be one specific right answer for each query. In cases where you may have dozens of acceptable results, like catalog search, MAP and nDCG are more helpful.

The rank evaluation API

If you’re using OpenSearch, you don’t need to implement most of this yourself. Send your queries and judgments to the _rank_eval endpoint and it’ll execute the queries and calculate precision, recall, MRR, or nDCG for you. MAP and $F_1$ aren’t supported, though.

POST /products/_rank_eval
{
  "requests": [
    {
      "id": "walnut_record_cabinet",
      "request": {
        "query": {
          "multi_match": {
            "query": "walnut record cabinet",
            "fields": ["title^4", "description"]
          }
        }
      },
      "ratings": [
        { "_index": "products", "_id": "vinyl_record_cabinet_v3", "rating": 3 },
        { "_index": "products", "_id": "walnut_storage_console",  "rating": 2 },
        { "_index": "products", "_id": "oak_record_stand",        "rating": 1 }
      ]
    }
  ],
  "metric": {
    "dcg": {
      "k": 10,
      "normalize": true
    }
  }
}

The only difference between runs is the metric block. Swap dcg for precision, recall, mean_reciprocal_rank, or expected_reciprocal_rank and the rest of the request body stays the same. Each metric also accepts a few metric-specific options (k, relevant_rating_threshold, maximum_relevance) described in the docs.

The response gives you an aggregate metric_score and a per-query details map. That’s all you need to plot your scores over time or compare two versions of your ranker head-to-head.

Picking one

Pick a metric that lines up with what you care about optimizing. nDCG@10 is my first pick for a product catalog that has graded judgments and a long tail of decent matches. MRR is my first pick when there’s only 1 correct match per query (known-item search, Q&A, etc.). Because P@k is easiest for non-engineers to grasp, it goes well alongside either of the above on a dashboard. I’d only use $F_1$ for classification.

Offline metrics let you test changes to your ranker without impacting real users. To determine if a change actually helps shoppers after it ships, you’ll want to use online metrics.