Principle of maximum entropy

The principle of maximum entropy is often used to obtain prior probability distributions for Bayesian inference. Jaynes was a strong advocate of this approach, claiming the maximum entropy distribution represented the least informative distribution.[4] A large amount of literature is now dedicated to the elicitation of maximum entropy priors and links with channel coding.[5][6][7][8]

Maximum entropy is a sufficient updating rule for radical probabilism. Richard Jeffrey's probability kinematics is a special case of maximum entropy inference. However, maximum entropy is not a generalisation of all such sufficient updating rules.[9]

Alternatively, the principle is often invoked for model specification: in this case the observed data itself is assumed to be the testable information. Such models are widely used in natural language processing. An example of such a model is logistic regression, which corresponds to the maximum entropy classifier for independent observations.

One of the main applications of the maximum entropy principle is in discrete and continuous density estimation.[10][11] Similar to support vector machine estimators, the maximum entropy principle may require the solution to a quadratic programming problem, and thus provide a sparse mixture model as the optimal density estimator. One important advantage of the method is its ability to incorporate prior information in the density estimation.[12]

We have some testable information I about a quantity x taking values in {x₁, x₂,..., x_n}. We assume this information has the form of m constraints on the expectations of the functions f_k; that is, we require our probability distribution to satisfy the moment inequality/equality constraints:

${\displaystyle \sum _{i=1}^{n}\Pr(x_{i})f_{k}(x_{i})\geq F_{k}\qquad k=1,\ldots ,m.}$

where the ${\displaystyle F_{k}}$ are observables. We also require the probability density to sum to one, which may be viewed as a primitive constraint on the identity function and an observable equal to 1 giving the constraint

${\displaystyle \sum _{i=1}^{n}\Pr(x_{i})=1.}$

The probability distribution with maximum information entropy subject to these inequality/equality constraints is of the form:[10]

${\displaystyle \Pr(x_{i})={\frac {1}{Z(\lambda _{1},\ldots ,\lambda _{m})}}\exp \left[\lambda _{1}f_{1}(x_{i})+\cdots +\lambda _{m}f_{m}(x_{i})\right],}$

for some ${\displaystyle \lambda _{1},\ldots ,\lambda _{m}}$. It is sometimes called the Gibbs distribution. The normalization constant is determined by:

${\displaystyle Z(\lambda _{1},\ldots ,\lambda _{m})=\sum _{i=1}^{n}\exp \left[\lambda _{1}f_{1}(x_{i})+\cdots +\lambda _{m}f_{m}(x_{i})\right],}$

and is conventionally called the partition function. (The Pitman–Koopman theorem states that the necessary and sufficient condition for a sampling distribution to admit sufficient statistics of bounded dimension is that it have the general form of a maximum entropy distribution.)

The λ_k parameters are Lagrange multipliers. In the case of equality constraints their values are determined from the solution of the nonlinear equations

${\displaystyle F_{k}={\frac {\partial }{\partial \lambda _{k}}}\log Z(\lambda _{1},\ldots ,\lambda _{m}).}$

In the case of inequality constraints, the Lagrange multipliers are determined from the solution of a convex optimization program with linear constraints.[10] In both cases, there is no closed form solution, and the computation of the Lagrange multipliers usually requires numerical methods.

For continuous distributions, the Shannon entropy cannot be used, as it is only defined for discrete probability spaces. Instead Edwin Jaynes (1963, 1968, 2003) gave the following formula, which is closely related to the relative entropy (see also differential entropy).

${\displaystyle H_{c}=-\int p(x)\log {\frac {p(x)}{q(x)}}\,dx}$

where q(x), which Jaynes called the "invariant measure", is proportional to the limiting density of discrete points. For now, we shall assume that q is known; we will discuss it further after the solution equations are given.

A closely related quantity, the relative entropy, is usually defined as the Kullback–Leibler divergence of p from q (although it is sometimes, confusingly, defined as the negative of this). The inference principle of minimizing this, due to Kullback, is known as the Principle of Minimum Discrimination Information.

We have some testable information I about a quantity x which takes values in some interval of the real numbers (all integrals below are over this interval). We assume this information has the form of m constraints on the expectations of the functions f_k, i.e. we require our probability density function to satisfy the inequality (or purely equality) moment constraints:

${\displaystyle \int p(x)f_{k}(x)\,dx\geq F_{k}\qquad k=1,\dotsc ,m.}$

where the ${\displaystyle F_{k}}$ are observables. We also require the probability density to integrate to one, which may be viewed as a primitive constraint on the identity function and an observable equal to 1 giving the constraint

${\displaystyle \int p(x)\,dx=1.}$

The probability density function with maximum H_c subject to these constraints is:[11]

${\displaystyle p(x)={\frac {1}{Z(\lambda _{1},\dotsc ,\lambda _{m})}}q(x)\exp \left[\lambda _{1}f_{1}(x)+\dotsb +\lambda _{m}f_{m}(x)\right]}$

with the partition function determined by

${\displaystyle Z(\lambda _{1},\dotsc ,\lambda _{m})=\int q(x)\exp \left[\lambda _{1}f_{1}(x)+\dotsb +\lambda _{m}f_{m}(x)\right]\,dx.}$

As in the discrete case, in the case where all moment constraints are equalities, the values of the ${\displaystyle \lambda _{k}}$ parameters are determined by the system of nonlinear equations:

${\displaystyle F_{k}={\frac {\partial }{\partial \lambda _{k}}}\log Z(\lambda _{1},\dotsc ,\lambda _{m}).}$

In the case with inequality moment constraints the Lagrange multipliers are determined from the solution of a convex optimization program.[11]

The invariant measure function q(x) can be best understood by supposing that x is known to take values only in the bounded interval (a, b), and that no other information is given. Then the maximum entropy probability density function is

${\displaystyle p(x)=A\cdot q(x),\qquad a<x<b}$

where A is a normalization constant. The invariant measure function is actually the prior density function encoding 'lack of relevant information'. It cannot be determined by the principle of maximum entropy, and must be determined by some other logical method, such as the principle of transformation groups or marginalization theory.

For several examples of maximum entropy distributions, see the article on maximum entropy probability distributions.

Consider a discrete probability distribution among ${\displaystyle m}$ mutually exclusive propositions. The most informative distribution would occur when one of the propositions was known to be true. In that case, the information entropy would be equal to zero. The least informative distribution would occur when there is no reason to favor any one of the propositions over the others. In that case, the only reasonable probability distribution would be uniform, and then the information entropy would be equal to its maximum possible value, ${\displaystyle \log m}$. The information entropy can therefore be seen as a numerical measure which describes how uninformative a particular probability distribution is, ranging from zero (completely informative) to ${\displaystyle \log m}$ (completely uninformative).

By choosing to use the distribution with the maximum entropy allowed by our information, the argument goes, we are choosing the most uninformative distribution possible. To choose a distribution with lower entropy would be to assume information we do not possess. Thus the maximum entropy distribution is the only reasonable distribution. The dependence of the solution on the dominating measure represented by ${\displaystyle m(x)}$ is however a source of criticisms of the approach since this dominating measure is in fact arbitrary.[13]

The following argument is the result of a suggestion made by Graham Wallis to E. T. Jaynes in 1962.[14] It is essentially the same mathematical argument used for the Maxwell–Boltzmann statistics in statistical mechanics, although the conceptual emphasis is quite different. It has the advantage of being strictly combinatorial in nature, making no reference to information entropy as a measure of 'uncertainty', 'uninformativeness', or any other imprecisely defined concept. The information entropy function is not assumed a priori, but rather is found in the course of the argument; and the argument leads naturally to the procedure of maximizing the information entropy, rather than treating it in some other way.

Suppose an individual wishes to make a probability assignment among ${\displaystyle m}$ mutually exclusive propositions. He has some testable information, but is not sure how to go about including this information in his probability assessment. He therefore conceives of the following random experiment. He will distribute ${\displaystyle N}$ quanta of probability (each worth ${\displaystyle 1/N}$) at random among the ${\displaystyle m}$ possibilities. (One might imagine that he will throw ${\displaystyle N}$ balls into ${\displaystyle m}$ buckets while blindfolded. In order to be as fair as possible, each throw is to be independent of any other, and every bucket is to be the same size.) Once the experiment is done, he will check if the probability assignment thus obtained is consistent with his information. (For this step to be successful, the information must be a constraint given by an open set in the space of probability measures). If it is inconsistent, he will reject it and try again. If it is consistent, his assessment will be

${\displaystyle p_{i}={\frac {n_{i}}{N}}}$

where ${\displaystyle p_{i}}$ is the probability of the ${\displaystyle i}$^th proposition, while n_i is the number of quanta that were assigned to the ${\displaystyle i}$^th proposition (i.e. the number of balls that ended up in bucket ${\displaystyle i}$).

Now, in order to reduce the 'graininess' of the probability assignment, it will be necessary to use quite a large number of quanta of probability. Rather than actually carry out, and possibly have to repeat, the rather long random experiment, the protagonist decides to simply calculate and use the most probable result. The probability of any particular result is the multinomial distribution,

${\displaystyle Pr(\mathbf {p} )=W\cdot m^{-N}}$

where

${\displaystyle W={\frac {N!}{n_{1}!\,n_{2}!\,\dotsb \,n_{m}!}}}$

is sometimes known as the multiplicity of the outcome.

The most probable result is the one which maximizes the multiplicity ${\displaystyle W}$. Rather than maximizing ${\displaystyle W}$ directly, the protagonist could equivalently maximize any monotonic increasing function of ${\displaystyle W}$. He decides to maximize

${\displaystyle {\begin{aligned}{\frac {1}{N}}\log W&={\frac {1}{N}}\log {\frac {N!}{n_{1}!\,n_{2}!\,\dotsb \,n_{m}!}}\\[6pt]&={\frac {1}{N}}\log {\frac {N!}{(Np_{1})!\,(Np_{2})!\,\dotsb \,(Np_{m})!}}\\[6pt]&={\frac {1}{N}}\left(\log N!-\sum _{i=1}^{m}\log((Np_{i})!)\right).\end{aligned}}}$

At this point, in order to simplify the expression, the protagonist takes the limit as ${\displaystyle N\to \infty }$, i.e. as the probability levels go from grainy discrete values to smooth continuous values. Using Stirling's approximation, he finds

${\displaystyle {\begin{aligned}\lim _{N\to \infty }\left({\frac {1}{N}}\log W\right)&={\frac {1}{N}}\left(N\log N-\sum _{i=1}^{m}Np_{i}\log(Np_{i})\right)\\[6pt]&=\log N-\sum _{i=1}^{m}p_{i}\log(Np_{i})\\[6pt]&=\log N-\log N\sum _{i=1}^{m}p_{i}-\sum _{i=1}^{m}p_{i}\log p_{i}\\[6pt]&=\left(1-\sum _{i=1}^{m}p_{i}\right)\log N-\sum _{i=1}^{m}p_{i}\log p_{i}\\[6pt]&=-\sum _{i=1}^{m}p_{i}\log p_{i}\\[6pt]&=H(\mathbf {p} ).\end{aligned}}}$

All that remains for the protagonist to do is to maximize entropy under the constraints of his testable information. He has found that the maximum entropy distribution is the most probable of all "fair" random distributions, in the limit as the probability levels go from discrete to continuous.

Giffin and Caticha (2007) state that Bayes' theorem and the principle of maximum entropy are completely compatible and can be seen as special cases of the "method of maximum relative entropy". They state that this method reproduces every aspect of orthodox Bayesian inference methods. In addition this new method opens the door to tackling problems that could not be addressed by either the maximal entropy principle or orthodox Bayesian methods individually. Moreover, recent contributions (Lazar 2003, and Schennach 2005) show that frequentist relative-entropy-based inference approaches (such as empirical likelihood and exponentially tilted empirical likelihood – see e.g. Owen 2001 and Kitamura 2006) can be combined with prior information to perform Bayesian posterior analysis.

Jaynes stated Bayes' theorem was a way to calculate a probability, while maximum entropy was a way to assign a prior probability distribution.[15]

It is however, possible in concept to solve for a posterior distribution directly from a stated prior distribution using the principle of minimum cross-entropy (or the Principle of Maximum Entropy being a special case of using a uniform distribution as the given prior), independently of any Bayesian considerations by treating the problem formally as a constrained optimisation problem, the Entropy functional being the objective function. For the case of given average values as testable information (averaged over the sought after probability distribution), the sought after distribution is formally the Gibbs (or Boltzmann) distribution the parameters of which must be solved for in order to achieve minimum cross entropy and satisfy the given testable information.