Abstract
Min-Yen Kan, Judith L. Klavans, Kathleen R. McKeown. Sixth Workshop on Very Large Corpora.
1998.
Introduction
In the late 1990s, natural language processing faced the challenge of "linear segmentation"—partitioning long texts into topically coherent blocks. While existing methods like TextTiling identified boundaries, they lacked the ability to characterize the role or significance of the resulting segments. This paper introduces a dual-module system, SEGMENTER and SEGNIFIER, designed to both locate topic shifts and rank segments by their importance for downstream tasks like summarization.
SEGMENTER: Finding Boundaries via Lexical Chains
The first module, SEGMENTER, identifies boundaries by analyzing lexical chains—sequences of related words that persist through a text. Unlike previous methods that treated all words equally, SEGMENTER employs term-specific link distances. It recognizes that different parts of speech have different "lifespans": proper nouns can link across many sentences, while pronouns have a very short scope.
Zero-Sum Weighting
The core innovation of SEGMENTER is its zero-sum weighting scheme. For every term, the system assigns scores to paragraphs based on their position relative to a lexical link:
- Front (f): Starts a link.
- During (d): Continues a link.
- Rear (r): Follows a link.
These weights are normalized so that the total score for any term across the entire document is zero. This filtering mechanism prevents ubiquitous "noisy" words from triggering false boundaries. A positive total score in a paragraph indicates a likely candidate for a new segment.
SEGNIFIER: Determining Significance
Once boundaries are established, the SEGNIFIER module evaluates the importance of each segment. It uses several metrics:
- TF*SF (Term Frequency * Segment Frequency): A variation of TF*IDF that rewards segments containing "central" terms appearing across multiple segments.
- Coverage: A measure of how well a segment represents the document's overall vocabulary using a harmonic series.
- Functional Labeling: Segments are classified as Summary (high importance), Anecdotal (introductory color using unique proper nouns), or Support (detailed filler).
Evaluation and Results
The system was tested on 20 news articles from the Wall Street Journal and The Economist, using a "gold standard" derived from human judges. SEGMENTER achieved a 10% increase in precision and recall over the TextTiling baseline, reaching 42.6% precision and 39.6% recall. Furthermore, incorporating segment significance into a sentence extraction system improved key sentence recall by 3.1%.
Conclusion
The research highlights that not all words contribute equally to topical flow. By modeling the "lifespan" of different word types and using zero-sum normalization, the authors significantly improved segmentation accuracy. While human agreement on discourse boundaries remains a challenge (62% in this study), the functional labeling provided by SEGNIFIER offers a valuable layer of context for automated summarization and information retrieval.
Summary updated