A Study of Global Inference Algorithms in Multi-document Summarization
Lecture notes in computer sciencePublished 4 June 2007
Ryan McDonald
Citations365
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work defines a general framework for inference in summarization and presents three algorithms: a greedy approximate method, a dynamic programming approach based on solutions to the knapsack problem, and an exact algorithm that uses an Integer Linear Programming formulation of the problem.
Abstract
In this work we study the theoretical and empirical properties of various global inference algorithms for multi-document summarization. We start by defining a general framework for inference in summarization. We then present three algorithms: The first is a greedy approximate method, the second a dynamic programming approach based on solutions to the knapsack problem, and the third is an exact algorithm that uses an Integer Linear Programming formulation of the problem. We empirically evaluate all three algorithms and show that, relative to the exact solution, the dynamic programming algorithm provides near optimal results with preferable scaling properties.
Keywords
Computer Science
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
IBM Journal of Research and DevelopmentThe Automatic Creation of Literature Abstracts
3,211 Citations1958H. P. Luhn
In the exploratory research described, the complete text of an article in machine-readable form is scanned by an IBM 704 data-processing machine and analyzed in accordance with a standard program.
Automatic evaluation of summaries using N-gram co-occurrence statistics
1,588 Citations2003Chin-Yew Lin, Eduard Hovy
The results show that automatic evaluation using unigram co-occurrences between summary pairs correlates surprising well with human evaluations, based on various statistical metrics; while direct application of the BLEU evaluation procedure does not always give good results.
Journal of the ACMNew Methods in Automatic Extracting
1,469 Citations1969H. P. Edmundson
New methods of automatically extracting documents for screening purposes, i.e. the computer selection of sentences having the greatest potential for conveying to the reader the substance of the document, indicate that the three newly proposed components dominate the frequency component in the production of better extracts.
A trainable document summarizer
1,349 Citations1995Julian Kupiec, Jan Pedersen +1 more
The trends in the results are in agreement with those of Edmundson who used a subjectively weighted combination of features as opposed to training the feature weights using a corpus, which suggests that even shorter extracts may be useful indicative summmies.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)A Linear Programming Formulation for Global Inference in Natural Language Tasks
442 Citations2004Dan Roth, Wen-tau Yih
This work develops a linear programing formulation for this problem and evaluates it in the context of simultaneously learning named entities and relations to efficiently incorporate domain and task specific constraints at decision time, resulting in significant improvements in the accuracy and the "human-like" quality of the inferences.
Machine LearningSearch-based structured prediction
436 Citations2009Hal Daumé, John Langford +1 more
Searn is an algorithm for integrating search and learning to solve complex structured prediction problems such as those that occur in natural language, speech, computational biology, and vision and comes with a strong, natural theoretical guarantee: good performance on the derived classification problems implies goodperformance on the structured prediction problem.
Journal of the ACMApproximation algorithms for classification problems with pairwise relationships
405 Citations2002Jon Kleinberg, Éva Tardos
Multi-document summarization by sentence extraction
356 Citations2000Jade Goldstein, Vibhu O. Mittal +2 more
This paper discusses a text extraction approach to multi- document summarization that builds on single-document summarization methods by using additional, available information about the document set as a whole and the relationships between the documents.
Journal of Artificial Intelligence ResearchInferring Strategies for Sentence Ordering in Multidocument News Summarization
333 Citations2002Regina Barzilay, Noémie Elhadad
A strategy for ordering information that combines constraints from chronological order of events and topical relatedness is implemented and Evaluation of the augmented algorithm shows a significant improvement of the ordering over two baseline strategies.
Fast decoding and optimal decoding for machine translation
234 Citations2001Ulrich Germann, Michael Jahr +3 more
This paper compares the speed and output quality of a traditional stack-based decoding algorithm with two new decoders: a fast greedy decoder and a slow but optimal decoder that treats decoding as an integer-programming optimization problem.
Sentence Extraction as a Classification Task
217 Citations1997Simone Teufel
Columbia Academic Commons (Columbia University)Towards multidocument summarization by reformulation: progress and prospects
192 Citations1999Kathleen McKeown, Judith L. Klavans +3 more
The evaluation of system components shows that learning over multiple extracted linguistic features is more effective than information retrieval approaches at identifying similar text units for summarization and that it is possible to generate a fluent summary that conveys similarities among documents even when full semantic interpretations of the input text are not available.
Semantic role labeling via integer linear programming inference
172 Citations2004Vasin Punyakanok, Dan Roth +2 more
A system that combines a machine learning technique with an inference procedure based on integer linear programming that supports the incorporation of linguistic and structural constraints into the decision process for semantic role labeling is presented.
Incremental integer linear programming for non-projective dependency parsing
108 Citations2006Sebastian Riedel, James Clarke
This work presents an approach which solves the problem incrementally, thus it avoids creating intractable integer linear programs and shows how the addition of linguistically motivated constraints can yield a significant improvement over state-of-the-art.
A formal model for information selection in multi-sentence text extraction
108 Citations2004Elena Filatova, Vasileios Hatzivassiloglou
A formal model is proposed that represents a collection of documents in a two-dimensional space of textual and conceptual units with an associated mapping between these two dimensions and is used to describe the task of selecting textual units for a summary or answer as a formal optimization task.
Inducing temporal graphs
106 Citations2006Philip Bramsen, Pawan Deshpande +2 more
This work considers the problem of constructing a directed acyclic graph that encodes temporal relations found in a text and achieves 83% F-measure in temporal segmentation and 84% accuracy in inferring temporal relations between two segments.
Models for sentence compression
103 Citations2006James Clarke, Mirella Lapata
This paper provides a novel comparison between a supervised constituent-based and an weakly supervised word-based compression algorithm and examines how these models port to different domains (written vs. spoken text).
Constraint-based sentence compression an integer programming approach
70 Citations2006James Clarke, Mirella Lapata
This work develops an integer programming formulation and infer globally optimal compressions in the face of linguistically motivated constraints and shows that such a formulation allows for relatively simple and knowledge-lean compression models that do not require parallel corpora or large-scale resources.