Abstract
Previous algorithms to compute lexical chains suffer either from a lack of accuracy in word sense disambiguation (WSD) or from computational inefficiency. In this paper, we present a new linear-time algorithm for lexical chaining that adopts the assumption of one sense per discourse. Our results show an improvement over previous algorithms when evaluated on a WSD task.
Introduction
Lexical cohesion is the property that gives a text a sense of unity, created by the presence of semantically related words (e.g., "cat" and "feline"). Lexical chaining is the computational process of identifying these threads of meaning throughout a document. It serves as a vital intermediate step for various Natural Language Processing (NLP) tasks, including automatic summarization, topic segmentation, and spell checking.
The primary challenge in lexical chaining is Word Sense Disambiguation (WSD). Since most words have multiple meanings (senses), an algorithm must correctly identify the intended sense for a chain to be semantically coherent. Historically, researchers faced a difficult trade-off:
- Greedy algorithms (e.g., Hirst and St-Onge) were computationally efficient (linear time) but often inaccurate because they committed to a word sense immediately upon encounter.
- Exhaustive algorithms (e.g., Barzilay and Elhadad) achieved higher accuracy but were computationally expensive (quadratic time), limiting their utility for long documents.
This paper introduces a "best of both worlds" solution: an algorithm that is both highly accurate and maintains linear time complexity.
Methodology
The proposed algorithm utilizes WordNet as its primary knowledge base and operates in three distinct phases:
1. Building the Disambiguation Graph
The algorithm performs a single pass through the text, identifying all possible semantic relations—such as synonyms, hypernyms/hyponyms, and siblings—for every sense of every noun. To maintain efficiency, the system uses an array-based indexing system to construct a "disambiguation graph" in linear time ($O(n)$).
2. Global Disambiguation
Instead of making local, word-by-word decisions, the algorithm applies the "one sense per discourse" constraint. It aggregates all occurrences of a word across the text and calculates the cumulative weight of all semantic edges connected to each potential sense. The sense with the highest total weight across the entire document is selected for every instance of that word.
3. Building the Chains
Once each word is assigned a single sense, the algorithm prunes the graph, discarding all edges connected to incorrect senses. The remaining connected components represent the final lexical chains. A key innovation is this separation of WSD from chaining, allowing the algorithm to leverage the global context of the entire document to inform local sense selection.
Evaluation and Results
The researchers evaluated the algorithm using the SemCor (Semantic Concordance) corpus, a subset of the Brown Corpus where words are manually annotated with their correct WordNet senses. The evaluation involved 74 documents containing approximately 35,000 nouns.
The proposed algorithm was benchmarked against two prominent models: Barzilay & Elhadad (1997) and Silber & McCoy (2003). As shown in the results, the new approach significantly outperformed the previous state-of-the-art.
The Galley and McKeown algorithm achieved an accuracy of 62.09%, a statistically significant improvement ($p < .001$) over Barzilay and Elhadad (56.56%) and Silber and McCoy (54.48%). Crucially, it achieved these results while maintaining linear time complexity, whereas the Barzilay and Elhadad model requires quadratic time.
Discussion
The success of this approach highlights several key insights:
- Heuristic Strength: The "one sense per discourse" heuristic is a powerful tool that simplifies WSD without substantial loss of accuracy.
- Weighted Relations: The algorithm benefits from weighting semantic links based on their type (e.g., synonyms are stronger than siblings) and their physical proximity in the text.
- Structural Efficiency: By delaying chain construction until after disambiguation, the model avoids the combinatorial explosion that hampered previous high-accuracy efforts.
While currently noun-centric and dependent on WordNet's coverage, this algorithm provides a robust foundation for more accurate and efficient lexical analysis in large-scale NLP applications. Future work may involve extending the model to other parts of speech and evaluating its impact on downstream tasks like summarization.
Summary updated