Introduction
Multi-document summarization (MDS) aims to generate a concise summary from a set of related documents. This task is categorized into traditional summarization and update summarization. The latter is particularly challenging as it requires "novelty detection"—identifying new information while avoiding redundancy from previously read articles. Researchers from Tsinghua University addressed these challenges by developing a formal framework based on Information Distance theory, which they presented at the Text Analysis Conference (TAC) 2009.
Theoretical Framework
The proposed method moves away from ad-hoc heuristics toward a mathematically grounded approach using algorithmic information theory.
- Information Distance & Kolmogorov Complexity: The theory utilizes Kolmogorov complexity ($K(x)$), which represents the length of the shortest program required to generate a string. The "distance" between documents measures the information needed to transform one into another.
- The "Most Typical" Object: The ideal summary is defined as the "most typical" object—the one that minimizes the sum of distances to all documents in the set. This distinguishes "typicality" (conciseness and shared ideas) from "comprehensiveness."
- Conditional Modeling for Update Tasks: Update summarization is modeled using conditional information distance. The summary must minimize the distance to new documents given the information already present in the "old" documents. This allows a single mathematical model to handle both tasks seamlessly, as traditional summarization is simply a case with an empty set of previously read material.
- Practical Implementation: Since Kolmogorov complexity is uncomputable, it is approximated using Shannon-Fano coding, where phrases are encoded based on their probability ($-\log p$ bits). The system also incorporates semantic element extraction and coreference resolution to normalize entities (e.g., linking "George Bush" to "George W. Bush").
Internal Evaluation
Before the official competition, the "new" 2009 method was compared against the team's 2008 system using DUC 2007 and TAC 2008 benchmarks. The new method consistently outperformed the old one in ROUGE-1 recall across various test clusters.
TAC 2009 Results and Discussion
The system was officially evaluated in the TAC 2009 competition against 51 other participants. The results highlighted the effectiveness of the conditional information distance model, particularly in update summarization.
In the update summarization task, the system ranked 1st in Average Linguistic Quality and 1st in Average Overall Responsiveness. For traditional summarization, while content scores (Modified Score) were lower (ranking 9th), the system maintained high readability, ranking 3rd in Linguistic Quality and 2nd in Overall Responsiveness.
The superior performance on update tasks suggests that the information distance framework is exceptionally well-suited for filtering out redundant information. However, the authors note that performance is currently limited by the statistical approximations used for Kolmogorov complexity. Future work will focus on refining these approximation methods and capturing more complex semantic relationships.
Conclusion
By framing summarization as a compression problem—where the best summary is the most efficient "bridge" to the source text—the Tsinghua team demonstrated a unified approach to multi-document summarization. Their success at TAC 2009 validates the use of Information Distance as a robust metric for both typicality and novelty detection.
Summary updated