TL;DR
This paper introduces a novel approach to Multi-Sentence Compression (MSC) using vertex-labeled graphs and Integer Linear Programming (ILP). By incorporating keywords as vertex labels and introducing a 3-gram score, the method aims to generate more informative and grammatically correct compressed sentences than existing state-of-the-art techniques, with the added flexibility of controlling compression length.
What Problem Does This Paper Address?
The proliferation of digital information, from news articles to online encyclopedias, has created a need for efficient summarization techniques. Automatic Text Summarization (ATS) aims to condense large amounts of text into shorter, digestible summaries. A specific challenge within ATS is Multi-Sentence Compression (MSC), which focuses on generating a single, concise sentence that captures the core information from a cluster of closely related sentences. Existing MSC methods often rely on graph-based approaches that primarily consider word cohesion. However, these methods can sometimes sacrifice informativeness or grammaticality. This paper addresses the need for MSC systems that can balance these crucial aspects, ensuring both that the key information is retained and that the resulting sentence is grammatically sound, while also offering control over the output length.
Methods
The proposed method builds upon existing graph-based approaches for MSC, specifically referencing Filippova's work using Word Graphs (WG). The core innovation lies in extending this framework with two key features:
- Vertex-Labeled Graphs: Instead of just representing word cohesion, the vertices in the graph are now labeled with keywords. This allows the system to explicitly prioritize the inclusion of representative keywords in the compressed sentence. The authors explore three keyword extraction methods: Latent Semantic Indexing (LSI), Latent Dirichlet Allocation (LDA), and TextRank.
- Integer Linear Programming (ILP) for Optimization: An ILP model is formulated to select the optimal path (representing the compressed sentence) within the vertex-labeled graph. This ILP model incorporates:
- Cohesion Scores: Inherited from previous graph-based methods.
- Keyword Bonuses: Awarded for including labeled keywords, promoting informativeness.
- 3-gram Scores: A novel score is introduced to evaluate the relevance of 3-grams, aiming to improve the grammatical correctness of the output.
The ILP formulation uses the Miller-Tucker-Zemlin (MTZ) method to prevent sub-cycles and ensure a valid path is selected. The system also allows for a maximum compression length to be specified, offering control over the output.
Datasets
The primary dataset used for evaluation is a corpus of 618 French sentences spread across 40 clusters, originally compiled by Boudin and Morin (2013). This corpus is noted for its suitability for multi-document summarization and question-answering tasks due to its clusters containing multiple similar sentences. The authors mention that this corpus was chosen because it is well-suited for multi-document summarization and question-answering tasks, with each cluster containing three sentences compressed by native speakers.
Key Insights and Ideas
- Keywords are Crucial for Informativeness: The study strongly suggests that explicitly incorporating keywords into the graph structure significantly enhances the informativeness of the compressed sentences. The choice of keyword extraction method (LDA and LSI performing better than TextRank) also impacts performance.
- 3-grams Enhance Grammaticality: The introduction of a 3-gram score is a novel way to improve the grammatical quality of the compressed output, complementing the cohesion-based scoring.
- Controllable Compression Length: The ability to modulate the compression ratio by adjusting the number of keywords or by setting an explicit
MaxSizeconstraint is a valuable feature, allowing users to balance informativeness and conciseness. - ILP as a Powerful Optimization Tool: The paper demonstrates the effectiveness of ILP in solving complex graph-based optimization problems for MSC, allowing for the simultaneous consideration of multiple scoring factors.
Key Results
- Improved ROUGE Scores: The proposed ILP method, particularly when using 10 keywords, consistently outperforms two baseline systems (Filippova and Boudin et al.) in terms of ROUGE F-measures on the French corpus.
- Enhanced Informativeness: Both automatic (ROUGE) and manual evaluations show that the ILP method generates more informative sentences compared to the baselines.
- Comparable Grammaticality: While the Filippova method achieved slightly higher grammaticality scores, the ILP method maintained comparable levels of grammatical correctness.
- Flexible Compression Length: The system can generate compressions with varying lengths, and interestingly, even shorter compressions (around 55-60% CR) achieved better ROUGE recall scores than baselines at comparable lengths.
Limitations and Future Work
- Subjectivity of Manual Evaluation: The authors acknowledge that human evaluation can be subjective, as indicated by a Fleiss' kappa value of 0.303. They note that evaluators often compared outputs within a cluster to make their judgments.
- Potential for Further Grammaticality Improvement: The authors suggest that incorporating language models over Part-of-Speech (POS) tags could further improve grammaticality.
- Handling Polysemy: Managing polysemy by using the same label for synonyms of keywords within the Word Graph is identified as a future research direction.
- Integration with Extractive Summarization: The paper proposes combining their MSC approach with traditional extractive summarization methods to generate even better summaries.
Summary updated