A Practical Solution to the Problem of Automatic Word Sense Induction

Reinhard RappACL 2004

TL;DR

This paper proposes a novel approach to automatically discover the different meanings (senses) of a word by clustering its local contexts, rather than relying on global co-occurrence statistics. By leveraging Singular Value Decomposition (SVD) to handle data sparsity, the method achieves a significant improvement in accurately identifying word senses, outperforming approaches that don't reduce dimensionality.

What Problem Does This Paper Address?

Word Sense Induction (WSI) is the task of automatically discovering the different meanings a word can have. This is a crucial step for many Natural Language Processing (NLP) tasks, as a word's meaning can drastically change its interpretation. Traditional WSI methods often rely on "global co-occurrence vectors," which represent a word's overall behavior across an entire corpus. The problem is that for ambiguous words, these global vectors are essentially mixtures of all their senses, making it difficult to disentangle them. Human performance shows that a word's local context is usually sufficient to determine its sense, suggesting that local information is key. This paper tackles the challenge of effectively using these local contexts for WSI, overcoming the inherent data sparsity problem.

Methods

The core of this paper's approach is to move away from global co-occurrence vectors and instead focus on "local co-occurrence vectors." For a given ambiguous word, the algorithm constructs a "term/context matrix" where rows represent potential context words and columns represent the local contexts (windows of text) in which the ambiguous word appears.

  1. Local Contextualization: Instead of analyzing a word's overall usage, the algorithm examines each instance of the ambiguous word within its immediate surroundings (±20 words).
  2. Term/Context Matrix Creation: For each ambiguous word, a matrix is built where entries indicate the presence of specific context words within its local windows.
  3. Dimensionality Reduction with SVD: To combat the extreme sparsity of these local context matrices, Singular Value Decomposition (SVD) is applied. The authors found that reducing the matrix to its three most significant dimensions was sufficient to generalize effectively and improve results.
  4. Clustering: The row vectors (representing context words) of the SVD-reduced matrix are then clustered using a hierarchical clustering algorithm. The resulting clusters are interpreted as the different senses of the ambiguous word.

The novelty lies in the explicit focus on local contexts and the successful application of SVD to mitigate sparsity, a common issue in such fine-grained analyses.

Datasets

The experiments were conducted on a partially lemmatized version of the British National Corpus (BNC). The authors used a list of 12 ambiguous words provided by Yarowsky (1995) for their experiments.

Key Insights and Ideas

  • Local Context is King: The paper strongly advocates for using local context windows over global co-occurrence vectors for WSI, aligning with human disambiguation capabilities.
  • SVD as a Sparsity Solver: SVD is not just a smoothing technique; it's presented as a crucial tool for dimensionality reduction that effectively handles the data sparsity inherent in local context analysis, leading to more salient and accurate sense distinctions.
  • Dendrograms as Diagnostic Tools: The paper uses dendrograms (visual representations of hierarchical clustering) to intuitively demonstrate the impact of SVD, showing how it leads to clearer, more human-intuitive cluster separations.
  • Sense-Specific Associations: Clustering local contexts allows for the discovery of sense-specific associations. For example, animals associated with "poach" can be correctly separated into those related to cooking versus those related to illegal hunting, a distinction that would be lost in global vectors.

Key Results

  • Improved Accuracy: The proposed method, using SVD on local context vectors, achieved an average accuracy of 85.6% in correctly classifying the top 30 associations into their respective senses, with only 4.3 misclassifications on average.
  • Qualitative Improvements: Visualizations (dendrograms) for words like "palm" and "poach" clearly show that the SVD-enhanced approach produces more distinct and intuitively correct sense clusters compared to clustering without SVD. For "palm," the word "frond" was correctly placed in the "tree" cluster after SVD, whereas it was ambiguous without it.
  • Handling Nuance: The clustering of local contexts allowed for nuanced distinctions, such as separating animals based on their relation to cooking versus poaching, demonstrating the method's ability to capture fine-grained semantic differences.

Limitations and Future Work

  • Data Sparsity Remains a Challenge: While SVD helps, the matrices of local vectors are still extremely sparse.
  • Future Work - Broader Context:
    • Considering All Context Words: Instead of just the top 30 associations, using all context words could further reduce sparsity issues, though this requires finding a more suitable association function than the current log-likelihood ratio.
  • Part-of-Speech Tagging: Incorporating part-of-speech information could lead to more refined sense distinctions, especially for senses that affect grammatical usage.
  • Dictionary Granularity: The authors acknowledge that their algorithm may not achieve the fine-grained distinctions found in comprehensive dictionaries like LDOCE or lexical databases like WordNet.

Summary updated

BibTeX
@inproceedings{rapp2004practical,
  author = {Reinhard Rapp},
  title = {{A Practical Solution to the Problem of Automatic Word Sense Induction}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2004},
}
Figure