Abstract
This paper explores the use of two graph algorithms for unsupervised induction and tagging of nominal word senses based on corpora. Our main contribution is the optimization of the free parameters of those algorithms and its evaluation against publicly available gold standards. We present a thorough evaluation comprising supervised and unsupervised modes, and both lexical-sample and all-words tasks. The results show that, in spite of the information loss inherent to mapping the induced senses to the gold-standard, the optimization of parameters based on a small sample of nouns carries over to all nouns, performing close to supervised systems in the lexical sample task and yielding the second-best WSD systems for the Senseval-3 all-words task.
Introduction
Word Sense Disambiguation (WSD)—the task of determining which "sense" of a word is used in a given context—is a foundational challenge in Natural Language Processing. The field has long faced a "knowledge acquisition bottleneck": supervised systems perform best but require massive amounts of hand-tagged data, while unsupervised systems, which induce senses from raw text, historically struggle to match their accuracy. This paper addresses this gap by demonstrating that optimized graph-based unsupervised algorithms can achieve performance levels competitive with top-tier supervised models.
Methodology
The researchers explore two primary graph-based strategies to identify word senses, referred to as "hubs" in the graph:
- Graph Construction: For a target word, a co-occurrence graph is built where vertices are nouns found in the same paragraphs. Edges are weighted based on co-occurrence frequency.
- HyperLex: An iterative algorithm that identifies hubs by selecting the most frequent vertices and removing their neighbors from future consideration, creating distinct clusters.
- PageRank: Utilizing a random-walk model, this method ranks the importance of vertices to select hubs.
- Disambiguation via MST: Once hubs are found, a Minimum Spanning Tree (MST) is constructed. New instances are disambiguated by calculating the distance of surrounding context words to the hubs within the MST.
A key contribution of this work is the systematic optimization of eight parameters (e.g., minimum frequency, edge weight thresholds) that control graph construction and hub extraction.
Experimental Setup
The study utilizes several standard benchmarks:
- Senseval-2 (S2LS): Used as the development set to tune algorithm parameters.
- Senseval-3 Lexical Sample (S3LS): Used for testing performance on a specific set of target nouns.
- Senseval-3 All-Words (S3AW): A more difficult task where every word in a text must be disambiguated.
- SemCor: A hand-annotated corpus used to map induced clusters to standard WordNet senses for evaluation.
Results and Discussion
The optimized systems demonstrated significant improvements over traditional baselines. In the Senseval-3 Lexical Sample task, the graph-based methods outperformed the Most Frequent Sense (MFS) baseline by over 10 percentage points and performed within 1-2 points of state-of-the-art supervised systems using comparable features.
In the Senseval-3 All-Words task, the PageRank-based system (Pr_fr) achieved a recall of 70.7%, placing it second overall among all participating systems and only 0.2% behind the winner.
Key findings include:
- Micro-senses: Performance peaked when inducing a large number of hubs (60-70 per word), providing a richer feature set for disambiguation.
- Universal Optimization: Parameters tuned on a small sample of nouns generalized effectively to all nouns, suggesting consistent structural properties in co-occurrence graphs across language.
- Unsupervised-Supervised Correlation: Optimizing for purely unsupervised metrics (like entropy or purity) yielded parameters that also performed exceptionally well when mapped to supervised gold standards.
Conclusion
This research proves that unsupervised graph-based algorithms, specifically HyperLex and PageRank, can achieve WSD performance nearly identical to top-tier supervised systems when properly optimized. While the current study focuses on nouns, future work will explore extending these methods to verbs and adjectives, and integrating more complex syntactic features into the graph structures.
Summary updated