Elamur Research⌕
☰
home / papers / 2009 / A Scalable Global Model for Summarization

A Scalable Global Model for Summarization

Summary

The paper addresses extractive multi-document summarization, where sentences must be chosen to be informative without repeating each other. A previous exact approach by McDonald (2007) scored sentences for relevance and penalized every pair of chosen sentences for overlap. This needs a quadratic number of variables, so it becomes impractical beyond roughly 100 input sentences. Gillick and Favre instead score a summary by the sub-sentence "concepts" it covers. In their experiments, concepts are stemmed word bigrams weighted by how many input documents contain them, and each concept earns credit only once. This choice handles redundancy for the summary as a whole rather than pair by pair. They cast the problem as an Integer Linear Program (a maximum-coverage-style model) and solve it with an off-the-shelf solver. On TAC 2008 data, the concept model clearly beats both the sentence-level ILP and a lead baseline, and it matches the top TAC systems on ROUGE, Pyramid and content responsiveness. They also extend the ILP to compress and select sentences jointly. This raised ROUGE-2 but hurt grammaticality and Pyramid.

Key points

  • Data and task: TAC 2008 multi-document summarization, standard task only. There are 48 topics, each with 10 newswire documents, and the target is a 100-word summary. Topics average 235 input sentences, ranging from 47 to 652.
  • Results (ROUGE-2 / Pyramid):
    • lead baseline: 0.058 / 0.186
    • McDonald's sentence-level ILP: 0.072 / 0.295
    • concept-based ILP: 0.110 / 0.345
    • All differences between systems are significant.
  • Concept weighting: Concepts are word bigrams weighted by document frequency. Bigrams worked better than unigrams or trigrams, and TFIDF-style normalization lowered ROUGE.
  • Why document frequency works: On DUC data, a bigram's document frequency correlates strongly with its chance of appearing in human summaries (ρ = 0.95 for DUC 2007, 0.97 for DUC 2006).
  • Pipeline:
    • Sentences are split with Punkt.
    • Sentences under 5 words are dropped.
    • Bigrams made only of stopwords, or found in fewer than three documents, are removed.
    • The ILP is solved with GLPK.
    • Chosen sentences are ordered by document date, then by position.
    • The parse-tree-based compression variant produced ungrammatical sentences in about 60% of its summaries.

Interesting ideas

  • I1. Implicit redundancy control: Instead of penalizing overlap between pairs of items, reward each unique unit of content once. This captures redundancy that only appears when three or more items are combined. It also avoids variables for every pair, so it suits any selection task where overlap is the concern, such as dataset deduplication or choosing examples for a corpus.
  • I2. Linking constraints between two layers: Two small inequalities tie sentence variables to concept variables. Choosing a sentence switches on its concepts, and a concept counts only if some chosen sentence contains it. This pattern carries over to many ILP problems where items are scored through their parts.
  • I3. Checking a cheap weighting signal against gold data: The authors justify document-frequency weights by showing a strong correlation with gold-summary content before relying on them. Testing whether a cheap heuristic tracks the target in this way is a useful habit before investing in learned weights.
  • I4. Joint compression and selection in one program: Compression options are encoded as tree nodes that can be extracted, removed or substituted, inside the same optimization. This lets shortening and choosing interact, but the paper warns that the candidate generator must keep outputs grammatical.
  • I5. Evaluating with both automatic and human metrics: In the compression experiment, ROUGE rose while Pyramid and linguistic quality fell. This shows that n-gram recall alone can reward broken output, so pairing it with human-based measures is worth doing in other generation evaluations.

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

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

Cite

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

@inproceedings{gillick2009scalable,
  title = {{A Scalable Global Model for Summarization}},
  author = {Gillick, Dan and Favre, Benoit},
  booktitle = {Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing},
  year = {2009},
  doi = {10.3115/1611638.1611640},
  url = {https://doi.org/10.3115/1611638.1611640}
}

References

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

  1. James Clarke and Mirella Lapata. 2008. Global inference for sentence compression: An integer linear programming approach. Journal of Artificial Intelligence Research, 31:273–381. find
  2. John M. Conroy, Judith D. Schlesinger, and Dianne P. O’Leary. 2006. Topic-focused multi-document summarization using an approximate oracle score. In Proceedings of COLING/ACL. find
  3. Hoa Trang Dang and Karolina Owczarzak. 2008. Overview of the TAC 2008 Update Summarization Task. In Proceedings of Text Analysis Conference. find
  4. E. Filatova and V. Hatzivassiloglou. 2004. Event-based extractive summarization. In Proceedings of ACL Workshop on Summarization, volume 111. find
  5. G. Gallo, PL Hammer, and B. Simeone. 1980. Quadratic knapsack problems. Mathematical Programming Study, 12:132–149. find
  6. D. Gillick, B. Favre, and D. Hakkani-Tur. 2008. The ICSI Summarization System at TAC 2008. In Proceedings of the Text Understanding Conference. find
  7. Jade Goldstein, Vibhu Mittal, Jaime Carbonell, and Mark Kantrowitz. 2000. Multi-document summarization by sentence extraction. Proceedings of the ANLP/NAACL Workshop on Automatic Summarization, pages 40–48. find
  8. Martin Hassel and Jonas Sjöbergh. 2006. Towards holistic summarization: Selecting summaries, not sentences. In Proceedings of Language Resources and Evaluation. find
  9. D.S. Hochbaum. 1996. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. PWS Publishing Co. Boston, MA, USA, pages 94–143. find
  10. E. Hovy, C.Y. Lin, and L. Zhou. 2005. A BE-based multi-document summarizer with sentence compression. In Proceedings of Multilingual Summarization Evaluation. find
  11. Fatma Jaoua Kallel, Maher Jaoua, Lamia Belguith Hadrich, and Abdelmajid Ben Hamadou. 2004. Summarization at LARIS Laboratory. In Proceedings of the Document Understanding Conference. find
  12. Richard Manning Karp. 1972. Reducibility among combinatorial problems. Complexity of Computer Computations, 43:85–103. find
  13. Tibor Kiss and Jan Strunk. 2006. Unsupervised multilingual sentence boundary detection. Computational Linguistics, 32. find our card
  14. K. Knight and D. Marcu. 2000. Statistics-Based Summarization-Step One: Sentence Compression. In Proceedings of the National Conference on Artificial Intelligence, pages 703–710. find
  15. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999. find
  16. Chin-Yew Lin. 2004. ROUGE: A Package for Automatic Evaluation of Summaries. In Proceedings of the Workshop on Text Summarization Branches Out (WAS 2004), pages 25–26. find
  17. D. Liu, Y. Wang, C. Liu, and Z. Wang. 2006. Multiple Documents Summarization Based on Genetic Algorithm. Lecture Notes in Computer Science, 4223:355. find
  18. N. Madnani, D. Zajic, B. Dorr, N.F. Ayan, and J. Lin. 2007. Multiple Alternative Sentence Compressions for Automatic Text Summarization. In Proceedings of the Document Understanding Conference at NLT/NAACL. find
  19. R. McDonald. 2006. Discriminative sentence compression with soft syntactic constraints. In Proceedings of the 11th EACL, pages 297–304. find
  20. R. McDonald. 2007. A Study of Global Inference Algorithms in Multi-document Summarization. Lecture Notes in Computer Science, 4425:557. find
  21. Ani Nenkova and Rebecca Passonneau. 2004. Evaluating content selection in summarization: The pyramid method. In Proceedings of HLT-NAACL. find
  22. A. Nenkova and L. Vanderwende. 2005. The impact of frequency on summarization. Technical Report MSR-TR-2005-101, Microsoft Research, Redmond, Washington. find
  23. A. Nenkova. 2008. Entity-driven rewrite for multidocument summarization. Proceedings of IJCNLP. find
  24. Slav Petrov and Dan Klein. 2007. Learning and inference for hierarchically split PCFGs. In AAAI 2007 (Nectar Track). find
  25. D. Pisinger, A.B. Rasmussen, and R. Sandvik. 2005. Solution of large-sized quadratic knapsack problems through aggressive reduction. INFORMS Journal on Computing. find
  26. K. Toutanova, C. Brockett, M. Gamon, J. Jagarlamudi, H. Suzuki, and L. Vanderwende. 2007. The Pythy Summarization System: Microsoft Research at DUC 2007. In Proceedings of the Document Understanding Conference. find
  27. J. Turner and E. Charniak. 2005. Supervised and Unsupervised Learning for Sentence Compression. In Proceedings of ACL. find
  28. W. Yih, J. Goodman, L. Vanderwende, and H. Suzuki. 2007. Multi-document summarization by maximizing informative content-words. In International Joint Conference on Artificial Intelligence. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/gillick-2009-scalable-global-model-summarization/