{'fraction_non_alphanumeric': 0.05470864795554922, 'fraction_numerical': 0.01182504630289215, 'mean_word_length': 4.146260997067449, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Submodularity in Batch Active Learning and Survey Problems on Gaussian Random Fields

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. We show that the V-optimality on GRFs as a function of the batch query set is submodular and hence its greedy selection algorithm guarantees an (1-1/e) approximation ratio. Moreover, GRF models have the absence-of-suppressor (AofS) condition. For active survey problems, we propose a similar survey criterion which minimizes 1'(Sigma)1. In practice, V-optimality criterion performs better than GPs with mutual information gain criteria and allows nonuniform costs for different nodes.


Introduction
In many real-world applications, such as author classification based on coauthorship graphs, one or more output variables need to be predicted from a subset of queryable inputs, constrained by a budget. In batch active learning applications, an algorithm refines its prediction by generating a list of queries for domain experts to answer [2,5,8]. In both cases, we consider the situation where the similarities between all instances, both labeled and unlabeled, are known a-priori. We formulate these similarities by a graph G = (V, E) with edge weights W . The goal is to optimize the subset of nodes to query within the budget so that the risk in prediction can be minimized. One common risk is the predictive variance, measured by the trace of the covariance matrix of multivariate outputs. Minimizing this risk is known as the V-optimality criterion.
Commonly used models for these subset selection or batch active learning problems are discrete Gaussian random fields (GRF) [2,5], finite-dimensional Gaussian processes (GP) [1], and linear regression with prior knowledge of covariances [3,4]. GRFs formulate the input-output correspondence by the conditional distribution of a (maybe improper) gaussian prior whose inverse covariance is set to be the graph Laplacian, sometimes with diagonal regularization. Finite-dimensional GPs define the prior as N (0, W ), where W is an arbitrary covariance matrix. Finally, linear regression with prior knowledge of covariance is essentially a finite-dimensional GP with linear covariance.
GPs have been used as a base model for both subset selection and active learning [1]. One minor issue is that they require W to be positive-semidefinite. However a major issue is that they do not have a provable lower bound for optimality [4]. Instead, [1] used an alternative mutual information gain (MIG) criterion for selecting nodes for query. The MIG-criterion is naturally a normalized, monotone, and submodular function. As a result, a greedy algorithm gaurantees an (1 − 1/e) approximation ratio. However, there is not classification-related risk function associated and the log determinates of covariance submatrices are sensitive to small eigenvalues, which can be a problem.
Another direction with GP models is to constrain the prior kernel matrix. [4] constrained the prior covariance matrix such that its diagonal entries are 1s and off-diagonal entries some very small values. However, these models can be approximated by regularized GRF models in that (I + εW ) −1 = I − εW + ε 2 W 2 − · · · ≈ I − εW , when lim ε s W s = 0, with small ε > 0. [4] also proposed an absence-of-suppressors (AofS) condition that is sufficient for submodularity. However, it is generally hard to verify if a discrete GP meets the AofS condition, whereas we will show that every GRF is AofS.
Finally, [5] demonstrates semi-supervised and active learning using GRFs. Their motivation is that unlabeled nodes can reasonably influence the prediction by their edge weights with other nodes, because these weights can encode information such as sample density (e.g. using a radial basis function kernel to calculate the weight matrix). Later research [1] used spectral methods to boost the computation speed for subset selection in batch active learning. However, they only solved the subset selection case where every node query has a unit cost. Moreover, in both works, the optimization lacks worst-case guarantees.
In this paper, we properly define a (regularized) discrete GRF model and prove an (1 − 1/e) approximation ratio lower bound with the V-optimality criterion under a limited budget for a greedy subset selection algorithm. We also extend this bound for the scenario where different nodes have different costs. GRF models are a special type of AofS GP models. Conversely, any GP model whose conditional covariance matrices are always nonnegative is a GRF model and is AofS. From real-world experiments we show that GRF models using the V-optimality criterion present advantages over GP models with the MIG criterion and random selection. where each node has an (either known or unknown) label and each edge e ij has a fixed nonnegative weight w ij (= w ji ) that reflects the proximity, similarity, etc between nodes v i and v j . Define the graph Laplacian of G to be L 0 = diag (W ) − W and the regularized graph Laplacian to be L σ = L 0 + diag σ −2 1 , ..., σ −2 N with σ i > 0, ∀i = 1, ..., N . We use L to generalize both.
The discrete Gaussian Random Field (GRF) is a joint continuous distribution on both labeled and unlabeled nodes, containing one tunable "heat" parameter β > 0, as Assuming labels y L = {y l1 , ..., y l |L| } are tagged as t L ∈ [0, 1] |L| , a Gaussian Harmonic predictor predicts all unlabeled continuous nodes y U = {y u1 , ..., y u |U | } by factoring out known variables [5], where L U is the submatrix consisting of the unlabeled row and column indices in L, for example the lower right block of L = L ll L lu L ul L uu and f U = (−L −1 U L ul t L ). By convention, L −1 (V−L) means the inverse of the submatrix. We use L (V−L) and L U interchangeably because L and U partition the set of all nodes V.
In some problems, a test set T ⊂ U is specified. Define T to be a |T | × |U| matrix such that t ij = δ(v ti , v uj ), i.e. T y U = y T . Otherwise, a default value of T is the identity matrix of size |U|. By marginalizing out node variables in U\T from (2), we have P(y T |t L ) ∼ N (T f U , βT L −1 (V−L) T T ).

Risk Minimization for Classification
Since in GRFs regression responses are taken directly as probability predictions, it is computationally and analytically more convenient to apply the regression loss and risk directly in the GRF as in [2]. Assume the L2 loss to be our classification loss, L c (y T , f T ) = vt i ∈T (y ti − f ti ) 2 , and a risk function whose input variable is the subset L as

The Subset Selection Problem (the Active Learning for Classification Problem)
Assume every vertex on the graph has a cost, (a unit cost if not specified), the major objective in this paper is to choose a subset of nodes L = {v l1 , ..., v l |L| } to query for labels, constrained by a given budget C, such that the risk is minimized. Formally, Though not explicitly denoted, the specific matrix

Submodularity, Suppressor-free, and Bounds for Greedy Method
In § 3, we assume that L is nonsingular. This could be achieved by either deleting a node (a row and a column) from the original undirected connected graph Laplacian, i.e. assuming that the dataset always contains a fixed label, or by using the regularized L σ . In these cases, L satisfies the following.
• Relationship with suppressor-free models. An absence-of suppressor (AofS) condition in regression models gaurantees submodularity. With our notation, 1 this condition is |Corr(y i , y j |L 1 ∪ L 2 )| ≤ |Corr(y i , y j |L 1 )|, ∀v i , v j , L 1 , L 2 . An example of suppressor variable is some node v k ∈ L 2 − L 1 such that y i + y j = y k . Such variable is counter-tuitive in prediction models because knowing y k suppresses an unmodeled correlation between the predictors. We show that the GRF model is a perfect example for AofS condition.
2 In the following, for any vector or matrix A, A ≥ 0 always stands for A being (entry-wise) nonnegative.

Lemma 4 (Submodularity). For function
Proof. We may assume that L 1 , L 2 , and {v} are disjoint. Without loss of generality, suppose and Apply block matrix inversion theorem, when a test set is not specified, i.e. T = I of size |U|, Notice that by sign rule (5) The proof when a test set T is specified is fundamentally similar because the indicator matrix T is always applied to nonnegative vectors or matrices.
Theorem 1 ((1-1/e) Bound). The function R ∆ (L) defined in § 2.3 is normalized (by definition), monotone (by lemma 3), and submodular (by lemma 4). Therefore, (12) can be established. Definition 1. Since the conditional covariance of a GRF model is L −1 L , we can properly define the corresponding conditional correlation to be Proof. We may assume that L 1 and L 2 are disjoint. Adopt the notations from (17-19). Now, Divide vector d by diagonal number e yields As we have proved in Lemma 4 Similarly, It suffices to multiply both sides of the above.

Extension to Active Survey and Tricks to Improve Efficiency
In an active survey problem [7], our goal is to actively query points to ultimately predict the proportion of a given class. Embedded in GRF models, it changes the loss function to the Mean Squared Error (MSE) L s (y T , f T ) = ( vt i ∈T (y ti − f ti )) 2 and the risk to R s (L) = 1 T T L −1 (V−L) T T 1. For the subset selection problem with this new objective function, all results in § 3 hold and the proofs are similar. Besides, we developed an algorithm with O(N 2.36 + kN 2 ) runtime complexity for k queries (O(kN 3.36 ) if implemented natively) similar to [2].

Tricks to Improve Efficiency: With Precomputed Covariance
In Algo 1, the most time-consuming step is to compute R(L ∪ {v }) for every possible v ∈ P, which in general involves taking the inverse of L (V−L∪{v }) . Zhu et. al. [5] presented a fast way to do this. Actually it can get even faster in the following way, assuming L −1 , and Σ * v to be the last column of Σ , In Algo 2, only linear time is needed to evaluate the marginal gain of a candidate because Algorithm 2: Fast progressive R(L ∪ {v }) evaluation with precomputed covariance. Input: Labeled set L, current R(L), Σ (covariance of y U conditioned on y L ), queryable pool P, and test set T ⊂ U if applicable (otherwise T ← I of size |U|). Output: R(L ∪ {v p1 }), ..., R(L ∪ {v p |P| }.

Tricks to Improve Efficiency: Singular Laplacian
However, we still have one question unsolved-how to compute the first L −1 when L for a connected graph is singular?
The algorithm for classification problem arg min v0 tr(L −1 (V−{v0}) ) has been optimized in [2]. We can follow a similar method to compute arg min v0 1 T L −1 (V−{v0}) 1 and also the criterion with specified test sets. Essentially, we want to avoid numerical inverse of large matrices as much as possible. In fact, both the algorithm in [2] and the following require only one eigen-decomposition of L , which has the same order of complexity as matrix inversion.
Definition 2 (First Query in Survey Problem). Suppose L satisfies (5-7), i.e. every property including connectivity but singularity. Also suppose L has eigen-decomposition L = QΛQ T , where Λ = diag (λ 1 , λ 2 , ..., λ N ) with λ 1 = 0, λ k > 0, ∀k = 1 and Q is the orthogonal matrix whose every column is the regularized eigenvector corresponding to the eigenvalue in Λ. Denote the row vector . The first query in survey problem asks to optimize

Solution (First Query in Survey Problem).
For any fixed i, denote (n-1)-by-nQ = Q −i, * . ThusQQ , whereΛ is (n-1)-by-(n-1) nonsingular diagonal matrix andL = L (V−{vi}) =QΛQ T . By matrix inversion theorem, Since L is a connected graph Laplacian, the normalized eigenvector for λ 1 = 0 is 1 Therefore, we can denote Apply matrix inver-sion theorem again, Assign a i = α T iM −1 α i and we have Finally, because the first column of the orthogonal Q is 1 where a i = (q i,2 , ..., When a test set T is specified, since v i ∈ T , A similar algorithm can be derived, though the runtime complexity may has a factor |T |.

Experiment
We performed various active learning methods on the DBLP coauthorship graph dataset 4 on four areas: machine learning, data mining, information retrieval and database. Edge weights are the number of papers coauthored. We took its largest connected component, which contains 1711 nodes and 0.3% of all possible edges. We used the V-optimality criterion ( § 2), mutual information gain (max L MI(L; V − L)) [1], and random selection. For fair comparison, every method was assigned the same random seed to start and the curves are the mean and the standard error of the mean after 120 repetitions (Figure 1). The V-optimality criterion performs better than others.

Conclusion
In this paper, we introduced the GRF model (1) and the Gaussian harmonic prediction (2). The batch active learning with V-optimality criterion, whose risk function is (3) can be formulated as the subset selection problem (4). Our major contribution is to prove the submodularity conditions (9-11) and an (1 − 1/e) optimality bound (12) for a greedy selection algorithm (Algo 1) when the graph Laplacian is nonsingular (5)(6)(7)(8), via either extracting a subgraph from the original connected graph or regularizing the GRF model. Furthermore, the fact that all GRFs meet the AofS condition (Theorem 2) may shed light on this otherwise obscure condition.
In § 4, we also proposed an active survey problem and its related risk R s (L). We can show that this batch active survey problem also meet the submodularity conditions and its greedy subset selection algorithm achieves a similar (1 − 1/e) optimality bound.