Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function

Proceedings of NAACL-HLT 2018, pages 1737–1746 New Orleans, Louisiana, June 1 - 6, 2018. c⃝2018 Association for Computational Linguistics Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function Shinsaku Sakaue Tsutomu Hirao Masaaki Nishino NTT Communication Science LaboratoriesMasaaki Nagata {sakaue.shinsaku, hirao.tsutomu}@lab.ntt.co.jp {nishino.masaaki, nagata.masaaki}@lab.ntt.co.jp Abstract Submodular maximization with the greedy algorithm has been studied as an effective approach to extractive summarization. This approach is known to have three advan- tages: its applicability to many useful sub- modular objective functions, the efficiency of the greedy algorithm, and the provable performance guarantee. However, when it comes to compressive summarization, we are currently missing a counterpart of the extractive method based on submodular- ity. In this paper, we propose a fast greedy method for compressive summarization. Our method is applicable to any mono- tone submodular objective function, includ- ing many functions well-suited for docu- ment summarization. We provide an ap- proximation guarantee of our greedy algo- rithm. Experiments show that our method is about 100 to 400 times faster than an existing method based on integer-linear- programming (ILP) formulations and that our method empirically achieves more than 95%-approximation. 1 Introduction Automatic document summarization continues to be a seminal subject of study in natural lan- guage processing and information retrieval (Luhn, 1958; Edmundson, 1969; Cheng and Lapata, 2016; Peyrard and Eckle-Kohler, 2017). Owing to the recent advances in data collection, the size of doc- ument data to be summarized has been exploding, which has been bringing a drastic increase in the demand for fast summarization systems. Extractive summarization is a widely used ap- proach to designing fast summarization systems. With this approach, we construct a summary by extracting some sentences from the original docu- ment(s). The extractive approach is not only fast but also has the potential to achieve state-of-the- art ROUGE scores (Lin, 2004), which was revealed by Hirao et al. (2017b). In many existing meth- ods, sentences are extracted by solving various subset selection problems: for example, the knap- sack problem (McDonald, 2007), maximum cover- age problem (Filatova and Hatzivassiloglou, 2004; Takamura and Okumura, 2009a), budgeted median problem (Takamura and Okumura, 2009b), and sub- modular maximization problem (Lin and Bilmes, 2010). Of particular interest, the method based on submodular maximization has three advantages: (1) Many objective functions used for document summarization are known to be monotone and submodular (Lin and Bilmes, 2011; J Kurisinkel et al., 2016); examples of such functions include the coverage function, diversity reward function, and ROUGE. Therefore, the method can deliver high performance by using monotone submodular objective functions that are suitable for the given tasks. (2) The efficient greedy algorithm is effective for the submodular maximization problem, which provides fast summarization systems. (3) Theo- retical performance guarantees of the greedy algo- rithm can be proved; for example, a 1 2(1 − e−1)- approximation guarantee can be obtained. Although the above extractive methods success- fully obtain summaries with high ROUGE scores, they have the following shortcoming: A long sen- tence typically has redundant parts, which means a summary …

Content truncated to 500 words