Improving Update Summarization via Supervised ILP and Sentence Reranking

Chen Li, Yang Liu, Lin ZhaoNAACL 2015 · DOI

Abstract

Update summarization aims to generate summaries of new document sets while excluding information already present in a prior set. Traditional methods rely on simple heuristics for concept weighting, often failing to distinguish between general salience and specific novelty. This paper introduces a supervised Integer Linear Programming (ILP) framework that learns bigram weights using an Average Perceptron model. This is followed by a two-step sentence reranking process using Support Vector Regression (SVR). Evaluation on TAC 2008-2011 datasets shows that this approach consistently outperforms standard ILP baselines and previous state-of-the-art systems.

Introduction

In automated summarization, Update Summarization presents a unique challenge: given a set of old documents (Set A) and a set of new documents (Set B) on the same topic, the system must generate a summary of Set B containing only novel information.

Most existing methods utilize Integer Linear Programming (ILP) to select sentences that maximize the total weight of covered concepts (typically bigrams) within a word limit. However, these models often rely on simple heuristics, such as document frequency, to determine concept weights. Such heuristics struggle to differentiate between information that is generally important (salience) and information that is specifically new to the second document set (novelty).

Methodology

The proposed framework improves the standard ILP approach through two primary components:

Supervised Bigram Weighting

Instead of raw frequency, a supervised model (Average Perceptron) is used to learn bigram weights. The model utilizes a rich feature set:

  • Importance Features: Document frequency in the new set, sentence position, and query overlap.
  • Novelty Features: Document frequency in the old set, and specific metrics like "bigram novelty value" and "uniqueness value."

Two-Step Sentence Reranking

While ILP excels at global optimization, it can overlook sentence-level nuances. The authors implement a two-step process:

  1. Candidate Generation: The supervised ILP generates a "long" summary (e.g., 200 words).
  2. Fine-grained Selection: Support Vector Regression (SVR) reranks these candidate sentences based on features like similarity to the old summary and sentence length to select the final 100-word output.

Experimental Setup

The system was evaluated using the TAC (Text Analysis Conference) update summarization datasets from 2008 to 2011. Each topic includes two sets of 10 documents. The goal is to produce a 100-word summary of Set B, assuming the user has read Set A. Performance is measured using ROUGE-2 (Recall-Oriented Understudy for Gisting Evaluation).

Results and Analysis

The proposed two-step supervised method consistently outperformed the standard ILP baseline and surpassed the "TAC Best" systems in several years.

Comparison of ROUGE-2 scores across TAC datasets for various system configurations.

As shown in the table above, the system achieved a ROUGE-2 score of 8.11 in TAC 2010 (beating the TAC Best of 8.00) and 9.99 in TAC 2011 (significantly higher than the TAC Best of 9.58). These results confirm that incorporating novelty-related features specifically enhances performance on update tasks.

The "N" Factor and Sensitivity

A key insight from the study is the sensitivity of the system to the length of the initial ILP output (the candidate set size $N$).

ROUGE-2 performance relative to the length of the initial ILP output.

Generating a candidate set of 150–250 words before reranking yielded the best results. If the candidate set is too large, it introduces redundancy that the current reranker cannot effectively filter, leading to a decline in performance.

Conclusion

This research demonstrates that moving from heuristic-based ILP to a supervised framework significantly improves update summarization. By explicitly modeling novelty and employing a two-step selection process, the system achieves superior content selection. Future work may focus on incorporating explicit redundancy removal (such as Maximal Marginal Relevance) into the reranking phase and expanding the feature set for the regression model to further refine sentence selection.

Summary updated

BibTeX
@inproceedings{li2015improving,
  author = {Chen Li and Yang Liu and Lin Zhao},
  title = {{Improving Update Summarization via Supervised ILP and Sentence Reranking}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  doi = {10.3115/v1/n15-1145},
}
Figure