Elamur Research⌕
☰
home / papers / 2005 / Sentence Fusion for Multidocument News Summarization

Sentence Fusion for Multidocument News Summarization

Summary

Most multidocument news summarizers handle a cluster of similar sentences by extracting one of them. That sentence often carries details specific to its source article, which introduces bias and hurts fluency. Barzilay and McKeown propose sentence fusion, a text-to-text generation technique that writes a new sentence expressing only the content shared by most sentences in a group. The input is a theme, meaning a cluster of related sentences from different articles. The method parses these sentences into dependency trees and aligns them bottom-up with local multisequence alignment, using identical words and paraphrase/synonymy matches as anchors. The aligned fragments are merged into a fusion lattice, and a language model ranks candidate verbalizations to linearize the lattice into one sentence. The technique runs inside MultiGen, the summarizer behind Columbia's Newsblaster news browsing service. In the authors' evaluation, fusion selected content better than extraction. The work matters because it moves summarization from extracts toward true abstracts that synthesize information across sources, without requiring domain-specific semantic input.

Key points

  • Theme construction. MultiGen's analysis module, Simfinder, groups sentences into themes. It uses a log-linear model over features such as WordNet synsets and subject–verb/verb–object dependencies. Human judges measured its performance at 49.3% precision and 52.9% recall, and these errors can feed unrelated sentences into fusion.
  • Theme selection and ordering. Themes are ranked by summing separate ranks for theme size, intra-theme similarity, and lexical-chain salience. Selected themes are then grouped into topical blocks and ordered chronologically by their earliest publication time.
  • Tree alignment. The algorithm scores edges by dependency type (subject-verb, object-verb) and nodes by identity, synonymy, or word overlap for flattened noun phrases. Memoization keeps the search efficient.
  • Deployment. Newsblaster collects articles from 30 news sites every day. MultiGen summarizes same-event clusters, while a second summarizer, DEMS, covers heterogeneous article sets.
  • Limitations and future work. Each sentence is generated in isolation, so the system repeats full named-entity descriptions instead of using shorter references. The authors suggest syntax-based language models and a probabilistic text-level coherence model for choosing among paraphrases.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

119 papers of our library cite it (of the 140884 whose bibliographies we read); 5 of them have a page here, 114 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/089120105774321091

@article{barzilay2005sentence,
  title = {{Sentence Fusion for Multidocument News Summarization}},
  author = {Barzilay, Regina and McKeown, Kathleen R.},
  journal = {Computational Linguistics},
  year = {2005},
  doi = {10.1162/089120105774321091},
  url = {https://doi.org/10.1162/089120105774321091}
}

References

59 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Amir, Amihood and Dmitry Keselman. 1994. Maximum agreement subtree in a set of evolutionary trees—Metrics and efficient algorithms. In Proceedings of FOCS, pages 758–769, Santa Fe, NM. find
  2. Bangalore, Srinivas, Vanessa Murdock, and Giuseppe Riccardi. 2002. Bootstrapping bilingual data using consensus translation for a multilingual instant messaging system. In International Conference on Computational Linguistics (COLING 2002), Tapei, Taiwan. find
  3. Bangalore, Srinivas and Owen Rambow. 2000. Exploiting a probabilistic hierarchical model for generation. In Proceedings of COLING, pages 42–48, Saarbruken, Germany. find
  4. Banko, Michele and Lucy Vanderwende. 2004. Using n-grams to understand the nature of summaries. In Proceedings of HLT-NAACL, pages 1– 4, Boston, MA. find
  5. Barzilay, Regina. 2003. Information Fusion for Multi-document Summarization: Paraphrasing and Generation. Ph.D. thesis, Columbia University. find
  6. Barzilay, Regina and Michael Elhadad. 1997. Using lexical chains for text summarization. In Proceedings of the ACL Workshop on Intelligent Scalable Text Summarization, pages 10–17, Madrid. find our card
  7. Barzilay, Regina, Noemie Elhadad, and Kathleen McKeown. 2002. Inferring strategies for sentence ordering in multi-document news summarization. Journal of Artificial Intelligence Research, 17:35–55. find
  8. Barzilay, Regina and Lillian Lee. 2002. Bootstrapping lexical choice via multiple-sequence alignment. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 164–171, Philadelphia, PA. find
  9. Barzilay, Regina and Kathleen McKeown. 2001. Extracting paraphrases from a parallel corpus. In Proceedings of the ACL/EACL, pages 50–57, Toulouse, France. find our card
  10. Barzilay, Regina, Kathleen McKeown, and Michael Elhadad. 1999. Information fusion in the context of multi-document summarization. In Proceedings of the ACL, pages 550–557, College Park, MD. find our card
  11. Beeferman, Doug, Adam Berger, and John Lafferty. 1998. Cyberpunc: A lightweight punctuation annotation system for speech. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, pages 689–692, Seattle, WA. find
  12. Borko, Harold and Charles Bernier. 1975. Abstracting Concepts and Methods. Academic Press, New York. find
  13. Brown, Peter F., Stephen Della Pietra, Vincent Della Pietra, and Robert Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263–311. find
  14. Carbonell, Jaime and Jade Goldstein. 1998. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proceedings of SIGIR, pages 335–336, Melbourne, Australia. find
  15. Chandrasekar, Raman, Christine Doran, and Srinivas Bangalore. 1996. Motivations and methods for text simplification. In International Conference on Computational Linguistics (COLING 1996), pages 1041–1044, Copenhagen, Denmark. find our card
  16. Chu-Carroll, Jennifer, Krzysztof Czuba, John Prager, and Abraham Ittycheriah. 2003. In question answering: Two heads are better than one. In Proceedings of HLT-NAACL, pages 24–31, Edmonton, Alberta. find
  17. Clarke, Charles, Gordon Cormack, and Thomas Lynam. 2001. Exploiting redundancy in question answering. In Proceedings of SIGIR, pages 358–365, New Orleans, LA. find
  18. Clarkson, Philip and R. Rosenfeld. 1997. Statistical language modeling using the CMU-Cambridge toolkit. In Proceedings ESCA Eurospeech, volume 5, pages 2707–2710, Rhodes, Greece. find
  19. Collins, Michael. 2003. Head-driven statistical models for natural language parsing. Computational Linguistics, 29(4):589–637. find our card
  20. Daume, Hal, Kevin Knight, Irene Langkilde-Geary, Daniel Marcu, and Kenji Yamada. 2002. The importance of lexicalized syntax models for natural language generation tasks. In Proceedings of INLG, pages 9–16, Arden House, Harriman, NJ. find
  21. Dumais, Susan, Michele Banko, Eric Brill, Jimmy Lin, and Andrew Ng. 2002. Web question answering: Is more always better? In Proceedings of SIGIR, pages 291–298, Tampere, Finland. find
  22. Durbin, Richard, Sean Eddy, Anders Krogh, and Graeme Mitchison. 1998. Biological Sequence Analysis. Cambridge University Press. find
  23. Elhadad, Michael, Yael Netzer, Regina Barzilay, and Kathleen McKeown. 2001. Ordering circumstantials for multi-document summarization. In Proceedings of BISFAI, Ramat Gan, Israel. find
  24. Elhadad, Michael and Jacques Robin. 1996. An overview of surge: A reusable comprehensive syntactic realization component. Technical Report 96–03, Department of Mathematics and Computer Science, Ben Gurion University, Beer Sheva, Israel. find our card
  25. Farach, Martin, Teresa Przytycka, and Mikkel Thorup. 1995. On the agreement of many trees. Information Processing Letters, 55(6):297–301. find
  26. Finden, C. R. and A. D. Gordon. 1985. Obtaining common pruned trees. Journal of Classification, 2:255–276. find
  27. Grefenstette, Gregory. 1998. Producing intelligent telegraphic text reduction to provide an audio scanning service for the blind. In Proceedings of the AAAI Spring Workshop on Intelligent Text Summarization, pages 111–115, Palo Alto, CA. find
  28. Gusfield, Dan. 1997. Algorithms on strings, trees and sequences. Cambridge University Press. find
  29. Hatzivassiloglou, Vasileios, Judith Klavans, and Eleazar Eskin. 1999. Detecting text similarity over short passages: Exploring linguistic feature combinations via machine learning. In Proceedings of the Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpor… find
  30. Hatzivassiloglou, Vasileios and Kathleen McKeown. 1993. Towards the automatic identification of adjectival scales: Clustering adjectives according to meaning. In Proceedings of the ACL, pages 172–182, Columbus, OH. find
  31. Jing, Hongyang and Kathleen McKeown. 2000. Cut and paste based summarization. In Proceedings of the First Conference of the North American Chapter of the Association of Computational Linguistics, pages 178–185, Seattle. find
  32. Knight, Kevin and Vasileios Hatzivassiloglou. 1995. Two-level, many-path generation. In Proceedings of the ACL, pages 252–260, Cambridge, MA. find
  33. Knight, Kevin and Daniel Marcu. 2002. Summarization beyond sentence extraction: A probabilistic approach to sentence compression. Artificial Intelligence Journal, 139(1):91–107. find
  34. Lacatusu, V. Finley, Steven J. Maiorano, and Sanda M. Harabagiu. 2004. Multi-document summarization using multi-sequence alignment. In International Conference on Language Resources and Evaluation, Lisbon, Portugal. find
  35. Langkilde, Irene and Kevin Knight. 1998. Generation that exploits corpus-based statistical knowledge. In Proceedings of the ACL/COLING, pages 704–710, Montreal, Quebec. find our card
  36. Lin, Chin-Yew and Eduard H. Hovy. 2002. From single to multi-document summarization: A prototype system and its evaluation. In Proceedings of the ACL, pages 457–464, Philadelphia, PA. find
  37. Lin, Chin-Yew and Eduard H. Hovy. 2003. Automatic evaluation of summaries using n-gram co-occurrence statistics. In Proceedings of HLT-NAACL, pages 150–157, Edmonton, Alberta. find our card
  38. Mani, Inderjeet and Eric Bloedorn. 1997. Multi-document summarization by graph search and matching. In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-97), pages 622–628, Providence, RI. AAAI. find
  39. Mani, Inderjeet, Barbara Gates, and Eric Bloedorn. 1999. Improving summaries by revising them. In Proceedings of the ACL, pages 558–565, College Park, MD. find
  40. Marcu, Daniel and Laurie Gerber. 2001. An inquiry into the nature of multidocument abstracts, extracts, and their evaluation. In Proceedings of the NAACL Workshop on Automatic Summarization, pages 2–11, Pittsburgh, PA. find
  41. McKeown, Kathleen R., Regina Barzilay, David Evans, Vasileios Hatzivassiloglou, Judith Klavans, Ani Nenkova, Carl Sable, Barry Schiffman, and Sergey Sigelman. 2002. Tracking and summarizing news on a daily basis with Columbia’s Newsblaster. In Proceedings of the Human Language Technology Conference… find
  42. McKeown, Kathleen R., Regina Barzilay, David Evans, Vasileios Hatzivassiloglou, Min Yen Kan, Barry Schiffman, and Simone Teufel. 2001. Columbia multi-document summarization: Approach and evaluation. In Proceedings of the Document Understanding Conference (DUC01), New Orleans, LA. find
  43. Melcuk, Igor. 1988. Dependency Syntax: Theory and Practice. Albany: State University of New York Press. find
  44. Meyers, Adam, Roman Yangarber, and Ralph Grishman. 1996. Alignment of shared forests for bilingual corpora. In International Conference on Computational Linguistics (COLING 1996), pages 460–465, Copenhagen, Denmark. find
  45. Miller, George A., Richard Beckwith, Christiane Fellbaum, Derek Gross, and Katherine J. Miller. 1990. Introduction to WordNet: An on-line lexical database. International Journal of Lexicography, 3(4):235–245. find
  46. Morris, Jane and Graeme Hirst. 1991. Lexical cohesion, the thesaurus, and the structure of text. Computational Linguistics, 17(1):21–48. find
  47. Nenkova, Ani and Kathleen R. McKeown. 2003. References to named entities: A corpus study. In Proceedings of the Human Language Technology Conference, Companion Volume, pages 70–73, Edmonton, Alberta. find
  48. Pang, Bo, Kevin Knight, and Daniel Marcu. 2003. Syntax-based alignment of multiple translations: Extracting paraphrases and generating new sentences. In Proceedings of HLT-NAACL, pages 180–187, Edmonton, Alberta. find our card
  49. Papineni, Kishore A., Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: A method for automatic evaluation of machine translation. In Proceedings of the ACL, pages 311–318, Philadelphia, PA. find our card
  50. Radev, Dragomir, Hongyan Jing, and Malgorzata Budzikowska. 2000. Centroid-based summarization of multiple documents: Sentence extraction, utility-based evaluation, and user studies. In Proceedings of the ANLP/NAACL 2000 Workshop on Automatic Summarization, pages 165–172, Seattle, WA. find
  51. Radev, Dragomir and Kathleen R. McKeown. 1998. Generating natural language summaries from multiple on-line sources. Computational Linguistics, 24(3):469–500. find
  52. Radev, Dragomir, John Prager, and Valerie Samn. 2000. Ranking suspected answers to natural language questions using predictive annotation. In Proceedings of Sixth Conference on Applied Natural Language Processing (ANLP), pages 150–157, Philadelphia, PA. find
  53. Reizler, Stefan, Tracy H. King, Richard Crouch, and Annie Zaenen. 2003. Statistical sentence condensation using ambiguity packing and stochastic disambiguation methods for lexical-functional grammar. In Proceedings of HLT-NAACL, pages 197–204, Edmonton, Alberta. find
  54. Robin, Jacques and Kathleen McKeown. 1996. Empirically designing and evaluating a new revision-based model for summary generation. Artificial Intelligence, 85(1–2):135–179. find
  55. Sankoff, David. 1975. Minimal mutation trees of sequences. SIAM Journal of Applied Mathematics, 28(1):35–42. find
  56. Schiffman, Barry, Ani Nenkova, and Kathleen R. McKeown. 2002. Experiments in multidocument summarization. In Proceedings of HLT, pages 52–58, San Diego, CA. find
  57. Shieber, Stuart and Xiapong Tao. 2003. Comma restoration using constituency information. In Proceedings of HLT-NAACL, pages 142–148, Edmonton, Alberta. find
  58. Siegel, Sidney and N. John Castellan. 1988. Nonparametric Statistics for Behavioral Sciences. McGraw-Hill. find
  59. Silber, Gregory and Kathleen McCoy. 2002. Computed lexical chains as an intermediate representation for automatic text summarization. Computational Linguistics, 28(4):487–496. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/barzilay-2005-sentence-fusion-multidocument-news-summarization/