A Semi-Supervised Method to Learn and Construct Taxonomies Using the Web

Zornitsa Kozareva, Eduard H. HovyEMNLP 2010 · OpenReview

Abstract

Although many algorithms have been developed to harvest lexical resources, few organize the mined terms into taxonomies. We propose (1) a semi-supervised algorithm that uses a root concept, a basic level concept, and recursive surface patterns to learn automatically from the Web hyponym-hypernym pairs subordinated to the root; (2) a Web based concept positioning procedure to validate the learned pairs' is-a relations; and (3) a graph algorithm that derives from scratch the integrated taxonomy structure of all the terms. Comparing results with WordNet, we find that the algorithm misses some concepts and links, but also that it discovers many additional ones lacking in WordNet. We evaluate the taxonomization power of our method on reconstructing parts of the WordNet taxonomy. Experiments show that starting from scratch, the algorithm can reconstruct 62% of the WordNet taxonomy for the regions tested.

Introduction

Large-scale lexical resources like WordNet are essential for natural language processing tasks, yet they suffer from being manually constructed and difficult to maintain. This leads to significant knowledge gaps in specialized or rapidly evolving domains. While existing automated methods often focus on extending existing ontologies, the challenge addressed by Kozareva and Hovy is taxonomy induction from scratch. The goal is to discover both terms and their hierarchical organization without prior structural knowledge, distinguishing between unrelated, sibling, or parent-child concepts.

Methodology

The proposed system utilizes a three-stage pipeline to build complex taxonomic hierarchies automatically from Web data.

1. Knowledge Harvesting and Hypernym Extraction

The system begins with "Doubly-Anchored Patterns" (DAP), such as “<root> such as <seed> and ”. By querying search engines with a root (e.g., "Animal") and a seed (e.g., "Lion"), it discovers new hyponyms like "Tiger." This process is bootstrapped recursively. Subsequently, inverse patterns like “ such as <lion> and <tiger>” are used to identify intermediate categories (hypernyms) that might be missing from standard resources, such as "felines" or "predators."

The semi-supervised algorithm for harvesting and ranking concepts.

2. Graph-Based Induction

The core innovation lies in the structural organization of these terms. The system constructs a Directed Acyclic Graph (DAG) where nodes represent concepts and edges denote "is-a" relationships validated by Web frequency. To resolve the hierarchy, the algorithm employs a longest path heuristic.

Transformation of a relationship graph into a hierarchical taxonomy using the longest path heuristic.

In a noisy graph of relationships, the longest path from the root to a specific term represents the most complete chain of taxonomic subsumption. For example, while a direct link might exist between "Animal" and "Lion," the longest path (Animal → Vertebrate → Mammal → Feline → Lion) provides a much richer and more accurate taxonomic structure.

Evaluation and Results

The method was evaluated by attempting to reconstruct sub-hierarchies of WordNet 3.0 in the Animals, Plants, and Vehicles domains using the live Web via the Yahoo! search API.

The system achieved remarkably high precision, ranging from 97% to 99% across all domains. Notably, it successfully reconstructed 62% of the WordNet taxonomy for the tested regions. Beyond mere reconstruction, the algorithm discovered valid categories absent in WordNet, such as "filter feeders" or "bottom dwellers," demonstrating its ability to capture specialized "folksonomies" present in natural human discourse.

Discussion

A key insight of this work is the use of Web redundancy as a natural filter; requiring terms to be discovered through multiple patterns effectively mitigates noise. However, limitations remain. Recall is lower (40-60%) for obscure intermediate concepts. Additionally, the system currently forces concepts into a single hierarchy, which does not account for multiple perspectives (e.g., a dolphin as a "mammal" vs. a "sea creature"). Future work aims to address these perspectival facets and develop more robust methods for merging independent taxonomic chains into a single cohesive graph.

Summary updated

Abstract

Although many algorithms have been developed to harvest lexical resources, few organize the mined terms into taxonomies. We propose (1) a semi-supervised algorithm that uses a root concept, a basic level concept, and recursive surface patterns to learn automatically from the Web hyponym-hypernym pairs subordinated to the root; (2) a Web based concept positioning procedure to validate the learned pairs' is-a relations; and (3) a graph algorithm that derives from scratch the integrated taxonomy structure of all the terms. Comparing results with WordNet, we find that the algorithm misses some concepts and links, but also that it discovers many additional ones lacking in WordNet. We evaluate the taxonomization power of our method on reconstructing parts of the WordNet taxonomy. Experiments show that starting from scratch, the algorithm can reconstruct 62% of the WordNet taxonomy for the regions tested.
BibTeX
@inproceedings{kozareva2010semi,
  author = {Zornitsa Kozareva and Eduard H. Hovy},
  title = {{A Semi-Supervised Method to Learn and Construct Taxonomies Using the Web}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2010},
  url = {https://openreview.net/forum?id=B1b-3Mfu-H},
}
Figure