{'fraction_non_alphanumeric': 0.04341881758296391, 'fraction_numerical': 0.013796246426647885, 'mean_word_length': 4.447528774542993, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Understanding seed selection in bootstrapping

Bootstrapping has recently become the focus of much attention in natural language processing to reduce labeling cost. In bootstrapping, unlabeled instances can be harvested from the initial labeled “seed” set. The selected seed set affects accuracy, but how to select a good seed set is not yet clear. Thus, an “iterative seeding” framework is proposed for bootstrapping to reduce its labeling cost. Our framework iteratively selects the unlabeled instance that has the best “goodness of seed” and labels the unlabeled instance in the seed set. Our framework deepens understanding of this seeding process in bootstrapping by deriving the dual problem. We propose a method called expected model rotation (EMR) that works well on not well-separated data which frequently occur as realistic data. Experimental results show that EMR can select seed sets that provide significantly higher mean reciprocal rank on realistic data than existing naive selection methods or random seed sets.


Introduction
Bootstrapping has recently drawn a great deal of attention in natural language processing (NLP) research. We define bootstrapping as a method for harvesting "instances" similar to given "seeds" by recursively harvesting "instances" and "patterns" by turns over corpora using the distributional hypothesis (Harris, 1954). This definition follows the definitions of bootstrapping in existing NLP papers (Komachi et al., 2008;Talukdar and Pereira, 2010;Kozareva et al., 2011). Bootstrapping can greatly reduce the cost of labeling instances, which is especially needed for tasks with high labeling costs.
The performance of bootstrapping algorithms, however, depends on the selection of seeds. Although various bootstrapping algorithms have been proposed, randomly chosen seeds are usually used instead. Kozareva and Hovy (2010) recently reports that the performance of bootstrapping algorithms depends on the selection of seeds, which sheds light on the importance of selecting a good seed set. Especially a method to select a seed set considering the characteristics of the dataset remains largely unaddressed. To this end, we propose an "iterative seeding" framework, where the algorithm iteratively ranks the goodness of seeds in response to current human labeling and the characteristics of the dataset. For iterative seeding, we added the following two properties to the bootstrapping; • criteria that support iterative updates of goodness of seeds for seed candidate unlabeled instances.
• iterative update of similarity "score" to the seeds.
To invent a "criterion" that captures the characteristics of a dataset, we need to measure the influence of the unlabeled instances to the model. This model, however, is not explicit in usual bootstrapping algorithms' notations. Thus, we need to reveal the model parameters of bootstrapping algorithms for explicit model notations.
To this end, we first reduced bootstrapping algorithms to label propagation using Komachi et al. (2008)'s theorization. Komachi et al. (2008) shows that simple bootstrapping algorithms can be interpreted as label propagation on graphs (Komachi et al., 2008). This accords with the fact that many papers such as (Talukdar and Pereira, 2010;Kozareva et al., 2011) suggest that graph-based semi-supervised learning, or label propagation, is another effective method for this harvesting task. Their theorization starts from a simple bootstrapping scheme that can model many bootstrapping algorithms so far proposed, including the "Espresso" algorithm (Pantel and Pennacchiotti, 2006), which was the most cited among the Association for Computational Linguistics (ACL) 2006 papers.
After reducing bootstrapping algorithms to label propagation, next, we will reveal the model parameters of a bootstrapping algorithm by taking the dual problem of bootstrapping formalization of (Komachi et al., 2008). By revealing the model parameters, we can obtain an interpretation of selecting seeds which helps us to create criteria for the iterative seeding framework. Namely, we propose expected model rotation (EMR) criterion that works well on realistic, and not well-separated data.
The contributions of this paper are summarized as follows.
• The iterative seeding framework, where seeds are selected by certain criteria and labeled iteratively.
• To measure the influence of the unlabeled instances to the model, we revealed the model parameters through the dual problem of bootstrapping.
• The revealed model parameters provides an interpretation of selecting seeds focusing on how well the dataset is separated.
• "EMR" criterion that works well on not wellseparated data which frequently occur as realistic data. . Kozareva and Hovy (2010) recently shed light on the problem of improving the seed set for bootstrapping. They defined several goodness of seeds and proposed a method to predict these measures using support vector regression (SVR) for their doubly anchored pattern (DAP) system. However, Kozareva and Hovy (2010) does not show how effective the seed set selected by the goodness of seeds that they defined was for the bootstrapping process while they show how accurately they could predict the goodness of seeds.

Related Work
Early work on bootstrapping includes that of (Hearst, 1992) and that of (Yarowsky, 1995). Abney (2004) extended self-training algorithms including that of (Yarowsky, 1995), forming a theory different from that of (Komachi et al., 2008). We chose to extend the theory of (Komachi et al., 2008) because it can actually explain recent graph-based algorithms including that of (Pantel and Pennacchiotti, 2006). The theory of Komachi et al. (2008) is also newer and simpler than that of (Abney, 2004).
The iterative seeding framework can be regarded as an example of active learning on graph-based semi-supervised learning. Selecting seed sets corresponds to sampling a data point in active learning. In active learning on supervised learning, the active learning survey (Settles, 2012) includes a method called expected model change, after which this paper's expected model rotation (EMR) is named. They share a basic concept: the data point that surprises the classifier the most is selected next. Expected model change mentioned by (Settles, 2012), however, is for supervised setting, not semisupervised setting, with which this paper deals. It also does not aim to provide intuitive understanding of the dataset. Note that our method is for semisupervised learning and we also made the calculation of EMR practical.
Another idea relevant to our EMR is an "angle diversity" method for support vector machines (Brinker, 2003). Unlike our method, the angle diversity method interprets each data point as data "lines" in a version space. The weight vector is expressed as a point in a version space. Then, it samples a data "line" whose angle formed with existing data lines is large. Again, our method builds upon different settings in that this method is only for supervised learning, while ours is for semi-supervised learning.

Theorization of Bootstrapping
This section introduces a theorization of bootstrapping by (Komachi et al., 2008).

Simple bootstrapping
Let D = {(y 1 , x 1 ), . . . , (y l , x l ), x l+1 , . . . , x l+u } be a dataset. The first l data are labeled, and the following u data are unlabeled. We let n = l + u for simplicity. Each x i ∈ R m is an m-dimensional input feature vector, and y i ∈ C is its corresponding label where C is the set of semantic classes. To handle |C| classes, for k ∈ C, we call an n-sized 0-1 vector y k = (y 1k , . . . , y nk ) ⊤ a "seed vector", where y ik = 1 if the i-th instance is labeled and its label is k, otherwise y ik = 0.
Note that this multi-class formalization includes typical ranking settings for harvesting tasks as its special case. For example, if the task is to harvest animal names from all given instances, such as "elephant" and "zebra", C is set to be binary as C = {animal, not animal}. The ranking is obtained by the score vector resulting from the seed vector y animal − y not animal due to the linearity.
By stacking row vectors x i , we denote X = (x 1 , . . . , x n ) ⊤ . Let X be an instance-pattern (feature) matrix where (X) ij stores the value of the jth feature in the ith datum. Note that we can almost always assume the matrix X to be sparse for bootstrapping purposes due to the language sparsity. This sparsity enables the fast computation.
The simple bootstrapping (Komachi et al., 2008) is a simple model of bootstrapping using matrix representation. The algorithm starts from f 0 def = y and repeats the following steps until f c converges.
The score vector after c iterations of the simple bootstrapping is obtained by the following equation.
"Simplified Espresso" is a special version of the simple bootstrapping where X ij = pmi(i,j) max pmi and we normalize score vectors uniformly: Komachi et al. (2008) pointed out that, although the scores f c are normalized during the iterations in the simple bootstrapping, when c → ∞, f c converges to a score vector that does not depend on the seed vector y as the principal eigenvector of ( 1 becomes dominant. For bootstrapping purposes, however, it is appropriate for the resulting score vector f c to depend on the seed vector y.

Laplacian label propagation
To make f seed dependent, Komachi et al. (2008) noted that we should use a power series of a matrix rather than a simple power of a matrix. As the following equation incorporates the score vectors ((−L) c y) with both low and high c values, it provides a seed dependent score vector with taking higher c into account.
This infinite summation of the matrix can be expressed by inverting the matrix under the condition that 0 < β < 1 ρ(L) , where ρ(L) be the spectral radius of L. Komachi et al. (2008)'s Laplacian label propagation is simply expressed as (3). Given y, it outputs the score vector f to rank unlabeled instances. They reports that the resulting score vector f constantly achieves better results than those by Espresso (Pantel and Pennacchiotti, 2006).
4 Proposal: criteria for iterative seeding This section describes our iterative seeding framework. The entire framework is shown in Algorithm 1. Let g i be the goodness of seed for an unlabeled instance i. We want to select the instance with the highest goodness of seed as the next seed added in the next iteration.î Algorithm 1 Iterative seeding framework Require: y, X, the set of unlabeled instances U , the set of classes C.
Each seed selection criterion defines each goodness of seed g i . To measure the goodness of seeds, we want to measure how an unlabeled instance will affect the model underlying Eq. (3). That is, we want to choose the unlabeled instance that would most influence the model. However, as the model parameters are not explicitly shown in Eq. (3), we first need to reveal them before measuring the influence of the unlabeled instances.

Scores as margins
This section reveals the model parameters through the dual problem of bootstrapping. We show that the score obtained by Eq. (3) can be regarded as the "margin" between each unlabeled data point and the hyperplane obtained by ridge regression; specifically, we can show that the i-th element of the resulting score vector obtained using Eq. (3) can be written as f i = β (y i − ⟨ŵ, ϕ (x i )⟩), whereŵ is the optimal model parameter that we need to reveal (Figure 1). ϕ is a feature function mapping x i to a feature space and is set to make this relation hold. Note that, for unlabeled instances, y i = 0 holds, and thus f i is simply f i = −β ⟨ŵ, ϕ (x i )⟩. Therefore, |f i | ∝ ∥ ⟨ŵ, ϕ (x i )⟩ ∥ denotes the "margin" between each unlabeled data point and the underlying hyperplane.
By taking the diagonal of ΦΦ ⊤ in Eq. (6), it is easy to see that ∥ϕ ( Thus, the data points mapped into the feature space are within a unit circle in the feature space shown as the dashed circles in Figure 1-3. The weight vector is then represented by the classifying hyperplane that goes through the origin in the feature space. The classifying hyperplane views all the points positioned left of this hyperplane as the green class, and all the points positioned right of this hyperplane as the blue gray-stroked class. Note that all the points shown in Figure 1 are unlabeled, and thus the classifying hyperplane does not know the true classes of the data points. Due to the lack of space, the proof is shown in the appendix.

Margin criterion
Section 4.1 uncovered the latent weight vector for the bootstrapping model Eq. (3). A weight vector specifies a hyperplane that classifies instances into semantic classes. Thus, weight vector interpretation easily leads to an iterative seeding criterion: an unlabeled instance closer to the classifying hyperplane is more uncertain, and therefore obtains higher goodness of seed. We call this criterion the "margin criterion" (Figure 2).
First, we define g k,i ′ def = |(f k ) i ′ |/s k as the goodness of an instance i ′ to be labeled as k. s k is the number of seeds labeled as class k in the current seed set. In the margin criterion, the goodness of the seed i ′ is then obtained by the difference between Figure 2: Margin criterion in binary setting. The instance closest to the underlying hyperplane, the red-and-blackstroked point, is selected. The part within the large gray dotted circle is not well separated. Margin criterion continues to select seeds from this part only in this example, and fails to sample from the left-bottom blue gray-stroked points. Note that all the points are unlabeled and thus the true classes of data points cannot be seen by the underlying hyperplane in this figure.
the largest and second largest g k,i ′ among all classes as follows: ) .
(7) The shortcoming of Margin criterion is that it can be "stuck", or jammed, or trapped, when the data are not well separated and the underlying hyperplanes goes right through the not well-separated part. In Figure 2, the part within the large gray dotted circle is not well separated. Margin criterion continues to select seeds from this part only in this example, and fails to sample from the left-bottom blue graystroked points.

Expected Model Rotation
To avoid Margin criterion from being stuck in the part where the data are not well separated, we propose another more promising criterion: the "Expected Model Rotation (EMR)". EMR measures the expected rotation of the classifying hyperplane (Figure 3) and selects the data point that rotates the un- derlying hyperplane "the most" is selected. This selection method prevents EMR from being stuck in the area where the data points are not well separated. Another way of viewing EMR is that it selects the data point that surprises the current classifier the most. This makes the data points influential to the classification selected in early iteration in the iterative seeding framework. A simple rationale of EMR is that important information must be made available earlier.
To obtain the "expected" model rotation, in EMR, we define the goodness of seeds for an instance i ′ , g i ′ as the sum of each per-class goodness of seeds g k,i ′ weighted by the probability that i ′ is labeled as k. Intuitively, g k,i ′ measures how the classifying hyperplane would rotate if the instance i ′ were labeled as k. Then, g k,i ′ is weighted by the probability that i ′ is labeled as k and summed. The probability for i ′ to be labeled as k can be obtained from the i ′ -th element of the current normalized score vector where s k is the number of seeds labeled as class k in the current seed set.
The per-class goodness of seeds g k,i ′ can be calculated as follows: From Eq. (17) in the proof, w = Φ ⊤ f . Here, e i ′ is a unit vector whose i ′ -th element is 1 and all other elements are 0.
Although Eqs. (10) and (11) use Φ, we do not need to directly calculate Φ. Instead, we can use Eq. (6) to calculate these weight vectors as follows: For more efficient computation, we cached (I + βL) e i ′ to boost the calculation in Eqs. (10) and (11) by exploiting the fact that y k can be written as the sum of e i for all the instances in class k.

Evaluation
We evaluated our method for two bootstrapping tasks with high labeling costs. Due to the nature of bootstrapping, previous papers have commonly evaluated each method by using running search engines. While this is useful and practical, it also reduces the reproducibility of the evaluation. We instead used openly available resources for our evaluation.
First, we want to focus on the separatedness of the dataset. To this end, we prepared two datasets: one is "Freebase 1", a not well-separated dataset, and another is "sb-8-1", a well-separated dataset. We fixed β = 0.01 as Zhou et al. (2011) reports that β = 0.01 generally provides good performance on various datasets and the performance is not keen to β except extreme settings such as 0 or 1. In all experiments, each class initially has 1 seed and the seeds are selected and increased iteratively according to each criterion. The meaning of each curve is shared by all experiments and is explained in the caption of Figure 4. "Freebase 1" is an experiment for information extraction, a common application target of bootstrapping methods. Based on (Talukdar and Pereira, 2010), the experiment setting is basically the same as that of the experiment Section 3.1 in their paper 1 .
As 39 instances have multiple correct labels, however, we removed these instances from the experiment to perform the experiment under multi-class setting. Eventually, we had 31, 143 instances with 1, 529 features in 23 classes. The task of "Freebase 1" is bootstrapping instances of a certain semantic class. For example, to harvest the names of stars, given {Vega, Altair} as a seed set, the bootstrapping ranks Sirius high among other instances (proper nouns) in the dataset. Following the experiment setting of (Talukdar and Pereira, 2010), we used mean reciprocal rank (MRR) throughout our evaluation 2 .
"sb-8-1" is manually designed to be wellseparated and taken from 20 Newsgroup subsets 3 . It has 4, 000 instances with 16, 282 features in 8 classes. Figure 4 and Figure 5 shows the results. We can easily see that "EMR" wins in "Freebase 1", a not well-separated dataset, and "Margin" wins in "sb-8-1", a well-separated dataset. This result can be regarded as showing that "EMR" successfully avoids being "stuck" in the area where the data are not well separated. In fact, in Figure 4, "Random" wins "Margin". This implies that the not well-separated part of this dataset causes the classifying hyperplane in "Margin" criterion to be stuck and make it lose against even simple "Random" criterion.
In contrast, in the "sb-8-1", a well-separated balanced dataset, "Margin" beats the other remaining two. This implies the following: When the dataset is well separated, uncertainty of a data point is the next important factor to select a seed set. As "Margin" exactly takes the data point that is the most uncertain to the current hyperplane, "Margin" works quite well in this example.
Note that all figures in all the experiments show the average of 30 random trials and win-and-lose relationships mentioned are statistically tested using Mann-Whitney test.
While "sb-8-1" is a balanced dataset, realistic data like "freebase 1" is not only not-well-separated, but also imbalanced . Therefore, we performed experiments "sb-8-1", an imbalanced well-separated dataset, and "ol-8-1", an imbalanced not-well sepa-2 MRR is defined as M RR def = 1 |Q| ∑ i∈Q 1 r i , where Q is the test set, i ∈ Q denotes an instance in the test set Q, and ri is the rank of the correct class among all |C| classes.
3 http://mlg.ucd.ie/datasets/20ng.html Figure 4: Freebase 1, a NOT well-separated dataset. Average of 30 random trials. "Random" and "Margin" are baselines. "Random" is the case that the seeds are selected randomly. "Margin" is the case that the seeds are selected using the margin criterion described in §4.2. "EMR" is proposed and is the case that the seeds are selected using the EMR criterion described in §4.3. At the rightmost point, all the curves meet because all the instances in the seed pool were labeled and used as seeds by this point. The MRR achieved by this point is shown as the line "All used". If a curve of each method crosses "All used", this can be intepretted as that iterative seeding of the curve's criterion can reduce the cost of labeling all the instances to the crossing point of the x-axis. "EMR" significantly beats "Random" and "Margin" where x-axis is 46 and 460 with p-value < 0.01.
Results are shown in Figure 6 and Figure 7. In Figure 6, "EMR" beats the other remaining two even though this is a well-separated data set. This implies that "EMR" can also be robust to the imbalancedness as well. In Figure 7, although the MRR of "Margin" eventually is the highest, the MRR of "EMR" rises far earlier than that of "Margin". This result can be explained as follows: "Margin" gets "stuck" in early iterations as this dataset is not well separated though "Margin" achieves best once it gets out of being stuck. In contrast, as "EMR" can avoid being stuck, it rises early achieving high performance with small number of seeds, or labeling. This result suggests that "EMR" is pereferable for reduc- Figure 5: sb-8-1. A dataset manually designed to be well separated. Average of 30 random trials. Legends are the same as those in Figure 4. "Margin" beats "Random" and "EMR" where x-axis is 500 with p-value < 0.01. Figure 6: sl-8-1. An imbalanced well separated dataset. Average of 30 random trials. Legends are the same as those in Figure 4. "EMR" significantly beats "Random" and "Margin" where x-axis is 100 with p-value < 0.01.
ing labeling cost while "Margin" can sometimes be preferable for higher performance.

Conclusion
Little is known about how best to select seed sets in bootstrapping. We thus introduced the iterative seeding framework, which provides criteria for selecting seeds. To introduce the iterative seeding framework, we deepened the understanding of the seeding process in bootstrapping through the dual problem by further extending the interpretation of bootstrapping as graph-based semi-supervised learning (Komachi et al., 2008), which generalizes  Figure 4. "EMR" significantly beats "Random" and "Margin" where x-axis is 100 with pvalue < 0.01. "Margin" significantly beats "EMR" and "Random" where x-axis is 1, 000 with p-value < 0.01. and improves Espresso-like algorithms.
Our method shows that existing simple "Margin" criterion can be "stuck" at the area when the data points are not well separated. Note that many realistic data are not well separated. To deal with this problem, we proposed "EMR" criterion that is not stuck in the area where the data points are not well separated.
We also contributed to make the calculation of "EMR" practical. In particular, we reduced the number of matrix inversions for calculating the goodness of seeds for "EMR". We also showed that the parameters for bootstrapping also affect the convergence speed of each matrix inversion and that the typical parameters used in other work are fairly efficient and practical.
Through experiments, we showed that the proposed "EMR" significantly beats "Margin" and "Random" baselines where the dataset are not well separated. We also showed that the iterative seeding framework with the proposed measures for the goodness of seeds can reduce labeling cost.
Appendix: Proof Consider a simple ridge regression of the following form where 0 < β < 1 is a positive constant. We define ξ i = y i − ⟨w, ϕ (x i )⟩. By using ξ i , we can rewrite Eq. (14) into an optimization problem with equality constraints as follows: s.t.∀i ∈ {1, . . . , n} ; y i = w ⊤ ϕ (x i ) + ξ i . (16) Because of the equality constraints of Eq. (16), we obtain the following Lagrange function h. Here, each bootstrapping score f i occurs as Lagrange multipliers: h (w, ξ, f ) By taking derivatives of h, we can deriveŵ by expressing it with the sum of each f i and ϕ (x i ).