Marshal Sinaga | Probability Improvement and Expected Improvement Acquisition Function

This post assumes the reader has a prequisite knowledge about Bayesian optimization. Recall that Bayesian optimization is a zero-th order optimization method which aims to find the optimum $x^{*}$ of a black-box function $f : X \to R$ . Bayesian optimization requires two important components, that is the surrogate model and the acquisition function. Due to black-box nature of $f$ , we introduce a surrogate function and instead perform the optimization w.r.t. this new function. In common settings, we utilize a Gaussian process (GP) as our surrogate model. The motivation comes from the Bayesian philosophy where we start with a belief and iteratively update it as we encounter data which explains the true distribution called the posterior distribution.

This post is focused on the second component, that is the acquisition function. This function governs the next input $x_{t}$ to be evaluated, with $t$ denotes the particular time step of the acquisition. The acquired data has the optimum statistical properties w.r.t. our surrogate model, i.e. the expectation, entropy, etc. Now, let us narrowing our scope again into two specific acquisition functions, that is the probability improvement and the expected improvement.

Probability Improvement

We first give the definition of improvement. Given the incummbent best value $x^{*} \in X$ and an arbitrary input $x \in X$ , we define the improvement $I (x)$ as

\begin{array}{r} (1) & I (x) = max (f (x) - f (x^{*}), 0) \end{array}

Note that we abuse the notation $x^{*}$ for a while as previously $x^{*}$ denotes the global optimum of the function $f$ . It is obvious that $I (x) \in [0, + \infty] \forall x \in X$ and $x = x^{*} \to I (x) = 0$ . Recall that we employ GP as the proxy of $f$ . For a particular data $x$ , the function value $f (x)$ follows a Gaussian distribution

f (x) \sim N (μ (x), σ^{2} (x))

Commonly we perform reparameterization-trick to draw samples from $f (x)$ . First, we introduce a random variable $z$ drawn from a standard normal distribution $N (0, 1)$ . It is known that drawing samples from such distribution is relatively easy. Leveraging this random variable, we obtain a new sample $f (x) = μ (x) + σ (x) z$ . Substituting the new definition will give us

I (x) = max (f (x) - f (x^{*})) = max (μ (x) + σ (x) z - f (x^{*}), 0) z \sim N (0, 1)

The probability improvement evaluates how likely the candidate $x$ gives us a positive improvement. Recall that we evaluate the probability w.r.t. $N (μ (x), σ^{2} (x))$ . Mathematically, we can write $PI (x)$ as

PI (x) = p (I (x) > 0) ⟺ p (f (x) > f (x^{*}))

By applying the additive and constant scaling properties of normal distribution, we obtain the following analytical form

PI (x) = 1 - Φ (z_{0}) = Φ (- z_{0}) = Φ (\frac{μ (x) - f (x^{*})}{σ (x)})

with $Φ (z) ≜ CDF (z)$ and $z_{0} = \frac{f (x^{*}) - μ (x)}{σ (x)}$

Expected Improvement

Unlike the probability improvement, the expected improvement (EI) (as the name suggests) aims to evaluate the expected value of $I (x)$ over $f$ . Intuitively, this criterion evaluates the average magnitude of the improvement.

\begin{array}{r} (2) & EI (x) ≜ E [I (x)] = \int_{- \infty}^{\infty} I (x) ϕ (z) \end{array}

Substituting the definition of probability improvement, we then obtain

EI = \int_{- \infty}^{\infty} I (x) ϕ (z) = \int_{- \infty}^{\infty} max (f (x) - f (x^{*}), 0) ϕ (z) d z

In order to compute the integral, we need to get rid of the $max$ operator. First, we decompose the integral into two parts. The first part is where $I (x) \leq 0$ and the later part is where $I (x) > 0$ . To set the bound for each integral, recall that we can perform the reparameterization trick to rewerite $f (x)$ , that is $f (x) = f (x^{*}) \to μ + σ z = f (x^{*}) \to z_{0} = \frac{f (x^{*}) - μ}{σ}$ . Thus, we can write $EI (x)$ as

EI (x) = \int_{- \infty}^{z_{0}} I (x) ϕ (z) d z + \int_{z_{0}}^{\infty} I (x) ϕ (z) d z

Observe that the first term vanishes to $0$ since $\forall z \leq z_{0}$ we have $I (x) = 0$ . Therefore, we only need to evaluate the second part of the integral.

\begin{aligned} EI (x) & = \int_{z_{0}}^{\infty} max (f (x) - f (x^{*}), 0) ϕ (z) d z = \int_{z_{0}}^{\infty} μ (x) + σ (x) z - f (x^{*}) ϕ (z) d z \\ = \int_{z_{0}}^{\infty} (μ - f (x^{*})) ϕ (z) d z + \int_{z_{0}}^{\infty} σ z \frac{1}{\sqrt{2 π}} \exp (\frac{- 1}{2} z^{2}) d z \\ = (μ - f (x^{*})) \int_{z_{0}}^{\infty} ϕ (z) d z + \frac{σ}{\sqrt{2 π}} \int_{z_{0}}^{\infty} z \exp (\frac{- 1}{2} z^{2}) d z \\ = (μ - f (x^{*})) (1 - Φ (z_{0})) - \int_{z_{0}}^{\infty} {(\exp (\frac{- 1}{2} z^{2}))}^{'} d z \\ = (μ - f (x^{*})) (1 - Φ (z_{0})) - \frac{σ}{\sqrt{2 π}} {[\exp (\frac{- 1}{2} z^{2})]}_{z_{0}}^{\infty} \\ = (μ - f (x^{*})) (1 - Φ (z_{0})) + σ ϕ (z_{0}) \\ = (μ - f (x^{*})) Φ (\frac{μ - f (x^{*})}{σ}) + σ ϕ (\frac{μ - f (x^{*})}{σ}) \end{aligned}

The last row comes from the fact that the normal density is symmetric, i.e., $ϕ (z_{0}) = ϕ (- z_{0})$ . $EI (x)$ takes high value when $μ > f (x^{*})$ As a side note, $EI$ requires the uncertainty $σ > 0$ since $σ = 0 \to EI (x) = 0$ . Finally, we intoroduce a hyperparameter $ξ$ which control the degree of exploration

\begin{array}{r} (3) & EI (x; ξ) = (μ - f (x^{*}) - ξ) Φ (\frac{μ - f (x^{*}) - ξ}{σ}) + σ ϕ (\frac{μ - f (x^{*}) - ξ}{σ}) \end{array}

Note that $ξ = 0 \to EI (x; ξ) = EI (x)$

References

Kamperis, S. (2021) Acquisition functions in Bayesian Optimization, https://ekamperi.github.io/machine%20learning/2021/06/11/acquisition-functions.html.