Relative entropy and Kullback–Leibler divergence - Data Science Lecture Notes from Konrad Völkel

Logarithms¶

The elementary properties of the logarithm – definition, change of base, bit and nat – are covered in the digression in the chapter Expected value and variance. Here we are after a different question: why it is the logarithm, of all functions, that turns up in information theory, and nothing else.

Equally clearly, the same lemma holds for $\log_2$ in place of $\ln$ (only the constant is different).

So if we want to count something in such a way that the count of a product is the sum of the individual counts, we have to use a logarithm.

Proof

We want to show that for functions $f,g \colon \mathbb{N}_{>0} \to \mathbb{R}$ satisfying the conditions of the lemma,

f(n) g(2) = f(2) g(n)

(2)

always holds, since with $g = \ln$ this proves the lemma ( $c=f(2)$ ).

Let $n,k,m \in \mathbb{N}$ be such that $2^{m-1} \leq n^k \leq 2^m$ . Monotonicity then gives

f(2^{m-1}) \leq f(n^k) \leq f(2^m)

(3)

and additivity gives

(m-1)f(2) \leq kf(n) \leq mf(2)

(4)

The same chain of inequalities holds for $g$ in place of $f$ ; this one we multiply by -1 as well:

-mg(2) \leq -kg(n) \leq -(m-1)g(2).

(5)

Adding the two chains of inequalities and simplifying gives

-f(2)g(2) \leq k\left(f(n)g(2) - f(2)g(n)\right) \leq f(2)g(2)

(6)

Dividing by $k$ and letting $k \to \infty$ , we see that $f(n)g(2) - f(2)g(n) \to 0$ (as $k \to \infty$ , on which the expression does not depend at all).

We have argued this heuristically before; now we can prove it rigorously:

Definition and properties¶

Example

Relative entropy is not symmetric, and it can become infinite. Let $p_t := (t,\ 1-t)$ for $0 < t < 1$ , a coin that for small $t$ comes up 1 almost surely. In one direction,

H\left(u_2 \,\Vert\, p_t\right) = \frac{1}{2} \log \frac{1}{2t} + \frac{1}{2}\log \frac{1}{2(1-t)} \xrightarrow{t \to 0} \infty,

(11)

since the first summand grows without bound, like $-\frac12\log t$ . In the other direction the proposition above gives

H\left(p_t \,\Vert\, u_2\right) = \log(2) - H(p_t), \qquad H(p_t) = -t\log t - (1-t)\log(1-t) \xrightarrow{t \to 0} 0,

(12)

so $H(p_t \Vert u_2) \to \log 2$ : finite, and to base 2 exactly one bit. Mistake the almost certain coin $p_t$ for a fair one and you pay at most one bit; mistake the fair coin for $p_t$ , and the side you thought impossible will surprise you infinitely.

Joint entropy¶

Proof

Independence means that for all $i,j$ :

P(X = z_i, Y = z_j) = P(X = z_i)\cdot P(Y = z_j)

(16)

We take logarithms:

\log P(X = z_i, Y = z_j) = \log P(X = z_i) + \log P(Y = z_j)

(17)

and so, all in all,

\begin{align} H(X,Y) &:= -\sum_{i=1}^n \sum_{j=1}^n P(X = z_i, Y = z_j) \log P(X = z_i, Y = z_j) \\ &= -\sum_{i=1}^n \sum_{j=1}^n P(X = z_i)P(Y = z_j) \left( \log P(X = z_i) + \log P(Y = z_j) \right) \\ &= -\sum_{i=1}^n \sum_{j=1}^n P(X = z_i)P(Y = z_j)\log P(X = z_i)\\ &\phantom{=}\ \ -\sum_{i=1}^n \sum_{j=1}^n P(X = z_i)P(Y = z_j)\log P(Y = z_j) \\ &= -\sum_{i=1}^n P(X = z_i)\log P(X = z_i)\\ &\phantom{=}\ \ -\sum_{j=1}^n P(Y = z_j)\log P(Y = z_j) \\ &= H(X) + H(Y) \end{align}

(18)

Definition

The mutual information (also transinformation) of two random variables $X,Y$ is defined as

I(X;Y) := H(X)+H(Y)-H(X,Y)= H(X,Y \Vert X\times Y)

(19)

Here $H(\cdot \Vert \cdot)$ stands for the relative entropy of the distribution of $(X,Y)$ with respect to the product distribution $P_X \times P_Y$ , that is, the distribution $(X,Y)$ would have if $X$ and $Y$ were independent.

A very common application of mutual information is in clustering. Suppose we have clustered a dataset by some method of our choice – that is, arrived at an estimated class membership (say 1, 2 or 3 as a label) – and a subset of the data has been classified by hand (for testing). Then we can compute the mutual information of these two class variables to quantify how well the clustering worked on the test data. The advantage is that the concrete labels no longer matter (that is, the method is invariant under permutation of the class names).

The conditional entropy of $X$ given $Y$ is defined as

H(X|Y) := H(X) - I(X;Y)

(20)

Figure 1:Entropy, conditional entropy, joint entropy and mutual information in a Venn diagram. Figure: Wikimedia Commons, user KonradVoelkel (2010, public domain).

A summand with $p_i > 0$ and $r_i = 0$ is $\infty$ here (with $\log 0 = -\infty$ ): an event that is impossible under $r$ but occurs under $p$ comes at infinite cost.

Careful: some authors unfortunately write the cross-entropy as $H(X, Y)$ too, which is easily confused with the joint entropy. And the notation $H(X;Y)$ resembles that of the mutual information $I(X;Y)$ above, which is something else entirely.

If we hold $X$ fixed and vary $Y$ , minimising $H(X;Y)$ and minimising $H(X \Vert Y)$ come to the same thing, which is why machine learning often substitutes one for the other. The maximum likelihood method can be read as minimising a cross-entropy, and hence as minimising a relative entropy. That is how, and why, entropy matters to machine learning.

Otherwise, the cross-entropy is used considerably less often in the theory than the relative entropy (usually called the Kullback–Leibler divergence $D_{KL}$ ).

Continuous entropy¶

One might think that the formula $H(p) = -\sum p_i \log p_i$ generalises to $H(P) = -\int \log P dP$ , but as it stands that makes no sense. What one can do is this:

It already has some of the pleasant properties we would expect of a continuous entropy, translation invariance for instance: $h(X) = h(X - v)$ for a vector $v \in \mathbb{R}^n$ .

Unfortunately the differential entropy is not invariant under arbitrary transformations, not even under isomorphisms.

Jaynes suggested picturing ever finer histograms, that is, a set of $N$ discrete points $\{x_i\}$ . We then write $M(a,b) = \lim_{N \to \infty} \frac{1}{N} (\text{number of } x_i : a < x_i < b)$ and call a density $m$ with $M(a,b) = \int_a^b m(x) dx$ an invariant measure. With that in hand we write

\lim_{N \to \infty} \log(N) - \int p(x) \log \dfrac{p(x)}{m(x)} dx

(26)

but since $\lim_{N \to \infty} \log(N) = \infty$ , we cheekily drop that part and so obtain a quantity that behaves much like $h(x)$ but is scale invariant:

H(X) := - \int p(x) \log \dfrac{p(x)}{m(x)} dx

(27)

The first thing to note is that the “discrete entropy” of a continuous distribution is really $\infty$ . The second is that a workable notion of entropy evidently cannot do without reference to a further distribution (here the “invariant measure”).

A theoretical analysis of what $h(X)$ and $H(X)$ really are leads to the general relative entropy $H(P,Q)$ , with $h(X) = -H(f\lambda \,\Vert\, \lambda)$ , where $\lambda$ is the Lebesgue measure and $f$ a density of $X$ .

We will not pursue that any further either; instead we record that for $P$ and $R$ with density functions $p,r \colon \mathbb{R}^n \to [0,\infty)$ it looks simpler:

H(P \Vert R) = \int_\Omega p(x) \log \frac{p(x)}{r(x)} dx

(29)

This expression, in turn, we may evaluate by Riemann sums (if the density functions are friendly enough). If for instance $n=1$ and $\Omega = \mathbb{R}$ , we can look at

$H(P \Vert R) = \int_{\mathbb{R}} p(x) \log \dfrac{p(x)}{r(x)} dx$ $= \sum_{k = -\infty}^{\infty} \int_{k}^{k+1} p(x) \log \dfrac{p(x)}{r(x)}dx$

and bound each of the integrals on the right by a value, so as to estimate $H(P \Vert R)$ .

H(P \Vert R) \approx \sum_{k = -\infty}^{\infty} p(k) \log \dfrac{p(k)}{r(k)}

(30)

The subdivision into intervals of length 1 can of course be made as fine as we like, making the approximation as accurate as we like. Replacing a continuous distribution by such a discrete one is the analogue of forming a histogram.

If you still doubt that abstract information theory has any relevance to the practical work of data scientists and machine learning engineers, a trip into the Wikipedia page on applications of mutual information and conditional entropy is recommended.