Σ-Optimality for Active Learning on Gaussian Random Fields
A common classifier for unlabeled nodes on undirected graphs uses label propagation from the labeled nodes, equivalent to the harmonic predictor on Gaussian random fields (GRFs). For active learning on GRFs, the commonly used V-optimality criterion queries nodes that reduce the L 2 (regression) loss. V-optimality satisfies a submodularity property showing that greedy reduction produces a (1 − 1/e) globally optimal solution. However, L 2 loss may not characterise the true nature of 0/1 loss in classification problems and thus may not be the best choice for active learning. We consider a new criterion we call Σ-optimality, which queries the node that minimizes the sum of the elements in the predictive covariance. Σ-optimality directly optimizes the risk of the surveying problem, which is to determine the proportion of nodes belonging to one class. In this paper we extend submodularity guarantees from V-optimality to Σ-optimality using properties specific to GRFs. We further show that GRFs satisfy the suppressor-free condition in addition to the conditional independence inherited from Markov random fields. We test Σ-optimality on real-world graphs with both synthetic and real data and show that it outperforms V-optimality and other related methods on classification.
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. The authors should be careful to note that this 
      optimality is with respect to the criterion itself and not with 
      respect to classification accuracy. While the empirical results do 
      give good classification performance, the criterion itself is only a 
      surrogate. Several existing criterion are mentioned in the 
      introduction (Settles, Krause et al, Ji and Han) to which the authors 
      compare their criterion. One item which is only given limited 
      discusion is the computational complexity of computing the reward. For 
      example, both V-optimality and Sigma-optimality require computing the 
      inverse of the graph Laplacian over the remaining unlabeled data. Some 
      of the other criterion have lower complexity. This is an important 
      issue since the problem is cast in terms of costs and since 
      performance of all criterion will eventually approach each other 
      (since they are presumably solving the same classification problem 
      following selection) a fairer comparison would include the cost of 
      computing the reward. It may be that the proposed method wins here, 
      but it at least bears some mention. Why do the authors cite 
      Streeter and Golovin for results regarding submodular set functions? 
      Shouldn't this be Nemhauser et al? Section 2.3 misstates several 
      things. The intractability of subset selection is not a consequence of 
      submodularity, it is simply a consequence of the combinatorics. 
      Furthermore, this does not mean that a greedy solution is "required". 
      Other strategies may have lower complexity and outperform the greedy 
      selection. It is merely, that by establishing the property, greedy 
      selection has certain guarantees relative to the optimal selection. 
      The fact that the criterion of interest was originally proposed by 
      Garnett et al in 2012 should be mentioned much earlier. This changes 
      the abstract from "We propos a new criterion" to something more 
      accurate, such as "We analyze a previously suggested criterion and 
      demonstrate its utility...". Establishing the sumodular 
      property as well as the suppressor free properties are interesting. 
      Empirical results are suffcient. Modulo the comments 
      above, the paper is fairly clear. The results are interesting and the 
      analysis, though limited, represents a contribution. minor 
      comments: Figure 3 lacks a horizontal axis. I assume it is 
      probability of correct classification, but the authors give an 
      ambiguous description in the caption.