TL;DR
This paper introduces a novel, linear-time algorithm called VERTEX ADDITION for query-focused sentence compression. It efficiently generates shortened sentences that must include specific query terms and adhere to a maximum length, a crucial requirement for search interfaces that often have limited display space. This method significantly outperforms existing techniques in terms of speed and accuracy without requiring expensive hardware like GPUs or specialized solvers.
What Problem Does This Paper Address?
Search engines and other applications often need to display snippets of text that summarize longer documents. Traditionally, sentence compression aims to create short, readable summaries. However, modern search interfaces have stricter requirements: the compressed sentence (snippet) must not only be short but also must contain specific keywords provided by the user's query, and it must fit within a predefined character limit (e.g., for display on a screen). Existing methods, like those based on Integer Linear Programming (ILP), can handle these constraints but are computationally expensive, leading to noticeable delays for users. Other methods, like LSTM taggers, don't easily support these specific length and lexical constraints. This gap means that current compression techniques are often too slow or inflexible for real-time applications like search result snippets, where both speed and constraint satisfaction are paramount.
Methods
The core contribution is the VERTEX ADDITION algorithm. Unlike traditional methods that might prune parts of a sentence's dependency parse, VERTEX ADDITION builds the compressed sentence by growing a subgraph within the dependency parse. It does this one "vertex" (word) at a time, maintaining a state that tracks the current compression and a priority queue of candidate words.
Here's a breakdown:
- Transition-Based Approach: Inspired by transition-based parsing, the algorithm makes a sequence of decisions.
- Growing Subgraph: It starts with the required query terms and iteratively adds words from the sentence's dependency parse.
- Stateful Decisions: At each step, it decides whether to include a candidate word based on its relationship to the current compression and the remaining character budget.
- Linear Time Complexity: The algorithm is designed to run in linear time with respect to the sentence length, a significant improvement over the exponential complexity of ILP methods.
- Two Models:
- VERTEX ADDITIONNN: Uses a neural network (LSTM classifier) to learn the inclusion decisions, treating it like a transition-based parsing problem.
- VERTEX ADDITIONLR: Uses a simpler binary logistic regression model, relying on features derived from the dependency parse edges and the current state of the compression.
Datasets
The authors re-purposed a standard sentence compression corpus (Filippova and Altun, 2013) for their evaluation. They created approximately 198,570 training tuples and 9949 test tuples. Each tuple consists of:
- A source sentence (S).
- A set of query terms (Q).
- A maximum character length budget (b).
- A known-good compression (Cg) that respects Q and b.
To create these tuples, they set the budget b to the character length of the gold compression Cg. They then sampled nouns from Cg to form the query set Q, aiming to mimic real-world search queries. The data was parsed and tagged using CoreNLP v3.8.0.
Key Insights and Ideas
- Linear Time is Achievable for Constrained Compression: The most significant insight is that complex constraints (lexical and length) don't necessarily require computationally expensive algorithms. A greedy, stateful approach can achieve this efficiently.
- Dependency Parse as a Foundation: Leveraging the structure of the dependency parse is crucial for both understanding sentence relationships and guiding the compression process.
- Local Decisions vs. Global Optimization: The paper highlights the trade-off between ILP's global optimization (which is slow) and VERTEX ADDITION's local, sequential decisions (which are fast). The results suggest that for this specific task, fast local decisions can yield comparable or better results.
- Practical Implications for Search: The speedup achieved by VERTEX ADDITION is directly relevant to user experience in search interfaces, where latency is a major factor. Faster snippets mean users can interact with information more fluidly.
Key Results
- Speed: VERTEX ADDITIONLR achieved an 11x empirical speedup over the ILP baseline. The latency for VERTEX ADDITIONLR was 4.1 ms/sentence, compared to 44.0 ms/sentence for ILP.
- Accuracy (F1 Score): VERTEX ADDITIONLR achieved the highest token-level F1 score of 0.881, slightly outperforming the ILP baseline (0.852).
- Constraint Satisfaction: Both VERTEX ADDITION models and the ILP baseline successfully handled the length and lexical constraints, unlike some prior methods.
- Readability (SLOR): VERTEX ADDITIONLR also showed strong performance in readability scores.
Limitations and Future Work
- Dependency Parse Assumption: The method assumes access to a reliable dependency parse. In real-world scenarios, parsing can be slow or inaccurate, especially on out-of-domain text. Future work could explore faster parsing methods or alternative representations.
- Query and Budget Definition: The current approach assumes a user provides a well-defined query (Q) and budget (b). The paper acknowledges that for some (Q, S, b) combinations, no well-formed compression might exist. Investigating how to handle such cases is a future direction.
- Meaning Preservation: The current study does not explicitly address whether the compressed sentences preserve the original meaning. Future work aims to incorporate research on textual entailment to develop semantically-informed compression.
- Ellipse Format: The paper notes that the common use of ellipses to indicate removed words can sometimes make compressions less readable. Further human experiments could guide better snippet generation algorithms.
- Out-of-Domain Performance: The neural model (VERTEX ADDITIONNN) was too slow for practical use on a CPU, suggesting it's best suited for environments with GPU access. The logistic regression model (VERTEX ADDITIONLR) is the more practical choice for general deployment.
Summary updated