Near-optimal sensor placements in Gaussian processes

ABSTRACT

When monitoring spatial phenomena, which are often modeled as Gaussian Processes (GPs), choosing sensor locations is a fundamental task. A common strategy is to place sensors at the points of highest entropy (variance) in the GP model. We propose a mutual information criteria, and show that it produces better placements. Furthermore, we prove that finding the configuration that maximizes mutual information is NP-complete. To address this issue, we describe a polynomial-time approximation that is within (1 -- 1/e) of the optimum by exploiting the submodularity of our criterion. This algorithm is extended to handle local structure in the GP, yielding significant speedups. We demonstrate the advantages of our approach on two real-world data sets.

REFERENCES

• 1: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 2: Cressie, N. A. (1991). Statistics for spatial data. Wiley.
• 3: Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J., & Hong, W. (2004). Model-driven data acquisition in sensor networks. VLDB.
• 4: Golub, G., & Van Loan, C. (1989). Matrix computations. Johns Hopkins.
• 5: H. González-Banos, A randomized art-gallery algorithm for sensor placement, Proceedings of the seventeenth annual symposium on Computational geometry, p.232-240, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378674]
• 6: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 7: Ko, C., Lee, J. & Queyranne, M. (1995). An exact algorithm for maximum entropy sampling. Ops Research, 43, 684--691.
• 8: Krause, A., & Guestrin, C. (2005). A note on the budgeted maximization of submodular functions (Technical Report). CMU-CALD-05-103.
• 9: David J. C. MacKay, Information Theory, Inference & Learning Algorithms, Cambridge University Press, New York, NY, 2002
• 10: McKay, M., Beckman, R., & Conover, W. (1979). A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 21, 239--245.
• 11: Nemhauser, G., Wolsey, L., & Fisher, M. (1978). An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14, 265--294.
• 12: Nam-Ky Nguyen , Alan J. Miller, A review of some exchange algorithms for constructing discrete D-optimal designs, Computational Statistics & Data Analysis, v.14 n.4, p.489-498, Nov. 1992 [doi>10.1016/0167-9473(92)90064-M ]
• 13: Paciorek, C. (2003). Nonstationary gaussian processes for regression and spatial modelling. Doctoral dissertation, CMU.
• 14: Ramakrishnan, N., Bailey-Kellogg, C., Tadepalli, S., & Pandey, V. (2005). Gaussian processes for active data mining of spatial aggregates. SIAM Data Mining.
• 15: Ribeiro Jr., P. J., & Diggle, P. J. (2001). geor: A package for geostatistical analysis. R-NEWS Vol I, No 2. ISSN 1609--3631.
• 16: Seeger, M. (2004). Gaussian processes for machine learning. International Journal of Neural Systems, 14, 69--106.
• 17: Storkey, A. J. (1999). Truncated covariance matrices and Toeplitz methods in gaussian processes. ICANN99.
• 18: Widmann, M., & Bretherton, C. S. (1999). 50 km resolution daily precipitation for the pacific northwest. http://www.jisao.washington.edu/data_sets/widmann/.