Nonmyopic active learning of Gaussian processes: an exploration-exploitation approach

ABSTRACT

When monitoring spatial phenomena, such as the ecological condition of a river, deciding where to make observations is a challenging task. In these settings, a fundamental question is when an active learning, or sequential design, strategy, where locations are selected based on previous measurements, will perform significantly better than sensing at an a priori specified set of locations. For Gaussian Processes (GPs), which often accurately model spatial phenomena, we present an analysis and efficient algorithms that address this question. Central to our analysis is a theoretical bound which quantifies the performance difference between active and a priori design strategies. We consider GPs with unknown kernel parameters and present a nonmyopic approach for trading off exploration, i.e., decreasing uncertainty about the model parameters, and exploitation, i.e., near-optimally selecting observations when the parameters are (approximately) known. We discuss several exploration strategies, and present logarithmic sample complexity bounds for the exploration phase. We then extend our algorithm to handle nonstationary GPs exploiting local structure in the model. We also present extensive empirical evaluation on several real-world problems.

REFERENCES

• 1: Maria-Florina Balcan , Alina Beygelzimer , John Langford, Agnostic active learning, Proceedings of the 23rd international conference on Machine learning, p.65-72, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143853]
• 2: Caselton, W., & Zidek, J. (1984). Optimal monitoring network designs. Statist. Prob. Lett., 2, 223--227.
• 3: Castro, R., Willett, R., & Nowak, R. (2005). Faster rates in regression via active learning. NIPS.
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: Cressie, N. A. (1991). Statistics for spatial data. Wiley.
• 6: Robert B. Gramacy , Herbert K. Lee, III, Bayesian treed gaussian process models, University of California at Santa Cruz, Santa Cruz, CA, 2005
• 7: Gretton, A., Borgwardt, K., Rasch, M., Schlkopf, B., & Smola, A. (2006). A kernel method for the two-sample-problem. NIPS.
• 8: Carlos Guestrin , Andreas Krause , Ajit Paul Singh, Near-optimal sensor placements in Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.265-272, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102385]
• 9: Harmon, T. C., Ambrose, R. F., Gilbert, R. M., Fisher, J. C., Stealey, M., & Kaiser, W. J. (2006). High resolution river hydraulic and water quality characterization using rapidly deployable networked infomechanical systems (nims rd) (Technical Report 60). CENS.
• 10: Ko, C., Lee, J., & Queyranne, M. (1995). An exact algorithm for maximum entropy sampling. Ops Res, 43.
• 11: Koller, D., & Friedman, N. (2007). Structured probabilistic models. Electronic Preprint.
• 12: Krause, A., & Guestrin, C. (2007). Nonmyopic active learning of gaussian processes: An exploration-exploitation approach (Techn. Report CMU-ML-07-105).
• 13: Nott, D. J., & Dunsmuir, W. T. M. (2002). Estimation of nonstationary spatial covariance structure. Biomet., 89.
• 14: Cheng Soon Ong , Alexander J. Smola , Robert C. Williamson, Learning the Kernel with Hyperkernels, The Journal of Machine Learning Research, 6, p.1043-1071, 12/1/2005
• 15: Paciorek, C. (2003). Nonstationary gaussian processes for regression and spatial mod. Doctoral dissertation, CMU.
• 16: Carl Edward Rasmussen , Christopher K. I. Williams, Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning), The MIT Press, 2005
• 17: Seo, S., Wallat, M., Graepel, T., & Obermayer, K. (2000). Gaussian process regression: Active data selection and test point rejection. IJCNN (pp. 241--246).
• 18: Shewry, M., & Wynn, H. (1987). Maximum entropy sampling. Journal of Applied Statistics, 14, 165--170.
• 19: Storkey, A. J. (99). Truncated covariance matrices and toeplitz methods in gaussian processes. ICANN.
• 20: Tresp, V. (2000). Mixtures of gaussian processes. NIPS (pp. 654--660).
• 21: Zhu, Z., & Stein, M. L. (2006). Spatial sampling design for prediction with estimated parameters. J Agric., Biol. Env. Statist., 11, 24--49.