11
$\begingroup$

I want to compare two ranking algorithms. In these algorithms, client specifies some conditions in his/her search. According to the client`s requirements, these algorithm should assign a score for each items in data base and retrieve items with highest scores.

I have read different topics related to my question in this site and searched the net. According to my searches, the most relevant article which explains about some metrics for comparing ranking algorithms, was this: Brian McFee and Gert R. G. Lanckriet, Metric Learning to Rank, ICML 2010 (https://bmcfee.github.io/papers/mlr.pdf). I think prec@k, MAP, MRR, and NDCG, are good metrics to use, but I have a problem:

My algorithm sort results, so the first item in my result list is the best one with highest score, the second result have the second top score, and so on. I limit my search algorithm to for example find 5 best results.The results are the most top 5 items. So,precision will be 1. When I limit my search to find best result,It finds the best one. Again, precision will be 1.But the problem is that,it is unacceptable for people who see this result.

What can I do? How I can I compare these algorithms and show one is better than the other?

$\endgroup$
3
$\begingroup$

Discounted Cumulative Gain (DCG) is one of the most popular metrics used for evaluation of ranking by any search engine. It is a measure of ranking quality. In information retrieval, it is often used to measure the effectiveness of web search engine.

It is based on the following assumptions:

  1. Highly relevant documents are more useful if appearing earlier in a search result.
  2. Highly relevant documents are more useful than marginally relevant documents which are better than non-relevant documents.

The formula for DCG goes as follows:

$$DCG_p = \sum_{i=1}^p \frac {rel_i} {log_2 (i+1)} = rel_1 + \sum_{i=2}^p \frac {rel_i} {log_2 (i+1)} \tag{1}$$

Where:

  • i is the returned position of a document in the search result.
  • $rel_i$ is the graded relevance of the document
  • summation over p (number of results returned) hence, accumulated cumulative gain gives the performance metrics of the returned result.

DCG is derived from CG (Cumulative Gain), given by:

$$CG_p = \sum_{i=1}^p rel_i \tag{2}$$

From (2) it can be seen that $CG_p$ does not change for a change in the order of results. Thus to overcome this issue DCG was introduced. There is a different form of DCG, which is popular for placing a very high emphasis on retrieval of the documents. This version of DCG is given by:

$$DCG_p = \sum_{i=1}^p \frac {2^{rel_i} - 1} {log_2 (i+1)} \tag{3}$$

One obvious drawback of the DCG equation presented in (1) and (3) is that algorithms returning a different number of results cannot be compared effectively. This is because the higher the value of $p$ the higher the value of $DCG_p$ will be scaled to.

To overcome this issue, normalized DCG (nDCG) is proposed. It is given by,

$$nDCG_p = \frac {DCG_p} {IDCG_p}$$

where $IDCG_p$ is the Ideal $DCG_p$, given by,

$$IDCG_p = \sum_{i=1}^{|REL|} \frac {2^{rel_i} - 1} {log_2 (i+1)}$$

Where |REL| is the list of documents ordered by relevance in the corpus up to position p.

For a perfect ranking algorithm,

$$DCG_p = IDCG_p$$

Since the values of nDCG are scaled within the range [0,1], the cross-query comparison is possible using these metrics.

Drawbacks: 1. nDCG does not penalize the retrieval of bad documents in the result. This is fixable by adjusting the values of relevance attributed to documents. 2. nDCG does not penalize missing documents. This can be fixed by fixing the retrieval size and using the minimum score for the missing documents.

Refer this for seeing example calculations of nDCG.

Reference

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.