When do people actually use the maximum entropy distribution?

Question

One of the standard problems in convex optimization is the calculation of the maximum entropy distribution that satisfies some set of criteria. For example, if $\mathbf{x} \in \mathbb R^n$ is an unknown vector of probabilities, one might solve a problem like $$\mathrm{maximize}_\mathbf{x\geq0} -\sum_{i=1}^n x_i \log x_i ~~~s.t. \\ A\mathbf{x}\leq \mathbf b \\ \sum_{i=1}^n x_i = 1~,$$which would of course find the probability distribution that satisfies a certain set of inequalities whose entropy is as large as possible. My question is: where do people actually use this (maybe not just using inequality constraints, other kinds of constraints would be possible as well of course)? I see problems of this kind arising in textbooks very often, but I don't see research papers in which one really makes use of these distributions to some specific aim.

Answer 1

In finance, finding risk neutral probabilities can be done via max-entropy methods.

In short, you observe prices $p_i$ of a finite number of instruments $\phi_i$, and you seek a probability measure $P$ such that $p_i = \int\phi_i\,\mathrm{d}P$. There is in general no uniqueness of $P$, and finding such a $P$ can be challenging. Finding $P$ by a max-entropy method is one very practical way to do this.

There are quite a lot of papers which do exactly this, to name only two:

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=648

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1968344

Answer 2

Many classically important probability distributions are maximum entropy distributions for suitable constraints, including the normal distribution, exponential distribution, and Poisson distribution. Viewing them as maximum entropy distributions gives a unified viewpoint for why such distributions occur often in practice.

Answer 3

I have found this book a useful reference:

Maximum-entropy Models in Science and Engineering

It may contain some pointers to applied work that you will find convincing (I don't have it on me right now) if you can get a copy.

Answer 4

The physicist E. T. Jaynes recommended using maximum entropy distributions as priors in Bayesian statistics. The most basic example of this is the (highly highly controversial) principle of indifference, which states that if you know nothing about a quantity, you should assume it is uniformly distributed.

A more general and wider-reaching version of the Principle of Indifference is the Principle of Maximum Entropy. (http://en.wikipedia.org/wiki/Principle_of_maximum_entropy)

Answer 5

Thermodynamics can be derived from this principle:

\begin{align*} 0 &\overset!=\delta \Big[\underbrace{-k_B\langle\ln p\rangle}_{S} + \alpha\Big(\langle1\rangle - 1\Big) + \beta\Big(\langle E\rangle - U\Big) + \mu\Big(\langle N\rangle - N\Big)\Big] \\\text{where}\ \langle x\rangle :&= \sum_i p_i x_i \ \text{denotes the expectation value of $x$} \end{align*}

$k_B$ is the Boltzmann constant, which makes the entropy $S$ equivalent to the physical one, while the Lagrangian multiplicators $\beta$ and $\mu$ which conserve (internal) energy and particle count respectively turn out to be equivalent to the thermodynamical quantities $\beta^{-1}=k_B T$ (i.e. $\propto$ inverse temperature) and chemical potential $\mu$.

For the canonical ensemble (i.e. no particle exchange, $N_i\equiv N$) this yields the Boltzmann distribution

$$p_i = \frac{e^{-\beta E_i}}{\sum\limits_j e^{-\beta E_j}}.$$

Answer 6

One way that maximum-entropy distributions (and, more generally, minimum-relative-entropy distributions) arise is as conditional frequency distributions of long sequences of IID random variables. Here's a sketch.

Say you have a sequence of IID random variables $X_1, \ldots, X_N$ taking values in a finite set $S$, with distribution $\vec{p}$. Measuring the frequency of each element of $S$ in this sequence gives a new random variable $\vec{F}$ taking values in the frequency simplex with $|S|$ corners. As $N$ grows, it becomes increasingly likely that $\vec{F}$ will be close to $\vec{p}$; in fact, the probability that $\vec{F}$ falls outside any neighborhood of this point approaches zero. This is the weak law of large numbers.

Suppose you learn that $\vec{F}$ lies in a certain open subset $Q$ of the frequency simplex, and you condition on this knowledge. Where is $\vec{F}$ likely to fall now? As $N$ grows, it becomes increasingly likely that $\vec{F}$ will be close to the points in $\overline{Q}$ that minimize the relative entropy $K(\vec{F}\|\vec{p})$; in fact, the probability that $\vec{F}$ falls outside any neighborhood of these points approaches zero. In other words, as $N$ grows, you become certain that $\vec{F}$ is close to to a minimum-relative-entropy distribution.

---

The result above can be generalized to cover multiple IID sequences, with different distributions, whose sizes are growing at roughly proportional rates. This generalization should have a neat application to random walks, although I haven't checked the details carefully.

Say a random walker departs from the point $a \in \mathbb{R}^n$, taking steps of uniform length along the cardinal directions. Suppose you learn that the walker ends up near point $b$ after $N$ steps, and you condition on this knowledge. Using the aforementioned generalization, you should be able to show that as the number of steps in the walk grows (with the length of each step shrinking proportionally), you become certain that the walker's path is close to the straight, constant-velocity path from $a$ to $b$.

---

The kind of reasoning used here is a baby example of large deviations theory. If you look there, you might find more maximum-entropy-type results.

Answer 7

The current best approximation algorithm for ATSP (the Asymmetric Traveling Salesman Problem) heavily leverages maximum-entropy distributions. The paper may be found here:

http://epubs.siam.org/doi/pdf/10.1137/1.9781611973075.32

A recent paper by Singh and Vishnoi generalizes the approach of the above to that the algorithmic problem of approximate counting (e.g. counting the number of spanning trees in a graph) is in a strong sense equivalent to computing max-entropy distributions.

http://arxiv.org/abs/1304.8108

Answer 8

The Bingham distribution is derived as the maximum entropy distribution on the hypersphere which matches the sample inertia matrix. This distribution have been used in a new algorithm to identify an object's orientation using far fewer data points than previous computer vision algorithms required.