Entropy search

As explained in Bayesian Optimization in Action

Entropy search is a Bayesian optimization decision procedure that selects evaluations expected to reduce uncertainty about the location of an objective's optimum.

Entropy search chooses the next costly observation for how much it is expected to reduce uncertainty about a target. Rather than sampling where an objective merely looks high or uncertain, it compares the possible outcomes of each action, averages their posterior entropies, and selects the action with the greatest expected entropy reduction. This makes information gain the decision rule. section 6.0 section 6.1.2

The target depends on the problem. To find a lost object, uncertainty concerns its location. In Bayesian optimization, the natural target is the optimizer x*, the input location at which a black-box objective f is maximal. A Gaussian process belief over f induces a probability distribution over x*, so an experiment is valuable when it sharpens that distribution. section 6.2.1 section 6.2

Apply entropy search as a decision procedure:

• Represent the current uncertainty about the quantity of interest with a probability distribution. section 6.1.2
• For each candidate action, consider the posterior distribution for every possible result. section 6.1.2
• Compute the expected posterior entropy by averaging across those results. section 6.1.2
• Choose the action with the lowest expected posterior entropy, equivalently the greatest expected reduction in uncertainty. section 6.1.2 section 6.4

Why binary search checks the middle

For a target in a sorted 100-element list with a uniform prior over positions, inspecting the middle divides the remaining possibilities into two equally sized cases. It minimizes expected posterior entropy, explaining binary search as an information-theoretic policy rather than just a halving trick. A nonuniform prior can instead shift the best query away from the middle, as in choosing phone-drop floors from an exponential belief about the highest safe floor. section 6.1.3 section 6.3.1

Figure 6.9 Expected posterior entropy in the location of the target as a function of the location within the list to inspect. The middle location is optimal, minimizing the expected entropy.

Compare expected posterior entropy across candidate list positions: the middle position is optimal under a uniform prior. section 6.1.3

Directly reducing uncertainty about x* is difficult. The optimizer distribution can be non-Gaussian and multimodal, and estimating it requires exponentially more samples as dimensionality grows. Max-value Entropy Search (MES) instead targets the optimal value f*, whose distribution is always one-dimensional. MES approximates acquisition scores with samples rather than a closed-form computation; a Sobol sequence supports sampling during policy initialization. section 6.2.1 section 6.4

Entropy search therefore emphasizes exploration that resolves the question that matters: where the optimum is, or in MES, what value it attains. It is a generic procedure for sequential decisions under uncertainty, but its BayesOpt form trades a direct optimizer-location objective for a more tractable optimal-value objective when dimensionality makes the former expensive. section 6.0 section 6.4

How Bayesian Optimization in Action covers it

How deep it goes

Derives expected posterior-entropy decisions, then explains optimizer-distribution difficulty and the MES approximation.

Examples

Uses a lost remote, a 100-element binary search, and phone-drop testing with a nonuniform prior.

What it assumes

Builds intuition from search examples while assuming familiarity with binary search for its algorithmic treatment.

What you can do after

Apply it via BoTorch by approximating MES acquisition scores with samples and Sobol initialization.

How it connects

Connects entropy, information theory, binary search, Gaussian processes, Bayesian optimization, acquisition functions, and Max-value Entropy Search.

liveBookmanning.com

Read Bayesian Optimization in Action on liveBook Get the book at manning.com

Related concepts

• entropyuses · Entropy is a quantitative measure of uncertainty or dispersion in a probability distribution and, more generally, of disorder in the possible states of a system.
• policykind of · A policy is a rule, strategy, or mapping that governs or determines decisions, actions, permissions, or behavior under specified conditions.
• posterior probabilityuses · A posterior probability or distribution expresses the probability assigned to an event, hypothesis, or unknown quantity conditional on observed evidence and prior information.
• binary searchproduces · Binary search is an algorithm that locates a target or boundary in an ordered collection by repeatedly comparing with a midpoint and halving the remaining search range.
• information theoryuses · Information theory is the mathematical study of quantifying information and uncertainty, and of representing, encoding, storing, processing, and communicating information.

This explainer was generated by Manning's knowledge graph from the text of Bayesian Optimization in Action. The section links point to the parts of the book it draws on.