Gaussian process regression: sudden increase of the prediction's variance I am trying to do a variance-based uncertainty sampling like in the book "Active Learning" by Burr Settles, page 18, Figure 2.6. Link to the book: http://active-learning.net/ 

I use Gaussian process regressor from scikit-learn to fit a 1-D Gaussian function. The parameters of the regressor are the same as in this example (a noise-free case) http://scikit-learn.org/stable/auto_examples/gaussian_process/plot_gpr_noisy_targets.html

kernel = C(1.0, (1e-3, 1e3)) * RBF(10, (1e-2, 1e2))
gp = GaussianProcessRegressor(kernel=kernel, n_restarts_optimizer=9)


Initially, I randomly choose two training data points and fit the curve based on them. The Figure below shows the fit (top) and the variance (bottom)



Then I add one more training data point taken at the place where the variance is the largest, and re-fit the data.



I repeat this process for a few iterations and the interpolation improves with each iteration, as expected. For example, this is the iteration 7:



However, at the next iteration, the interpolation is worse. The variance suddenly increases:



The next few iterations are fine again. For example, iteration 9:



But at the iteration 11 I get a large variance again:

 

Iterations 12 through 15 show very small variance again - the curve is interpolated very well at those iterations. I stopped at 15.

Why does this sudden increase of variance happen at certain steps? How to avoid it?

When I change the parameter n_restarts_optimizer, this behavior is still observed but at different iteration steps. For example, when n_restarts_optimizer=8, the increase in variance is at iteration 9. When n_restarts_optimizer=7, the increase in variance is at iteration 4, 10, 11. When n_restarts_optimizer=4, the increase in variance is at iteration 7, 14. 

When I change the parameter length_scale in the RBF kernel from 10 to 1.0 I don't see this increase in variance anymore. However, when I make it even smaller (length_scale = 0.1) it appears again.
Hmm, I've seen this before. It seemed to be some kind of overfitting on the time component where only very nearby samples were taken into account, before defaulting to the prior (which has zero mean). That would explain why increasing the length scale would help. 

Do you see large changes in the hyper parameters of the kernel between iterations (gp.kernel_.get_params())? You could consider using the hyper parameters from a previous iteration as initial guess for the next iteration.