25
$\begingroup$

Given two probability distributions $p,q$ on a finite set $X$, the quantity variously known as relative information, relative entropy, information gain or Kullback–Leibler divergence is defined to be

$$ D_{KL}(p\|q) = \sum_{i \in X} p_i \ln\left(\frac{p_i}{q_i}\right) $$

This is a natural generalization of the Shannon information of a single probability measure.

I wrote a paper with Tobias Fritz giving a category-theoretic characterization of this quantity:

Belatedly I'm wondering what other characterizations are known. On Wikipedia I read:

Arthur Hobson proved that the Kullback–Leibler divergence is the only measure of difference between probability distributions that satisfies some desiderata, which are the canonical extension to those appearing in a commonly used characterization of entropy.

Unfortunately they don't give these desiderata, and there are lots of different characterizations of entropy, so I don't know which one is meant here. I also don't have quick access to Hobson's book:

  • Arthur Hobson, Concepts in Statistical Mechanics, Gordon and Breach, New York, 1971.

Wikipedia also gives a characterization in terms of coding theory:

The Kullback–Leibler divergence can be interpreted as the expected extra message-length per datum that must be communicated if a code that is optimal for a given (wrong) distribution $q$ is used, compared to using a code based on the true distribution $p$.

This is made precise in Theorem 5.4.3 here:

  • T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd Edition, Wiley-Interscience, New York, 2006.

What other characterizations of relative entropy are known?

$\endgroup$
12
$\begingroup$

Maximum likelihood Estimation:

Let $X_1,\dots,X_n$ be independently and identically distributed observations from a distribution modeled by the parametric family $\mathcal{F} = \{P_{\theta}:\theta\in\Theta\}$. Let us suppose that all the distributions in $\mathcal{F}$ have a common finite support set $\mathcal{X}$. The maximum likelihood estimation (MLE) corresponds to the probability distribution $P_{\theta}$ which maximizes $\small\prod_{i=1}^n P_{\theta}(X_i)$. Let $\hat{P}$ be the empirical distribution of the observations. Then \begin{eqnarray} \small\frac{\prod_{i=1}^n P_{\theta}(X_i)}{\prod_{i=1}^n \hat P(X_i)} & = & \small\prod_{x\in\mathcal{X}} \Big(\frac{P_{\theta}(x)}{\hat P(x)}\Big)^{n\hat P(x)}\\ & = & \small \exp\Big\{n\sum\limits_{x\in\mathcal{X}}\hat P(x)\log\Big(\frac{P_{\theta}(x)}{\hat P(x)}\Big)\Big\}\\ & = & \small\exp\{-nD(\hat P\|P_{\theta})\}. \end{eqnarray}

Thus maximizing $\small\prod_{i=1}^n P_{\theta}(X_i)$ is same as minimizing $\small D(\hat P\|P_{\theta})$.

Source: I. Csiszar and P. C. Shields, “Information Theory and Statistics: A Tutorial.

$\endgroup$
10
$\begingroup$

One related result is the Chernoff characterization of the best achievable exponent in Bayesian hypothesis testing. Given $X_1,\ldots,X_n$ i.i.d., ($X_k \in {\cal X}$, which is a finite set, for $k=1,\ldots,n$) from the distribution $\mathbb{Q}$ and two hypotheses $$H_k:\mathbb{Q}=\mathbb{P}_k$$ with $k=1,2$ and prior probabilities $\pi_k,$ the overall probability of error is $$P_e^{(n)}=\pi_1 \alpha_n + \pi_2 \beta_n$$ where $\alpha_n$ (resp. $\beta_n$) is the error conditional on $H_1$ (resp. $H_2$) being true when the $n$ measurements above are used. Let $A_n$ be the region where the decision $H_1$ is 'true' is made. Then $$\lim_{n\rightarrow \infty} \min_{A_n \in {\cal X}^n} -\frac{1}{n}P_e^{(n)}=D^{\ast} $$ where $$P_{\lambda}=\frac{P_1^{\lambda}(x) P_2^{1-\lambda}(x)}{\sum_{a \in {\cal X}} P_1^{\lambda}(a) P_2^{1-\lambda}(a)}$$ and $\lambda^{\ast}$ is the value of $\lambda$ given by $$D(P_{\lambda^{\ast}}||P_1)=D(P_{\lambda^{\ast}}||P_1).$$

There is also a data compression (rate distortion) version of your statement regarding the penalty in expected codeword length when the wrong statistics are used to derive the compression code.

$\endgroup$
6
$\begingroup$

The relative entropy is frequently framed as the inverse temperature times the difference between the Helmholtz and variational/Bethe free energies, the latter of which is minimized as a proxy objective function in mean field theory and Bayesian estimation via the well-known expectation maximization algorithm. MacKay's book is a good reference for this.

$\endgroup$
5
$\begingroup$

I don't have Hobson's book, but I do have a paper by Hobson in which he proves the theorem that Wikipedia is presumably referring to:

Arthur Hobson, A new theorem in information theory. Journal of Statistical Physics 1 (1969), 383-391.

(What a title. Long gone are the days when you could get away with that!)

Here's Hobson's theorem. Let $I(p; q)$ be defined for any pair of probability distributions $p, q$ on a finite set. Suppose it satisfies the properties below. Then $I$ is a constant multiple of relative entropy.

Before I list the properties, let me make a comment: the phrasing "let ... be defined" is his. He's not precise about the codomain of the function $I$. I see no mention of the fact that relative entropy can be infinite, and it may be tacitly assumed that $I(p; q)$ is always nonnegative.

His properties:

  • $I$ is a continuous function of its $2n$ variables. (Again, I don't know how/whether he handles infinities. As John and Tobias make clear in their paper, continuity as relative entropy tends to $\infty$ is actually a tricky point.)

  • $I$ is permutation-invariant (doing the same permutation to both arguments). Actually, he only states invariance under a single transposition, but obviously that's equivalent.

  • $I(p; p) = 0$ for all $p$.

  • $I((1/m, \ldots, 1/m, 0, \ldots, 0); (1/n, \ldots, 1/n))$ is an increasing function of $n$ and a decreasing function of $m$, for all $n \geq m \geq 1$. (I don't know whether he means increasing and decreasing in the strict or weak sense.)

  • We have \begin{align*} & I((p_1, \ldots, p_m, p_{m + 1}, \ldots, p_n); (q_1, \ldots, q_m, q_{m + 1}, \ldots, q_n)) \\ & = I((P, P'); (Q; Q')) + P\cdot I((p_1/P, \ldots, p_m/P); (q_1/Q, \ldots, q_m/Q))\\ & \quad + P'\cdot I((p_{m + 1}/P', \ldots, p_n/P'); (q_{m + 1}/Q', \ldots, q_n/Q')) \end{align*} for all probability distributions $p$ and $q$ and all $m \in \{1, \ldots, n\}$, where we have put $P = p_1 + \cdots + p_m$, $P' = 1 - P$, $Q = q_1 + \cdots + q_m$, and $Q' = 1 - Q$. (Although he divides by $P$, $P'$, $Q$ and $Q'$ here, he doesn't seem to say what to do if they're zero.)

This theorem is weaker than the result in my earlier answer. In that other answer, his continuity axiom is replaced by measurability, the permutation-invariance and vanishing axioms are the same, and his fourth axiom (about increasing/decreasing) just isn't there. The last axioms in both lists look different, but are actually equivalent. This takes a bit of explanation, as follows.

As usul points out, most theorems characterizing entropies involve one axiom looking like these ones. In fact, both Hobson's last axiom and the last axiom in my earlier answer are special cases of the following general axiom, which I'm told is known as the "chain rule".

To state it, let me introduce some notation. Given probability distributions $\mathbf{w}$ on $n$ elements, $\mathbf{p}^1$ on $k_1$ elements, ..., $\mathbf{p}^n$ on $k_n$ elements, we get a distribution $$ \mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) = (w_1 p^1_1, \ldots, w_1 p^1_{k_1}, \ \ldots, \ w_n p^n_1, \ldots, w_n p^n_{k_n}) $$ on $k_1 + \cdots + k_n$. Using that notation, the chain rule for relative entropy states that $$ D\bigl(\mathbf{w} \circ (\mathbf{p}^1, \ldots, \mathbf{p}^n) \,\|\, \tilde{\mathbf{w}} \circ (\tilde{\mathbf{p}}^1, \ldots, \tilde{\mathbf{p}}^n)\bigr) = D(\mathbf{w} \,\|\, \tilde{\mathbf{w}}) + \sum_{i = 1}^n p_i D(\mathbf{p}^i \,\|\, \tilde{\mathbf{p}}^i). $$ It's easy to see that both Hobson's last axiom and the last axiom in my earlier answer are special cases of this general rule. But by simple inductive arguments, either one of these special cases implies the general case. That's why I say they're equivalent.

Whether you find the general case or one of the special cases more appealing is a matter of taste.

$\endgroup$
  • $\begingroup$ Thanks for reviving this thread (which I'd completely forgotten) and pushing it forward. $\endgroup$ – John Baez Mar 21 '17 at 4:53
5
$\begingroup$

Let $A_n$ be the set of pairs $(p, q)$ of probability distributions on $\{1, \ldots, n\}$ such that $q_i = 0 \implies p_i = 0$. (This is exactly the condition needed to guarantee that $D(p\|q) < \infty$.)

Theorem Let $(I: A_n \to [0, \infty))_{n \geq 1}$ be a sequence of functions. Then $I$ is a scalar multiple of relative information if and only if:

  • the functions $I$ are measurable;
  • the functions $I$ are permutation-invariant (that is, $I(p\sigma\|q\sigma) = I(p\|q)$ for all $\sigma \in S_n$);
  • $I(p\|p) = 0$ for all $p$;
  • we have $$ \begin{align*} & I\bigl(tp_1, (1 - t)p_2, p_3, \ldots, p_n \,\|\, uq_1, (1 - u)q_2, q_3, \ldots, q_n)\bigr)\\ & = I(p\|q) + p_1 I\bigl((t, 1 - t)\,\|\,(u, 1 - u)\bigr) \end{align*} $$ for all distributions $p, q$ and all $t, u \in [0, 1]$ such that $((t, 1 - t), (u, 1 - u)) \in A_2$.

I don't know who first stated or proved this theorem. I found it myself (inspired by John and Tobias's paper), and wrote about it here. But it seems unlikely that it's new. It could have been found any time since the 1950s, and probably has been. The literature search is made difficult by the fact that relative information is studied in multiple disciplines (mathematics, physics, engineering, statistics, ...) and goes by many names.

Edit (months later) Something very similar to this result was implicitly proved by Kannappan and Ng in 1972. I just wrote up a shorter proof as arXiv:1712.04903, and the history is discussed in Remark 2.7 there. This remark includes a summary of the theorem of Hobson that John originally asked about.

$\endgroup$
4
$\begingroup$

I just want to make a point (and apologies if this seems already clear or obvious) that many such characterizations wil have a simple feature in common: a form of additivity axiom.

This goes right back to Shannon's 1948 characterization of entropy (and is common to any number of subsequent variations). You start with some very weak conditions, such as continuity and symmetry, which give a very general class of possible entropy functions. Then you add one additional condition: If you have two possibly-correlated variables such as $X$ and a $\lambda$-weighted coin flip, then

$$ H(X,\text{flip}) = H(\lambda) + \lambda H(X|\text{heads}) + (1-\lambda) H(X|\text{tails}) \qquad (*) $$

and you recover Shannon entropy as the unique satisficer. Here $H(X|\text{heads})$ is the entropy of the distribution of $X$ conditioned on the coin coming up heads, etc.

OK, we are discussing relative entropy rather than entropy, but I don't think the distinction is so important since one is usually defined using the other. For example, if your entropy function is any symmetric concave functions of probability distributions (these satisfy some nice properties), define relative entropy to be the Bregman divergence of the negative of these functions. In the case of Shannon entropy, of course this gives KL-divergence. So the distinction between characterizing the entropy function itself and the relative entropy does not seem so conceptually large to me.

So for example:

  • The paper originally mentioned (Baez and Fritz) includes this kind of condition:

    Intuitively, this means that if we flip a probability-λ coin to decide whether to perform one measurement process or another, the expected information gained is λ times the expected information gain of the first process plus (1−λ) times the expected information gain of the second.

  • In Tom's recent answer, additivity is the key final axiom.

  • The MLE approach used in e.g. Ashok's answer is relying on additivity to turn a product into the exponential of a sum. But that's a nice, relatively separate characterization. I think there's a related discussion involving (generalized) exponential family distributions, where this additivity condition should single out KL-divergence, but enough for one post.

Footnote. To me, the wikipedia characterization mentioned in the question (cf Cover and Thomas 5.4.3) is not saying much: the same statement will be true for a generalized entropy and corresponding generalized relative entropy as mentioned above. This actually can be interpreted as a statement about proper scoring rules, where if the scoring rule is derived from a convex "generalized entropy" function $g$, then the average penalty for an incorrect guess is the "generalized relative entropy", i.e. the Bregman divergence.

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