Query-focused Sentence Compression in Linear Time

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 5969–5975, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 5969 Query-focused Sentence Compression in Linear Time Abram Handler and Brendan O’Connor College of Information and Computer Sciences University of Massachusetts Amherst {ahandler,brenocon}@cs.umass.edu Abstract Search applications often display shortened sentences which must contain certain query terms and must fit within the space constraints of a user interface. This work introduces a new transition-based sentence compression technique developed for such settings. Our query-focused method constructs length and lexically constrained compressions in linear time, by growing a subgraph in the depen- dency parse of a sentence. This theoretically efficient approach achieves an 11x empirical speedup over baseline ILP methods, while bet- ter reconstructing gold constrained shorten- ings. Such speedups help query-focused ap- plications, because users are measurably hin- dered by interface lags. Additionally, our tech- nique does not require an ILP solver or a GPU. 1 Introduction Traditional study of extractive sentence com- pression seeks to create short, readable, single- sentence summaries which retain the most “im- portant” information from source sentences. But search user interfaces often require compressions which must include a user’s query terms and must not exceed some maximum length, permitted by screen space. Figure 1 shows an example. This study examines the English-language com- pression problem with such length and lexical re- quirements. In our constrained compression set- ting, a source sentence S is shortened to a com- pression C which (1) must include all tokens in a set of query terms Q and (2) must be no longer than a maximum budgeted character length, b ∈ Z+. Formally, constrained compression maps (S, Q, b) → C, such that C respects Q and b. We describe this task as query-focused compression because Q places a hard requirement on words from S which must be included in C. Gazprom the Russian state gas giant announced a 40 percent increase in the price of natural gas sold to Ukraine which is heavily dependent on Russia for its gas supply. Gazprom announced increase in the price of gas sold to Ukraine Ukraine’s dependence on Gazprom left the country vulnerable Kremlin-backed Gazprom transports gas to Europe through Ukraine Gazprom Ukraine S Q C b = 75 char. max. Figure 1: A search user interface (boxed, top) returns a snippet consisting of three compressions which must contain a users’ query Q (bold) and must not exceed b = 75 characters in length. The third compression C was derived from source sentence S (italics, bottom). Existing techniques are poorly suited to con- strained compression. While methods based on integer linear programming (ILP) can trivially ac- commodate such length and lexical restrictions (Clarke and Lapata, 2008; Filippova and Altun, 2013; Wang et al., 2017), these approaches rely on slow third-party solvers to optimize an NP- hard integer linear programming objective, caus- ing user wait time. An alternative LSTM tag- ging …

Content truncated to 500 words