A Framework for Identifying Textual Redundancy

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 873–880 Manchester, August 2008 A Framework for Identifying Textual Redundancy Kapil Thadani and Kathleen McKeown Department of Computer Science, Columbia University, New York, NY USA {kapil,kathy}@cs.columbia.edu Abstract The task of identifying redundant infor- mation in documents that are generated from multiple sources provides a signifi- cant challenge for summarization and QA systems. Traditional clustering techniques detect redundancy at the sentential level and do not guarantee the preservation of all information within the document. We discuss an algorithm that generates a novel graph-based representation for a document and then utilizes a set cover approximation algorithm to remove redundant text from it. Our experiments show that this approach offers a significant performance advantage over clustering when evaluated over an an- notated dataset. 1 Introduction This paper approaches the problem of identifying and reducing redundant information in documents that are generated from multiple sources. This task is closely related to many well-studied problems in the field of natural language processing such as summarization and paraphrase recognition. Sys- tems that utilize data from multiple sources, such as question-answering and extractive summariza- tion systems that operate on news data, usually in- clude a component to remove redundant informa- tion from appearing in their generated output. However, practical attempts at reducing redun- dancy in the output of these types of systems usu- ally involve clustering the sentences of the gener- ated output, picking a representative sentence from each cluster and discarding the rest. Although this strategy would remove some redundant in- formation, clustering approaches tuned for coarse c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. matches could also remove non-redundant infor- mation whereas clustering approaches tuned for near-exact matches could end up removing very little repeated information. This is simply a con- sequence of the fact that information can, and usu- ally does, exist at the sub-sentential level and that clusters of sentences don’t necessarily correspond to clusters of information. In this paper, we discuss a framework for build- ing a novel graph-based representation to detect re- dundancy within documents. We identify redun- dancy at the sub-sentential level through pairwise alignment between the sentences of a document and use this to build a bipartite graph which en- ables us to keep track of redundant information across all sentences. Common information be- tween pairs of sentences, detected with the align- ment algorithm, can be extrapolated to document- wide units of information using the graph struc- ture. Individual sentences that are encompassed by the information in the rest of the document can then be identified and removed efficiently by us- ing a well-known greedy algorithm adapted for this representation. 2 Related Work The challenge of minimizing redundant informa- tion is commonly faced by IR engines and extrac- tive summarization systems when generating their responses. A well-known diversity-based rerank- ing technique for these types of systems is MMR (Carbonell and Goldstein, 1998), which attempts to reduce redundancy by …

Content truncated to 500 words