What is the NDCG metric?
NDCG stands for Normalized Discounted Cumulative Gain.
Recommender systems are important in sevaral application domains such as e-commerce, finance, healthcare and so on. It is important to come up with evaluation metrics to measure how well a recommender system works. Look at our article on Evaluation metrics for recommender systems for a quick overview.
Why do we need the NDCG metric?
Typical classification and regression metrics measure whether the predicted value is close to the actual value. But they do not account for the order of predictions. To evaluate recommender systems we need to measure how relevant the results are and how good the ordering is.
The most popular metric to evaluate a recommender system is the MAP@K metric. This metric tries to measure how many of the recommended results are relevant and are showing at the top.
However, the MAP@K metric has some shortcomings. The MAP@K metric focusses on precision – which which of the recommended items are relevant and which are not. It does not take into account how relevant the recommended results are.
There are many instances where the user assigns an explicit score to a recommended item, or we have expert evauators give a score for recommendations. When we have the ground truth for relevence score, we can try to evaluate how relevant the recommendations are.
One can think of the difference between the MAP and NDCG metric as the difference between evaluating predictions of 0-1 decisions like in classification vs predicting scores as in regression.
How does the NDCG Metric Work?
The NDCG metric involves finding the normalized discounted cumulative gain.
What is Gain?
Gain is just the relevance score for each item recommended.
What is cumulative gain?
Cumulative gain at K is the sum of gains of the first K items recommended.
Note that this still does not take into account the ordering of the items.
What is discounted cumulative gain?
Discounted cumulative gain weighs each relevance score based on its position. The recommendations at the top get a higher weight while the relevance of those at the bottom get a lower weight.
Note that the denominator is log(i+1) giving more weightage to items recommended at the top.
The DCG has one shortcoming: The score is dependent on the number of items recommended. If we have two recommenders that are recommending a different number of items, it is hard to compare the DCG score. The recommender with more items is likely to have a higher score.
What is the NDCG Metric ?
The normalized discounted cumulative gain is the DCG with a normalization factor in the denominator.
The denominator is the ideal DCG score when we recommend the most relevant items first.
NDCG Example:
To understand this better, here is an example that shows how the NDCG is computed.
| i | Recommender:Doc Order | Recommender:Doc Relevance | Ground Truth:Doc Order | Ground Truth:Doc Relevance |
| 1 | d10 | 3 | d3 | 4 |
| 2 | d3 | 4 | d10 | 3 |
| 3 | d1 | 3 | d1 | 3 |
The table above shows the document order as shown by the recommender. This is based on the relevance score predicted by the recommender.
The second column is the actual relevance score given by the customer or the evaluator.
The third column shows the documents in descending order of this relevance score. The fourth column once again shows the ground truth relevance score given by the customer or evaluator.
The DCG is computed from the first two columns (with the order shown in column 1). The IDCG or the ideal DCG is computed using the last two columns. The NDCG is the ratio as shown in the picture.