Entropy measures uncertainty in a random variable from its probability distribution. For a discrete variable X, it is H(X) = −Σx p(x) log2 p(x): outcomes that are both possible and surprising contribute more than outcomes that are nearly certain. Entropy is measured in bits when the logarithm has base 2. It describes variability in possible values, rather than the predictive standard deviation used for a Gaussian process. section 6.1.1
A biased coin
For a Bernoulli variable with probability p of heads, H(X) = −p log2 p − (1−p) log2(1−p). Entropy is nonnegative, reaches its maximum when p = 0.5, and falls as either outcome becomes nearly certain. A fair coin is therefore more uncertain than a heavily biased one. section 6.1.1 section 6.1.1
Figure 6.1 Entropy of a Bernoulli random variable as a function of the success probability. The entropy is maximized (uncertainty is at its highest) when the success probability is at 0.5.
The curve makes the central idea visible: uncertainty peaks when heads and tails are equally likely, not when one outcome is expected. section 6.1.1
Entropy becomes a decision tool when an action can change a probability distribution. Compare actions by their expected posterior entropy: prefer the action expected to leave the least uncertainty, or equivalently to produce the greatest expected reduction in entropy. Searching the likely living-room region for a lost remote reduces uncertainty; searching a bathroom where the remote cannot be does not. section 6.1.2 section 6.4
This same principle explains several search choices:
- Binary search inspects the middle of a uniformly likely sorted list, because the comparison splits the possible target locations and minimizes expected posterior entropy. section 6.1.3
- A nonuniform prior can move the best test away from the midpoint, as in selecting a phone-drop floor when lower safe floors are believed more likely. section 6.3.1
- Bayesian optimization can select experiments that reduce uncertainty about an objective function’s optimum. section 6.2
In BayesOpt, the optimizer location x* is a natural target, but its GP-induced distribution can be complicated, multimodal, and increasingly hard to estimate in higher dimensions. Max-value Entropy Search (MES) instead targets the optimal value f*, whose distribution is one-dimensional, and uses an approximation to score candidate evaluations by expected entropy reduction. section 6.2.1 section 6.4
MES in practice
BoTorch provides MES as qMaxValueEntropy. Initialize it with a GPyTorch GP model and candidate samples, which may come from a Sobol sequence; more candidate samples improve approximation fidelity at greater computational cost. On a one-dimensional Forrester-function run, MES finds the global optimum after five of ten queries. section 6.2.2 section 6.2.2
