Jdtcujk

In mathematical statistics, the Kullback–Leibler divergence (also called relative entropy) is a measure of how one probability distribution is different from a second, reference probability distribution.^[1]^[2] Applications include characterizing the relative (Shannon) entropy in information systems, randomness in continuous time-series, and information gain when comparing statistical models of inference. In contrast to variation of information, it is a distribution-wise asymmetric measure and thus does not qualify as a statistical metric of spread. In the simple case, a Kullback–Leibler divergence of 0 indicates that the two distributions in question are identical. In simplified terms, it is a measure of surprise, with diverse applications such as applied statistics, fluid mechanics, neuroscience and machine learning.

Etymology

The Kullback–Leibler divergence was introduced by Solomon Kullback and Richard Leibler in 1951 as the directed divergence between two distributions; Kullback preferred the term discrimination information.^[3] The divergence is discussed in Kullback's 1959 book, Information Theory and Statistics.^[2]

Definition

For discrete probability distributions $P$ and $Q$ defined on the same probability space, the Kullback–Leibler divergence between $P$ and $Q$ is defined^[4] to be

${displaystyle D_{text{KL}}(Pparallel Q)=-sum _{xin {mathcal {X}}}P(x)log left({frac {Q(x)}{P(x)}}right)}$

(Eq.1)

which is equivalent to

{displaystyle D_{text{KL}}(Pparallel Q)=sum _{xin {mathcal {X}}}P(x)log left({frac {P(x)}{Q(x)}}right).}

In other words, it is the expectation of the logarithmic difference between the probabilities $P$ and $Q$ , where the expectation is taken using the probabilities $P$ . The Kullback–Leibler divergence is defined only if for all $x$ , $Q(x)=0$ implies $P(x)=0$ (absolute continuity). Whenever $P(x)$ is zero the contribution of the corresponding term is interpreted as zero because

{displaystyle lim _{xto 0^{+}}xlog(x)=0}

.

For distributions $P$ and $Q$ of a continuous random variable, the Kullback–Leibler divergence is defined to be the integral:^[5]^{:p. 55}

${displaystyle D_{text{KL}}(Pparallel Q)=int _{-infty }^{infty }p(x)log left({frac {p(x)}{q(x)}}right),dx}$

(Eq.2)

where $p$ and $q$ denote the probability densities of $P$ and $Q$ .

More generally, if $P$ and $Q$ are probability measures over a set ${mathcal{X}}$ , and $P$ is absolutely continuous with respect to $Q$ , then the Kullback–Leibler divergence from $Q$ to $P$ is defined as

{displaystyle D_{text{KL}}(Pparallel Q)=int _{mathcal {X}}log left({frac {dP}{dQ}}right),dP,}

where ${displaystyle {frac {dP}{dQ}}}$ is the Radon–Nikodym derivative of $P$ with respect to $Q$ , and provided the expression on the right-hand side exists. Equivalently (by the chain rule), this can be written as

{displaystyle D_{text{KL}}(Pparallel Q)=int _{mathcal {X}}log left({frac {dP}{dQ}}right){frac {dP}{dQ}},dQ,}

which is the entropy of $P$ relative to $Q$ . Continuing in this case, if $mu$ is any measure on ${mathcal {X}}$ for which ${displaystyle p={frac {dP}{dmu }}}$ and ${displaystyle q={frac {dQ}{dmu }}}$ exist (meaning that $p$ and $q$ are absolutely continuous with respect to $mu$ ), then the Kullback–Leibler divergence from $Q$ to $P$ is given as

{displaystyle D_{text{KL}}(Pparallel Q)=int _{mathcal {X}}plog left({frac {p}{q}}right),dmu .}

The logarithms in these formulae are taken to base 2 if information is measured in units of bits, or to base $e$ if information is measured in nats. Most formulas involving the Kullback–Leibler divergence hold regardless of the base of the logarithm.

Various conventions exist for referring to ${displaystyle D_{text{KL}}(Pparallel Q)}$ in words. Often it is referred to as the divergence between $P$ and $Q$ ; however this fails to convey the fundamental asymmetry in the relation. Sometimes, as in this article, it may be found described as the divergence of $P$ from, or with respect to $Q$ . This reflects the asymmetry in Bayesian inference, which starts from a prior $Q$ and updates to the posterior $P$ .

Basic example

Kullback^[2] gives the following example (Table 2.1, Example 2.1). Let $P$ and $Q$ be the distributions shown in the table and figure. $P$ is the distribution on the left side of the figure, a binomial distribution with $N=2$ and ${displaystyle p=0.4}$ . $Q$ is the distribution on the right side of the figure, a discrete uniform distribution with the three possible outcomes $x=0$ , $1$ , or $2$ (i.e. ${displaystyle {mathcal {X}}={0,1,2}}$ ), each with probability $p=1/3$ .

x	0	1	2
Distribution P(x)	0.36	0.48	0.16
Distribution Q(x)	0.333	0.333	0.333

The KL divergence is calculated using the definition Eq.1 as follows. This example uses the natural log with base e, designated ${displaystyle operatorname {ln} }$ .

{displaystyle {begin{aligned}D_{text{KL}}(Qparallel P)&=sum _{xin {mathcal {X}}}Q(x)ln left({frac {P(x)}{Q(x)}}right)\[6pt]&=0.333ln left({frac {0.333}{0.36}}right)+0.333ln left({frac {0.333}{0.48}}right)+0.333ln left({frac {0.333}{0.16}}right)\[6pt]&=-0.02596+(-0.12176)+0.24408\[6pt]&=0.09637end{aligned}}}

nats (see units of information).

Interpretations

The Kullback–Leibler divergence from $Q$ to $P$ is often denoted ${displaystyle D_{text{KL}}(Pparallel Q)}$ .

In the context of machine learning, ${displaystyle D_{text{KL}}(Pparallel Q)}$ is often called the information gain achieved if $Q$ is used instead of $P$ . By analogy with information theory, it is also called the relative entropy of $P$ with respect to $Q$ . In the context of coding theory, ${displaystyle D_{text{KL}}(Pparallel Q)}$ can be construed as measuring the expected number of extra bits required to code samples from $P$ using a code optimized for $Q$ rather than the code optimized for $P$ .

Expressed in the language of Bayesian inference, ${displaystyle D_{text{KL}}(Pparallel Q)}$ is a measure of the information gained when one revises one's beliefs from the prior probability distribution $Q$ to the posterior probability distribution $P$ . In other words, it is the amount of information lost when $Q$ is used to approximate $P$ .^[6] In applications, $P$ typically represents the "true" distribution of data, observations, or a precisely calculated theoretical distribution, while $Q$ typically represents a theory, model, description, or approximation of $P$ . In order to find a distribution $Q$ that is closest to $P$ , we can minimize KL divergence and compute an information projection.

The Kullback–Leibler divergence is a special case of a broader class of divergences called f-divergences as well as the class of Bregman divergences. It is the only such divergence over probabilities that is a member of both classes. Although it is often intuited as a way of measuring the distance between probability distributions, the Kullback–Leibler divergence is not a true metric. It does not obey the triangle inequality, and in general ${displaystyle D_{text{KL}}(Pparallel Q)}$ does not equal ${displaystyle D_{text{KL}}(Qparallel P)}$ . However, its infinitesimal form, specifically its Hessian, gives a metric tensor known as the Fisher information metric.

Characterization

Arthur Hobson proved that the Kullback–Leibler divergence is the only measure of difference between probability distributions that satisfies some desired properties, which are the canonical extension to those appearing in a commonly used characterization of entropy.^[7] Consequently, mutual information is the only measure of mutual dependence that obeys certain related conditions, since it can be defined in terms of Kullback–Leibler divergence.

There is also a Bayesian characterization of the Kullback–Leibler divergence.^[8]

Motivation

Illustration of the Kullback–Leibler (KL) divergence for two normal distributions. The typical asymmetry for the Kullback–Leibler divergence is clearly visible.

In information theory, the Kraft–McMillan theorem establishes that any directly decodable coding scheme for coding a message to identify one value $x_{i}$ out of a set of possibilities $X$ can be seen as representing an implicit probability distribution $q(x_{i})=2^{-l_{i}}$ over $X$ , where $l_{i}$ is the length of the code for $x_{i}$ in bits. Therefore, 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$ .

{displaystyle {begin{aligned}D_{text{KL}}(Pparallel Q)&=-sum _{xin {mathcal {X}}}p(x)log q(x)+sum _{xin {mathcal {X}}}p(x)log p(x)\&=mathrm {H} (P,Q)-mathrm {H} (P)end{aligned}}}

where ${displaystyle mathrm {H} (P,Q)}$ is the cross entropy of $P$ and $Q$ , and ${displaystyle mathrm {H} (P)}$ is the entropy of $P$ .

Note also that there is a relation between the Kullback–Leibler divergence and the "rate function" in the theory of large deviations.^[9]^[10]

Properties

The Kullback–Leibler divergence is always non-negative,

{displaystyle D_{text{KL}}(Pparallel Q)geq 0,}

a result known as Gibbs' inequality, with

{displaystyle D_{text{KL}}(Pparallel Q)}

zero if and only if

P=Q

almost everywhere. The entropy

{displaystyle mathrm {H} (P)}

thus sets a minimum value for the cross-entropy

{displaystyle mathrm {H} (P,Q)}

, the expected number of bits required when using a code based on

Q

rather than

P

; and the Kullback–Leibler divergence therefore represents the expected number of extra bits that must be transmitted to identify a value

x

drawn from

X

, if a code is used corresponding to the probability distribution

Q

, rather than the "true" distribution

P

.

The Kullback–Leibler divergence remains well-defined for continuous distributions, and furthermore is invariant under parameter transformations. For example, if a transformation is made from variable $x$ to variable $y(x)$ , then, since ${displaystyle P(x)dx=P(y)dy}$ and ${displaystyle Q(x)dx=Q(y)dy}$ the Kullback–Leibler divergence may be rewritten:

{displaystyle {begin{aligned}D_{text{KL}}(Pparallel Q)&=int _{x_{a}}^{x_{b}}P(x)log left({frac {P(x)}{Q(x)}}right),dx\[6pt]&=int _{y_{a}}^{y_{b}}P(y)log left({frac {P(y),{frac {dy}{dx}}}{Q(y),{frac {dy}{dx}}}}right),dy=int _{y_{a}}^{y_{b}}P(y)log left({frac {P(y)}{Q(y)}}right),dyend{aligned}}}

where

{displaystyle y_{a}=y(x_{a})}

and

{displaystyle y_{b}=y(x_{b})}

. Although it was assumed that the transformation was continuous, this need not be the case. This also shows that the Kullback–Leibler divergence produces a dimensionally consistent quantity, since if

x

is a dimensioned variable,

P(x)

and

Q(x)

are also dimensioned, since e.g.

{displaystyle P(x)dx}

is dimensionless. The argument of the logarithmic term is and remains dimensionless, as it must. It can therefore be seen as in some ways a more fundamental quantity than some other properties in information theory^[11] (such as self-information or Shannon entropy), which can become undefined or negative for non-discrete probabilities.

The Kullback–Leibler divergence is additive for independent distributions in much the same way as Shannon entropy. If $P_{1},P_{2}$ are independent distributions, with the joint distribution ${displaystyle P(x,y)=P_{1}(x)P_{2}(y)}$ , and $Q,Q_{1},Q_{2}$ likewise, then

{displaystyle D_{text{KL}}(Pparallel Q)=D_{text{KL}}(P_{1}parallel Q_{1})+D_{text{KL}}(P_{2}parallel Q_{2}).}

The Kullback–Leibler divergence ${displaystyle D_{text{KL}}(Pparallel Q)}$ is convex in the pair of probability mass functions $(p,q)$ , i.e. if ${displaystyle (p_{1},q_{1})}$ and ${displaystyle (p_{2},q_{2})}$ are two pairs of probability mass functions, then

{displaystyle D_{text{KL}}(lambda p_{1}+(1-lambda )p_{2}parallel lambda q_{1}+(1-lambda )q_{2})leq lambda D_{text{KL}}(p_{1}parallel q_{1})+(1-lambda )D_{text{KL}}(p_{2}parallel q_{2}){text{ for }}0leq lambda leq 1.}

Examples

Multivariate normal distributions

Suppose that we have two multivariate normal distributions, with means $mu _{0},mu _{1}$ and with (non-singular) covariance matrices ${displaystyle Sigma _{0},Sigma _{1}.}$ If the two distributions have the same dimension, $k$ , then the Kullback–Leibler divergence between the distributions is as follows:^[12]^{:p. 13}

{displaystyle D_{text{KL}}({mathcal {N}}_{0}parallel {mathcal {N}}_{1})={frac {1}{2}}left(operatorname {tr} left(Sigma _{1}^{-1}Sigma _{0}right)+(mu _{1}-mu _{0})^{mathsf {T}}Sigma _{1}^{-1}(mu _{1}-mu _{0})-k+ln left({frac {det Sigma _{1}}{det Sigma _{0}}}right)right).}

The logarithm in the last term must be taken to base e since all terms apart from the last are base-e logarithms of expressions that are either factors of the density function or otherwise arise naturally. The equation therefore gives a result measured in nats. Dividing the entire expression above by $ln(2)$ yields the divergence in bits.

A special case, and a common quantity in variational inference, is the KL-divergence between a diagonal multivariate normal, and a standard normal distribution:

{displaystyle D_{text{KL}}left({mathcal {N}}left((mu _{1},ldots ,mu _{k})^{mathsf {T}},operatorname {diag} (sigma _{1}^{2},ldots ,sigma _{k}^{2})right)parallel {mathcal {N}}left(mathbf {0} ,mathbf {I} right)right)={1 over 2}sum _{i=1}^{k}(sigma _{i}^{2}+mu _{i}^{2}-ln(sigma _{i}^{2})-1).}

Relation to metrics

One might be tempted to call the Kullback–Leibler divergence a "distance metric" on the space of probability distributions, but this would not be correct as it is not symmetric – that is, ${displaystyle D_{text{KL}}(Pparallel Q)neq D_{text{KL}}(Qparallel P)}$ – nor does it satisfy the triangle inequality. Even so, being a premetric, it generates a topology on the space of probability distributions. More concretely, if ${displaystyle {P_{1},P_{2},ldots }}$ is a sequence of distributions such that

${displaystyle lim _{nto infty }D_{text{KL}}(P_{n}parallel Q)=0}$

(1)

then it is said that

${displaystyle P_{n}{xrightarrow {D}}Q.}$

(2)

Pinsker's inequality entails that

${displaystyle P_{n}{xrightarrow {D}}PRightarrow P_{n}{xrightarrow {TV}}P,}$

(3)

where the latter stands for the usual convergence in total variation.

Following Rényi (1970, 1961)^[13]^[14]

Fisher information metric

The Kullback–Leibler divergence is directly related to the Fisher information metric. This can be made explicit as follows. Assume that the probability distributions $P$ and $Q$ are both parameterized by some (possibly multi-dimensional) parameter $theta$ . Consider then two close-by values of $P=P(theta )$ and $Q=P(theta _{0})$ so that the parameter $theta$ differs by only a small amount from the parameter value $theta _{0}$ . Specifically, up to first order one has (using the Einstein summation convention)

{displaystyle P(theta )=P(theta _{0})+Delta theta ^{j}P_{j}(theta _{0})+cdots }

with $Delta theta ^{j}=(theta -theta _{0})^{j}$ a small change of $theta$ in the $j$ direction, and ${displaystyle P_{j}left(theta _{0}right)={frac {partial P}{partial theta ^{j}}}(theta _{0})}$ the corresponding rate of change in the probability distribution. Since the Kullback–Leibler divergence has an absolute minimum 0 for $P=Q$ , i.e. $theta =theta _{0}$ , it changes only to second order in the small parameters $Delta theta ^{j}$ . More formally, as for any minimum, the first derivatives of the divergence vanish

{displaystyle left.{frac {partial }{partial theta ^{j}}}right|_{theta =theta _{0}}D_{KL}(P(theta )parallel P(theta _{0}))=0,}

and by the Taylor expansion one has up to second order

{displaystyle D_{text{KL}}(P(theta )parallel P(theta _{0}))={frac {1}{2}}Delta theta ^{j}Delta theta ^{k}g_{jk}(theta _{0})+cdots }

where the Hessian matrix of the divergence

{displaystyle g_{jk}(theta _{0})=left.{frac {partial ^{2}}{partial theta ^{j},partial theta ^{k}}}right|_{theta =theta _{0}}D_{text{KL}}(P(theta )parallel P(theta _{0}))}

must be positive semidefinite. Letting $theta _{0}$ vary (and dropping the subindex 0) the Hessian $g_{jk}(theta )$ defines a (possibly degenerate) Riemannian metric on the $θ$ parameter space, called the Fisher information metric.

Fisher information metric theorem

When ${displaystyle p_{(x,rho )}}$ satisfies the following regulatory conditions: ${displaystyle {tfrac {partial log(p)}{partial rho }},{tfrac {partial ^{2}log(p)}{partial rho ^{2}}},{tfrac {partial ^{3}log(p)}{partial rho ^{3}}}}$ exist,

{displaystyle {begin{aligned}left|{frac {partial p}{partial rho }}right|&<F(x):int _{x=0}^{infty }F(x),dx<infty ,\left|{frac {partial ^{2}p}{partial rho ^{2}}}right|&<G(x):int _{x=0}^{infty }G(x),dx<infty \left|{frac {partial ^{3}log(p)}{partial rho ^{3}}}right|&<H(x):int _{x=0}^{infty }p(x,0)H(x),dx<xi <infty end{aligned}}}

where $ξ$ is independent of $ρ$

{displaystyle left.int _{x=0}^{infty }{frac {partial p(x,rho )}{partial rho }}right|_{rho =0},dx=left.int _{x=0}^{infty }{frac {partial ^{2}p(x,rho )}{partial rho ^{2}}}right|_{rho =0},dx=0}

then:

{displaystyle {mathcal {D}}(p(x,0)parallel p(x,rho ))={frac {crho ^{2}}{2}}+{mathcal {O}}(rho ^{3}){text{ as }}rho to 0.}

Relation to other quantities of information theory

Many of the other quantities of information theory can be interpreted as applications of the Kullback–Leibler divergence to specific cases.

Self-information

The self-information, also known as the information content of a signal, random variable, or event is defined as the negative logarithm of the probability of the given outcome occurring.

When applied to a discrete random variable, the self-information can be represented as^{[citation needed]}

{displaystyle operatorname {operatorname {I} } (m)=D_{text{KL}}(delta _{im}parallel {p_{i}}),}

is the Kullback–Leibler divergence of the probability distribution ${displaystyle P(i)}$ from a Kronecker delta representing certainty that ${displaystyle i=m}$ — i.e. the number of extra bits that must be transmitted to identify $i$ if only the probability distribution ${displaystyle P(i)}$ is available to the receiver, not the fact that ${displaystyle i=m}$ .

Mutual information

The mutual information,^{[citation needed]}

{displaystyle {begin{aligned}operatorname {I} (X;Y)&=D_{text{KL}}(P(X,Y)parallel P(X)P(Y))\&=operatorname {E} _{X}{D_{text{KL}}(P(Ymid X)parallel P(Y))}\&=operatorname {E} _{Y}{D_{text{KL}}(P(Xmid Y)parallel P(X))}end{aligned}}}

is the Kullback–Leibler divergence of the product ${displaystyle P(X)P(Y)}$ of the two marginal probability distributions from the joint probability distribution ${displaystyle P(X,Y)}$ — i.e. the expected number of extra bits that must be transmitted to identify $X$ and $Y$ if they are coded using only their marginal distributions instead of the joint distribution. Equivalently, if the joint probability ${displaystyle P(X,Y)}$ is known, it is the expected number of extra bits that must on average be sent to identify $Y$ if the value of $X$ is not already known to the receiver.

Shannon entropy

The Shannon entropy,^{[citation needed]}

${displaystyle mathrm {H} (X)=}$	${displaystyle operatorname {E} [operatorname {I} _{X}(x)]}$	(s1)
$=$	${displaystyle log(N)-D_{text{KL}}(p_{X}(x)parallel P_{U}(X))}$	(s2)

is the number of bits which would have to be transmitted to identify $X$ from $N$ equally likely possibilities, less the Kullback–Leibler divergence of the uniform distribution on the random variates of $X$ , ${displaystyle P_{U}(X)}$ , from the true distribution $P(X)$ — i.e. less the expected number of bits saved, which would have had to be sent if the value of $X$ were coded according to the uniform distribution ${displaystyle P_{U}(X)}$ rather than the true distribution $P(X)$ .

Conditional entropy

The conditional entropy,^{[citation needed]}

${displaystyle mathrm {H} (Xmid Y)=}$	${displaystyle log(N)-D_{text{KL}}(P(X,Y)parallel P_{U}(X)P(Y))}$
$=$	${displaystyle log(N)-D_{text{KL}}(P(X,Y)parallel P(X)P(Y))-D_{text{KL}}(P(X)parallel P_{U}(X))}$	(c1)
$=$	${displaystyle mathrm {H} (X)-operatorname {I} (X;Y)}$
$=$	${displaystyle log(N)-operatorname {E} _{Y}{bigl [}D_{text{KL}}(P(Xmid Y)parallel P_{U}(X)){bigr ]}}$	(c2)

is the number of bits which would have to be transmitted to identify $X$ from $N$ equally likely possibilities, less the Kullback–Leibler divergence of the product distribution ${displaystyle P_{U}(X)P(Y)}$ from the true joint distribution ${displaystyle P(X,Y)}$ — i.e. less the expected number of bits saved which would have had to be sent if the value of $X$ were coded according to the uniform distribution ${displaystyle P_{U}(X)}$ rather than the conditional distribution $P(X|Y)$ of $X$ given $Y$ .

Cross entropy

The cross entropy between two probability distributions measures the average number of bits needed to identify an event from a set of possibilities, if a coding scheme is used based on a given probability distribution $q$ , rather than the "true" distribution $p$ . The cross entropy for two distributions $p$ and $q$ over the same probability space is thus defined as follows:^{[citation needed]}

{displaystyle mathrm {H} (p,q)=operatorname {E} _{p}[-log(q)]=mathrm {H} (p)+D_{text{KL}}(pparallel q).}

Bayesian updating

In Bayesian statistics the Kullback–Leibler divergence can be used as a measure of the information gain in moving from a prior distribution to a posterior distribution: ${displaystyle p(x)to p(xmid I)}$ . If some new fact ${displaystyle Y=y}$ is discovered, it can be used to update the posterior distribution for $X$ from ${displaystyle p(xmid I)}$ to a new posterior distribution ${displaystyle p(xmid y,I)}$ using Bayes' theorem:

{displaystyle p(xmid y,I)={frac {p(ymid x,I)p(xmid I)}{p(ymid I)}}}

This distribution has a new entropy:

{displaystyle mathrm {H} {big (}p(-mid y,I){big )}=-sum _{x}p(xmid y,I)log p(xmid y,I),}

which may be less than or greater than the original entropy ${displaystyle mathrm {H} (p(-mid I))}$ . However, from the standpoint of the new probability distribution one can estimate that to have used the original code based on ${displaystyle p(xmid I)}$ instead of a new code based on ${displaystyle p(xmid y,I)}$ would have added an expected number of bits:

{displaystyle D_{text{KL}}{big (}p(-mid y,I)parallel p(-mid I){big )}=sum _{x}p(xmid y,I)log left({frac {p(xmid y,I)}{p(xmid I)}}right)}

to the message length. This therefore represents the amount of useful information, or information gain, about $X$ , that we can estimate has been learned by discovering ${displaystyle Y=y}$ .

If a further piece of data, ${displaystyle Y_{2}=y_{2}}$ , subsequently comes in, the probability distribution for $x$ can be updated further, to give a new best guess ${displaystyle p(xmid y_{1},y_{2},I)}$ . If one reinvestigates the information gain for using ${displaystyle p(xmid y_{1},I)}$ rather than ${displaystyle p(xmid I)}$ , it turns out that it may be either greater or less than previously estimated:

{displaystyle sum _{x}p(xmid y_{1},y_{2},I)log left({frac {p(xmid y_{1},y_{2},I)}{p(xmid I)}}right)}

may be ≤ or > than

{displaystyle displaystyle sum _{x}p(xmid y_{1},I)log left({frac {p(xmid y_{1},I)}{p(xmid I)}}right)}

and so the combined information gain does not obey the triangle inequality:

{displaystyle D_{text{KL}}{big (}p(-mid y_{1},y_{2},I)parallel p(-mid I){big )}}

may be <, = or > than

{displaystyle D_{text{KL}}{big (}p(-mid y_{1},y_{2},I)parallel p(-mid y_{1},I){big )}+D_{text{KL}}{big (}p(-mid y_{1},I)parallel p(-mid I){big )}}

All one can say is that on average, averaging using ${displaystyle p(y_{2}mid y_{1},x,I)}$ , the two sides will average out.

Bayesian experimental design

A common goal in Bayesian experimental design is to maximise the expected Kullback–Leibler divergence between the prior and the posterior.^[15] When posteriors are approximated to be Gaussian distributions, a design maximising the expected Kullback–Leibler divergence is called Bayes d-optimal.

Discrimination information

The Kullback–Leibler divergence ${textstyle D_{text{KL}}{bigl (}p(xmid H_{1})parallel p(xmid H_{0}){bigr )}}$ can also be interpreted as the expected discrimination information for $H_{1}$ over $H_{0}$ : the mean information per sample for discriminating in favor of a hypothesis $H_{1}$ against a hypothesis $H_{0}$ , when hypothesis $H_{1}$ is true.^[16] Another name for this quantity, given to it by I. J. Good, is the expected weight of evidence for $H_{1}$ over $H_{0}$ to be expected from each sample.

The expected weight of evidence for $H_{1}$ over $H_{0}$ is not the same as the information gain expected per sample about the probability distribution ${displaystyle p(H)}$ of the hypotheses,

{displaystyle D_{text{KL}}(p(xmid H_{1})parallel p(xmid H_{0}))neq IG=D_{text{KL}}(p(Hmid x)parallel p(Hmid I)).}

Either of the two quantities can be used as a utility function in Bayesian experimental design, to choose an optimal next question to investigate: but they will in general lead to rather different experimental strategies.

On the entropy scale of information gain there is very little difference between near certainty and absolute certainty—coding according to a near certainty requires hardly any more bits than coding according to an absolute certainty. On the other hand, on the logit scale implied by weight of evidence, the difference between the two is enormous – infinite perhaps; this might reflect the difference between being almost sure (on a probabilistic level) that, say, the Riemann hypothesis is correct, compared to being certain that it is correct because one has a mathematical proof. These two different scales of loss function for uncertainty are both useful, according to how well each reflects the particular circumstances of the problem in question.

Principle of minimum discrimination information

The idea of Kullback–Leibler divergence as discrimination information led Kullback to propose the Principle of Minimum Discrimination Information (MDI): given new facts, a new distribution $f$ should be chosen which is as hard to discriminate from the original distribution $f_{0}$ as possible; so that the new data produces as small an information gain ${displaystyle D_{text{KL}}(fparallel f_{0})}$ as possible.

For example, if one had a prior distribution ${displaystyle p(x,a)}$ over $x$ and $a$ , and subsequently learnt the true distribution of $a$ was ${displaystyle u(a)}$ , then the Kullback–Leibler divergence between the new joint distribution for $x$ and $a$ , ${displaystyle q(xmid a)u(a)}$ , and the earlier prior distribution would be:

{displaystyle D_{text{KL}}(q(xmid a)u(a)parallel p(x,a))=operatorname {E} _{u(a)}left{D_{text{KL}}(q(xmid a)parallel p(xmid a))right}+D_{text{KL}}(u(a)parallel p(a)),}

i.e. the sum of the Kullback–Leibler divergence of $p(a)$ the prior distribution for $a$ from the updated distribution ${displaystyle u(a)}$ , plus the expected value (using the probability distribution ${displaystyle u(a)}$ ) of the Kullback–Leibler divergence of the prior conditional distribution ${displaystyle p(xmid a)}$ from the new conditional distribution ${displaystyle q(xmid a}$ . (Note that often the later expected value is called the conditional Kullback–Leibler divergence (or conditional relative entropy) and denoted by ${displaystyle D_{text{KL}}(q(xmid a)parallel p(xmid a))}$ ^[17]^{:p. 22}) This is minimized if ${displaystyle q(xmid a)=p(xmid a)}$ over the whole support of ${displaystyle u(a)}$ ; and we note that this result incorporates Bayes' theorem, if the new distribution ${displaystyle u(a)}$ is in fact a δ function representing certainty that $a$ has one particular value.

MDI can be seen as an extension of Laplace's Principle of Insufficient Reason, and the Principle of Maximum Entropy of E.T. Jaynes. In particular, it is the natural extension of the principle of maximum entropy from discrete to continuous distributions, for which Shannon entropy ceases to be so useful (see differential entropy), but the Kullback–Leibler divergence continues to be just as relevant.

In the engineering literature, MDI is sometimes called the Principle of Minimum Cross-Entropy (MCE) or Minxent for short. Minimising the Kullback–Leibler divergence from $m$ to $p$ with respect to $m$ is equivalent to minimizing the cross-entropy of $p$ and $m$ , since

{displaystyle mathrm {H} (p,m)=mathrm {H} (p)+D_{text{KL}}(pparallel m),}

which is appropriate if one is trying to choose an adequate approximation to $p$ . However, this is just as often not the task one is trying to achieve. Instead, just as often it is $m$ that is some fixed prior reference measure, and $p$ that one is attempting to optimise by minimising ${displaystyle D_{text{KL}}(pparallel m)}$ subject to some constraint. This has led to some ambiguity in the literature, with some authors attempting to resolve the inconsistency by redefining cross-entropy to be ${displaystyle D_{text{KL}}(pparallel m)}$ , rather than ${displaystyle mathrm {H} (p,m)}$ .

Relationship to available work

Pressure versus volume plot of available work from a mole of argon gas relative to ambient, calculated as

T_{o}

times the Kullback–Leibler divergence.

Surprisals^[18] add where probabilities multiply. The surprisal for an event of probability $p$ is defined as ${displaystyle s=kln(1/p)}$ . If $k$ is ${displaystyle left{1,1/ln 2,1.38times 10^{-23}right}}$ then surprisal is in ${$ nats, bits, or $J/K}$ so that, for instance, there are $N$ bits of surprisal for landing all "heads" on a toss of $N$ coins.

Best-guess states (e.g. for atoms in a gas) are inferred by maximizing the average surprisal $S$ (entropy) for a given set of control parameters (like pressure $P$ or volume $V$ ). This constrained entropy maximization, both classically^[19] and quantum mechanically,^[20] minimizes Gibbs availability in entropy units^[21] ${displaystyle Aequiv -kln(Z)}$ where $Z$ is a constrained multiplicity or partition function.

When temperature $T$ is fixed, free energy ( $Ttimes A$ ) is also minimized. Thus if $T,V$ and number of molecules $N$ are constant, the Helmholtz free energy ${displaystyle Fequiv U-TS}$ (where $U$ is energy) is minimized as a system "equilibrates." If $T$ and $P$ are held constant (say during processes in your body), the Gibbs free energy ${displaystyle G=U+PV-TS}$ is minimized instead. The change in free energy under these conditions is a measure of available work that might be done in the process. Thus available work for an ideal gas at constant temperature $T_{o}$ and pressure $P_{o}$ is ${displaystyle W=Delta G=NkT_{o}Theta (V/V_{o})}$ where $V_{o}=NkT_{o}/P_{o}$ and ${displaystyle Theta (x)=x-1-ln xgeq 0}$ (see also Gibbs inequality).

More generally^[22] the work available relative to some ambient is obtained by multiplying ambient temperature $T_{o}$ by Kullback–Leibler divergence or net surprisal ${displaystyle Delta Igeq 0,}$ defined as the average value of $kln(p/p_{o})$ where $p_{o}$ is the probability of a given state under ambient conditions. For instance, the work available in equilibrating a monatomic ideal gas to ambient values of $V_{o}$ and $T_{o}$ is thus ${displaystyle W=T_{o}Delta I}$ , where Kullback–Leibler divergence

{displaystyle Delta I=Nkleft[Theta left({frac {V}{V_{o}}}right)+{frac {3}{2}}Theta left({frac {T}{T_{o}}}right)right].}

The resulting contours of constant Kullback–Leibler divergence, shown at right for a mole of Argon at standard temperature and pressure, for example put limits on the conversion of hot to cold as in flame-powered air-conditioning or in the unpowered device to convert boiling-water to ice-water discussed here.^[23] Thus Kullback–Leibler divergence measures thermodynamic availability in bits.

Quantum information theory

For density matrices $P$ and $Q$ on a Hilbert space, the K–L divergence (or quantum relative entropy as it is often called in this case) from $Q$ to $P$ is defined to be

{displaystyle D_{text{KL}}(Pparallel Q)=operatorname {Tr} (P(log(P)-log(Q))).}

In quantum information science the minimum of ${displaystyle D_{text{KL}}(Pparallel Q)}$ over all separable states $Q$ can also be used as a measure of entanglement in the state $P$ .

Relationship between models and reality

Just as Kullback–Leibler divergence of "actual from ambient" measures thermodynamic availability, Kullback–Leibler divergence of "reality from a model" is also useful even if the only clues we have about reality are some experimental measurements. In the former case Kullback–Leibler divergence describes distance to equilibrium or (when multiplied by ambient temperature) the amount of available work, while in the latter case it tells you about surprises that reality has up its sleeve or, in other words, how much the model has yet to learn.

Although this tool for evaluating models against systems that are accessible experimentally may be applied in any field, its application to selecting a statistical model via Akaike information criterion are particularly well described in papers^[24] and a book^[25] by Burnham and Anderson. In a nutshell the Kullback–Leibler divergence of reality from a model may be estimated, to within a constant additive term, by a function (like the squares summed) of the deviations observed between data and the model's predictions. Estimates of such divergence for models that share the same additive term can in turn be used to select among models.

When trying to fit parametrized models to data there are various estimators which attempt to minimize Kullback–Leibler divergence, such as maximum likelihood and maximum spacing estimators.

Symmetrised divergence

Kullback and Leibler themselves actually defined the divergence as:

{displaystyle D_{text{KL}}(Pparallel Q)+D_{text{KL}}(Qparallel P)}

which is symmetric and nonnegative. This quantity has sometimes been used for feature selection in classification problems, where $P$ and $Q$ are the conditional pdfs of a feature under two different classes.

An alternative is given via the $lambda$ divergence,

{displaystyle D_{lambda }(Pparallel Q)=lambda D_{text{KL}}(Pparallel lambda P+(1-lambda )Q)+(1-lambda )D_{text{KL}}(Qparallel lambda P+(1-lambda )Q),}

which can be interpreted as the expected information gain about $X$ from discovering which probability distribution $X$ is drawn from, $P$ or $Q$ , if they currently have probabilities $lambda$ and $1-lambda$ respectively.^{[clarification needed]}^{[citation needed]}

The value ${displaystyle lambda =0.5}$ gives the Jensen–Shannon divergence, defined by

{displaystyle D_{text{JS}}={frac {1}{2}}D_{text{KL}}(Pparallel M)+{frac {1}{2}}D_{text{KL}}(Qparallel M)}

where $M$ is the average of the two distributions,

{displaystyle M={frac {1}{2}}(P+Q).}

${displaystyle D_{JS}}$ can also be interpreted as the capacity of a noisy information channel with two inputs giving the output distributions $P$ and $Q$ . The Jensen–Shannon divergence, like all f-divergences, is locally proportional to the Fisher information metric. It is similar to the Hellinger metric (in the sense that induces the same affine connection on a statistical manifold).

Relationship to other probability-distance measures

There are many other important measures of probability distance. Some of these are particularly connected with the Kullback–Leibler divergence. For example:

The total variation distance, $delta (p,q)$ . This is connected to the divergence through Pinsker's inequality: ${displaystyle delta (P,Q)leq {sqrt {{frac {1}{2}}D_{text{KL}}(Pparallel Q)}}}$

The family of Rényi divergences provide generalizations of the Kullback–Leibler divergence. Depending on the value of a certain parameter, $alpha$ , various inequalities may be deduced.

Other notable measures of distance include the Hellinger distance, histogram intersection, Chi-squared statistic, quadratic form distance, match distance, Kolmogorov–Smirnov distance, and earth mover's distance.^[26]

Data differencing

Just as absolute entropy serves as theoretical background for data compression, relative entropy serves as theoretical background for data differencing – the absolute entropy of a set of data in this sense being the data required to reconstruct it (minimum compressed size), while the relative entropy of a target set of data, given a source set of data, is the data required to reconstruct the target given the source (minimum size of a patch).

References

^ Kullback, S.; Leibler, R.A. (1951). "On information and sufficiency". Annals of Mathematical Statistics. 22 (1): 79–86. doi:10.1214/aoms/1177729694. MR 0039968..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}

^ ^a^b^c Kullback, S. (1959), Information Theory and Statistics, John Wiley & Sons. Republished by Dover Publications in 1968; reprinted in 1978:
ISBN 0-8446-5625-9.

^ Kullback, S. (1987). "Letter to the Editor: The Kullback–Leibler distance". The American Statistician. 41 (4): 340–341. doi:10.1080/00031305.1987.10475510. JSTOR 2684769.

^ MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms (First ed.). Cambridge University Press. p. 34.

^ Bishop C. (2006). Pattern Recognition and Machine Learning

^ Burnham, K. P.; Anderson, D. R. (2002). Model Selection and Multi-Model Inference (2nd ed.). Springer. p. 51.

^ Hobson, Arthur (1971). Concepts in statistical mechanics. New York: Gordon and Breach. ISBN 0677032404.

^ Baez, John; Fritz, Tobias (2014). "A Bayesian characterization of relative entropy". Theory and Application of Categories. 29: 421–456. arXiv:1402.3067.

^ Sanov, I.N. (1957). "On the probability of large deviations of random magnitudes". Matem. Sbornik. 42 (84): 11–44.

^ Novak S.Y. (2011), Extreme Value Methods with Applications to Finance ch. 14.5 (Chapman & Hall).
ISBN 978-1-4398-3574-6.

^ See the section "differential entropy – 4" in Relative Entropy video lecture by Sergio Verdú NIPS 2009

^ Duchi J., "Derivations for Linear Algebra and Optimization".

^ Rényi A. (1970). Probability Theory. Elsevier. Appendix, Sec.4. ISBN 0-486-45867-9.

^ Rényi, A. (1961), "On measures of entropy and information" (PDF), Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability 1960, pp. 547–561

^ Chaloner, K.; Verdinelli, I. (1995). "Bayesian experimental design: a review". Statistical Science. 10 (3): 273–304. doi:10.1214/ss/1177009939.

^ Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (2007). "Section 14.7.2. Kullback–Leibler Distance". Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. ISBN 978-0-521-88068-8

^ Thomas M. Cover, Joy A. Thomas (1991) Elements of Information Theory (John Wiley & Sons)

^ Myron Tribus (1961), Thermodynamics and Thermostatics (D. Van Nostrand, New York)

^ Jaynes, E. T. (1957). "Information theory and statistical mechanics" (PDF). Physical Review. 106: 620–630. Bibcode:1957PhRv..106..620J. doi:10.1103/physrev.106.620.

^ Jaynes, E. T. (1957). "Information theory and statistical mechanics II" (PDF). Physical Review. 108: 171–190. Bibcode:1957PhRv..108..171J. doi:10.1103/physrev.108.171.

^ J.W. Gibbs (1873), "A method of geometrical representation of thermodynamic properties of substances by means of surfaces", reprinted in The Collected Works of J. W. Gibbs, Volume I Thermodynamics, ed. W. R. Longley and R. G. Van Name (New York: Longmans, Green, 1931) footnote page 52.

^ Tribus, M.; McIrvine, E. C. (1971). "Energy and information". Scientific American. 224: 179–186. Bibcode:1971SciAm.225c.179T. doi:10.1038/scientificamerican0971-179.

^ Fraundorf, P. (2007). "Thermal roots of correlation-based complexity". Complexity. 13 (3): 18–26. arXiv:1103.2481. Bibcode:2008Cmplx..13c..18F. doi:10.1002/cplx.20195.

^ Burnham, K.P.; Anderson, D.R. (2001). "Kullback–Leibler information as a basis for strong inference in ecological studies". Wildlife Research. 28: 111–119. doi:10.1071/WR99107.

^ Burnham, K. P. and Anderson D. R. (2002), Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science)
ISBN 978-0-387-95364-9.

^ Rubner, Y.; Tomasi, C.; Guibas, L. J. (2000). "The earth mover's distance as a metric for image retrieval". International Journal of Computer Vision. 40 (2): 99–121.

External links

Information Theoretical Estimators Toolbox

Ruby gem for calculating Kullback–Leibler divergence

Jon Shlens' tutorial on Kullback–Leibler divergence and likelihood theory

Matlab code for calculating Kullback–Leibler divergence for discrete distributions

Sergio Verdú, Relative Entropy, NIPS 2009. One-hour video lecture.

A modern summary of info-theoretic divergence measures

[1] Kullback, S.; Leibler, R.A. (1951). "On information and sufficiency". Annals of Mathematical Statistics. 22 (1): 79–86. doi:10.1214/aoms/1177729694. MR 0039968..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}

[Kullback-2] Kullback, S. (1959), Information Theory and Statistics, John Wiley & Sons. Republished by Dover Publications in 1968; reprinted in 1978:
ISBN 0-8446-5625-9.

[3] Kullback, S. (1987). "Letter to the Editor: The Kullback–Leibler distance". The American Statistician. 41 (4): 340–341. doi:10.1080/00031305.1987.10475510. JSTOR 2684769.

[4] MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms (First ed.). Cambridge University Press. p. 34.

[5] Bishop C. (2006). Pattern Recognition and Machine Learning

[6] Burnham, K. P.; Anderson, D. R. (2002). Model Selection and Multi-Model Inference (2nd ed.). Springer. p. 51.

[7] Hobson, Arthur (1971). Concepts in statistical mechanics. New York: Gordon and Breach. ISBN 0677032404.

[8] Baez, John; Fritz, Tobias (2014). "A Bayesian characterization of relative entropy". Theory and Application of Categories. 29: 421–456. arXiv:1402.3067.

[Sanov-9] Sanov, I.N. (1957). "On the probability of large deviations of random magnitudes". Matem. Sbornik. 42 (84): 11–44.

[Novak-10] Novak S.Y. (2011), Extreme Value Methods with Applications to Finance ch. 14.5 (Chapman & Hall).
ISBN 978-1-4398-3574-6.

[VerduLecture-11] See the section "differential entropy – 4" in Relative Entropy video lecture by Sergio Verdú NIPS 2009

[12] Duchi J., "Derivations for Linear Algebra and Optimization".

[13] Rényi A. (1970). Probability Theory. Elsevier. Appendix, Sec.4. ISBN 0-486-45867-9.

[14] Rényi, A. (1961), "On measures of entropy and information" (PDF), Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability 1960, pp. 547–561

[15] Chaloner, K.; Verdinelli, I. (1995). "Bayesian experimental design: a review". Statistical Science. 10 (3): 273–304. doi:10.1214/ss/1177009939.

[16] Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (2007). "Section 14.7.2. Kullback–Leibler Distance". Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. ISBN 978-0-521-88068-8

[17] Thomas M. Cover, Joy A. Thomas (1991) Elements of Information Theory (John Wiley & Sons)

[18] Myron Tribus (1961), Thermodynamics and Thermostatics (D. Van Nostrand, New York)

[19] Jaynes, E. T. (1957). "Information theory and statistical mechanics" (PDF). Physical Review. 106: 620–630. Bibcode:1957PhRv..106..620J. doi:10.1103/physrev.106.620.

[20] Jaynes, E. T. (1957). "Information theory and statistical mechanics II" (PDF). Physical Review. 108: 171–190. Bibcode:1957PhRv..108..171J. doi:10.1103/physrev.108.171.

[21] J.W. Gibbs (1873), "A method of geometrical representation of thermodynamic properties of substances by means of surfaces", reprinted in The Collected Works of J. W. Gibbs, Volume I Thermodynamics, ed. W. R. Longley and R. G. Van Name (New York: Longmans, Green, 1931) footnote page 52.

[22] Tribus, M.; McIrvine, E. C. (1971). "Energy and information". Scientific American. 224: 179–186. Bibcode:1971SciAm.225c.179T. doi:10.1038/scientificamerican0971-179.

[23] Fraundorf, P. (2007). "Thermal roots of correlation-based complexity". Complexity. 13 (3): 18–26. arXiv:1103.2481. Bibcode:2008Cmplx..13c..18F. doi:10.1002/cplx.20195.

[24] Burnham, K.P.; Anderson, D.R. (2001). "Kullback–Leibler information as a basis for strong inference in ecological studies". Wildlife Research. 28: 111–119. doi:10.1071/WR99107.

[25] Burnham, K. P. and Anderson D. R. (2002), Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science)
ISBN 978-0-387-95364-9.

[earth-26] Rubner, Y.; Tomasi, C.; Guibas, L. J. (2000). "The earth mover's distance as a metric for image retrieval". International Journal of Computer Vision. 40 (2): 99–121.

Category

Random preview

Kullback–Leibler divergence

Contents