Linear Segmentation and Segment Significance

Min-Yen Kan, Judith L. Klavans, Kathleen R. McKeown

Abstract

Automatically decomposing documents into coherent topical segments is a fundamental challenge in natural language processing. This paper introduces a two-part system consisting of SEGMENTER, which identifies linear segment boundaries, and SEGNIFIER, which evaluates the significance and functional role of those segments. By employing a zero-sum weighting scheme that accounts for the varying discourse properties of proper nouns, common nouns, and pronouns, the proposed method achieves a 10% improvement in segmentation accuracy over existing state-of-the-art algorithms like TextTiling.

Introduction

For human readers, a long document is not a flat sequence of words but a structured collection of sub-topics. Identifying this "discourse structure" is essential for advanced tasks such as automated summarization and targeted information retrieval. While previous methods like TextTiling relied heavily on simple word repetition, they often lacked precision and failed to provide context regarding the importance or function of the identified segments. This research addresses these gaps by integrating linguistic intuition into a robust algorithmic framework.

The SEGMENTER System

The first stage of the pipeline, SEGMENTER, focuses on identifying where one topic ends and another begins. Unlike previous models that treat all words equally, SEGMENTER prioritizes "terms"—specifically proper nouns, common nouns, and pronouns.

The SEGMENTER pipeline consists of term identification, link weighting, and boundary scoring.

Linguistic Weighting and Zero-Sum Scoring

A core innovation of this work is the recognition that different linguistic categories have different "shelf lives" in discourse. For instance, a proper noun can link across many paragraphs, whereas a pronoun typically only refers to a very recent antecedent. The system assigns weights based on where a term link appears relative to a paragraph: at the start (Front), continuing (During), or ending (Rear).

Weighting table for different term types based on their position and link length.

To avoid the need for arbitrary thresholds, the authors implemented a zero-sum weighting scheme. In this approach, positive scores for active links are balanced by negative scores in paragraphs where the term is absent. This normalization allows the system to identify boundaries by searching for local maxima in the total paragraph scores, making it resilient to variations in document length and term density.

SEGNIFIER: Assessing Segment Significance

Once segments are delineated, the SEGNIFIER component evaluates their role within the document. It uses a modified Term Frequency * Segment Frequency (TF*SF) metric to identify "central" terms that persist throughout the text. Segments are then classified into functional roles:

  • Summary: High-importance segments located at the document's periphery.
  • Anecdotal: Segments introducing unique proper nouns that do not reappear, often serving as journalistic "leads."
  • Support: Segments providing detailed evidence or elaboration.

Evaluation and Results

The system was evaluated using a corpus of 20 news articles from the Wall Street Journal and The Economist. A "gold standard" was established by aggregating the judgments of at least four human readers per article.

Key findings include:

  • Accuracy: SEGMENTER outperformed the TextTiling algorithm by 10% in both precision and recall.
  • Summarization Utility: Incorporating segment significance into a summarization system led to a 3.1% increase in the recall of key sentences.
  • Human Alignment: Despite the inherent subjectivity of segmentation (human agreement was approximately 62%), the system's outputs closely mirrored the majority human opinion.

Conclusion

By grounding algorithmic segmentation in linguistic principles, this research demonstrates that distinguishing between term types significantly improves discourse analysis. The zero-sum weighting scheme provides a robust method for boundary detection without manual threshold tuning. Future work will explore the application of machine learning to automatically refine weights and test the system's performance on longer, more complex document types.

Summary updated

BibTeX
@inproceedings{kan1998linear,
  author = {Min-Yen Kan and Judith L. Klavans and Kathleen R. McKeown},
  title = {{Linear Segmentation and Segment Significance}},
  booktitle = {VLC @ COLING},
  year = {1998},
  url = {https://openreview.net/forum?id=0fGZAXQqNTm},
}
Figure