Improvement, and its expectation

Define the improvement a new evaluation at x would deliver: I(x) = max( f(x) − f^*_n, 0 ). Under the posterior, f(x) is Gaussian, so I(x) is a censored Gaussian — and its expectation has a closed form:

EI_n(x) = 𝔼[I(x)] = (μ_n(x) − f^*_n)·Φ(z) + σ_n(x)·φ(z)

μ_n, σ_n the posterior mean and standard deviation at x · f*_n the best value seen so far · z = (μ_n − f*_n)/σ_n the standardized improvement · Φ, φ the standard normal CDF and density

with Φ and φ the standard normal CDF and PDF. The two terms are exploitation and exploration wearing mathematical clothes: the first pays for a mean above the incumbent (weighted by the probability the improvement is real), the second pays for spread — a chance of a large upside even when the mean is unpromising. At z = 0 (mean exactly at the incumbent), EI = σ·φ(0) ≈ 0.40σ: pure uncertainty value.

Faded derivation: EI in closed form

1Write EI as an integral over the posterior for f(x) (drop subscripts: mean μ, sd σ, incumbent f^*).

EI = ∫_f*^∞ (v − f^*) · 𝒩(v; μ, σ²) dv

Values below f^* contribute zero improvement, so the integral starts at f^*.

2Standardize: substitute v = μ + σu and z = (μ − f^*)/σ.

EI = σ ∫_−z^∞ (u + z) φ(u) du

The lower limit v = f^* maps to u = (f^* − μ)/σ = −z, and (v − f^*) = σ(u + z).

3Evaluate ∫_−z^∞ u·φ(u) du using the identity φ′(u) = −uφ(u).

∫_−z^∞ uφ(u) du = [−φ(u)]_−z^∞ = φ(−z) = φ(z)

The Gaussian PDF is its own (negated) antiderivative under multiplication by u, and it is symmetric.

4Evaluate the remaining piece z·∫_−z^∞ φ(u) du.

z ∫_−z^∞ φ(u) du = z (1 − Φ(−z)) = z·Φ(z)

Tail probability plus symmetry of Φ.

5Assemble, un-standardize, and sanity-check z = 0.

EI = σ[ zΦ(z) + φ(z) ] = (μ − f^*)Φ(z) + σφ(z)

At z = 0: EI = σφ(0) = σ/√(2π) ≈ 0.399σ — a point whose mean merely ties the incumbent is still worth two-fifths of its standard deviation. Uncertainty alone has cash value.

Five steps, one substitution, two normal identities. This is the same derivation Jones et al. relied on in 1998 — try to reproduce it cold.

← The Maths II: Acquisition Functions The acquisition zoo →