12
$\begingroup$

For a discrete probability distribution, the entropy is defined as: $$H(p) = \sum_i p(x_i) \log(p(x_i))$$ I'm trying to use the entropy as a measure of how "flat / noisy" vs. "peaked" a distribution is, where smaller entropy corresponds to more "peakedness". I want to use a cutoff threshold to decide which distributions are "peaked" and which are "flat". The problem with this approach is that for "same shaped" distributions, the entropy is different for different sample sizes! as a simple example take the uniform distribution - it's entropy is: $$p_i = \frac{1}{n}\ \ \to \ \ H = \log n$$ To make things worse, there doesn't seem to be a general rule for more complex distributions.

So, the question is:

How should I normalize the entropy so that I get the same "scaled entropy" for "same" distributions irrespective of the sample size?

$\endgroup$
  • 3
    $\begingroup$ If I may give a tip that does not directly help with your question: you should consider using Rényi entropies of which Shannon entropy is just a special case. It gives a more refined reflection of distributions. It's like the Fourier analysis for fractals. $\endgroup$ – Raskolnikov May 18 '13 at 2:37
  • $\begingroup$ @Raskolnikov - that is very interesting! Unfortunately, one would still run into scaling problems for any of the Rényi entropies. $\endgroup$ – nbubis May 18 '13 at 2:40
12
$\begingroup$

Use the normalized entropy:

$$H_n(p) = -\sum_i \frac{p_i \log_b p_i}{\log_b n}.$$

For a vector $p_i = \frac{1}{n}\ \ \forall \ \ i = 1,...,n$, the Shannon entropy is maximized. Normalizing the entropy by $\log_b n$ gives $H_n(p) \in [0, 1]$. You will see that this is simply a change of base, so one may drop the normalization term and set $b = n$. You can read more about normalized entropy here and here.

$\endgroup$
  • $\begingroup$ Thank you! I'll read up about efficiency. $\endgroup$ – nbubis Sep 25 '14 at 12:13
  • $\begingroup$ @nbubis, I came across this information trying to solve a similar problem as you posed. However, I'm not able to find more on "efficiency" other than the link I posted. However, I did find more results on normalized entropy. $\endgroup$ – a Data Head Sep 25 '14 at 15:06
5
$\begingroup$

A partial answer for further reference:

In short, use the integral formulation of the entropy and pretend that the discrete distribution is sampling a continuous one.

Thus, create a continuous distribution $p(x)$ whose integral is approximated by the Riemann sum of the $p_i$'s: $$\int_0^1 p(x)dx \sim \sum_i p_i\cdot \frac{1}{N} = 1$$ This means that the $p_i$'s must first be normalized so that $\sum_i p_i = N$.

After normalization, we calculate the entropy: $$H=-\int_0^1 p(x)\log\left(p(x)\right)dx \sim -\sum_i p_i \log(p_i)\cdot \frac{1}{N}$$

As $N\to \infty$ this gives an entropy which is solely related to the distribution shape and does not depend on $N$. For small $N$, the difference will depend on how good the Riemann sum approximates the integrals for given $N$.

$\endgroup$
  • 2
    $\begingroup$ Great thought there. I wish I had thought of that. $\endgroup$ – Raskolnikov May 20 '13 at 21:54
  • 1
    $\begingroup$ This gives $H=0$ for a uniform distribution, and you were looking for a measure of flatness. No ? $\endgroup$ – Stéphane Laurent May 31 '13 at 20:55
  • $\begingroup$ @StéphaneLaurent - yes it does, but peaked distributions will still have lower entropies $H < 0$ $\endgroup$ – nbubis May 31 '13 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.