Abstract Rule Learning for Paraphrase Generation

1 Introduction

Paraphrase generation aims to restate the given sentence with different expressions while preserving the original semantics. It has been widely used in various downstream tasks such as information retrieval [Knight and Marcu, 2000], dialogue systems [Gao et al., 2020], serving as a fundamental task in natural language processing (NLP).

In early years, paraphrasing was typically accomplished by knowledge-based or statistical machine translation (SMT) based approaches. Knowledge-based (also called rule-based) paraphrasing methods manually design explainable handcrafted rules [Barzilay and Lee, 2003] or automatically extract transforming patterns [Zhao et al., 2009]. Though these paraphrasers provide robust out-of-domain quality, the generated sentences lack the fluency that readers usually expect. The SMT-based methods [Quirk et al., 2004] formulate paraphrasing as a monolingual translation task based on sufficient

∗ Jizhe Zhou is the corresponding author

Abstract rule learning

• Direction of rule transformation Direction of information flow

Figure 1: An example of the learning and transformation of an abstract rule r. $z is a symbol (placeholder) that can be assigned to various words during rule transformations.

parallel corpus. These SMT-based approaches are also easily explained but struggle to handle the sentences not seen before.

Recently, neural networks have made impressive success in various NLP tasks, including paraphrase generation. Conventional neural-based approaches formulate paraphrasing as a supervised encoding-decoding problem [Wang et al., 2019]. For instance, Prakash et al. [2016] use stacked residual LSTM networks to generate paraphrases. To improve the diversity of generated sentences, Gupta et al. [2018] introduce the variational auto-encoder (VAE) to perform paraphrase generation. But those generated paraphrases tend to only make trivial changes to original sentences, such as modifications from singular to plural. To be a good paraphrase, a sentence should share similar semantics but have noticeable syntactically or lexically differences from the original one.

To further push paraphrases lexically away from original sentences, SEPARATOR [Hosking and Lapata, 2021] first encodes the syntax and meaning separately and then decodes paraphrases by perturbing syntactic encodings. However, in such latent sampling procedures, the generated paraphrases are less "controllable" in the meaning preservation and lack interpretability of how the predictions are made.

In this work, we integrate the advantages of the rulebased and neural-based methods into RULER, an interpretable framework that generates paraphrases by abstract RUle LEaRning. The abstract rule is the generalizable transformation from perceptual inputs to desired outputs. Our key idea is to learn abstract rules underlying paraphrasing that benefit the paraphrase generation process of neural networks. In particular, we first propose an evaluation metric to indicate the rule generalizability. Next, a rule learner learns to generate rules by maximizing the expected rewards (i.e., rule generalizability). Then, we select a suitable rule from the learned rules for the coming sentence and apply symbolic rule transformation. Finally, a neural network takes the transformed sentence as a reference to generate the paraphrase.

The advantage of performing paraphrasing by abstract rule learning is multi-fold: (1) Since rules are explicit knowledge (compared to neural networks), RULER presents good interpretability of why it produces such paraphrases. (2) RULER enjoys better generalizability to out-of-domain sentences due to symbolic rule transformations (Figure 1). (3) The rule transformation makes it possible to perform global modifications, which is a long-standing goal of paraphrase generation.

We evaluate the effectiveness of our method on two benchmark paraphrasing datasets, namely, Quora and Wikianswers. Experimental results show that RULER achieves a new stateof-the-art performance in terms of both automatic metrics and human evaluation. Moreover, we observe that RULER achieves better generalizability to the out-of-domain data.

2 RelatedWork

Traditional paraphrase generation methods mainly comprise rule-based methods [Mckeown, 1983; Barzilay and Lee, 2003; Zhao et al., 2009; Lin and Pantel, 2001] and statistical machine translation (SMT) based methods [Quirk et al., 2004]. In particular, Mckeown [1983] proposes to leverage rules extracted from the parsed grammatical tree to perform the transformations of given sentences. Lin and Pantel [2001] assume that dependency trees with similar arguments (leaves) are close in meaning. Based on the assumption, they extract paraphrasing rules to improve question answering. However, these rule-based systems can hardly ensure the fluency of the generated sentences. The SMT-based methods perform better in the quality of the generated paraphrases by calculating the translation probability from given inputs to the outputs [Dolan et al., 2004].

With the development of deep learning, neural networks have become a prevailing approach to paraphrase generation, e.g., using VAE [Gupta et al., 2018], residual LSTM [Prakash et al., 2016] and the latent bag-of-words model [Fu et al., 2019]. To improve the dissimilarity between the outputs and input sentences, Lin and Wan [2021] leverage multi-round paraphrase generation and back translation. Also, Liu et al. [2021] propose multi-round modification in hope of lexically different sequences (e.g., paraphrases). In addition, Li et al. [2019] generate paraphrases of a sentence at different levels of granularity in a disentangled way. However, the granularity of structures is hard to divide, which needs laborintensive annotations to guide the learning.

Our work is also related to rule-enhanced neural networks. Hu et al. [2016] harness deep neural networks with a few manually-designed rules to perform text classification. But it could not be used in text generation and does not involve learning rules. To our knowledge, RULER is the first work of learning the transforming rules in paraphrase generation.

3 The ProposedMethod

To learn to generate high-quality paraphrases, our method RULER consists of two processes, i.e., the abstract rule learning and the rule-enhanced generation, which will be elaborated in the rest of this section.

3.1 Abstract Rules in Paraphrase Generation

The abstract rule was first introduced to study the language acquisition of infants [Marcus et al., 1999]. In this paper, we use an abstract rule to represent a type of paraphrase transformation. Let W be the word vocabulary and Z be the vocabulary of the symbols (placeholders) that can be assigned to various words. An abstract rule r = w → v is an implication corresponding to the conditional statement: "if w is matched, then produce v", where w = [w1, . . . , wLw ] and v = [v1, . . . , vLv ] are the abstract patterns of the input sentence and the corresponding paraphrase, respectively. Lw and Lv are the lengths of tokens of w and v. Note that w and v are not sentences because they commonly contain symbols.

Formally speaking, a rule r describes the mapping from the input sentence to its paraphrase, which is of the form

where Lz is the number of the symbols in rule r.

To apply rule r to transform a given sentence X, the first step is to check whether the sentence X follows the pattern w and determine the words that the symbols z correspond to.

where function "Match" performs token-wise alignment to identify the words in sentence X that match symbols in z (Figure 1). If sentence X is not matched to the rule, function "Match" returns a special token "[None]". Based on the assigned symbols ˆ z, the transformed sentence is

where r(·) produces the sequence v but all symbols in v are assigned to the corresponding words. For notation simplicity, we use T (r,X) to represent the whole rule transformation.

3.2 Abstract Rule Learning

As shown in Figure 2(a), the rule learning process mainly involves a rule learner and a rule evaluation module. The rule learner takes a data point (including both the input sentence X and its paraphrase Y ) as input and generates a candidate rule underlying this data point. The rule evaluation module assesses the generalizability of the extracted rules, and thus guides the learning of the rule learner. The rest of this section will first formulate the rule generation subtask and then elaborate on these two components in detail.

Formulation of the Rule Generation. The rule generation subtask is to extract generalizable rules from a given data point. Let G be the rule learning agent. It functions as

However, if we generate the rule expression (i.e., Equation 1) token by token, the generative complexity is O(|W ∪ Z|L+K ), which will result in low search efficiency. Considering the evaluation of each rule is time-consuming (explained later), it will take a long time to figure out a suitable rule for a data point, making it intractable to train a rule learner. In this work, we try to simplify the rule generation subtask by restricting the output space of the rule learner.

Considering that the extracted rule r is expected to characterize the general mapping of the given data point, we assume that, the tokens of an abstract rule are either the words in the given data point or symbols. Specifically, for each word Yl in the target paraphrase Y , the rule learner predicts a tag Ol, deciding whether the word should be preserved (i.e., the action of holding) or symbolized (i.e., the action of symbolizing).

where θ denotes all model parameters and Ol ∈ {hold, symbolize}. O is the output of the rule learner and Lo is the length of the output O. Note that, to have a one-toone mapping between the output and the target paraphrase, the length of the output is the same as the target paraphrase.

Based on the sequence of binary decisions of the rule learner, it is not difficult to align the symbols to the target paraphrase and the input sentence. Therefore, the abstract rule is obtained by

where "AlignAndMatch" stands for the computations from the output of the rule learner to the generated rule.

In this way, the generation complexity is reduced to O(2Lo ), significantly lower than the original one.

Rule Learner. We use the standard Transformer architecture [Vaswani et al., 2017] as the rule learner. Since both the input sentence and the target paraphrase are inputs of the rule learner, we insert a special separator token [SEP] between them and feed their concatenation into Transformer, given by

Rule Evaluation Module. Besides the huge search space, the lack of direct supervision is the second challenge of rule learning. In this work, we develop a rule evaluation module to automatically assess its quality. We consider the quality of a rule in two aspects, namely, the coverage of the rule and the usefulness of the rule for paraphrase generation.

First, the rule evaluation module tries to figure out how many data points that rule r covers. The wider coverage of a rule, the better generalization it possesses. Therefore, it calculates the coverage score by counting the samples from the training data that comply with the abstract rule r

Dr = {(X, Y )|Match(r,X) ̸= [None] and (X, Y ) ∈ D}, (9) where D is the training dataset and Match(r,X) ̸= [None] denotes the event that sentence X follows rule r. Thus, Dr is the collection of matched samples of rule r.

In order to avoid enumerating all the training data, we stipulate a minimum number Cmin of samples the rule should cover. If the matched samples are more than Cmin, the coverage score is 1. Otherwise, it is the ratio of the number of matched samples to Cmin, computed by

where |Dr| is the size of collection Dr. Hence, for the evaluation of a rule, we only keep up to Cmin samples in Dr to accelerate the evaluation speed.

Second, the rule evaluation module tries to answer the question how many data points that rule r can help to perform paraphrasing. We suppose that, if the sentence transformed by rule r provides more information for paraphrase generation than the original sentence X, rule r is useful to X. As shown in Figure 3, the rule evaluation module leverages a trained paraphrase generator PGα to evaluate the difficulty of the paraphrasing based on the given inputs. For a rule r that is useful to sentence X, we expect the output PGα(X, T (r,X)) is of better quality than the output PGα(X,X). Considering one of the paraphrases of the input sentence X is available (i.e., Y ), the rule evaluation module adopts the reduction of the generation loss induced by the rule r to indicate the improvement of the generation:

where L is the cross-entropy loss of the model to generate target sentence Y from the inputs. α denotes the parameters of PGα. To eliminate the influence of noises, we impose a hyperparameter τ; If the reduction sredu is greater than τ, we call rule r succeeds to help the paraphrase generation task.

The paraphrase generator is also implemented by a Transformer model, given by

where Xaux is the auxiliary input of PGα, such as the sentences transformed by rules.

To reflect a statistical assessment of rule r in terms of usefulness, the rule evaluation module computes an average success rate of the r in helping the paraphrase generator over all the matched sentences

which is used to indicate the usefulness of r. I{} is an indicator that yields 1 when its argument is true, and 0 otherwise.

Finally, the rule evaluation module combines the coverage score and the usefulness score into an overall score to represent the generalizability of the given rule, computed by

Optimization of Rule Learner. After determining the rule generation process and the evaluation of the rule, there is still a difficulty in optimizing the rule learner. That is, the labels contain only ultimate scores (i.e., S(r)), instead of full supervision to the each action. We therefore apply reinforcement learning to train our rule learner. Concretely, we define the generalizability score produced by the evaluation module as the reward of the rule learner. To maximize the expected reward, we compute the gradient of the policy, given by

where πθ(O|X, Y ) stands for the probability of generating the output O given data point (X, Y ). We use REINFORCE algorithm [Williams, 1992] and follow the practical techniques in Liu et al. [2018] to train the rule learner.

When the abstract rule learning process is finished, we obtain a collection of the generated rules R, given by

As the rules whose rewards are zeros have no contributions to paraphrase generation, they are not considered in R.

3.3 Rule-enhanced Paraphrase Generation

For a sentence X with a suitable abstract rule r, we presume that it is easier to generate its paraphrase from the transformed sentence T (r,X) than the original sentence X. Thus, we aim to train a powerful generator PGβ to perform paraphrasing based on the learned rules (Figure 2(b)), where β denotes the parameters of the paraphrase generator PGβ.

We adopt same loss function for the paraphrase generator PGβ as used in the rule evaluator module, but with a different training set. In the rule-enhanced generation process, we add the transformed sentence as the auxiliary input into the training data of the paraphrase generator. Specifically, we select the matched rule with the highest reward to perform the transformation for each sample. Therefore, we have the ruleenhanced training dataset:

When coming a new sentence ˆX for testing, we also perform the same procedures to obtain the auxiliary input (i.e., T (r, ˆX)). Then we feed these two types of inputs into the trained PGβ to generate the final paraphrase ˆ Y , given by

4 Experiments

4.1 Datasets

We evaluate RULER on two widely used datasets, namely, the Quora question pairs and Wikianswers datasets. The Quora dataset contains approximately 140K parallel sentences, which are sourced from question answering forum Quora. The Wikianswers dataset [Fader et al., 2013] comprises 2.3M pairs of question paraphrases scraped from the Wikianswers website. On these two datasets, we adopt the same data splits with Hosking and Lapata [2021] for a fair comparison. Due to the complexity of rule learning, we limit our work to questions for the following two considerations: (1) The space of possible rules is smaller for questions than generic utterances, making the rule learning task more tractable; (2) It is more clearly defined for the concept of question paraphrases (i.e., corresponding to the same answer), thus leading to a better quality of the datasets.

4.2 Implementation Details

The paraphrase generators PGα and PGβ adopt the Transformer architecture and the previous best performing paraphraser model (i.e., SEPARATOR), respectively. To have a fair comparison with SEPARATOR, we use the same hyperparameters with it.

The other hyperparameters involved in our method include the minimum number Cmin of the matched samples for a rule and the improvement threshold τ of the generator loss. As the training of the rule learner is time-consuming (approximately 8 days), these two hyperparameters were selected by manual tuning towards the paraphrasing performance on the validation set on Quora. The minimum number Cmin of matched samples was set to 16. The improvement threshold τ of the generator loss is 0.2.

4.3 CompetingMethods andMetrics

The competing methods used in our work include SEPARATOR [Hosking and Lapata, 2021], vector-quantized variational autoencoder (VQ-VAE) [Van den Oord et al., 2017], diverse paraphraser using submodularity (DiPS) [Kumar et al., 2019], and latent bag-of-words (LBoW) [Fu et al., 2019], paraphraser by neural machine translation (ParaNMT) [Wieting and Gimpel, 2017], and neural syntactic preordering (denoted by SOW/REAP) [Goyal and Durrett, 2020].

Besides the neural-based approaches, we would compare RULER with the rule-based methods. However, the extracted rules of early work [Mckeown, 1983; Barzilay and Lee, 2003] were not available. We are unable to compare them in this paper. Therefore, we implement a rule-based control model named HardMatch. HardMatch shares the same framework with RULER but generates rules by the token-wise matching rather than the rule learner. The extracted rules of HardMatch are scored using iBLEU instead of S(r). We also include a simple baseline named tf-idf. It retrieves the most similar sentences from the training set using tf-idf scores.

We adopt BLEU, iBLEU, and METEOR scores as automatic metrics to evaluate the generation performance. Among them, iBLEU is the BLEU score penalized by the similarity with the original sentence. It is more comprehensive for evaluation, and thus we take it as our major metric.

where ˆ Y is the reference cluster of the input. We follow Hosking and Lapata [2021] to set λ to 0.7.

4.4 Results

Table 1 presents the performance of all competing methods on Quora and Wikianswers. We observe that, the Copy, tfidf and ParaNMT methods show high BLEU scores but the lowest iBLEU scores, indicating that they are just parroting input sentences. The encoder-decoder frameworks, including Transformer, LBoW, VAE and SEPARATOR achieve higher iBLEU scores, which is mainly benefited from the supervised training data. However, such improvement comes with the reduction of the similarity with references. We further observe that RULER yields better results than the other paraphrasing systems, even the previous state-of-the-art model (i.e., SEPARATOR). In addition, the generation performance of HardMatch is also impressive, reflecting that the extracted rules by hard matching could also enhance the paraphrase generation process. But RULER can outperform it by a noticeable margin. This comparison shows that the rules underlying paraphrasing can not be well extracted by simple matching.

It is curious to see how the paraphrase generators perform on a new domain where most sentences are not seen before. In this experiment, a supervised model is trained on one domain and directly tested on the other. As shown in Table 3, the generation performance of supervised methods decreases drastically on out-of-domain sentences. In addition, we also add two domain-adapted methods, including CGMH [Miao et al., 2019] and UPSA [Liu et al., 2020] into comparison. They are unsupervised paraphrasing methods but also perform adaption to the target domain. We find that our approach RULER still obtains better results than all the other methods. We conjecture this is because some of the extracted rules are shared across different domains, which makes RULER more generalizable to the out-of-domain data.

Human Evaluation. In addition to automatic evaluation, we ask three human annotators to evaluate the paraphrases generated by several competing generators (including SEPARATOR, VAE and LBoW). We use a total of 200 questions sampled equally from both Quora and Wikianswers. Each annotator is asked to evaluate generated paraphrases in terms of semantic relevance and expression dissimilarity, scoring from 1 to 5. Note that this experiment is conducted in a blind manner. The average human scores and Cohen's kappa scores are shown in Table 2. Most of the agreement scores are above 0.4, indicating moderate inter-annotator agreement. We observe RULER achieves the highest human satisfaction scores in terms of semantic relevance, and SEPARATOR performs better in expression dissimilarity. Compared with SEPARATOR, RULER presents a large advantage in semantic relevance and small drops in dissimilarity.

5 Model Analysis

Ablation Study. We then probe the influences of different design choices of the paraphrase generator to the performance of RULER. As shown in Table 4, if the generator PGβ uses the rules for training but does not use the rules to transform the input, the performance decreases by about 0.1 iBLEU. However, if we do not use any rules for training, the performance decreases heavily, suggesting the superiority of RULER mainly stems from the improvement of the quality of training data. We hope this observation provides a new perspective on how to use rules in neural networks.

Case Study and Error Analysis. We showcase several generated rules and corresponding paraphrases in Table 5. We see qualitatively that RULER produces more reasonable paraphrases than SEPARATOR in terms of both closeness in meaning and difference in expressions. In these examples, SEPARATOR just changes a few inconsequential words. By leveraging learned rules, RULER can make global modifications to the inputs. Meanwhile, RULER fails to provide suitable rules for some complicated sentences.

6 Conclusion and FutureWork

Abstract rule learning is the ability to find generalizable transformations from the perceptual input to the desired output [Marcus et al., 1999]. In this paper, we explore it in a specific problem, i.e., paraphrase generation. Our proposed method, RULER, first learns the abstract rules by reinforcement learning and then generates paraphrases by taking the rule-enhanced input as an auxiliary input. In the future, we plan to perform symbolic reasoning based on learned rules in hopes of generating more syntactically different sentences.

Acknowledgments

This work was supported by the State Key Program of the National Science Foundation of China under Grant 61836006.