Submodularity in Batch Active Learning and Survey Problems on Gaussian Random Fields

Understand

Many real-world datasets can be represented in the form of a graph whose edge weights designate similarities between instances.

• A discrete Gaussian random field (GRF) model is a finite-dimensional Gaussian process (GP) whose prior covariance is the inverse of a graph Laplacian.
• Minimizing the trace of the predictive covariance Sigma (V-optimality) on GRFs has proven successful in batch active learning classification problems with budget constraints.
• However, its worst-case bound has been missing.