Abstract
In this paper we propose a machine-learning approach to paragraph boundary identification which utilizes linguistically motivated features. We investigate the relation between paragraph boundaries and discourse cues, pronominalization and information structure. We test our algorithm on German data and report improvements over three baselines including a reimplementation of Sporleder & Lapata's (2006) work on paragraph segmentation. An analysis of the features' contribution suggests an interpretation of what paragraph boundaries indicate and what they depend on.
Introduction
Paragraph Boundary Identification (PBI) is a critical task for document layout regeneration, particularly in multi-document summarization or when processing transcripts from speech recognition and OCR systems where original formatting is often lost. While similar to topic segmentation, PBI is more fine-grained and stylistic; a single topic can span multiple paragraphs.
Previous state-of-the-art approaches relied heavily on superficial surface features such as punctuation, sentence length, and specific keywords. This research investigates whether deeper, linguistically motivated features—specifically tracking entity reference (pronominalization) and syntactic information structure—can more accurately predict where humans naturally break paragraphs.
Methodology
The authors frame PBI as a binary classification problem: for every sentence, the model predicts whether it marks the start of a new paragraph. Two classifiers were evaluated: BoosTexter (a boosting algorithm) and TiMBL (a memory-based learner).
The core novelty of this approach lies in the introduction of features based on text cohesion:
- Pronominalization: This tracks "over-reference." Writers often restart a paragraph by using a full name even if a pronoun would be grammatically sufficient. The system tracks subject reference types and changes between sentences.
- Information Structure: In German, the first element of a sentence (the Vorfeld) often signals a thematic shift. The model tracks the syntactic category of this element.
- Discourse Cues: The model tracks connectives like "finally" or "afterwards."
- Lexical Cohesion: This measures noun and verb overlap between adjacent sentences.
A hill-climbing feature selection algorithm was utilized to identify the optimal subset of these features.
Dataset and Experimental Setup
The models were tested on a custom corpus of 970 German Wikipedia biographies (physicists, chemists, mathematicians, and biologists). The dataset contains approximately 413,000 tokens and 15,000 sentences, split into training (85%), development (10%), and test (5%) sets. Preprocessing included part-of-speech tagging, lemmatization, dependency parsing, named entity recognition, and coreference resolution.
Performance was compared against three baselines: a naive distance baseline (a break every 3 sentences), a topic-segmentation baseline (LCseg), and a reimplementation of the surface-feature model by Sporleder & Lapata.
Results and Analysis
Feature Contribution
Feature ablation and addition studies revealed that pronouns are powerful paragraph signals. The way a subject is referred to (e.g., switching from "he" back to "Einstein") was the strongest novel predictor. As shown in the feature addition analysis, adding the referring expression feature (currSRE) to a minimal set of surface features provided a massive 10.50% boost to the F-measure.
Conversely, discourse cues were found to be less effective in this specific dataset, likely due to data sparseness. The best-performing model successfully combined basic surface features (relative position, initial words) with these deep cohesive features.
Overall Performance
The optimized model using TiMBL achieved an F-measure of 58.50% and a WindowDiff score of 0.302 on the test set. This significantly outperformed the Sporleder & Lapata baseline (F-measure 54.68%, WindowDiff 0.345) and the naive distance baseline (F-measure 34.66%).
Conclusion
This study demonstrates that paragraphing is a hybrid of structural style and semantic content. Linguistically motivated features, particularly those related to pronominalization and information structure, provide significant improvements over surface-level models. Future work will involve testing these features on larger, more diverse datasets to address data sparseness in discourse cues and integrating the PBI system into broader multi-document summarization pipelines.
Summary updated