Taxonomy Learning Using Word Sense Induction

Ioannis P. Klapaftis, Suresh ManandharNAACL 2010

TL;DR

This paper tackles the challenge of building accurate taxonomies from text by addressing the issue of word polysemy, which traditional methods often ignore. They propose a novel unsupervised approach that first uses Word Sense Induction (WSI) to identify distinct word senses and then employs Hierarchical Agglomerative Clustering (HAC) to build a taxonomy of these senses, leading to more nuanced and accurate hierarchical structures.

What Problem Does This Paper Address?

Building taxonomies, which are hierarchical structures of concepts (like "fruit" is a hypernym of "apple"), is crucial for many Natural Language Processing (NLP) applications, including information retrieval and question answering. However, a significant limitation of existing taxonomy learning methods is their failure to adequately handle word polysemy – the phenomenon where a single word can have multiple distinct meanings. Traditional approaches often conflate these different senses by treating each word as having a single, unified representation (e.g., a single feature vector). This can lead to inaccurate taxonomic relationships, as a word's hypernyms might only be relevant to one of its senses, not all of them. For instance, the word "house" has senses related to a dwelling and a place of entertainment (like a casino or theater), but traditional methods might only capture relationships relevant to the most frequent sense, missing important taxonomic connections for less frequent senses.

Methods

The core of this paper's contribution lies in its two-stage approach:

  1. Word Sense Induction (WSI): The authors leverage a WSI method, specifically the one proposed by Klapaftis & Manandhar (2008), to automatically identify the different senses of target words within an unlabelled corpus. This is a crucial step as it moves beyond treating words as monolithic entities. The WSI process involves:
  2. Corpus Preprocessing: Extracting relevant nouns from paragraphs where the target word appears.
  3. Graph Creation & Clustering: Building a graph where nodes represent collocations (pairs of nouns co-occurring in a paragraph) and edges represent their relationships. This graph is then clustered (using Chinese Whispers) to identify distinct senses, each represented by a set of contextually related collocations.
  4. Hierarchical Agglomerative Clustering (HAC): Once distinct senses are identified by WSI, these senses are then hierarchically classified using HAC.
  5. Sense Representation: Each induced sense is represented by the set of paragraphs it is associated with (based on its collocations).
  6. Similarity Calculation: The Jaccard coefficient is used to calculate the similarity between senses based on their shared associated paragraphs.
  7. Hierarchical Construction: HAC iteratively merges the most similar clusters (senses) until a single root cluster is formed, thus creating the taxonomy. The paper explores different linkage criteria for HAC: single-linkage, complete-linkage, and average-linkage.

Datasets

The evaluation of the proposed method was performed on two sub-taxonomies derived from WordNet:

  • Network Taxonomy: Extracted from WordNet, this taxonomy includes hyponyms of the senses of the word "network." It contains 29 senses realized by 24 word sets.
  • Speaker Taxonomy: Derived from concepts under the senses of the word "speaker." This taxonomy contains 52 senses realized by 50 word sets.

For corpus creation, the authors utilized the Yahoo! search API to retrieve up to 1000 pages for each target word.

Key Insights and Ideas

  • Polysemy is Key: The paper strongly advocates that explicitly handling word polysemy through WSI is essential for building more accurate and comprehensive taxonomies. Ignoring it leads to a significant loss of information and potential taxonomic relationships.
  • WSI as a Precursor to Taxonomy Learning: WSI is not just an auxiliary task but a foundational step that enables more sophisticated taxonomy construction by providing a finer-grained representation of word meanings.
  • HAC Linkage Matters: The choice of linkage criterion in HAC (single, complete, average) significantly impacts the resulting taxonomy's quality. Single-linkage and average-linkage performed notably better, suggesting that capturing broader contextual relationships (even if some are less direct) is beneficial for taxonomy construction.
  • Gold Standard vs. Learned Taxonomies: The evaluation highlights the challenges in directly comparing automatically learned taxonomies with gold standards, especially concerning internal node labeling and the presence of elongated clusters in gold standards that are harder to replicate with purely local clustering criteria.

Key Results

The proposed WSI + HAC method demonstrated superior performance compared to baseline methods:

  • Outperforming RAND: The WSI+HAC approach (specifically with single-linkage and average-linkage) significantly outperformed a random clustering baseline (RAND) on both the network and speaker datasets, achieving higher taxonomic similarity scores.
  • Outperforming TL MFS: The method also significantly outperformed the "taxonomy most frequent sense" (TL MFS) baseline, which does not perform WSI and relies on a single vector per word. This indicates that by capturing more senses, the WSI+HAC method discovers a greater number of correct taxonomic relations.
  • Sense Coverage: The superior performance is attributed to the WSI process enabling the learned taxonomies to contain a higher number of senses, leading to better coverage of the semantic space. For example, in the speaker dataset, the WSI+HAC method achieved 86.54% of the gold standard taxonomy senses with specific parameter settings.
  • Parameter Sensitivity: The performance was sensitive to parameters like collocation frequency and weight. Higher collocation weights (e.g., 0.4) tended to reduce sense coverage and overall performance, likely due to the creation of too many small clusters.

Limitations and Future Work

  • Mapping Induced Senses to WordNet: The paper acknowledges that mapping induced senses to WordNet senses can be challenging, and sometimes multiple induced senses might map to a single WordNet sense, requiring merging. This process might also miss domain-specific senses not present in WordNet.
  • Evaluation Metrics: Directly comparing automatically learned taxonomies with gold standards is difficult due to differences in internal node labeling and the nature of clusters. The authors propose a specific evaluation metric (TS) that focuses on internal nodes.
  • Future Work: The paper suggests that further research could explore more sophisticated WSI methods and investigate how to better handle the mapping of induced senses to existing knowledge bases like WordNet, especially for domain-specific terms. The authors also hint at the potential for improving the evaluation metrics to better capture the nuances of taxonomy comparison.

Summary updated

BibTeX
@inproceedings{klapaftis2010taxonomy,
  author = {Ioannis P. Klapaftis and Suresh Manandhar},
  title = {{Taxonomy Learning Using Word Sense Induction}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure