A General Optimization Framework for Multi-Document Summarization Using Genetic Algorithms and Swarm Intelligence

Maxime Peyrard, Judith Eckle-KohlerCOLING 2016 · OpenReview

Abstract

This paper introduces a flexible optimization framework for extractive multi-document summarization (MDS) that bypasses the mathematical constraints of traditional scoring metrics. By employing metaheuristics—specifically Genetic Algorithms (GA) and Swarm Intelligence (Artificial Bee Colony)—the authors can optimize for complex, non-linear, and non-submodular objectives like Jensen-Shannon (JS) divergence. Evaluated on DUC-2002 and DUC-2003 datasets, the framework achieves state-of-the-art results comparable to ILP-based systems while discovering a diverse range of high-quality summaries that traditional methods often overlook.

Introduction

Extractive multi-document summarization (MDS) is the task of selecting a representative subset of sentences from a large collection of documents. Traditionally, this is treated as a discrete optimization problem. To solve it efficiently, researchers usually rely on Integer Linear Programming (ILP) or submodular function maximization.

However, these methods come with a "mathematical tax": the objective function must be either linearly factorizable or submodular. While the popular ROUGE metric fits these criteria, many other promising information-theoretic metrics—like Jensen-Shannon (JS) divergence—do not. This constraint has often forced researchers to choose metrics based on mathematical convenience rather than correlation with human judgment. This paper breaks that constraint by providing a framework where any metric can be used as the optimization target.

Methodology

The authors propose two biologically-inspired metaheuristic approaches to navigate the massive search space of possible sentence combinations:

  1. Genetic Summarizer (GA): This simulates evolution. A population of valid summaries undergoes iterations of reproduction (combining high-performing parents), mutation (randomly swapping sentences), and selection. A key feature is "Embryogenesis," which ensures the algorithm only considers summaries meeting length constraints at every step.
  2. Swarm Summarizer (Artificial Bee Colony - ABC): This simulates honey bees searching for nectar. Employed bees perform local searches, onlooker bees investigate areas based on fitness scores, and scout bees perform random restarts to avoid local optima.

The framework is "plug-and-play," allowing researchers to provide documents and any scoring function (e.g., JS divergence) to find the optimal summary.

Experimental Setup

The framework was evaluated using the DUC-2002 and DUC-2003 benchmarks, which are standard for MDS and contain news article clusters with human-written reference summaries. The primary optimization target was JS divergence, with performance measured using both JS and ROUGE metrics.

Key Results

The Genetic and Swarm summarizers significantly outperformed greedy baselines. When optimizing for JS divergence, the framework performed on par with ICSI, a top-tier ILP-based system, in terms of ROUGE scores, while achieving superior results on information-theoretic metrics.

Table 1: Performance comparison of metaheuristic methods (GA and Swarm) against baselines and state-of-the-art systems on DUC datasets.

The Swarm Summarizer (ABC) was particularly efficient, converging to high-quality solutions in approximately one minute per topic on a standard laptop, compared to 2-3 minutes for the Genetic Algorithm.

Discussion: Diversity and "Many Paths to Greatness"

A significant discovery was that the algorithms produced summaries with high ROUGE scores that had very little sentence overlap with summaries from other state-of-the-art systems. This suggests that the "summary space" contains many distinct peaks of high quality.

Table 2: Jaccard similarity metrics showing low overlap between the proposed framework and ICSI, alongside high internal diversity.

As shown in Table 2, the Jaccard similarity between the framework's summaries and ICSI's was less than 10%. This proves the framework's ability to find novel, high-quality content that traditional methods miss. Furthermore, JS divergence proved to be a powerful complementary metric, helping to identify the most representative summaries among several candidates with similar ROUGE scores.

Conclusion

While metaheuristics require hyperparameter tuning and are computationally more intensive than simple greedy heuristics, they offer a powerful way to optimize "black-box" functions directly. Future work could involve optimizing combined metrics—such as a weighted sum of ROUGE, JS divergence, and readability—to produce summaries that are both informative and linguistically superior. The authors have released their Python-based framework to encourage further community experimentation.

Summary updated

BibTeX
@inproceedings{peyrard2016general,
  author = {Maxime Peyrard and Judith Eckle-Kohler},
  title = {{A General Optimization Framework for Multi-Document Summarization Using Genetic Algorithms and Swarm Intelligence}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2016},
  url = {https://openreview.net/forum?id=6UKEsqHoia1},
}
Figure