Normalized Cross Entropy

In this paper: http://quinonero.net/Publications/predicting-clicks-facebook.pdf, the authors introduce a metric called Normalized Cross Entropy (NCE):

$$\text{NE} = \frac{-\frac{1}{N} \sum_{i=1}^n(y_i\log(p_i) + (1-y_i)\log(1-p_i))}{-(p\log(p) + (1-p)\log(1-p))}$$

where $$p_i$$ is the estimated $$P(y_i=1)$$ and $$p=\sum_i y_i/N$$ is the "average" probability over the training set. Note that here, unlike the paper, I've assumed $$y_i \in \{0,1\}$$ to give the numerator the more familiar looking form of binary cross entropy.

The authors claim that the normalization, i.e. dividing the cross entropy in the numerator by the cross entropy for a model that predicts $$p$$ for every example, is because the closer $$p$$ is to 0 or 1, the easier it is to achieve a better log loss (i.e. cross entropy, i.e. numerator). Can someone explain why this is true?

• First note that the denominator does not depend on the model, so it is only a linear transform of the LLH.
• Unless your model is worse than predicting a constant, the denominator should be higher than the numerator, so it is usually between 0 and 1
• Typically, when the label is difficult to predict accurately, the LLH is not very far from the denominator. The proposed normalization may allow to get a metric a bit more comparable between datasets with different ratio of positives.

Personally I like using 1 - LLH / Entropy ( So 1 minus their metric), which can be interpreted as the "proportion of entropy explained by the model".

I think what the author meant was that the denominator (log loss from the background CTR) will be close to 0 when the background CTR p is close to either 0 or 1. This can be easily verified by plotting a graph. It does not look like the sentence was referring to the numerator.

Simply speaking, one wants to compare his model accuracy versus a 'free' vanilla model (that outputs always the majority class). How? create a ratio and put the entropy of the free model into denominator. Why? for extremely unbalanced data with 99% majority class, even 'free' vanilla model claims high accuracy, which in real life often a useless prediction.

I further would suggest the following modification: E(of my model)/E(of baseline 'free' model) - 1 to capture the actual improvement in entropy.

the closer p is to 0 or 1, the easier it is to achieve a better log loss (i.e. cross entropy, i.e. numerator).

If almost all of the cases are of one category, then we can always predict a high probability of that category and get a fairly small log loss, since extreme probabilities will be close to almost all of the cases, and then there are just a couple of mistakes. Contrast this with perfect balance of the classes. If we predict extreme probabilities in favor of class $$0$$, then we have bad predictions half of the time. If we predict extreme probabilities in favor of class $$1$$, then we have bad predictions half of the time.

There are ways to break this. For instance, an extremely extreme probability prediction of the wrong class can wreck the entire log loss calculation (in the sense of making the log loss very large). Because of this, I am not so sure that I agree with the claim the authors make.

Nonetheless, their approach seems to be similar to (if not the same as) McFadden's $$R^2$$, and they do exactly what I argue is correct for an out-of-sample $$R^2$$-style metric. That McFadden $$R^2$$ metric, and many more, are discussed on a UCLA page about pseudo $$R^2$$ values in classification problems.