Concept Discovery from Text

Dekang Lin, Patrick PantelCOLING 2002

TL;DR

This paper introduces CBC (Clustering By Committee), a novel algorithm for automatically discovering semantic concepts from text. Unlike traditional methods that rely on simple centroids, CBC uses a "committee" of representative elements to define cluster centroids, leading to higher quality clusters and outperforming existing algorithms in experiments.

What Problem Does This Paper Address?

Lexical resources like WordNet are invaluable for natural language processing tasks, but they have limitations: they often contain rare senses and miss domain-specific ones. For instance, WordNet might list "dog" as a type of "person" (a rare sense) but miss the "user-interface-object" sense of "dialog" common in software manuals. This gap makes it difficult for NLP systems to accurately understand word meanings in specific contexts. The paper proposes an automatic clustering algorithm to discover these semantic classes directly from text, addressing the need for more contextually relevant and comprehensive semantic representations.

Methods

The paper introduces the CBC (Clustering By Committee) algorithm, which operates in three phases:

  • Phase I: Find Top-Similar Elements: For each element (word), the algorithm efficiently identifies its top-k most similar elements. This is done by leveraging the sparsity of feature vectors and indexing features, avoiding the computation of a full similarity matrix.
  • Phase II: Find Committees: This is the core innovation. CBC recursively identifies tight clusters called "committees." A committee's centroid is not a simple average of all its members but an average of a subset of its members, forming a more robust representation. Clusters are formed based on a score that balances size and tightness, and new committees are only added if they are sufficiently dissimilar to existing ones. This phase also identifies "residue" elements not yet assigned to a committee, which are then recursively clustered.
  • Phase III: Assign Elements to Clusters: Finally, each element is assigned to the cluster whose committee centroid it is most similar to. This phase is similar to K-means in assigning elements to the closest centroid, but the centroids are fixed and defined by the committees.

The paper also introduces a novel evaluation methodology based on the editing distance between the algorithm's output clusters and a manually generated "answer key" (classes extracted from WordNet). This measure quantifies the number of operations (merging clusters or moving elements) needed to make the output consistent with the answer key, normalized by the baseline of treating each element as its own cluster.

Datasets

The experiments were conducted on two test sets, S13403 and S3566, derived from a large news corpus (TREC collection) and WordNet.

  • The test sets were constructed by intersecting words from WordNet with nouns from the corpus that had a high mutual information score with their contexts.
  • Proper names (capitalized nouns) were removed due to WordNet's low coverage of them.
  • The sizes of WordNet classes vary significantly, with some containing very few words and others thousands.

Key Insights and Ideas

  • The "Committee" Concept: The most significant insight is the use of a "committee" of representative elements to define a cluster's centroid. This approach mitigates the problem of outliers or elements with marginal belonging unduly influencing the centroid, leading to more representative cluster centers.
  • Balancing Cluster Quality and Novelty: Phase II of CBC prioritizes both "tight" and "well-scattered" clusters. By ensuring new committees are dissimilar to existing ones, the algorithm aims to discover a diverse set of concepts rather than just refining existing ones.
  • Novel Evaluation Metric: The editing distance-based evaluation metric is a valuable contribution. It provides a more nuanced way to assess clustering quality by considering the cost of transforming output clusters into a gold standard, acknowledging that perfect replication of WordNet senses might be impossible.
  • WordNet's Limitations Highlighted: The experiments implicitly highlight WordNet's shortcomings, particularly its difficulty in capturing domain-specific senses and its sometimes arbitrary hierarchical classifications (e.g., "pest" under "person").

Key Results

  • Superior Cluster Quality: CBC consistently outperformed several well-known clustering algorithms (K-means, Buckshot, Bisecting K-means, Chameleon, Average-link, Complete-link, Single-link) on both test sets according to the proposed evaluation metric.
  • Quantitative Improvement: For example, in one experiment, CBC outperformed K-means by 4.25% on the S13403 dataset.
  • Coherent Clusters: Manual inspection of CBC-discovered clusters revealed high coherence, even for lower-ranked clusters. The features associated with these clusters were useful for classifying unseen words.
  • Chameleon Performance: Chameleon's hierarchical nature made it too slow to complete clustering on one of the test sets within a reasonable time.

Limitations and Future Work

  • Chameleon's Scalability: The paper notes that Chameleon's time complexity was a limitation, preventing its full evaluation on larger datasets.
  • WordNet's Oversight: The authors acknowledge that their evaluation method can reveal oversights in WordNet itself, as the algorithm might discover coherent clusters for senses not explicitly represented or well-categorized in WordNet.
  • Parameter Tuning: While specific thresholds (e.g., $\theta_1 = 0.35$) were used in experiments, the paper doesn't extensively discuss the sensitivity of the algorithm to these parameters or provide a systematic method for their selection.
  • Future Work: The paper suggests that the discovered semantic classes can be used for various NLP applications, implying future work could focus on integrating CBC into downstream tasks like Word Sense Disambiguation or Question Answering. The evaluation methodology itself could also be further explored and refined.

Summary updated

BibTeX
@inproceedings{lin2002concept,
  author = {Dekang Lin and Patrick Pantel},
  title = {{Concept Discovery from Text}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure