Estimating the entropy

Question

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?

Answer 1

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.

Answer 2

This answer does not contradict Memming's answer, but but I think it is worth mentioning:

There is a unbiased estimator for entropy, as discussed in this paper. But for the estimator to work, two conditions must hold:

1. You must know the number of classes(=values) the random variable can have. (The number of classes must be finite).
2. Your set of samples must contain at least one sample of each class.

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$.

EDIT: I guess the right property of this estimator would be "consistent" rather than "unbiased", since it requires infinitely many samples.