Measuring Information

Section 5.3.1 left a question open. A Bayesian model keeps its uncertainty so that an optimizer can spend each evaluation where it teaches the most. But how much does an evaluation teach? To compare two candidate queries, or to say how much a person's answer to a comparison can possibly reveal, we need to measure what is learned in a unit, the way bytes measure storage.

Claude Shannon supplied that unit in 1948, for a different problem: how many binary digits it takes to transmit a message (Shannon, 1948). His measure, entropy, turns out to quantify uncertainty in general, and two quantities built from it, the Kullback-Leibler divergence and mutual information, measure how far apart two beliefs are and how much one variable tells about another. This chapter builds the three from a single idea, the surprise of one outcome, and then uses them for the two jobs the rest of the book needs.

The first job is choosing what to ask. Lindley (1956) proposed to choose an experiment by the information its outcome is expected to provide, and several acquisition functions in Chapter 12 and most query rules for comparisons in Chapter 20 are versions of his criterion. The second job is analysis. An optimizer's regret is the shortfall of the values it obtained from the best value available, added up over its evaluations, and the theory in Chapter 13 bounds how fast it can grow. Those bounds measure how hard a problem is by the most information that $T$ evaluations could gather about the objective, a number written $\gamma_T$. The chapter ends by computing it and watching how fast it grows with the dimension of the input.

A note on units. Information is measured with logarithms, and the base of the logarithm sets the unit. Base 2 gives bits, natural for yes/no questions; base $e$ gives nats, natural for Gaussians. We use bits for discrete examples and nats for continuous ones, as the literature does. One nat is $1/\ln 2 \approx 1.443$ bits, so converting is a single multiplication.

6.1 Surprise and entropy #

6.1.1 Surprise #

Start with one outcome. A fair coin landing heads is mildly surprising; a lottery ticket winning is very surprising; the sun rising is not surprising at all. A measure of surprise should depend only on the probability $p$ of what happened, should be zero when $p = 1$, and should grow as $p$ shrinks. One more requirement fixes it. Two independent events, such as a coin landing heads and a die showing six, have probability $\tfrac12 \times \tfrac16$, and we would like the surprise of seeing both to be the sum of the two surprises. The function that turns products into sums is the logarithm, so the surprise, or information content, of an outcome with probability $p$ is

In bits, an outcome with probability $1/2$ carries 1 bit, one with probability $1/8$ carries 3 bits, and one with probability $1/1024$ carries 10 bits. The surprise is the number of fair coin flips that would have to come out a particular way to be as unlikely as the outcome.

6.1.2 Entropy #

Surprise belongs to an outcome. Before the outcome is known, we can ask how surprised we expect to be. That expectation is the entropy of the distribution:

with the convention $0 \log 0 = 0$, since an outcome that never happens contributes nothing. Entropy is a property of a distribution, not of a value, and it measures how uncertain the distribution is.

A few cases make the scale concrete. A fair coin has $H = 1$ bit. A fair die has $\log_2 6 \approx 2.585$ bits. A coin that lands heads with probability $0.9$ has

where $h(p) = -p\log_2 p - (1 - p)\log_2(1 - p)$ is the binary entropy function. It equals 1 bit at $p = 1/2$ and falls to 0 as $p$ approaches 0 or 1. A yes/no question whose answer is nearly certain has almost no entropy, and, as Section 6.3 will show, can teach almost nothing.

Entropy has an operational meaning that makes it more than a formula. Suppose someone draws an outcome from $p$ and you must identify it by asking yes/no questions, any questions you like. The smallest possible average number of questions lies between $H(X)$ and $H(X) + 1$ when entropy is measured in bits, because a strategy of questions is a binary code for the outcomes and the best binary codes achieve this length (Cover and Thomas, 2006, ch. 5). To identify one of 128 equally likely outcomes takes exactly 7 questions, each halving the remaining set, and $\log_2 128 = 7$. A distribution that piles its probability onto a few outcomes takes fewer questions on average, because the likely outcomes can be asked about first.

Among distributions over $K$ outcomes, the uniform one has the largest entropy, $\log K$, and a distribution that puts all its probability on one outcome has the smallest, zero. Exercise 6.1 proves the first claim with a tool from the next section.

6.1.3 Entropy of a continuous variable #

For a continuous variable with density $p$, the sum becomes an integral,

called the differential entropy. It keeps the meaning "how spread out", but it is not a limit of the discrete entropy, and two of its properties are surprising at first. It can be negative: a density squeezed into an interval of width $0.1$ has values around 10, so $-\log p(x)$ is negative there. And it depends on the units: measuring the same quantity in millimeters instead of meters adds $\log 1000$. Differences of differential entropies, which is all the rest of this chapter uses, have neither problem.

The entropy of a Gaussian does not depend on its mean, only on its spread: it grows like the log of the standard deviation, and in many dimensions like the log of the volume $\lvert\mSigma\rvert^{1/2}$ of its ellipsoids (Section 3.6). A standard normal has $\tfrac12\log(2\pi e) \approx 1.419$ nats; the entropy drops below zero once $\sigma < 1/\sqrt{2\pi e} \approx 0.242$.

Section 4.1.2 claimed that the Gaussian assumes the least of any distribution with a given mean and variance. In the language of this section: among all densities on the real line with variance $\sigma^2$, the Gaussian has the largest differential entropy, $\tfrac12\log(2\pi e\,\sigma^2)$ (Cover and Thomas, 2006, ch. 12). The proof takes two lines once the next section's tool is in hand, and Section 6.2.4 gives it.

6.2 KL divergence #

Entropy measures one distribution. Much of inference compares two: the posterior and an approximation to it, the true distribution of answers and a model's prediction, a fair coin and a biased one. The comparison the rest of the book uses is the Kullback-Leibler divergence.

6.2.1 Definition #

Suppose the data come from a distribution $p$, and we score them with a model $q$. Each outcome $x$ costs us a surprise of $-\log q(x)$ under the model, where the best possible model, $p$ itself, would have charged $-\log p(x)$. The Kullback-Leibler divergence is the average excess:

with an integral for densities. It is also called relative entropy.

The same quantity has a second reading that explains its role in statistics. The ratio $\log(p(x)/q(x))$ is the log-likelihood ratio of one observation, the evidence it provides for "the data come from $p$" against "the data come from $q$". Averaged over observations that really do come from $p$, it is the expected evidence per observation for the truth. This is how Kullback and Leibler (1951) introduced it, as the mean information per observation for discriminating between two hypotheses, and it is how the lower bounds of Section 13.3 use it. In a bandit problem, where one chooses repeatedly among a few options with unknown reward distributions, the number of tries needed to tell a worse option from the best over $T$ rounds grows like $\ln T$ divided by the divergence between their reward distributions.

The divergence behaves like a distance in one important way and fails to in another.

So the divergence is zero for identical distributions and positive otherwise, like a distance. It is not symmetric, though: $\KL(p \,\|\, q)$ and $\KL(q \,\|\, p)$ are different numbers in general, and the difference can be large. It is a measure of how badly $q$ stands in for $p$, and that is not the same as how badly $p$ stands in for $q$.

Readers who have trained a classifier have minimized a KL divergence without the name. The quantity such training minimizes, called cross-entropy, $-\sum_x p(x)\log q(x)$, splits as

The entropy of the data does not depend on the model, so minimizing the cross-entropy over $q$ minimizes the divergence from the data to the model.

6.2.2 Two coins and two Gaussians #

Two closed forms appear later in the book. For coins with heads probabilities $p$ and $q$, the divergence, written $\mathrm{kl}(p, q)$ in the bandit literature, is

A coin with $p = 0.6$ judged against a fair coin has $\mathrm{kl}(0.6, 0.5) \approx 0.020$ nats: each flip carries a fiftieth of a nat of evidence, which is why telling a 0.6 coin from a fair one takes on the order of a hundred flips, as Section 2.5.2 found.

For two one-dimensional Gaussians,

which Exercise 6.2 derives. The asymmetry is easy to see in it. With equal means, a narrow $p = \N(0, 1)$ scored by a wide $q = \N(0, 2^2)$ costs $\log 2 + \tfrac18 - \tfrac12 \approx 0.318$ nats, while the wide one scored by the narrow one costs $-\log 2 + 2 - \tfrac12 \approx 0.807$ nats. A model that is too confident is punished more than one that is too vague, because it assigns tiny probability to outcomes that do happen.

6.2.3 Which direction #

The asymmetry matters most when we approximate a complicated distribution $p$ by a simple one $q$, such as a Gaussian, by minimizing a divergence. The two directions ask for different things.

• $\KL(p \,\|\, q)$ averages over $p$. Wherever $p$ has probability and $q$ has almost none, the ratio $p/q$ explodes, so the minimizer spreads $q$ to cover everything $p$ covers. For a Gaussian $q$, the minimizer matches the mean and the covariance of $p$ (Exercise 6.3). This is called mass-covering.
• $\KL(q \,\|\, p)$ averages over $q$. Wherever $q$ puts probability and $p$ has almost none, the ratio $q/p$ explodes, so the minimizer keeps $q$ inside the regions where $p$ is large, even if that means ignoring some of them. This is called mode-seeking.

Fit by $\KL(p \,\|\, q)$. The Gaussian centers between the bumps and stretches to cover both, with the mean and variance of $p$. It puts its peak where $p$ has almost no probability, but it never misses an outcome that $p$ produces.

Fit by $\KL(q \,\|\, p)$. The Gaussian locks onto one bump and ignores the other. Which one depends on where $q$ starts: drag its mean to the other side and fit again. The reverse divergence has one local minimum per bump, and an optimizer finds whichever is nearest.

Compare the numbers after each fit. The mode-seeking fit has a reverse divergence of about $\log 2 \approx 0.69$ nats, the price of ignoring half of $p$, and a forward divergence above 10 nats, because $p$ produces many values that this $q$ calls nearly impossible.

Push the bumps together. Below a separation of about 3.3, both directions prefer a single wide Gaussian, and the difference between them almost vanishes. The choice of direction matters most when the distribution being approximated is lopsided or has several peaks (Bishop, 2006, sec. 10.1.2).

These two behaviors return in Chapter 17. Variational inference (Section 17.4) fits an approximation by minimizing $\KL(q \,\|\, p)$ and inherits its tendency to be overconfident; expectation propagation (Section 17.3) matches moments, in the spirit of $\KL(p \,\|\, q)$, and tends to cover more. The divergence also appears as a penalty: fine-tuning a language model from human preferences adds the divergence between the tuned model's distribution and the original one to the objective, so that the model cannot drift arbitrarily far to please a learned reward (Ouyang et al., 2022), as Section 35.1.2 explains.

6.2.4 The Gaussian has the most entropy #

The nonnegativity of the divergence settles the claim deferred from Section 6.1.3.

The same argument with a uniform $\varphi$ over $K$ outcomes shows that no distribution over $K$ outcomes has more entropy than $\log K$ (Exercise 6.1).

6.3 Mutual information #

The divergence compares two distributions over the same variable. The question an experimenter asks is different: if I observe $Y$, how much will I learn about $X$? Entropy answers it directly. Before the observation, the uncertainty about $X$ is $H(X)$. After observing $Y = y$, it is the entropy of the conditional distribution, $H(X \given Y = y)$. Averaging that over the possible observations gives the conditional entropy

and the expected reduction in uncertainty is the mutual information

Three facts make mutual information easy to work with.

1. It is symmetric. By the product rule, $p(x, y) = p(y)\,p(x \given y)$, and taking $-\E\log$ of both sides gives the chain rule $H(X, Y) = H(Y) + H(X \given Y)$. Written the other way round, $H(X, Y) = H(X) + H(Y \given X)$. Subtracting the two shows $H(X) - H(X \given Y) = H(Y) - H(Y \given X)$: $Y$ tells as much about $X$ as $X$ tells about $Y$.
2. It is a divergence. Substituting the definitions, $I(X; Y) = \KL\big(p(x, y) \,\|\, p(x)\,p(y)\big)$, how far the joint distribution is from the one in which the two variables are independent. By Gibbs' inequality, $I(X; Y) \ge 0$, with equality exactly when $X$ and $Y$ are independent: on average, an observation never increases uncertainty.
3. It is bounded by what the observation can hold. Since conditional entropy of a discrete variable is never negative, $I(X; Y) = H(Y) - H(Y \given X) \le H(Y)$.

The third fact has a consequence the book returns to often. A yes/no answer has at most one bit of entropy, so it can carry at most one bit of information about anything: about a coin, a threshold, or a person's utility function. A comparison between two options is such an answer, and Section 16.6 shows that a typical comparison carries much less than the full bit.

A fourth fact concerns chains. If $Z$ is computed from $Y$ alone, possibly with added randomness, so that $X \to Y \to Z$ form a chain in which $Z$ depends on $X$ only through $Y$, then

This is the data processing inequality (Cover and Thomas, 2006, ch. 2): no processing of an observation, however clever, can create information about $X$ that the observation did not contain. Recording a person's graded answer as a forced binary choice, for example, can only lose information, which Section 20.4 uses to compare answer formats.

6.3.1 Mutual information of Gaussians #

For jointly Gaussian variables the conditional entropies come from the conditional variances of Section 4.5, so mutual information has a closed form. For two variables with correlation $\rho$, the conditional variance of $X$ given $Y$ is $\sigma_X^2(1 - \rho^2)$ for every observed value (Equation (4.14)), so by Equation (6.4)

Correlation 0.8 gives about 0.51 nats; correlation 0.99 gives about 1.96 nats; perfect correlation gives infinite information, because a continuous value would then be known exactly. The case that matters most for this book is noisy observations of a Gaussian vector.

With a single observation of a value with prior variance 1, this is $\tfrac12\log(1 + \sigma_n^{-2})$: about 2.31 nats, or 3.3 bits, when the noise standard deviation is 0.1. The formula contains the covariance and the noise level but not the observed values, for the reason we met in Section 4.5: how much a Gaussian model expects to learn depends on where it looks, not on what it finds.

6.4 Expected information gain #

We can now say which experiment to run. Let $\theta$ be what we want to learn and $\xi$ a choice of experiment: an input to evaluate, a question to ask, a pair of options to show. Each choice leads to an outcome $y$ we cannot predict exactly. Lindley (1956) proposed to measure the information an experiment provides by the expected reduction in the entropy of $\theta$, averaged over its possible outcomes, and to prefer the experiment for which this is largest:

The expected information gain is the mutual information between the unknown and the outcome, for the experiment $\xi$. Choosing experiments this way is the core of Bayesian experimental design, which Chaloner and Verdinelli (1995) review, and MacKay (1992) brought it to the selection of training data for neural networks.

The definition is stated in terms of $\theta$, which may have many dimensions, and computing posterior entropies over it is expensive. Symmetry of mutual information gives a second form in terms of the outcome, which is usually a single number or a yes/no answer:

The first term is how uncertain we are about the outcome. The second is how uncertain we would still be if we knew $\theta$, which is the noise of the experiment. An informative experiment is one whose outcome we cannot predict because we do not know $\theta$, not because the measurement is noisy. Put differently, it is the question on which the plausible values of $\theta$ disagree most. This form was popularized for classifiers and preference learning under the name BALD, Bayesian active learning by disagreement, in a 2011 preprint (Houlsby et al., 2011).

6.4.1 Twenty questions with noise #

The smallest problem that shows the criterion at work is locating a threshold. An unknown $\theta$ lies somewhere in $[0, 1]$, and we may ask "is $\theta$ below $x$?" for any $x$ we like. Answers are noisy: the probability of "yes" is $\Phi\big((x - \theta)/s\big)$, the standard normal distribution function of Section 4.1.1 used as an S-shaped response curve (a probit curve), with a noise scale $s$, so questions far from $\theta$ are answered reliably and questions close to it are a coin flip. The belief about $\theta$ is a grid of 128 cells, so the uniform prior has an entropy of exactly 7 bits, and a perfect yes/no answer could remove at most one of them.

Ask at the best $x$ a few times. The first question goes to the middle, where the answer is least predictable, and carries 0.90 bits in expectation at the default noise; the shortfall from a full bit is the noise. Each later question goes to the middle of the remaining belief. This is bisection, the binary search a programmer would write, rediscovered by the criterion.

Set the noise to its minimum and start over. Now the first several questions each carry a full bit, and eight to ten questions pin $\theta$ to a single cell, close to the $\log_2 128 = 7$ that perfect answers would need.

Ask at random $x$ instead. Questions far from the remaining belief are answered with near certainty, so they carry almost nothing; the entropy plateaus for several questions at a time. In our runs, twenty random questions at the default noise left about 4.1 bits of uncertainty, where twenty chosen by the criterion left about 2.7.

Raise the noise. Every answer is now partly a coin flip, and the expected gain of the best question drops well below a bit. Late in a session, the best questions sit close to $\theta$, where answers are least reliable, and each teaches less. Noisy answers can still be informative; there just have to be more of them.

This is not a toy. Measuring a perceptual threshold, such as the faintest contrast a person can detect, is the same problem, with a trial in place of a question, and Bayesian adaptive methods have been widely used in psychophysics since QUEST (Watson and Pelli, 1983). The method of Kontsevich and Tyler (1999) keeps a posterior over both the threshold and the slope of the psychometric function (the curve that gives the probability of a correct response at each stimulus strength) and sets each trial's stimulus to maximize the expected information gained by that trial. In their simulations and an experiment in which each trial is a choice between two alternatives, the threshold was estimated to within 2 dB (23%) in fewer than 30 trials, while the slope took about 300 trials for the same precision.

6.4.2 What the criterion does not say #

Two cautions apply to every use of the criterion in this book.

The criterion is myopic: it scores one experiment at a time, assuming no more will follow. A sequence of individually best experiments is not always the best sequence, although for many problems, including the threshold above, it is close.

More importantly for optimization, information about $\theta$ is not the same as progress toward a goal. An optimizer does not need to know the objective everywhere, only where its maximum is. Spending evaluations to learn the objective precisely in regions that are clearly poor is informative and wasteful. Entropy search changes the unknown: instead of the whole function, it asks for the information an evaluation provides about the location $\vx^\star$ of the maximum (Hennig and Schuler, 2012; Hernández-Lobato et al., 2014), or about the maximum value $f^\star$ (Wang and Jegelka, 2017). These are Equation (6.13) with a different $\theta$, and Section 12.7 develops them. For comparisons, the same move gives the information-based query rules of Section 19.3.

6.5 Information gain of a Gaussian process #

The last job is analysis: how much can $T$ evaluations of an unknown function reveal about it? The answer needs the model that Part II builds, so this section borrows three of its objects ahead of time. A reader meeting them for the first time can follow the figure now and return to the formulas after Chapter 8.

A Gaussian process prior, written $f \sim \GP(0, k)$, says that the values of $f$ at any finite set of inputs are jointly Gaussian with mean zero, and that the covariance between the values at two inputs $\vx$ and $\vx'$ is $k(\vx, \vx')$, the kernel of Section 3.1.1. The kernel matrix $\mK_A$ of a set $A$ of inputs is the covariance matrix of the values there. And the posterior variance $\sigma_t^2(\vx)$ is the variance of $f(\vx)$ after conditioning on $t$ observations with Equation (4.15).

With these the answer is already in hand. If we evaluate $f$ with Gaussian noise of variance $\sigma_n^2$ at a set $A$ of $T$ inputs, the observations depend on $f$ only through its values $\vf_A$ there, and Equation (6.12) gives

with $\mK_A$ the $T \times T$ kernel matrix of the chosen inputs. This is the information gain that Section 13.4.2 uses, in the same notation.

6.5.1 One evaluation at a time #

The determinant hides a simple sequential structure. Mutual information obeys the same chain rule as entropy, so the information from $T$ evaluations is the sum of what each one adds given the ones before it. The $t$th evaluation, at $\vx_t$, has predictive variance $\sigma_{t-1}^2(\vx_t) + \sigma_n^2$ given the first $t - 1$ observations, of which $\sigma_n^2$ would remain if $f$ were known. As in Equation (6.11), only the ratio of the two variances matters, and

where, as above, $\sigma_{t-1}^2(\vx_t)$ is the posterior variance at $\vx_t$ after the first $t - 1$ observations (Srinivas et al., 2010). Each evaluation contributes in proportion to the log of how uncertain the model was where it looked. An evaluation at an input the model already knows well adds almost nothing; one at an input where the model is as uncertain as its prior adds the full $\tfrac12\log(1 + \sigma_n^{-2})$, the most any single evaluation can add when the prior variance is 1.

The sum suggests a rule for gathering information quickly: always evaluate where the posterior variance is largest. This is uncertainty sampling, and MacKay (1992) showed that, for interpolation models with Gaussian noise of constant variance, maximizing the expected information about the model's parameters means sampling where the model's error bars are largest. It is not an optimizer, since it ignores the values it observes, but it is the yardstick for how much there is to learn.

6.5.2 The maximum information gain #

The most that any $T$ evaluations could teach about $f$ is

the maximum information gain, which Definition 13.3 states formally. Like the information of any fixed design, it depends on the kernel, the domain, and the noise, never on observed values, so it is a property of the problem before any data are collected. Computing the maximum exactly means searching over all sets of $T$ inputs, which is intractable. Uncertainty sampling comes within a factor $1 - 1/e \approx 0.63$ of it, because the information gain has diminishing returns, a property called submodularity (Srinivas et al., 2010).

6.5.3 Dimension and the number of evaluations #

How $\gamma_T$ grows as $T$ becomes large is a statement about the long run. In practice the question is what happens in the first hundred evaluations, and here the dimension of the input dominates. The figure computes Equation (6.16) under uncertainty sampling in five dimensions at once.

Read the default. With lengthscale 0.2, one dimension is covered after 5 evaluations, two after 21, and three after 84. In six and ten dimensions, the information curves lie on the dashed line for all 100 evaluations: each evaluation is nearly uncorrelated with every other, so the model learns about each evaluated point and generalizes to almost nothing else.

Count the regions. These numbers track $(1/\ell)^d$, the number of cells of side $\ell$ in the unit cube: 5, 25, and 125 for $d = 1, 2, 3$, and about 15,600 for $d = 6$. A model with lengthscale $\ell$ treats such cells as roughly independent, and it has to visit a fair fraction of them before it can say something about all of them (inference). The asymptotic rates of Table 13.1 apply only after that initial phase, which grows exponentially with the dimension (inference).

Scale the lengthscale by $\sqrt{d}$ and raise it to 0.3. Now the curves for different dimensions bunch together: 4, 9, 13, 34, and 68 evaluations cover the candidates in 1, 2, 3, 6, and 10 dimensions. The typical distance between two random points in the unit cube grows like $\sqrt{d/6}$, so a lengthscale proportional to $\sqrt{d}$ keeps the correlation between typical points roughly fixed. This is the idea behind the dimension-scaled lengthscale priors with which standard Bayesian optimization became competitive on real high-dimensional tasks (Hvarfner et al., 2024). It is not free: a longer lengthscale is a stronger assumption, that the objective varies slowly along every input, and when the assumption is wrong the model generalizes confidently and incorrectly. Figure 30.1 shows the distances behind the scaling, and Chapter 30 reports what the literature has found.

Switch to Matérn 5/2. Its functions are rougher than the default RBF kernel's at the same lengthscale (Section 7.5.3), so each evaluation speaks for less of the cube, and the information grows faster and more evaluations are needed to cover it.

Two cautions keep the picture honest. The figure measures information about the function everywhere, which overstates what an optimizer needs: it only has to rule out regions that cannot contain the maximum, and good acquisition functions skip most of the cube. And in ten dimensions, 800 candidates are sparse, so covering them is much easier than covering the cube. The figure shows the direction and rough size of the effect, not a budget for any particular problem (inference). For a real tuning problem with seven hyperparameters worked end to end, see Section 22.4.

6.5.4 From information to regret #

The reason $\gamma_T$ appears in every bound in Chapter 13 is the sequential sum Equation (6.16). An optimizer such as GP-UCB (Section 12.4), which evaluates the input where the posterior mean plus a multiple of the posterior standard deviation is largest, can only lose much at a step where the model is uncertain about the input it chooses, and large posterior variance at the chosen input is what makes a term of the sum large. Summing over steps, the total regret is controlled by the total information gathered, which is at most $\gamma_T$. The result, Theorem 13.3, bounds the cumulative regret after $T$ steps by a constant times $\sqrt{T\beta_T\gamma_T}$, where $\beta_T$ is the square of that multiple at step $T$, which sets the width of the confidence bound. A problem whose maximum information gain grows slowly is one where each mistake teaches a lot, so mistakes cannot go on for long. The figure above shows the other side: in high dimensions with a short lengthscale, $\gamma_T$ stays close to its largest possible value, $T$ times the gain of one fresh evaluation, for a long time, and the bound says nothing useful until it bends.

6.6 Exercises #

Further reading #

• Cover and Thomas (2006) is the standard textbook. Its chapter 2 develops entropy, relative entropy, and mutual information with their inequalities, chapter 8 treats differential entropy, and chapter 12 maximum entropy.
• MacKay (2003), chapter 2 onward, introduces the same ideas through inference and coding, with many worked examples; the book is free online.
• Shannon (1948) defined entropy as the measure of information in a message, and Kullback and Leibler (1951) defined the divergence as the information for discriminating between two hypotheses.
• Lindley (1956) proposed the expected information gain as the criterion for choosing experiments; Chaloner and Verdinelli (1995) review the Bayesian experimental design that grew from it.
• Srinivas et al. (2010) connected the information gain of a Gaussian process to the regret of Bayesian optimization, the link Chapter 13 builds on.