Introduction
Multi-document summarization (MDS) is the process of distilling information from a collection of related documents into a concise, unified text. While extractive techniques can identify the most salient sentences, arranging them into a coherent narrative remains a significant challenge. Without proper ordering, the resulting summary often resembles a "Frankenstein" text—a collection of disjointed segments that lack logical flow and stylistic consistency, making them difficult for humans to process.
Traditional ordering strategies frequently fall short. Chronological Ordering is effective for news but relies on timestamps that are often missing or inconsistent. Majority Ordering (MO) attempts to find common themes across documents but is prone to "topic disruption" due to its rigid heuristic nature. Probabilistic Ordering (PO) typically employs a Markovian assumption, where the choice of the next sentence depends only on the current one. This "short-term memory" often leads to "topic bias," where the algorithm becomes trapped in a repetitive loop because it lacks a record of previously covered information.
Methodology
The authors propose a robust two-stage pipeline that combines advanced classification with a history-aware ordering mechanism.
Manifold-based Sentence Classification
The first stage involves grouping document sentences into classes corresponding to the sentences selected for the summary. This is a difficult classification task because only one labeled example exists for each class (the summary sentence itself). Standard supervised algorithms like Support Vector Machines (SVMs) struggle with such extreme data sparsity.
The authors utilize a semi-supervised manifold approach. They construct a sentence network where edges are weighted by Jensen-Shannon divergence, a measure of distributional similarity. By executing a Markov random walk on this graph, the algorithm identifies the underlying "manifold" or geometric structure of the data. This allows label information to propagate from the single summary sentence to thousands of unlabeled document sentences based on global density rather than simple local proximity.
Historical Ordering (HO)
Once sentences are classified, the Historical Ordering (HO) strategy determines their final sequence. The core innovation of HO is its departure from the Markovian "memoryless" property.
As illustrated in the directed graph above, sentence classes are nodes, and edges represent potential transitions with associated weights. Unlike PO, which only considers the last sentence, HO maintains a "history" of all previously selected sentences. When a class is chosen, its relationships with all remaining classes are used to update the transition weights for the next step. This cumulative process ensures the summary maintains thematic continuity while preventing the model from drifting off-topic or becoming redundant.
Experimental Setup and Results
The system was evaluated using the DUC04 (Document Understanding Conference 2004) dataset, which contains 50 document clusters, each with 20 documents and 4 human-written "gold standard" summaries. Performance was quantified using Kendall’s $\tau$, a coefficient measuring the alignment between algorithmic and human ordering.
The results demonstrate the superiority of the HO approach:
- HO (Historical Ordering): 0.42
- PO (Probabilistic Ordering): 0.33
- MO (Majority Ordering): 0.31
Furthermore, the manifold-based classification exhibited lower pointwise entropy compared to SVMs, indicating higher confidence in class assignments. The researchers also identified a "Goldilocks" zone for data density: performance was optimal when using the top 40% of sentences ranked by membership probability. Including the noisier bottom 60% introduced significant confusion into the ordering logic.
Conclusion
This paper highlights the power of the manifold assumption in NLP tasks with sparse labels. By treating summarization as a cumulative path through a structured data space rather than a simple chain of local transitions, the authors achieve significantly more coherent and readable summaries. Future research will focus on integrating word-level features, resolving co-references, and developing more sophisticated models for natural topic transitions.
Summary updated