The n-Category Café

As someone who until recently had no clue about entropy, let alone maximizing it, I’d like to share this. It’s a pleasant account of how, if you wanted to model the behaviour of an expert translator of French (e.g. if you wanted to train a machine to do it?), you’d naturally run into the concept of maximum entropy.

As it says, the maximum entropy method is this:

given a collection of facts, choose a model which is consistent with all the facts, but otherwise as uniform as possible.

From notes I see I once knew that there’s a nice geometric interpretation of the distributions that maximise Tsallis entropy here. If you place a uniform distribution on the $n$-sphere of radius $\sqrt{n}$, and project onto $m$ of the co-ordinates, Poincaré had observed that in the limit as $n$ tends to infinity, this $m$-vector is distributed according to an $m$-variate Gaussian distribution with unit covariance matrix. Now these Gaussian distributions are maximisers of the Shannon entropy with this covariance matrix. Some of the Tsallis MaxEnt distributions come from projecting $m$ dimensions from a uniform distribution over an $n$-sphere. You can pick up distributions corresponding to different covariance matrices by looking at uniform distributions over corresponding ellipsoids.

David wrote, challengingly,

If all of the members of that family of entropies he told us about are so interesting […]

If you’re making the sceptical point I think you are, then I probably agree. My belief is that, in some sense, Shannon entropy $H_1$ has prime position among the family $H_\alpha$ ($\alpha \geq 0$) of entropy measures that I discussed. The others are still interesting, but not, I think, as important.

By way of analogy, there are many interesting invariants of topological spaces that can be defined via homology: the rank of the $3$rd homology group, for instance. But in some sense it’s the Euler characteristic that has primacy: it’s the invariant that behaves most like cardinality.

Certainly Shannon entropy has properties not shared by the $\alpha$-entropies $H_\alpha$ for $\alpha \neq 1$. Indeed, Rényi made exactly this point when he introduced $H_\alpha$. In particular, he observed that while $H_\alpha$ shares with $H_1$ the property that the entropy of a product is the sum of the entropies, it does not share the property that the entropy of a convex combination $\lambda \mathbf{p} + (1 - \lambda)\mathbf{q}$ can be expressed in terms of $\lambda$, $H(\mathbf{p})$ and $H(\mathbf{q})$.

In Part 2 (coming soon!), I’ll define $\alpha$-entropy, $\alpha$-diversity and $\alpha$-cardinality of finite probability spaces in which the underlying set is equipped with a metric. Curiously, in this extended setting it’s the case $\alpha = 2$ that seems to be best-understood. But I’m sure $\alpha = 1$ must play a special role.

Continuing David’s sentence:

[…] why is it that so many of our best loved distributions are maximum entropy distributions (under various constraints) for Shannon entropy?

A priori, that doesn’t exclude the possibility that they’re also maximum entropy distributions for other entropies $H_\alpha$.

As I understand it, you’re mostly referring to distributions on the real line, and the task is to find the distribution having maximum entropy subject to certain constraints (e.g. ‘mean must be $0$ and standard deviation must be $1$’). But let’s go back to a much simpler case: distributions on a finite set, subject to no constraints. As we saw in Part 1, the distribution with maximum entropy is the uniform distribution — and that’s true for $\alpha$-entropy, no matter what $\alpha$ is. So in this case, the distribution that maximizes the $\alpha$-entropy is the same for all $\alpha$.

I’ll talk more about maximizing entropy in Part 2. There seem to be some unsolved problems.

The Pareto distribution is equivalent to a q-exponential, that can be obtained by extremising Tsallis entropy.

Regarding David’s last question, this is probably the best answer.

Regarding the observation typically ascribed to Poincare which David mentioned here, the history seems a little murky. I haven’t tried checking original sources myself, but this paper, which proves a stronger version of the statement, claims that it can’t be found in Poincare’s writings.

Here’s a guess.

Shannon entropy can be derived as the limit of a distribution’s multiplicity as the elements increase to infinity.

http://en.wikipedia.org/wiki/Maximum_entropy#The_Wallis_derivation

Out of all the distributions you are choosing one that can exist in the most number of ways given the constraints. Its like the mean of all possible distributions.

To understand what the other distributions are maximizing exactly one should look at their discrete forms before the limit is taken.

A paper on Maximum Entropy on Compact Groups.

On a compact group the Haar probability measure plays the role as uniform distribution. The entropy and rate distortion theory for this uniform distribution is studied. New results and simplified proofs on convergence of convolutions on compact groups are presented and they can be formulated as entropy increases to its maximum. Information theoretic techniques and Markov chains play a crucial role. The rate of convergence is shown to be exponential. The results are also formulated via rate distortion functions.