11
$\begingroup$

I am using Gaussian process (GP) for regression.

In my problem it is quite common for two or more data points $\vec{x}^{(1)},\vec{x}^{(2)},\ldots$ to be close to each other, relatively to the length scales of the problem. Also, observations can be extremely noisy. To speed up computations and improve measurement precision, it seems natural to merge/integrate clusters of points that are close to each other, as long as I care about predictions on a larger length scale.

I wonder what is a fast but semi-principled way of doing this.

If two data points were perfectly overlapping, $\vec{x}^{(1)} = \vec{x}^{(2)}$, and the observation noise (i.e., the likelihood) is Gaussian, possibly heteroskedastic but known, the natural way of proceeding seems to merge them in a single data point with:

  • $\vec{\bar{x}} \equiv \vec{x}^{(k)}$, for $k=1,2$.

  • Observed value $\bar{y}$ which is an average of observed values $y^{(1)}, y^{(2)}$ weighted by their relative precision: $\bar{y} = \frac{\sigma_y^2(\vec{x}^{(2)})}{\sigma_y^2(\vec{x}^{(1)}) + \sigma_y^2(\vec{x}^{(2)})} y^{(1)} + \frac{\sigma_y^2(\vec{x}^{(1)})}{\sigma_y^2(\vec{x}^{(1)}) + \sigma_y^2(\vec{x}^{(2)})} y^{(2)}$.

  • Noise associated with the observation equal to: $\sigma_y^2(\bar{x}) = \frac{\sigma_y^2(\vec{x}^{(1)}) \sigma_y^2(\vec{x}^{(2)})}{\sigma_y^2(\vec{x}^{(1)}) + \sigma_y^2(\vec{x}^{(2)})}$.

However, how should I merge two points that are close but not overlapping?

  • I think that $\vec{\bar{x}}$ should still be a weighted average of the two positions, again using the relative reliability. The rationale is a center-of-mass argument (i.e., think of a very precise observation as a stack of less precise observations).

  • For $\bar{y}$ same formula as above.

  • For the noise associated to the observation, I wonder if in addition to the formula above I should add a correction term to the noise because I am moving the data point around. Essentially, I would get an increase in uncertainty that is related to $\sigma_f^2$ and $\ell^2$ (respectively, signal variance and length scale of the covariance function). I am not sure of the form of this term, but I have some tentative ideas for how to compute it given the covariance function.

Before proceeding, I wondered if there was already something out there; and if this seems to be a sensible way of proceeding, or there are better quick methods.

The closest thing I could find in the literature is this paper: E. Snelson and Z. Ghahramani, Sparse Gaussian Processes using Pseudo-inputs, NIPS '05; but their method is (relatively) involved, requiring an optimization to find the pseudo-inputs.

$\endgroup$
  • 1
    $\begingroup$ By they way, I appreciate that I could use approximate inference or some large-scale methods, but this is another point. $\endgroup$ – lacerbi Aug 31 '15 at 15:01
4
$\begingroup$

Great question and what you are suggesting sounds reasonable. However personally I would proceed differently in order to be efficient. As you said two points that are close provide little additional information and hence the effective degrees of freedom of the model is less than the number of data points observed. In such a case it may be worth using Nystroms method which is described well in GPML (chapter on sparse approximations can be seen http://www.gaussianprocess.org/gpml/). The method is very easy to implement and recently been proved to be highly accurate by Rudi et al. (http://arxiv.org/abs/1507.04717)

$\endgroup$
  • $\begingroup$ Thanks, Nystrom's method seems an interesting approach, I'll look into it. However, in my first post I had forgotten to mention that the noise in the observations can be very high (possibly larger than the signal), so that averaging nearby points will provide additional information. $\endgroup$ – lacerbi Sep 5 '15 at 12:55
  • 1
    $\begingroup$ Well that is actually even more of a reason to use Nystroms method. High noise reduces the effective degrees of freedom so if only the first m eigenvalues hold the signal and the rest are simply noise then Nystroms method will drop the all those less than the first m. I think it will fit the bill for what you are looking for. Best of luck! $\endgroup$ – j__ Sep 5 '15 at 13:01
  • $\begingroup$ The Nystrom method is what I would suggest (+1). Simply merging the points into one may run into problems with estimating the marginal likelihood of the model as the two genuine datapoints are unlikely to have the same effect as one single point. My advice would be to keep the two points separate, but to find a way of making the computation less expensive, which the Nystrom emthod should achieve, $\endgroup$ – Dikran Marsupial Sep 5 '15 at 13:16
  • $\begingroup$ Which kind of problems? If you consider the case of two overlapping points with Gaussian noise, then the averaging method is exact (as long as you keep track of the decrease in observation noise). I don't see why the same argument should not work for points that are close wrt to the length scale of the problem (with the approximation becoming worse with increasing distance). Perhaps this is what Nystrom's method does, in a more principled way -- I still need to understand the details. I am curious to compare it with the averaging method, both in terms of accuracy and speed. Thanks $\endgroup$ – lacerbi Sep 5 '15 at 14:18
  • 1
    $\begingroup$ @Seeda we are not using nystrom as a preconditioned effectively rather than the usual reduced time conpkexity, so yes. $\endgroup$ – j__ Dec 27 '16 at 18:50
1
$\begingroup$

I have also been investigating merging observations when performing Gaussian Process regression. In my problem I have only one covariate.

I'm not sure I necessarily agree that the Nystrom approximation is preferable. In particular, if a sufficient approximation can be found based on a merged dataset, calculations could be quicker than when one uses the Nystrom approximation.

Below are some graphs showing 1000 data points and the posterior GP mean, the posterior GP mean with merged records, and the posterior GP mean using the Nystrom approximation. Records were grouped based on equal sized buckets of the ordered covariate. The approximation order relates to the number of groups when merging records and the order of the Nystrom approximation. The merging approach and the Nystrom approximation both produce results that are identical to standard GP regression when when the approximation order is equal to the number of points.

In this case, when the order of the approximation is 10 the merging approach seems preferable. When the order is 20, the mean from the Nystrom approximation is visually indistinguishable from the exact GP posterior mean, although the mean based on merging observations is probably good enough. When the order is 5, both are pretty poor.

enter image description here enter image description here enter image description here

$\endgroup$

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.