I am thinking about a problem using Bayesian optimization with a Gaussian process. Bayesian optimization is explained well elsewhere; briefly the idea is that we sequentially evaluate a function where at each iteration the value we try is informed by the results from previous evaluations. The way we select the next value is by fitting a Gaussian process over the values we have already tried and choosing a point that maximizes an acquisition function (e.g. expected improvement, probability of improvement).

I am wondering if it is possible to use the area of the covariance function as a representation for total uncertainty and to specify a stopping criteria.


First, a note about terminology: the "covariance function" in GP parlance means the same thing as the kernel. Thus the area of a covariance kernel is just a constant depending on your hyperparameters; for a Gaussian kernel it's $(2 \pi)^{d/2} \sqrt{\mathrm{det}(\Sigma)}$.

What you actually meant to ask seems to be about the area contained within, say, a 95% confidence band. This is a measure of your posterior uncertainty about the underlying function.

Calculating it

Let's assume the GP has domain $\mathcal X \subseteq \mathbb R^n$ with mean function $m(x)$ and variance function $v(x)$, and say we want the area within $\gamma$ standard deviations (corresponding to a $2 \Phi(\gamma) - 1$ confidence band, i.e. $\gamma = 1.96$ is approximately 95%). Then the quantity in question is $$a = \int_{x \in \mathcal X} \left( \int_{y = m(x) - \gamma \sqrt{v(x)}}^{y = m(x) + \gamma \sqrt{v(x)}} \mathrm d y \right) \mathrm d x = \int_{x \in \mathcal X} 2 \gamma \sqrt{v(x)} \mathrm d x .$$

Note that this doesn't depend on the mean function at all.

Now, in most settings (including the usual Bayesian optimization), your GP is the posterior corresponding to observations $\{(X_i, y_i)\}_{i=1}^n$, and the prior has zero mean and covariance $k(x, y) + \sigma^2 I(x = y)$. (This corresponds to observations made with iid $\mathcal{N}(0, \sigma^2)$ noise; if you want a prior mean function, just subtract it from the observations.) Defining $$\mathbf K := \begin{bmatrix} k(x_1, x_1) & \cdots & k(x_1, x_n) \\ \vdots & \ddots & \vdots \\ k(x_n, x_1) & \cdots & k(x_n, x_n) \end{bmatrix} \quad\text{and}\quad \mathbf k(x) = \begin{bmatrix}k(x, x_1) \\ \vdots \\ k(x, x_n)\end{bmatrix} ,$$ the posterior variance function has the form $$ v(x) = k(x, x) - \mathbf k(x)^T \left( \mathbf K + \sigma^2 I \right)^{-1} \mathbf k(x) .$$ Some notes about this:

  • Though this depends on which $x$ you've picked, it doesn't depend on the observations $y$ at all.
  • If $\mathcal X$ is unbounded, as $x$ gets far away from the computed samples the variance goes to $k(x, x)$ (typically a constant) and so $a$ is infinite. This is unlikely to be an issue for you, since Bayesian optimization on unbounded domains without localizing priors rarely makes sense.
  • I doubt it's going to be analytically computable, though you might be able to get an analytic upper bound for particular kernels via Jensen's inequality. For low-dimensional $\mathcal X$ it shouldn't be too terrible to compute numerically.

What the function means

The doesn't make any claims about the maximum of that function, which is what we usually care about for Bayesian optimization.

Instead, this is the kind of criterion that's usually used for active learning of a function. That is, your goal is to query points to maximally reduce your uncertainty about the function as a whole (as measured by some uncertainty function). In Bayesian optimization, we want to reduce our uncertainty about the location of the maximum of the function, which is in some sense an easier problem. You should be able to imagine a GP posterior with high area but very certain maximal position, and likewise a GP posterior with relatively small area but pretty uncertain maximal position. So, this isn't necessarily great to use as an acquisition function for optimization, though it might make sense for active learning of functions.

Of course, you're not proposing to use it as an acquisition function, but instead as a measure of uncertainty to decide when to stop. This isn't crazy – when you understand the function well, you're more willing to stop – but since it doesn't distinguish between uncertainty about the maximum and uncertainty about areas you're pretty sure are not the maximum, it's not necessarily the most efficient way to do so.

  • $\begingroup$ I meant the area contained by an interval around the GP. Obviously the size of the interval would change the scale. If you have a GP with 3 points it stands to reason there is more uncertainty than if you have a GP with 30 points. In the Bayesian optimization case you are fitting a GP, selecting a new point, fitting a new GP – so you will get new data. My thought was just that using the area of the 95% interval would be an interesting way to characterize the uncertainty. $\endgroup$ – Ellis Valentiner Oct 21 '15 at 19:47
  • $\begingroup$ @user12202013 Oh. That's not what the "covariance function" means in a GP; let me edit to address. $\endgroup$ – Dougal Oct 21 '15 at 19:48
  • $\begingroup$ @user12202013 I've updated with a discussion of what you actually meant to ask about. :) $\endgroup$ – Dougal Oct 22 '15 at 19:12
  • $\begingroup$ There are methods that minimize the uncertainty of the minimizer distribution under gaussian processes. memming.wordpress.com/2012/02/19/active-bayesian-optimization $\endgroup$ – Memming Oct 22 '15 at 19:32
  • $\begingroup$ @Memming Yes – that's explicitly not what the OP is asking about. $\endgroup$ – Dougal Oct 22 '15 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.