Online and Offline

When we refer to online vs. offline recommenders we are referring to when you’re running evals. Offline evaluation is when you start with a test/evaluation dataset, outside your production system, and compute a set of metrics. This is often the simplest to set up, but has the highest expectation of existing data. Using historical data, you construct a set of relevant responses, which you can then use during simulated inference. This is the most similar to other kinds of traditional Machine Learning, although with slightly different computations for the error.

When we’re training large models, these datasets are very similar to an offline dataset. We previously saw prequential data, which is much more relevant in Recommendation Systems than in lots of other ML applications. Sometimes you’ll hear people say that “all recommenders are sequential recommenders” because of how important historical exposure is to the recommender problem.

Online evaluation takes place during inference, usually in prod. The tricky part is, you essentially never know the counter-factual outcomes. You can compute specific metrics on the online rankings: frequency and distributions of covariates, click-through-rate/success-rate, or time-on-platform, but ultimately these are different than the offline metrics.

User vs. Item metrics

Because Recommender Systems are personalization machines, it can be very easy to think that we always want to be making recommendations for the user, and measuring the performance as such. There are some subtleties, though. We want to be sure individual items are getting a fair chance, and sometimes looking at the other side of the equation can help us assess this. In other words, are the items getting recommended frequently enough to have a chance to find their niche. We should explicitly compute our metrics over user and item axes.

Another aspect of item-side metrics, is for set-based recommenders. The other items that are recommended in context, can have a very significant effect on the performance of a recommendation. As a result, we should be careful to measure the pairwise item metrics in our large scale evaluations.

A/B testing

It’s good to use randomized, controlled trials to evaluate if your new recommendation model is performing. For recommendations, this is quite tricky. We’ll see at the end of this chapter some of the nuance in this, but for now, let’s consider a quick reminder of how to think about A/B testing in a closed-loop paradigm.

A/B tests are ultimately attempting to estimate the effect size of swapping one model in for another – effect size estimation is the process of measuring the causal impact of an intervention on a target metric. First, we would need to deploy two recommender models. We’d also hope that there’s a reasonable randomization of users into each of the recommenders. However, what’s the randomization unit? It’s easy to quickly assume it’s the user, but what has changed about the recommender? Has the recommender changed in a way that covaries with some properties of the distribution, e.g. have you built a new recommender that is less friendly towards seasonal TV specials just as we enter into the second week of November?

Another consideration with this sort of testing for recommendation systems is the long term compounding effects. A frequent rejoinder about a series of positive A/B test outcomes over several years is “have you tested the first recommender against the last?”. This is because populations change, both the users and the items. As you vary also the recommender system, you frequently find yourself in a double-blind situation where you’ve never seen this user or item population with any other recommender. If all the effect-sizes of every A/B test was additive across the industry, the world GDP would likely be 2-3 times as large.

The way to guard against protests like this is via something called a long-term holdout, i.e. a set of random subset (continually being added to) users who will not be upgraded to new models through time. By measuring the target metrics on this set vs. the most cutting edge model in production, you’re always able to understand the long term effects of your work. The downside of a long-term holdout? They’re hard to maintain, and it’s hard to sacrifice some of the effects of your work on a subset of the population.

Now let’s finally get to the metrics already!

@ K

In much of this chapter and recsys metrics discussion, we say things like @ K. This means “at K” which should really be “in K” or “out of K”. These are simply the size of the set of recommendations. We will often anchor the customer experience on “how many recommendations we can show to the user without the experience suffering. We also will need to know the cardinality of the set of relevant items, which we call @ R. Note that while it may not feel like it’s possible to ever know this number, we assume this refers to “known relevant” via our training or test data.

Precision at K

Precision is the ratio of the size of the set relevant recommendations to K, the size of the set of recommendations.

Notice that the size of the relevant items doesn’t appear in the formula. That’s ok, the size of the intersection is still dependent on the size of the set of relevant items.

Looking at our examples, technically 2 has the highest precision, but it’s a bit of red herring because of how many relevant results there are. This is one reason why precision is not the most common metric for evaluating recommendation systems.

Recall at K

Recall is the ratio of the size of the set of relevant recommendations to R, the size of the set of relevant items.

But wait! If the ratio is the relevant recommendations over the relevant items, where is K? K is still important here because the size of the set of recommendations constrains the possible size of the intersection. Recall that these ratios are operating on that intersection which is always dependent on K. This means you often consider the max of R and K.

In scenario three, we hope that some of the movies that fit our heart’s desire will be on the right streaming platform. The number of these divided by the count of all the media anywhere is the recall. If all your relevant movies are on this platform, you might call that Total Recall.

Scenario four’s cafe experience shows that recall is sometimes the “inverse probability of an avoid”; because you like so many coffees we might instead find it easier to talk about what you don’t like. In this case, the number of avoids in their offering will have a large effect on the recall:

This is the core mathematical definition for recall, and is often one of the first measurements we’ll consider due to the fact that it’s a pure estimate of how your retrieval is performing.

R-precision

If we also have a ranking on our recommendations we can take the ratio of relevant recommendations to R in the top-R recommendations. This improves this metric in cases where R is very small – like examples one and three.

MAP

This is a vital metric in recommendation systems, and it’s particularly adept at accounting for the rank of relevant items. If, in a list of five items, the relevant ones are found at positions 2, 3, and 5, mAP would be calculated by computing precision@2, precision@3, and precision@5, and then taking an average of these values. The strength of mAP lies in its sensitivity to the ordering of relevant items, providing a higher score when these items are ranked higher.

Consider an example with two recommendation algorithms A and B:

• For Algorithm A, we compute the mAP as: mAP = (precision@2 + precision@3 + precision@5) / 3 = (1/2 + 2/3 + 3/5) / 3 = 0.6

• For Algorithm B, which perfectly ranks the items, mAP is calculated as: mAP = (precision@1 + precision@2 + precision@3) / 3 = (1/1 + 2/2 + 3/3) / 3 = 1

The generalized formula for mAP across a set of queries Q is:

Here, $\left|Q\right|$ is the total number of queries, $m_q$ is the number of relevant documents for a specific query $q$, $P\left(k\right)$ stands for the precision at the k’th cutoff, and $rel\left(k\right)$ is an indicator function equating to 1 if the item at rank $k$ is relevant, and 0 otherwise.

MRR

Another effective metric used in recommendation systems is MRR. Unlike MAP, which considers all relevant items, MRR primarily focuses on the position of the first relevant item in the recommendation list. It’s computed as the reciprocal of the rank where the first relevant item appears.

Consequently, MRR can reach its maximum value of 1 if the first item in the list is relevant. If the first relevant item is found further down the list, MRR takes a value less than 1. For instance, if the first relevant item is positioned at rank 2, the MRR would be 1/2.

Let’s look at this in the context of the recommendation algorithms A and B that we used earlier:

• For Algorithm A, the first relevant item is at rank 2, so the MRR equals 1/2 = 0.5.

• For Algorithm B, which perfectly ranked the items, the first relevant item is at rank 1, so the MRR equals 1/1 = 1.

Extending this to multiple queries, the general formula for MRR is:

Here, |Q| represents the total number of queries and $ran{k}_i$ is the position of the first relevant item in the list for the ith query. This metric provides valuable insight into how well a recommendation algorithm delivers a relevant recommendation right at the top of the list.

NDCG

To further refine our understanding of ranking metrics, let’s step into the world of NDCG. Like mAP and MRR, NDCG also acknowledges the rank order of relevant items, but it introduces a twist. It discounts the relevance of items as we move down the list, signifying that items appearing earlier in the list are more valuable than those ranked lower.

NDCG begins with the concept of Cumulative Gain (CG), which is simply the sum of the relevance scores of the top k items in the list. Discounted Cumulative Gain (DCG) takes a step further, discounting the relevance of each item based on its position. NDCG, then, is the DCG value normalized by the Ideal DCG (IDCG), the DCG that we would obtain if all relevant items appeared at the very top of the list.

Assuming we have five items in our list and a specific user for whom the relevant items are found at positions 2 and 3, the IDCG@k would be (1/log(1 + 1) + 1/log(2 + 1)) = 1.5 + 0.63 = 2.13.

To put this into the context of our example algorithms A and B:

For Algorithm A:

• DCG@5 = 1/log(2 + 1) + 1/log(3 + 1) + 1/log(5 + 1) = 0.63 + 0.5 + 0.39 = 1.52

• NDCG@5 = DCG@5 / IDCG@5 = 1.52 / 2.13 = 0.71

For Algorithm B:

• DCG@5 = 1/log(1 + 1) + 1/log(2 + 1) + 1/log(3 + 1) = 1 + 0.63 + 0.5 = 2.13

• NDCG@5 = DCG@5 / IDCG@5 = 2.13 / 2.13 = 1

The general formula for NDCG can be represented as:

$NDCG@k=\frac{DCG@k}{IDCG@k}$,

where

• $DCG@k={\sum }_{i=1}^k\frac{re{l}_i}{lo{g}_2(i+1)}$,

• $IDCG@k={\sum }_{i=1}^{\left|ℛ\right|}\frac{1}{lo{g}_2(i+1)}$,

and $ℛ$ is the set of relevant documents.

This metric gives us a normalized score for how well our recommendation algorithm ranks relevant items, discounting as we move further down the list.

Correlation coefficients

While correlation coefficients like Pearson’s or Spearman’s can be employed to evaluate the similarity between two rankings (for instance, between the predicted and the ground truth rankings), they do not provide the exact same information as MAP, MRR, or NDCG.

Correlation coefficients are typically used to measure the degree of linear association between two continuous variables, and in the context of ranking, they can indicate the overall similarity between two ordered lists. However, they do not directly account for aspects such as the relevance of individual items, the position of relevant items, or varying degrees of relevance among items, which are integral to mAP, MRR, and NDCG.

For example, consider a scenario where a user has interacted with five items in the past. A recommender system might predict that the user will interact with these items again, but rank them in the opposite order of importance. Even though the system has correctly identified the items of interest, the reversed ranking would lead to poor performance as measured by mAP, MRR, or NDCG, but a high negative correlation coefficient would be obtained due to the linear relationship.

As a result, while correlation coefficients can provide a high-level understanding of ranking performance, they are not sufficient substitutes for the more detailed information provided by metrics like mAP, MRR, and NDCG.

To utilize correlation coefficients in the context of ranking, it would be essential to pair them with other metrics that account for the specific nuances of the recommendation problem, such as the relevance of individual items and their positions in the ranking.

Recommendation Probabilities to AUC-ROC

In a binary classification setup, the Area Under the Receiver Operating Characteristic Curve (AUC-ROC) measures the ability of the recommendation model to distinguish between positive (relevant) and negative (irrelevant) instances. It is calculated by plotting the True Positive Rate (TPR) against the False Positive Rate (FPR) at various threshold settings, then computing the area under this curve.

In the context of recommendations, you can think of these “thresholds” as varying the number of top items recommended to a user. The AUC-ROC metric becomes an evaluation of how well your model ranks relevant items over irrelevant ones, irrespective of the actual rank position. In other words, AUC-ROC effectively quantifies the likelihood that a randomly chosen relevant item is ranked higher than a randomly chosen irrelevant one by the model. This, however, doesn’t account for the actual position or order of items in the list, only the relative ranking of positive versus negative instances. The affinity of an item when calibrated may be interpreted as a confidence measure by the model that an item is relevant, and when considering historical data, even uncalibrated affinity scores may make a great suggestion both for the number of recs necessary to find something useful.

One very serious implementation of these affinity scores might be to only show users items over a particular score; otherwise telling the user to come back later or utilizing some exploration methods to improve your data. For example if you sold hygeine products and were considering asking customers to add on some Aesop soap during checkout, you may wish to evaluate the Aesop ROC and only make this suggestion when the observed affinity passed the learned threashold. We’ll also see these concepts used later during our discussion of “Inventory Health”.

Comparison to Other Metrics

1. Mean Average Precision (mAP): this metric expands on the idea of precision at a specific cut-off in the ranked list to provide an overall measure of model performance. It does this by averaging the precision values computed at the ranks where each relevant item is found. Unlike AUC-ROC, mAP puts emphasis on the higher-ranked items and is more sensitive to changes at the top of the ranking.

2. Mean Reciprocal Rank (MRR): Unlike AUC-ROC and mAP which consider all relevant items in the list, MRR focuses only on the rank of the first relevant item in the list. It is a measure of how quickly the model can find a relevant item. If the model consistently places a relevant item at the top of the list, it will have a higher MRR.

3. Normalized Discounted Cumulative Gain (NDCG): this metric evaluates the quality of the ranking by not only considering the order of recommendations but also taking into account the graded relevance of items (which the previous metrics don’t). NDCG discounts items further down the list, rewarding relevant items that appear near the top of the list.

AUC-ROC provides a valuable aggregate measure of a model’s ability to differentiate between relevant and irrelevant items, mAP, MRR, and NDCG offer a more nuanced evaluation of the model’s ranking quality, considering factors like position bias and varying degrees of relevance.

Note that we sometimes compute the AUC on a per-customer basis and then average. That’s cAUC and can often provide a good expectation for a user’s experience.