Estimate entropy, based upon observed frequency counts

Question

Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution. I can count the frequency $f_s$ of each symbol $s \in \Sigma$ among the observations; how should I use them to estimate the Shannon entropy of the source?

---

The obvious approach is to estimate the probability of each symbol $s$ as $\Pr[X=s]=f_s/n$, and then calculate the entropy using the standard formula for Shannon entropy. This leads to the following estimate of the entropy $H(X)$:

$$\text{estimate}(H(X)) = - \sum_{s \in \Sigma} {f_s \over n} \lg (f_s/n).$$

However, this feels like it might not produce the best estimate. Consider, by analogy, the problem of estimating the probability of symbol $s$ based upon its frequency $f_s$. The naive estimate $f_s/n$ is likely an underestimate of its probability. For instance, if I make 100 observations of birds in my back yard and none of them were a hummingbird, should my best estimate of the probability of seeing a hummingbird on my next observation be exactly 0? No, instead, it's probably more realistic to estimate the probability is something small but not zero. (A zero estimate means that a hummingbird is absolutely impossible, which seems unlikely.)

For the problem of estimating the probability of symbol $s$, there are a number of standard techniques for addressing this problem. Additive smoothing (aka Laplace smoothing) is one standard technique, where we estimate the probability of symbol $s$ as $\Pr[X=s] = (f_s + 1)/(n+|\Sigma|)$. Others have proposed Bayesian smoothing or other methods. These methods are widely used in natural language processing and document analysis, where just because a word never appears in your document set doesn't mean that the word has probability zero. In natural language processing, this also goes by the name smoothing.

So, taking these considerations into account, how should I estimate the entropy, based upon observed frequency counts? Should I apply additive smoothing to get an estimate of each of the probabilities $\Pr[X=s]$, then use the standard formula for Shannon entropy with those probabilities? Or is there a better method that should be used for this specific problem?

Answer 1

Like most things of this nature the best method is best found by empirical evaluation. One thing worth noting is that most smoothing schemes can be thought of as the incorporation of a prior into your likelihood estimate. For example if you are trying to estimate the parameter $\theta$ of a binary random variable $X$ and you have data $\mathcal{D} = \{x_1, \ldots, x_n\}$ consisting of i.i.d. realizations of $X$ then your posterior takes the form

$$ \begin{align*} P(\theta|\mathcal{D}) &\varpropto P(\theta)P(\mathcal{D}|\theta)\\ \end{align*} $$ Assuming $P(\theta) = B(\alpha,\beta)^{-1}\theta^{\alpha-1}(1-\theta)^{\beta-1}$, i.e., a Beta distribution and letting $n_1 = |\{x_i \in \mathcal{D} \colon x_i = 1\}|$ then we have

$$ \begin{align*} P(\theta|\mathcal{D}) &\varpropto \theta^{\alpha-1}(1-\theta)^{\beta-1} \theta^{n_1}(1-\theta)^{n - n_1}\\ &= \theta^{n_1 + \alpha - 1}(1- \theta)^{n - n_1 + \beta - 1}. \end{align*} $$ Notice the effect of the hyperparameters ($\alpha$ and $\beta$) is essentially to just add some constant to your counts of each possible outcome. So additive smoothing (at least all applications I've encountered) is really just a special case of Bayesian estimation.

Answer 2

This is an old but very nice question.

Since the expectation of any estimate from i.i.d. samples is a polynomial function of class probabilities, unbiased estimators of entropy do not exist, entropy being non-polynomial. There are bias corrections used for a maximum likelihood entropy estimator, but such an estimator is very sensitive to the small values of probabilities $\log(1/p_i)$ being large when $p_i$ is small.

Batu et al: The Complexity of Approximating the Entropy, SIAM Journal on Computing, 35(1):132-150, 2005m, available here consider this problem.

Furthermore, it is impossible to have an algorithm which outputs an estimate of the entropy with a multiplicative guarantee $\gamma,$ i.e., such that the estimate is in $(\gamma^{-1}H_0,\gamma H_0)$ with probability $\geq 3/4,$ where $H_0$ is the true value of the entropy. This can be seen by considering the two distributions $$ (1,0,\ldots,0) $$ and $$ (1-\delta,\delta,0,\ldots,0) $$ on the same domain, since one has entropy zero and the other strictly bigger than zero.

This question falls under what the authors call the generation oracle model. In that case, the main result is the following:

Fix $\eta>0,$ to be arbitrarily small. If a distribution on $\{1,2,\ldots, n\}$ has entropy $\Omega(\gamma/\eta),$ then a $\gamma-$multiplicative approximation to the entropy can be obtained in time $$O(n^{(1+\eta)/\gamma^2}\log n).$$

For the same class of distributions, the authors prove the following lower bound on time complexity of a $\gamma-$multiplicative algorithm:$$O(n^{1/(2\gamma^2)}).$$

For monotone and flat distributions (on a subset) they obtain better results.