Toward Completeness in Concept Extraction and Classification

Eduard H. Hovy, Zornitsa Kozareva, Ellen RiloffEMNLP 2009 · OpenReview

Abstract

Many algorithms extract terms from text together with some kind of taxonomic classification (is-a) link. However, the general approaches used today, and specifically the methods of evaluating results, exhibit serious shortcomings. Harvesting without focusing on a specific conceptual area may deliver large numbers of terms, but they are scattered over an immense concept space, making Recall judgments impossible. Regarding Precision, simply judging the correctness of terms and their individual classification links may provide high scores, but this doesn't help with the eventual assembly of terms into a single coherent taxonomy. Furthermore, since there is no correct and complete gold standard to measure against, most work invents some ad hoc evaluation measure. We present an algorithm that is more precise and complete than previous ones for identifying from web text just those concepts 'below' a given seed term. Comparing the results to WordNet, we find that the algorithm misses terms, but also that it learns many new terms not in WordNet, and that it classifies them in ways acceptable to humans but different from WordNet.

Introduction: The Taxonomy Challenge

Building a comprehensive taxonomy—a hierarchical map of concepts—is a monumental task. Traditionally, researchers have relied on manual efforts like WordNet, but these are perpetually incomplete and often lack the "fine-grained" categories used in everyday language. Automated "concept harvesting" from the web has attempted to fill these gaps but faces three critical issues:

  1. The Scattering Problem: Algorithms often find thousands of random, unrelated terms without a mechanism to organize them into a coherent structure.
  2. Recall Blindness: The vastness of the web makes it impossible to determine what an algorithm has missed unless the search is focused on a specific conceptual branch.
  3. Hierarchy Confusion: Simple "is-a" links (e.g., "jaguar is an animal") are insufficient. A robust taxonomy requires intermediate categories like "mammal," "feline," and "predator."

This research aims to achieve "completeness" by focusing on populating the space beneath a specific root concept (e.g., "Animals" or "People") with high precision and structural integrity.

Methodology: Doubly-Anchored Bootstrapping

The core innovation is the Doubly-Anchored Pattern (DAP), which leverages two known terms to discover a third. This process operates in two distinct stages:

Stage 1: Discovering Leaf Nodes (DAP)

The system employs patterns such as [RootConcept] such as [SeedTerm] and <X>. For instance, searching for "Presidents such as Ford and <X>" forces the search engine to return other presidents (e.g., "Carter" or "Lincoln") rather than car companies. This "reckless bootstrapping" iterates until no new terms are discovered.

Stage 2: Discovering Intermediate Categories (DAP$^{-1}$)

To build the hierarchy, the pattern is inverted: <X> such as [Term1] and [Term2]. If the system identifies "lions" and "tigers," it searches for <X> such as lions and tigers, yielding categories like "large cats" or "predators."

Concept Positioning Test (CPT)

To ensure a discovered category is a valid sub-concept of the root, the system compares web hit counts. A concept is validated if "Root such as Concept" generates significantly more hits than "Concept such as Root."

Experimental Results

The algorithm was tested using live web data via Google search snippets. Evaluation involved comparison with WordNet and verification by human judges using a nuanced 14-label classification system.

Scale and Growth

The algorithm demonstrated significant growth over 10 iterations, successfully identifying 913 animal concepts and 1,344 people instances.

Learning curves showing the cumulative number of animal and people concepts/instances discovered over ten iterations.

Precision and Discovery

Human judges verified the "People" instances at 95% precision. The "Animal" concepts achieved a lower precision of 71%, largely due to the complexity of the category, which includes functional and behavioral terms (e.g., "laboratory animals").

Precision of extracted 'People' instances across different ranks.

Notably, the system discovered 986 correct people and 48 correct animal terms entirely absent from WordNet. Structural accuracy for "is-a" links reached 88% for animals and 94% for people.

Discussion and Future Work

The results highlight that WordNet serves as a floor rather than a ceiling for taxonomic knowledge. The DAP algorithm effectively identifies common functional groupings (e.g., "endangered species") that formal databases often omit.

However, limitations remain. The system's reliance on search engine hit counts is subject to API constraints. Additionally, "relative terms" like "large mammals" present challenges for absolute classification. Future work will focus on the full assembly of these links into a multi-layered, coherent tree structure that can handle concepts with multiple parents.

Summary updated

Abstract

Many algorithms extract terms from text together with some kind of taxonomic classification (is-a) link. However, the general approaches used today, and specifically the methods of evaluating results, exhibit serious shortcomings. Harvesting without focusing on a specific conceptual area may deliver large numbers of terms, but they are scattered over an immense concept space, making Recall judgments impossible. Regarding Precision, simply judging the correctness of terms and their individual classification links may provide high scores, but this doesn't help with the eventual assembly of terms into a single coherent taxonomy. Furthermore, since there is no correct and complete gold standard to measure against, most work invents some ad hoc evaluation measure. We present an algorithm that is more precise and complete than previous ones for identifying from web text just those concepts 'below' a given seed term. Comparing the results to WordNet, we find that the algorithm misses terms, but also that it learns many new terms not in WordNet, and that it classifies them in ways acceptable to humans but different from WordNet.
BibTeX
@inproceedings{hovy2009toward,
  author = {Eduard H. Hovy and Zornitsa Kozareva and Ellen Riloff},
  title = {{Toward Completeness in Concept Extraction and Classification}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=ByWckGMdZS},
}
Figure