Single-Document Summarization as a Tree Knapsack Problem

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1515–1520, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Single-Document Summarization as a Tree Knapsack Problem Tsutomu Hirao† Yasuhisa Yoshida† Masaaki Nishino† Norihito Yasuda‡ Masaaki Nagata† †NTT Communication Science Laboratories, NTT Corporation 2-4, Hikaridai, Seika-cho, Soraku-gun, Kyoto, 619-0237, Japan {hirao.tsutomu,yoshida.y,nishino.masaaki, nagata.masaaki}@lab.ntt.co.jp ‡ Japan Science and Technology Agency North 14 West 9, Sapporo, Hokkaido, 060-0814, Japan yasuda@erato.ist.hokudai.ac.jp Abstract Recent studies on extractive text summariza- tion formulate it as a combinatorial optimiza- tion problem such as a Knapsack Problem, a Maximum Coverage Problem or a Budgeted Median Problem. These methods successfully improved summarization quality, but they did not consider the rhetorical relations between the textual units of a source document. Thus, summaries generated by these methods may lack logical coherence. This paper proposes a single document summarization method based on the trimming of a discourse tree. This is a two-fold process. First, we propose rules for transforming a rhetorical structure theory- based discourse tree into a dependency-based discourse tree, which allows us to take a tree- trimming approach to summarization. Sec- ond, we formulate the problem of trimming a dependency-based discourse tree as a Tree Knapsack Problem, then solve it with integer linear programming (ILP). Evaluation results showed that our method improved ROUGE scores. 1 Introduction State-of-the-art extractive text summarization meth- ods regard a document (or a document set) as a set of textual units (e.g. sentences, clauses, phrases) and formulate summarization as a combinatorial op- timization problem, i.e. selecting a subset of the set of textual units that maximizes an objective with- out violating a length constraint. For example, Mc- Donald (2007) formulated text summarization as a Knapsack Problem, where he selects a set of textual units that maximize the sum of significance scores of each unit. Filatova et al. (2004) proposed a summarization method based on a Maximum Cov- erage Problem, in which they select a set of textual units that maximizes the weighted sum of the con- ceptual units (e.g. unigrams) contained in the set. Although, their greedy solution is only an approxi- mation, Takamura et al. (2009a) extended it to ob- tain the exact solution. More recently, Takamura et al. (2009b) regarded summarization as a Budgeted Median Problem and obtain exact solutions with in- teger linear programming. These methods successfully improved ROUGE (Lin, 2004) scores, but they still have one critical shortcoming. Since these methods are based on sub- set selection, the summaries they generate cannot preserve the rhetorical structure of the textual units of a source document. Thus, the resulting summary may lack coherence and may not include significant textual units from a source document. One powerful and potential way to overcome the problem is to include discourse tree constraints in the summarization procedure. Marcu (1998) re- garded a document as a Rhetorical Structure The- ory (RST) (William Charles, Mann and Sandra An- near, Thompson, 1988)-based discourse tree (RST- DT) and selected textual units according to a prefer- ence ranking derived …

Content truncated to 500 words