Name and origin of a metric for evaluating ranking performance

Question

I came across an evaluation metric to test whether a predicted rank is good, especially the top k items. But I don't know what it is called or where it is used, which makes my discussion of this metric very limited.

Suppose we have 5 items, A, B, C, D, and E.

Their corresponding values leading to the above rank are [ 10, 9, 7, 6, 3]. If k = 2, then our top k items are A and B.

Now without knowing the true rank or values, I trained a model and got a prediction for the ranking - [A, C, B, E, D]. Its top k items are A and C.

At the same time, I have another set of predictions from another method - [A, D, B, C, E]. Its top k items are A and D.

Although both have a top k accuracy of 0.5 because they both predicted Item A correctly only, the second one makes a worse decision on deciding the top k items.

To evaluate this, I first calculate the sum of the true values top k items, i.e. (A -> 10 + B -> 9) = 19.

For the first prediction, as A and C are chosen, the same calculation goes: (A -> 10 + B -> 7) = 17.

For the second prediction, the calculation is: (A -> 10 + D -> 6) = 16.

Then I divide the predicted top k sum by the true top k sum. So the first prediction got a value of 0.895. The second one got a value of 0.842. Therefore, the second prediction is worse than the first.

So does anyone know where does this method come from, and if I am using it correctly? My friend who works on active learning stuff told me this. But he can't remember where did he see this...

Answer 1

The evaluation metric you described is similar to the concept of "Cumulative Gain" (CG) in Information Retrieval. CG measures the quality of a ranked list of items by summing up the relevance scores of the items in the list.

In your example, the true top k items have a cumulative gain of 19, and the predicted top k items have a cumulative gain of 17 and 16 for the first and second predictions, respectively. By dividing the predicted cumulative gain by the true cumulative gain, you can get a value that indicates the effectiveness of the prediction.

It's worth noting that there are several variants of CG, such as Normalized Cumulative Gain (NCG), Discounted Cumulative Gain (DCG), and Normalized Discounted Cumulative Gain (NDCG). These variants differ in how they weight the relevance scores of the items in the list, but the basic idea is the same.

I hope this helps! Let me know if you have any other questions.