Non-decreasing Sub-modular Function for Comprehensible Summarization

Litton J Kurisinkel, Pruthwik Mishra, Vigneshwaran Muralidaran, Vasudeva Varma, Dipti Misra SharmaNAACL 2016

TL;DR

This paper introduces a novel approach to extractive summarization that prioritizes comprehensibility over pure information coverage. By modeling sentences' "contextual independence" and incorporating this into a sub-modular scoring function, they achieve summaries that are more understandable and human-like, even with a slight trade-off in ROUGE scores.

What Problem Does This Paper Address?

Traditional extractive summarization techniques often focus on maximizing information coverage, measured by metrics like ROUGE scores. While this is important, it can lead to summaries where sentences, when taken out of their original context, become difficult to understand or even convey misleading information. This happens because sentences might rely heavily on preceding or following sentences for their meaning, especially through anaphora (pronoun references) or discourse connectives. The paper argues that for a summary to be truly useful, it needs to be comprehensible, meaning each sentence should make sense on its own or with minimal external context. They aim to address this gap by developing a method that explicitly models and favors contextually independent sentences.

Methods

The core of the paper's contribution lies in two main areas:

  • Contextual Independence Measurement: They propose a method to quantify how contextually independent a sentence is. Instead of relying on computationally expensive full syntactic parsing, they use a sequence labeling approach (CRF) with surface-level features. These features include:
  • Discourse Connectives (DConnect): Identifying words that link sentences (e.g., "however," "therefore").
  • Pronoun Count (PRPcount): The number of pronouns, which often signal anaphora.
  • Named Entity Count (NEcount): The number of named entities, which can help resolve references.
  • Coordinating Conjunctions (CC): Words like "and," "but."
    • Question Words (WhCount): For interrogative sentences.
  • Noun Phrases (NounPhrase): Identifying noun phrases that might start prepositional phrases.

    These features are extracted from a window of words preceding and following the sentence to capture local context. The model learns to predict the probability of a sentence being contextually independent.

  • Non-decreasing Sub-modular Scoring Function: They build upon the work of Lin and Bilmes (2011), which formulated summarization as a sub-modular function maximization problem. Sub-modular functions have the desirable property that a greedy approach can achieve a near-optimal solution. The authors augment the existing scoring function by adding the contextual independence score as a bias term. This new function, $F(S) = L_1(S) + \lambda_1 * R_1(S) + \lambda_2 * CI(S)$, encourages the selection of sentences that are more contextually independent, thus improving comprehensibility without significantly disturbing the sub-modular property.

  • Comprehensibility Index: They also propose a metric, $Compreh(S) = CI(S) / N$, where $CI(S)$ is the sum of contextual independence scores for sentences in a summary $S$, and $N$ is the number of sentences in $S$. This index aims to quantify the overall comprehensibility of a generated summary.

Datasets

  • Training Data: A corpus of 2900 narrative documents was used for training the LDU identification model. This corpus was annotated by two Computational Linguistics students.
  • Evaluation Data: The DUC-2004 Task2 dataset was used for evaluating the summarization system.

Key Insights and Ideas

  • Contextual Independence is Key to Comprehensibility: The paper strongly argues that a sentence's ability to stand alone (contextual independence) is a crucial factor for a summary's comprehensibility, more so than just covering information.
  • Surface-Level Features Suffice: Surprisingly, complex syntactic parsing is not necessary to achieve good results in measuring contextual independence. Simpler, surface-level features can effectively capture the necessary cues.
  • Sub-modularity is Preserved: By carefully adding the contextual independence score as a bias term, the authors ensure that the overall scoring function remains monotone sub-modular, allowing for efficient greedy optimization.
  • Human Evaluation Matters: The paper emphasizes the importance of human evaluation for assessing comprehensibility, as automated metrics like ROUGE don't fully capture this aspect.

Key Results

  • Improved Comprehensibility: Human evaluations showed a strong preference for summaries generated by their system over those produced by Lin and Bilmes, indicating significantly better comprehensibility. In one experiment, their summary was chosen overwhelmingly more often (70% vs. 13% for Lin & Bilmes, with 20% ambiguous).
  • ROUGE Score Trade-off: While comprehensibility improved, there was a proportional decline in content coverage as measured by ROUGE scores. However, the authors deem this decline "tolerable."
  • LDU Identification Accuracy: The LDU identification model achieved a Kappa score of 0.703 for agreement between annotators and an accuracy of 91.05% in classification.
  • Comprehensibility Index Validation: The proposed Comprehensibility Index showed good correlation with human judgments, achieving an accuracy of 79% in predicting which summaries humans would find more comprehensible.

Limitations and Future Work

  • Limited Context Window: The current LDU identification relies on a fixed window of preceding and succeeding sentences. The authors suggest that using Recurrent Neural Networks (RNNs) could allow for learning contextual dependencies beyond a single preceding sentence boundary.
  • Topical Context: The current approach focuses on local discourse context and structural dependence. Future work could improve comprehensibility estimation by incorporating more information regarding topical context.
  • ROUGE Score Decline: While acceptable, the decline in ROUGE scores is a limitation. Future work might explore ways to balance comprehensibility and content coverage more effectively.

Summary updated

BibTeX
@inproceedings{kurisinkel2016non,
  author = {Litton J Kurisinkel and Pruthwik Mishra and Vigneshwaran Muralidaran and Vasudeva Varma and Dipti Misra Sharma},
  title = {{Non-decreasing Sub-modular Function for Comprehensible Summarization}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2016},
}
Figure