Subtree Extractive Summarization via Submodular Maximization

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1023–1032, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Subtree Extractive Summarization via Submodular Maximization Hajime Morita Tokyo Institute of Technology, Japan morita@lr.pi.titech.ac.jp Hiroya Takamura Tokyo Institute of Technology, Japan takamura@pi.titech.ac.jp Ryohei Sasano Tokyo Institute of Technology, Japan sasano@pi.titech.ac.jp Manabu Okumura Tokyo Institute of Technology, Japan oku@pi.titech.ac.jp Abstract This study proposes a text summarization model that simultaneously performs sen- tence extraction and compression. We translate the text summarization task into a problem of extracting a set of depen- dency subtrees in the document cluster. We also encode obligatory case constraints as must-link dependency constraints in or- der to guarantee the readability of the gen- erated summary. In order to handle the subtree extraction problem, we investigate a new class of submodular maximization problem, and a new algorithm that has the approximation ratio 1 2(1 − e−1). Our experiments with the NTCIR ACLIA test collections show that our approach outper- forms a state-of-the-art algorithm. 1 Introduction Text summarization is often addressed as a task of simultaneously performing sentence extraction and sentence compression (Berg-Kirkpatrick et al., 2011; Martins and Smith, 2009). Joint mod- els of sentence extraction and compression have a great benefit in that they have a large degree of freedom as far as controlling redundancy goes. In contrast, conventional two-stage approaches (Za- jic et al., 2006), which first generate candidate compressed sentences and then use them to gen- erate a summary, have less computational com- plexity than joint models. However, two-stage ap- proaches are suboptimal for text summarization. For example, when we compress sentences first, the compressed sentences may fail to contain im- portant pieces of information due to the length limit imposed on each sentence. On the other hand, when we extract sentences first, an impor- tant sentence may fail to be selected, simply be- cause it is long. Enumerating a huge number of compressed sentences is also infeasible. Joint models can prune unimportant or redundant de- scriptions without resorting to enumeration. Meanwhile, submodular maximization has re- cently been applied to the text summarization task, and the methods thereof have performed very well (Lin and Bilmes, 2010; Lin and Bilmes, 2011; Morita et al., 2011). Formalizing summarization as a submodular maximization problem has an im- portant benefit inthat the problem can be solved by using a greedy algorithm with a performance guar- antee. We therefore decided to formalize the task of si- multaneously performing sentence extraction and compression as a submodular maximization prob- lem. That is, we extract subsentences for mak- ing the summary directly from all available sub- sentences in the documents and not in a stepwise fashion. However, there is a difficulty with such a formalization. In the past, the resulting maxi- mization problem has been often accompanied by thousands of linear constraints representing logi- cal relations between words. The existing greedy algorithm for solving submodular maximization problems cannot work in the presence of such nu- merous constraints although monotone and non- …

Content truncated to 500 words