7810ccd41bf26faaa2c4e1f20db70a71-Reviews.html

The authors suggest the use of a criterion, Σ-Optimality, for active learning in Gauss-Markov random fields. The criterion itself was originally proposed by Garnett et al for active surveying, but it does not appear that the submodular property was recognized in that previous work. Labeled and unlabeled are embedded in a graph nodes represent both labeled and unlabled data and edge weights, computed via a kernel, capture similarity. The motivation for an active approach is that acquiring labels on the full data set may incur some cost (presumably greater than computing the edge weights over all data) so a criterion is used to determine which of the remaining unlabeled data should be labeled. The authors establish that the criterion satifies the submodular monotone property and as such greedy selection achieve (1-1/e) performance relative to optimal selection.