A Dynamic Programming Algorithm for Tree Trimming-based Text Summarization

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 462–471, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics A Dynamic Programming Algorithm for Tree Trimming-based Text Summarization Masaaki Nishino1, Norihito Yasuda2, Tsutomu Hirao1, Shin-ichi Minato2,3, Masaaki Nagata1 1NTT Communication Science Laboratories, NTT Corporation 2ERATO Minato Discrete Structure Manipulation System Project, JST 3Graduate School of Information Science and Technology, Hokkaido University nishino.masaaki@lab.ntt.co.jp Abstract Tree trimming is the problem of extracting an optimal subtree from an input tree, and sentence extraction and sentence compres- sion methods can be formulated and solved as tree trimming problems. Previous ap- proaches require integer linear programming (ILP) solvers to obtain exact solutions. The problem of this approach is that ILP solvers are black-boxes and have no theoretical guar- antee as to their computation complexity. We propose a dynamic programming (DP) algo- rithm for tree trimming problems whose run- ning time is O(NL log N), where N is the number of tree nodes and L is the length limit. Our algorithm exploits the zero-suppressed bi- nary decision diagram (ZDD), a data struc- ture that represents a family of sets as a di- rected acyclic graph, to represent the set of subtrees in a compact form; the structure of ZDD permits the application of DP to obtain exact solutions, and our algorithm is applica- ble to different tree trimming problems. More- over, experiments show that our algorithm is faster than state-of-the-art ILP solvers, and that it scales well to handle large summariza- tion problems. 1 Introduction Extractive text summarization and sentence com- pression are tasks that basically select a subset of the input set of textual units that is appropriate as a summary or a compressed sentence. Current text summarization and sentence compression methods regard the problem of extracting such a subset as a combinatorial optimization problem (e.g., (Filatova and Hatzivassiloglou, 2004; McDonald, 2007; Lin and Bilmes, 2010)). Tree trimming, the problem of finding an optimal subtree of an input tree, is one kind of these combinatorial optimization problems, and it is used in three classes of text summarizations: sentence compression (Filippova and Strube, 2008; Filippova and Altun, 2013), single-document sum- marization (Hirao et al., 2013), and the combination of sentence compression and single-document sum- marization (Kikuchi et al., 2014). In these tasks, the set of input textual units is represented as a rooted tree whose nodes correspond to the minimum tex- tual units such as sentences and words. Next, a sub- set is made by forming a subtree by trimming the input tree. Since the optimal trimmed subtree pre- serves the relationships between textual units, it is a concise representation of the original set that pre- serves linguistic quality. A shortcoming of tree trimming-based methods is that they are formulated as integer linear program- ming (ILP) problems and so an ILP solver is needed to solve them. Although modern ILP solvers can solve many instances of tree trimming problems in a short time, there is …

Content truncated to 500 words