Maximum lexical cohesion for fine-grained news story segmentation

Zihan Liu, Lei Xie, Wei FengInterspeech 2010 · DOI

Introduction

Automated news processing relies heavily on "story segmentation"—the process of dividing a continuous stream of text or audio into discrete news items. While punctuation and paragraph breaks facilitate this in written text, Automatic Speech Recognition (ASR) transcripts present a significant challenge. These transcripts often lack reliable sentence delimiters, appearing as a continuous "bag of words."

Traditional methods attempt to solve this by imposing "pseudo-sentences" (e.g., blocks of 20 words). However, this approach suffers from boundary mismatch—where a story ends mid-block—and high sensitivity to the chosen block size. To address these issues, researchers have proposed a Maximum Lexical Cohesion (MLC) framework designed for fine-grained segmentation at the word or subword level, eliminating the need for artificial boundaries.

Methodology: Maximum Lexical Cohesion

The MLC approach treats segmentation as a global optimization problem, focusing on three core components:

1. Measuring Cohesion via KL-Divergence

Instead of simple word overlap, the system measures how a segment's word distribution deviates from a "piecewise uniform" distribution using Kullback-Leibler (KL) divergence. In a cohesive segment, topic-specific words appear significantly more frequently than they would by random chance.

2. Difference From Expectation (DFE) Weighting

A novel weighting scheme, Difference From Expectation (DFE), was introduced. Unlike standard Inverse Document Frequency (IDF), which relies on global corpus statistics, DFE measures how much a word's frequency within a specific segment differs from its average frequency in the current document. This effectively filters out common "stop words" and highlights the specific vocabulary defining a news story.

3. Length Regularization

To prevent the algorithm from merging multiple stories into a single large block, the system incorporates an exponential prior. This mathematical constraint reflects the empirical observation that very long news stories are statistically rare, helping the model maintain realistic story boundaries.

Distribution of story lengths in the TDT2 corpus, showing the exponential decay used for length regularization.

Experimental Evaluation

The framework was tested on the TDT2 Mandarin Broadcast News (BN) corpus, consisting of approximately 53 hours of VOA Mandarin audio. The transcripts, generated by the Dragon LVCSR system, featured a high word error rate (37%), providing a rigorous test for robustness. Evaluation focused on both words and subword units (character n-grams and syllables), which are typically more resilient to ASR errors.

Key Results and Insights

The MLC approach significantly outperformed existing state-of-the-art methods. Using character bigrams and DFE weighting, the system achieved a peak F1-measure of 0.7230, representing a 4.62% relative improvement over previous subword-based methods.

Comparison of F1-measures across various segmentation methods, highlighting the superior performance of the proposed MLC framework.

Subwords and Local Context

A critical finding was that character bigrams outperformed full words in noisy ASR data. While speech recognition often misidentifies specific words, the underlying characters are frequently captured correctly. Furthermore, the DFE weighting proved more effective than IDF for longer n-grams, suggesting that local context within a broadcast is more informative for fine-grained segmentation than global historical data.

Conclusion

The MLC framework provides a robust solution for segmenting noisy speech transcripts without relying on sentence markers. By combining global optimization via dynamic programming with local lexical cohesion measures, the system achieves high accuracy even in the presence of significant ASR errors. Future work may involve integrating acoustic cues, such as pauses and pitch changes, to further refine boundary detection.

Summary updated

BibTeX
@inproceedings{liu2010maximum,
  author = {Zihan Liu and Lei Xie and Wei Feng},
  title = {{Maximum lexical cohesion for fine-grained news story segmentation}},
  booktitle = {Interspeech},
  year = {2010},
  doi = {10.21437/interspeech.2010-407},
}
Figure