With Measured Words: Simple Sentence Selection for Black-Box Optimization of Sentence Compression Algorithms (2021)

Abstract: Sentence Compression is the task of generating a shorter, yet grammatical, version of a given sentence, preserving the essence of the original sentence. This paper proposes a Black-Box Optimizer for Compression (B-BOC): given a black-box compression algorithm and assuming not all sentences need be compressed – find the best candidates for compression in order to maximize both compression rate and quality. Given a required compression ratio, we consider two scenarios: (i) single-sentence compression, and (ii) sentences-sequence compression. In the first scenario our optimizer is trained to predict how well each sentence could be compressed while meeting the specified ratio requirement. In the latter, the desired compression ratio is applied to a sequence of sentences (e.g., a paragraph) as a whole, rather than on each individual sentence. To achieve that we use B-BOC to assign an optimal compression ratio to each sentence, then cast it as a Knapsack problem which we solve using bounded dynamic programming. We evaluate B-BOC on both scenarios on three datasets, demonstrating that our optimizer improves both accuracy and Rouge-F1-score compared to direct application of other compression algorithms.

## introduction sentence compression is the task of generating a short, accurate, and fluent sentence that preserves the essence of a given original sentence by removing nonessential words and/or rephrasing it in a compact form. compression can take many forms, ranging from extractive and abstractive summarization @xcite @xcite @xcite @xcite to text simplification and paraphrasing @xcite @xcite @xcite , among others. on the sentential level, compression is often viewed as a word deletion task @xcite @xcite @xcite @xcite . however, not all sentences could, or should be compressed as part of compressing a longer text they reside in. consider the familiar scenario in which a full paragraph needs to be compressed in order to have an eacl paper meet the page restriction specified in the submission guidelines. a common approach by l a t e x users is to first identify paragraphs ending with a short line, (e.g., this very paragraph), then choose one or more sentences that could be compressed with a minimal loss of information -shaving the extra line. we propose a black-box optimizer for compression (b-boc) that mitigates this problem. given a compression algorithm a, a desired compression ratio, and a document d, b-boc chooses the best sentences to compress using a in order to produce a shorter version of d, while keeping the other sentences of d untouched. b-boc achieves that without explicit knowledge of the inner-workings of the given compression algorithm, hence we call it a black-box optimizer. selected sentences are expected to be the best candidates for compressionbalancing compression rate with compression quality. this paper addresses two main research questions: (1) how to predict the compression performance (preserving meaning and grammar) of an algorithm on a given sentence? (2) given a document and a required compression ratio, how to choose the optimal subset of sentences to compress, along with the appropriate compression ratio per each of the sentences, so that the total compression meets the required compression requirement? given a gold set of pairs of sentences and their compressions, we represent each sentence as a vector of shallow and syntactic features, and train a regression model to predict its expected compression rate. b-boc ranks all sentences by the predicted compression potential while considering a required compression ratio. the document-level task could be modeled as a knapsack optimization problem, considering the subset of sentences to be compressed in order to satisfy the overall compression requirement (capacity), with a minimal loss of information (value). the solution space covers the trade-off between aggressively compressing only a few sentences and applying minimal compression on a larger number of sentences. while the general knapsack is npcomplete, the 0-1 variation can be approximated efficiently by using dynamic programming @xcite . we evaluate b-boc on three benchmarks commonly used for the sentence compression task. we show that applying b-boc on top of state-of-theart sentence compression models improves the performance for any desired compression rate. in addition, optimizing the b-boc-knapsack achieves top performance on the document-level task. ## related work early sentence compression works employ the noisy channel model, learning the words and clauses to be pruned @xcite @xcite @xcite . the top-performing sentence compression models use a policy network coupled with a syntactic language model (bi-lstm) evaluator @xcite , and a stacked lstm with dropout layers @xcite . an extension of filippova et al., adding syntactic features and using integer linear programming (ilp), yields improved results in a cross-domain setting @xcite . sentence selection is used for document extractive summarization -a task conceptually close to ours, in which full sentences are extracted from a long document, see @xcite for an overview. state-of-the-art selection is achieved by combining sentence and document encoders (cnn and lstm) with a sentence extraction model (lstm) and a reinforcement layer @xcite . sentence rephrasing is an abstractive approach to rewrite a sentence into a shorter form using some words that may not appear in the original sentence. a data-driven approach to abstractive sentence summarization is suggested in @xcite , using about four million title-article pairs from the gigaword corpus for training, and uses a convolutional neural network model to encode the source and produce a single representation for the entire input sentence. tree-to-tree grammar extraction method for the rewriting task is used in @xcite . state-of-the-art performance on the abstractive summarization task is obtained using hierarchical attentional seq2seq recurrent neural network @xcite . ## task definitions and methodology in this section we formally define the sentencelevel and the document-level tasks ( §3.1) and provide a detailed description of the application of b-boc in both settings ( §3.2). ## conclusions in this paper we presented b-boc-black-box optimizer for compression, a new complexity optimization method designated to the sentence compression problem. we defined the correlation between the complexity of a sentence and the chance that a black-box compression model could successfully compress it. our optimization model is independent of the compression model used to compress the sentences and can be combined with any sentence compression model. our evaluation on three benchmarks revealed promising results when applied to three different types of sentence compression models. we achieve top performance for a document compression problem using the b-boc-knapsack optimization implemented with a bounded dynamic programming technique. our method could assist in compressing any kind of text while applying their desired compression model. utilizing our method provides a proper guideline for which of the sentences are the most beneficial to focus on, in order to compress a given text, while yielding the best overall compression results. for future work, we plan to construct model-dependant optimization that accounts for the features of each compression model. this will facilitate a choice of the compression model that is the most suitable for a given sentence.