I regularly use the Expected Improvement (EI) as an acquisition function in Bayesian optimization (BO), but I’ve never fully understood the derivation of its closed form solution. This blog post aims to derive EI step by step.
Assume we have an optimization problem
In BO with EI as an acquisition function, we want to choose the point that is expected to improve the most upon the existing best observed point . is the number of observations thus far.
More formally, we can create an improvement function that tells us how much better the posterior of our probabilistic model at is than our best observed point . If it the posterior is less than the best observed point, we make zero.
is most commonly the posterior of a Gaussian process, which, at a specific input , is a normal distribution:
For EI, we want the expectation of the improvement:
If you’ve ever used EI or read about it in a paper, you might have been confused how to get the following closed form of EI:
where is the cumulative distribution function of the normal distribution and is the probability density function of the normal distribution. Let’s derive that closed form!
The upper limit of the expectation integral can actually stop at since we consider to be 0 when :
Substituting in the definition :
It’s not obvious how to solve this integral since it is in terms of a parametrized random variable . To find a closed form for the integral, we can use the reparameterization trick, which essentially replaces a parametrized random variable (in our case ) with a deterministic function multiplied by a non-parametrized random variable. As a side note, the reparametrization trick is most famously what makes variational autoencoders possible, but it also has applications across Bayesian optimization.
Our reparameterization is as follows: where . Therefore:
So, the limits of the integral become:
Now, substituting into the integral:
That above step just uses the definition of the CDF, recalling that is normally distributed. If you replace , you’ll see that the first term is already the same as our desired form. For the second term, we need to substitute in the equation for the PDF of the normal distribution and simplify. We then get:
Proof of the final integral
We can use the substitution (), so:
Just note that this . Therefore, putting this all together, we get desired final result:
As Martin Krasser points out, the two terms we get in this closed form represent the classic exploration-exploitation tradeoff. The first term is the exploitation term that that primarily takes into account the improvement of the mean over our best observed value (though is weighted by to reduce this exploitation under high uncertainty). The second term focuses on exploration by allocating more weight to predictions with large uncertainty.
Also, note that, in practice, we would implement EI using an if statement to set to zero if there is no predicted improvement.
Thanks to following resources: