Not All Seeds Are Equal: Measuring the Quality of Text Mining Seeds

Zornitsa Kozareva, Eduard H. HovyNAACL 2010 · OpenReview

TL;DR

This paper tackles the crucial problem of selecting "good" initial seeds for bootstrapping semantic lexicons from text. They propose a novel regression model that learns from the "connectivity behavior" of seeds during bootstrapping to predict their quality, achieving high accuracy and even generalizing across different patterns and languages.

What Problem Does This Paper Address?

Extracting structured knowledge from unstructured text is vital for many NLP tasks like information extraction and question answering. A common approach is "semantic lexicon induction," where we automatically build lists of terms belonging to specific semantic classes (e.g., all singers, all countries). A popular method for this is "bootstrapping," which starts with a few initial "seeds" (example terms) and iteratively finds more terms using patterns. However, the performance of this bootstrapping process is highly sensitive to the quality of the initial seeds. Poor seeds can lead to noisy results or slow convergence. The problem is that it's hard for humans to know a priori which seeds will be good, and manual selection is expensive. This paper aims to automatically measure the "goodness" of a seed without human intervention.

Methods

The core of the paper is a regression model designed to predict the "goodness" of a seed. "Goodness" is defined by two metrics: yield (total number of unique instances learned) and distance (number of iterations to reach exhaustion).

  1. Recursive Pattern Bootstrapping: They leverage a "doubly-anchored pattern" (DAP) mechanism, which is a recursive bootstrapping approach. This method can even generate its own seeds, making the entire process more automated.
  2. Seed Behavior Modeling: Instead of just looking at the final yield, the authors focus on the connectivity behavior of a seed during the bootstrapping process. This includes tracking the number of instances learned at each iteration.
  3. Regression Model: They train a regression model (specifically, Support Vector Regression) using the iterative yield data of many seeds. This model learns to associate a seed's early behavior with its eventual yield and distance.
  4. Generalized Model: Crucially, they propose a generalized regression model. This model is trained on data from one set of patterns (e.g., "people" and "city") and then tested on entirely new patterns and languages, demonstrating transferability.

Datasets

The paper doesn't introduce new benchmark datasets but uses existing data collection methods.

  • Data Collection: They collected data for the open semantic classes "people" and "city" using Yahoo!Boss queries with DAP patterns. This resulted in approximately 1.5GB and 1.9GB of snippets, respectively. All unique harvested instances were then used as seeds for further experiments.
  • Evaluation: The models were evaluated on these collected seeds, as well as on Spanish versions of the "people" and "city" patterns, and two new verb-preposition patterns (" and X fly to" and " and X work for").

Key Insights and Ideas

  • Seed behavior is predictable: The "single-hump" pattern observed in seed learning speed (yield over iterations) is regular enough to be modeled. This regularity is key to predicting seed quality.
  • Early behavior matters, but not exclusively: While early iterations provide some signal, they are insufficient on their own. The model needs to consider behavior over a significant portion of the bootstrapping process to accurately predict quality.
  • Generalization is possible: A model trained on one type of semantic relation (e.g., "people") can predict seed quality for entirely different relations and even languages, which is a significant finding for practical applications.
  • Human intuition is fallible: The study suggests that humans are prone to choosing non-productive seeds, highlighting the need for automated quality assessment.

Key Results

  • Pattern-specific models: Achieved high correlation coefficients (cc) and low error rates. For instance, by the ninth iteration, pattern-specific models reached cc=1.0 with a 5% error rate for predicting seed yield.
  • Generalized model performance: The generalized model, trained on "people" and "city" patterns, showed robust performance across new patterns and languages. On the twelfth iteration, it achieved cc=1.0 with an error rate of 0.4% to 8.0%.
  • Cross-lingual and cross-pattern transfer: The generalized model demonstrated consistent performance across English and Spanish, and across different types of patterns (entity-based and verb-prepositional).
  • Seed classification: The analysis revealed that a significant portion of seeds are "hermits" (non-productive), with a smaller percentage being "high connectors" (productive).

Limitations and Future Work

  • Pattern-specific training: While the generalized model is a significant step, the initial pattern-specific models require training over the entire bootstrapping process for that pattern.
  • Stopping criteria: For real-world applications with limited resources, finding optimal stopping criteria for bootstrapping is important to balance accuracy and efficiency.
  • Distribution of out-degrees: The authors suggest exploring the distribution of term connectivity (e.g., Poisson vs. Gaussian) to further understand and potentially model seed behavior more deeply.
  • Discovering regularities: Future work could involve discovering more general regularities about term usage within semantic domains and term network connectivity.

Summary updated

Abstract

Open-class semantic lexicon induction is of great interest for current knowledge harvesting algorithms. We propose a general framework that uses patterns in bootstrapping fashion to learn open-class semantic lexicons for different kinds of relations. These patterns require seeds. To estimate the goodness (the potential yield) of new seeds, we introduce a regression model that considers the connectivity behavior of the seed during bootstrapping. The generalized regression model is evaluated on six different kinds of relations with over 10000 different seeds for English and Spanish patterns. Our approach reaches robust performance of 90% correlation coefficient with 15% error rate for any of the patterns when predicting the goodness of seeds.
BibTeX
@inproceedings{kozareva2010not,
  author = {Zornitsa Kozareva and Eduard H. Hovy},
  title = {{Not All Seeds Are Equal: Measuring the Quality of Text Mining Seeds}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=r14707-ubB},
}

Loading related content...

Figure