Fast Concept Mention Grouping for Concept Map-based Multi-Document Summarization

Proceedings of NAACL-HLT 2019, pages 695–700 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 695 Fast Concept Mention Grouping for Concept Map–based Multi-Document Summarization Tobias Falke and Iryna Gurevych Research Training Group AIPHES and UKP Lab Department of Computer Science, Technische Universit¨at Darmstadt https://www.aiphes.tu-darmstadt.de Abstract Concept map–based multi-document summa- rization has recently been proposed as a vari- ant of the traditional summarization task with graph-structured summaries. As shown by previous work, the grouping of coreferent con- cept mentions across documents is a crucial subtask of it. However, while the current state- of-the-art method suggested a new grouping method that was shown to improve the sum- mary quality, its use of pairwise comparisons leads to polynomial runtime complexity that prohibits the application to large document collections. In this paper, we propose two alternative grouping techniques based on lo- cality sensitive hashing, approximate nearest neighbor search and a fast clustering algo- rithm. They exhibit linear and log-linear run- time complexity, making them much more scalable. We report experimental results that confirm the improved runtime behavior while also showing that the quality of the summary concept maps remains comparable.1 1 Introduction Concept maps are labeled graphs with nodes rep- resenting concepts and edges showing relation- ships between them (Novak and Gowin, 1984). Following earlier work on the automatic extraction of concept maps from text (Rajaraman and Tan, 2002; Valerio and Leake, 2006; Villalon, 2012; Zubrinic et al., 2015), concept maps have recently been promoted as an alternative representation for summaries (Falke and Gurevych, 2017; Handler and O’Connor, 2018). In the corresponding task, concept map–based multi-document summariza- tion (CM-MDS), a set of documents has to be automatically summarized as a concept map that does not exceed a pre-defined size limit. 1Code used for experiments available at https:// github.com/UKPLab/naacl2019-cmaps-lshcw An important subtask of CM-MDS is concept mention grouping, in which all mentions that refer to a specific concept should be grouped together. Without grouping, duplicates can appear in a sum- mary concept map that make the map harder to understand and that waste valuable space. To approach the mention grouping subtask, Falke et al. (2017) proposed to make pairwise coreference classifications between mentions and to induce a partitioning from those predictions. Their experiments showed that this leads to better summary concept maps, establishing the current state-of-the-art for CM-MDS. However, the com- putational costs of the approach are high, as it ex- hibits a O(n4) worst-case time complexity. When the number of documents that should be summa- rized is large, applying that technique can quickly become impractical. But exactly for those large document sets, a summary would be most helpful. As the first contribution of this paper, we pro- pose two faster grouping techniques. First, we apply locality sensitive hashing (LSH) (Charikar, 2002) to word embeddings in order to find simi- lar mentions without making all pairwise compar- isons. That directly leads to a simple O(n) group- ing method. Second, we also propose a novel grouping technique that combines the hashing …

Content truncated to 500 words