Re: NDCG

[Kalervo Jarvelin <Kalervo.Jarvelin@uta.fi>]

This is a good summary. A point to add is that if one wants to 
consistently discount the gains, the log(rank+1) variant runs the risk 
of boosting (instead of discounting) at ranks below the log base. With 
base=2 this does not matter.

- Kal


Nick Craswell wrote:
> Executive summary: I think my statement is only true for the log(rank+1) variant.  That version of NDCG is used a lot, e.g. in SIGIR.
> 
> Now in detail:
> 
> Aha, good point, it depends on whether we're talking about original DCG, with its special case up to rank b, or the log(rank+1) version.
> 
> I agree that if you have a special case up to rank b, then the choice of b affects NDCG.
> 
> However, I think the log(rank+1) version is quite prevalent these days, if only because of all those MSR papers. :-)
> 
> In that version, log base doesn't matter.  To change base, you multiply by a constant, and you can move that constant to the outside of DCG's sum.  In NDCG, where you have two DCGs, the two constants cancel.  It's possible to write this down more formally, and I also tested it empirically once, if you're not convinced perhaps we can discuss offline.
> 
> I've worked with the original DCG in e.g. TREC Web Track a few years ago.  However, since then I've mainly used the log(rank+1) version (or a different/custom Discount function based on user data).  In my previous message I should have made it clear which version I was thinking of, my apologies.
> 
> cheers,
> Nick.
> 
> 
>> -----Original Message-----
>> From: ireval@nist.gov [mailto:ireval@nist.gov] On Behalf Of Tetsuya
>> Sakai (office)
>> Sent: 22 November 2007 00:36
>> To: Multiple recipients of list
>> Subject: Re: NDCG
>>
>>
>> Nick, that's not right.
>>
>> The log discounting is applied to the raw gain (G),
>> NOT to the cumulative gain (CG).
>> That is, G is first divided by a log, and then these
>> discounted values are added across ranks.
>> Hence the log base does make a difference.
>>
>> If you are using the ORIGINAL nDCG,
>> the choice of the log base b is indeed a crucial matter,
>> because you cannot apply the discounting until after Rank b.
>> And until you get to Rank b, nDCG is in fact nCG (the one without
>> discounting)
>> which is not good.
>>
>> Not good in the sense that the metric does not care
>> whether a relevant doc is at Rank 1 or at Rank b.
>> (This just generalises what Steve has already mentioned.)
>>
>>
>> If any of you are interested at all:
>>
>> Figure 1 (page 4) in this paper illustrates the curious property of
>> the original nDCG which Steve mentioned:
>> http://voice.fresheye.com/sakai/fi07.pdf
>> and a way to handle this issue is mentioned at the end of Section 3
>> (page
>> 3).
>> (Just a  generalisation of the Microsoft approach.)
>>
>> And if you'd like to see what nDCG with a large log base actually
>> behaves
>> like,
>> you might want to have a look at this paper:
>> http://research.nii.ac.jp/ntcir/workshop/OnlineProceedings6/EVIA/1.pdf
>>
>> (In my papers the log base is denoted by a, not b
>> because I use b for something else.)
>>
>> Dr. Tetsuya Sakai (sakai@newswatch.co.jp)
>> http://voice.fresheye.com/sakai/
>>
>>> Minor point: The base of the log changes DCG by a constant
>> multiplier,
>>> which cancels out when you calculate NDCG, so NDCG is completely
>>> unaffected by the log base.  I think.
>>>
>>> DCG = sum_r ( gain / log2(r) )
>>>    = sum_r ( gain / ( log(r) / log(2) ) )
>>>    = sum_r ( log(2) * gain / log(r) )
>>>    = log(2) * sum_r ( gain / log(r) )
>>>
>>> Nick.
>>>
>>>> -----Original Message-----
>>>> From: ireval@nist.gov [mailto:ireval@nist.gov] On Behalf Of Ian
>>>> Soboroff
>>>> Sent: 21 November 2007 14:45
>>>> To: Multiple recipients of list
>>>> Subject: Re: NDCG
>>>>
>>>>
>>>> Stephen Robertson <ser@microsoft.com> writes:
>>>>
>>>>> You might like to note that the original version has the rather
>>>>> curious property that rank 2 gets no discount.  A version commonly
>>>>> used in Microsoft is adjusted to give a discount even on rank 2.
>> How
>>>>> flexible are you making your implementation?  Any gain
>>>>> function/discount function/truncation point?
>>>> A few people are using such a variant that discounts by log(rank +
>> 1).
>>>> I like this approach better myself, but at this point I want to make
>>>> sure I've caught all the bugs and to do that I want to make sure I
>>>> match
>>>> the specification of the measure in the ToIS article.
>>>>
>>>> My implementation is based on trec_eval, and will allow specifying
>> gain
>>>> values per relevance level.  I think I will leave the log base as 2,
>> as
>>>> I have not seen much research that shows much sensitivity in that
>>>> parameter.  Truncation will be as usual in trec_eval (using the -M
>>>> option).
>>>>
>>>> I don't know if this will make it into the official trec_eval, but
>> if
>>>> not I'll probably post my patch someplace.
>>>>
>>>> Ian
>>>>
>>>
>>>
> 
> 
> 


-- 


----------------------------------------------------------------
Kalervo Jarvelin                  email: kalervo.jarvelin@uta.fi
Academy Professor                 www:   www.uta.fi/~likaja/
Department of Information Studies tel:   +358 3 3551 6953
FIN-33014 University of Tampere   gsm:   +358 50 547 9062
Finland                           home:  +358  3 317 1794