# Estimating the entropy

Given a discrete random variable $X$, I would like to estimate the entropy of $Y=f(X)$ by sampling. I can sample uniformly from $X$. The samples are just random vectors of length $n$ where the entries are $0$ or $1$. For each sample vector $x_i$, I can then compute the function $f(x_i)$ which itself is a vector. A naive method is to run this process for as long as time allows and then to take the collection of $f(x_i)$ vectors and compute its entropy by making a histogram of how frequently each vector has occurred.

This however doesn't seem a good estimate. In particular, the sample space for $Y$ is exponential in $n$ and so I am very likely never to have seen any samples with low probability. This will mean I may grossly underestimate the entropy I think.

The size of the vectors $n$ will typically be at most $100$ and is known.

Is there an unbiased estimator for the entropy?

Or alternatively,

Is there an estimator with lower variance?

• Note that a low probability event doesn't contribute much to the entropy. If you have something with probability $p=\frac 1{1000}$, then $-p \log p\approx 0.0069$ If you miss it, you don't miss much. – Ross Millikan Dec 12 '13 at 21:09
• @RossMillikan Imagine that Y is actually uniform over $2^n$ values and I do 100 samples all of which are distinct. My entropy estimate would be way way off. – user66307 Dec 12 '13 at 21:30
• Yes, I was taking your question as about missing one (or a few) low probability bins. You are correct that if you miss lots of bins you have a problem. I think then you need more samples-100 samples can't hope to tell you if there are 10,000 or 10,000,000 bins. – Ross Millikan Dec 12 '13 at 21:34
• @RossMillikan It's true that more samples is always better but I also suspect there must be a better estimator than the one I described which is just really dim. – user66307 Dec 13 '13 at 8:48

Estimating entropy is not an easy problem and have been a subject of research for years.

1. There is no unbiased estimator for entropy [Paninski 2003].
2. There are plenty of good entropy estimators that have low bias and/or low variance.

Here's a partial list for the estimators I think are good:

• Paninski. Estimation of Entropy and Mutual Information. Neural Computation, Vol. 15, No. 6. (1 June 2003), pp. 1191-1253
• Vincent Q. Vu, Bin Yu, Robert E. Kass. Coverage-adjusted entropy estimation. Statist. Med., Vol. 26, No. 21. (2007), pp. 4039-4060, doi:10.1002/sim.2942
• Ilya Nemenman, Fariel Shafee, William Bialek. Entropy and inference, revisited PRE (9 Jan 2002)
• Evan Archer, Il Memming Park, Jonathan Pillow. Bayesian Entropy Estimation for Countable Discrete Distributions (arXiv) (Disclaimer: this is my paper)
• Valiant and Valiant. Estimating the Unseen: Improved Estimators for Entropy and other Properties. NIPS 2013 (link)

For uniform distribution, CAE works very well, and also Valiant & Valiant should work well too. A quick and dirty estimator for uniform would be the Ma estimator. And here's my citeulike tag page for entropy estimation, in case you need more papers. :)

EDIT: I made a flowchart! Details in my blog.

• There actually is an unbiased estimator for entropy: arxiv.org/abs/1410.5002 – Lior Oct 20 '17 at 18:40
• But this does not contradict the answer, though, since this estimator works only under the condition that we know that our sample set contains at least one sample from each class. – Lior Oct 20 '17 at 19:05

It seems that I need to give a more detailed answer in the post but not only refer to the references for the main technical ideas. Let me start with a general picture.

Estimating the entropy, from a statistical perspective, is by no means a unique problem among the problems of estimating functionals of parameters. The reason why it has attracted so much attention till now is that it is important in practice, and also we have a rather poor understanding of the general problem of functional estimation. We believe, a complete and satisfactory solution to the entropy estimation should be based on a general methodology for functional estimation.

Let's first consider functional estimation problems in parametric settings. In this setting, it has long been observed that in general we cannot obtain any estimator that satisfies some finite sample optimality criterion (check the book by Lehmann and Cesalla for details), and we need to go to asymptotics, where we fix the parameter, and let the sample size go to infinity. Interesting, in this regime, a very wide class of functional estimation problems are trivial, and the simple MLE plug-in approach is asymptotically efficient [check the book by van der Vaart on asymptotic statistics, chapter 8]. Because of this, the statistics community have shifted its focus to nonparametric settings, i.e., estimating functionals of an infinite dimensional parameter.

The nonparametric functional estimation problem, turns out to be extremely challenging. We have a fairly good understanding of linear functionals (Donoho and Liu'91, Donoho'94, etc), quite good understanding of quadratic and smooth functionals (Bickel and Ritov'88, Birge and Massart'95, etc), but very limited understanding of nonsmooth functionals. One breakthrough in the nonparametric functional estimation literature is the paper by Lepski, Nemirovski, and Spokoiny in 1999 entitled "on estimating the Lr norm of a regression function", in which they showed a general method based on approximation can help construct nearly minimax optimal estimators for a class of functionals. This idea, was later generalized and applied to estimating the $\ell_1$ norm of a Gaussian mean in Cai and Low'11.

Our work (http://arxiv.org/abs/1406.6956) aims to present a general methodology that can help (hopefully) construct minimax optimal estimators for any functionals. The recipe is very easy to describe.

First, let us think, why the entropy estimation problem is hard? You may say that it is because $H(P) = \sum_{i = 1}^S -p_i \ln p_i$, and the function $f(x) = -x \ln x$ is not differentiable at $x = 0$. If you think along this line, you are absolutely right and have captured the essential feature of the entropy functional. The fact that $-x \ln x$ is not quite smooth at $x =0$ implies that, if the true $p$ is small, we had better have a very good estimate of it. When the true $p$ is large, perhaps the MLE of $p$ is already accurate to make it a good estimate for $f(p)$. The solution follows from this idea:

We first compute the empirical distribution. When we find some entry of the empirical distribution is significantly less than $\ln n/n$, which means it appears very few times, we construct a polynomial that approximates the function $f(x) = -x\ln x$ in the interval $[0, \ln n/n]$ as well as possible, and directly estimate this polynomial instead of the original function. When the entries of the empirical distribution are large enough, we simply plug it into the definition of entropy, and do a first order bias correction. This scheme can be applied to any functionals.

In retrospect, this recipe is the precisely the dual of the shrinkage idea originally proposed by Stein'56. In shrinkage, we improve the MLE by introducing bias and significantly reduce the variance. Here, we improve the MLE by introducing variance and significantly reduce the bias. Shrinkage is usually helpful in cases where the variance is the dominating term, and our recipe is usually helpful in cases where the bias if the dominating term.

We support this recipe with strong theoretical guarantees: we show that this recipe achieves the minimax rates for $H(P)$, and $F_\alpha(P) = \sum_{i = 1}^S p_i^\alpha, \alpha>0$, for any $\alpha>0$. It is the first recipe in the literature that can achieve the minimax rates for all these functionals, and we have also shown that the MLE cannot achieve the minimax rates.

We are in fact more ambitious than obtaining the minimax rates: we want something that actually works in practice, and our applied scientists friends can directly apply it in their experiments. In the experiments section of Our work (http://arxiv.org/abs/1406.6956), we have shown that this new estimator for entropy can help reduce the mean squared error significantly, and has linear computational complexity.

There are some other work going on demonstrating its efficacy in various statistical problems, and we hope applied scientists could soon apply these tools to their work and research.

We have something exciting to share: recently we have constructed a new class of estimators for entropy (and actually also for nearly every functional of distributions) that have provable optimal performance guarantees with linear complexity. In particular, our estimator for entropy can also achieve the optimal n/log n scaling achieved by Valiant and Valiant, and ours demonstrate superior empirical performances in various experiments. For details please check the following two papers:

http://arxiv.org/abs/1406.6956

http://arxiv.org/abs/1406.6959

Edit: also, we remark that our estimators are agnostic to the knowledge of the alphabet size, which usually is unknown to the statistician. In fact, existing approaches usually need the knowledge, or at least an upper bound of the alphabet size, and even with these knowledge they generally cannot achieve the optimal n/log n scaling.

• Please try to describe as much here as possible in order to make the answer self-contained. Links are fine as support, but they can go stale and then an answer which is nothing more than a link loses its value. – robjohn Jul 7 '14 at 15:19
• arXiv links going stale? Sooner the SO ones will :) – quant_dev Nov 6 '17 at 22:48
• I agree, it would be great to have a summary of the papers here in the answer. – danijar Feb 5 '18 at 12:38

Given that these two conditions hold, the following is an unbiased estimator of entropy: $$\sum_{i=1}^{M}\frac{I_{N_i\geq2}}{N_i-1}$$ Where $M$ is the number of classes, $N_i$ is the index of the first occurrence of a sample whose class is $i$ (here we assume that the samples are ordered, and that the classes are designated by numbers $1,...,M$), and $I_{\bullet}$ is the identity function that equals $1$ if the condition $\bullet$ holds, and equals $0$ otherwise. The proof can be found in the linked paper.
Note that in principle, this estimator requires you have an unlimited number of samples, so that you can ensure that the second condition holds with probability $1$.