18
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ I am amazed that nobody noticed the wrong sign. The entropy is $-\sum x_i\log x_i$. As a matter of fact, one usually maximize concave functions and minimize convex functions, and $x\mapsto x\log x$ is convex. $\endgroup$ – Denis Serre Dec 1 '14 at 6:05
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Although don't they try to minimize entropy? With the understanding that finding a low entropy Radon-Nikodym derivative is equivalent to finding a martingale measure that deviates as little as possible from the physical probability measure. $\endgroup$ – weakstar Nov 23 '15 at 20:25
  • 1
    $\begingroup$ @weakstar: One either maximizes the entropy, or minimizes the Kullback-Leibler divergence. The former is the opposite of the latter. $\endgroup$ – Alexandre C. Nov 23 '15 at 20:42
18
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Since the Boltzmann constant was mentioned here, I feel compelled to mention that this number is not a physical constant, but rather a unit conversion factor. When temperature was first discovered, people didn't realize that it had units of inverse energy, so they made up a new unit for it. As a result, many expressions in statistical mechanics are traditionally written with some variables in units of temperature and others in units of energy, and we have to use a conversion factor to translate between them. $\endgroup$ – Vectornaut Dec 3 '14 at 4:47
  • 1
    $\begingroup$ @Vectornaut Excellent point, that's why I prefer natural units :-) $\endgroup$ – Tobias Kienzler Dec 3 '14 at 5:50
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.