{'fraction_non_alphanumeric': 0.02754767114723351, 'fraction_numerical': 0.011722413254141919, 'mean_word_length': 5.010568341944575, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
PARADIGM: Paraphrase Diagnostics through Grammar Matching

Paraphrase evaluation is typically done either manually or through indirect, taskbased evaluation. We introduce an intrinsic evaluation PARADIGM which measures the goodness of paraphrase collections that are represented using synchronous grammars. We formulate two measures that evaluate these paraphrase grammars using gold standard sentential paraphrases drawn from a monolingual parallel corpus. The first measure calculates how often a paraphrase grammar is able to synchronously parse the sentence pairs in the corpus. The second measure enumerates paraphrase rules from the monolingual parallel corpus and calculates the overlap between this reference paraphrase collection and the paraphrase resource being evaluated. We demonstrate the use of these evaluation metrics on paraphrase collections derived from three different data types: multiple translations of classic French novels, comparable sentence pairs drawn from different newspapers, and bilingual parallel corpora. We show that PARADIGM correlates with human judgments more strongly than BLEU on a task-based evaluation of paraphrase quality.


Introduction
Paraphrases are useful in a wide range of natural language processing applications. A variety of data-driven approaches have been proposed to generate paraphrase resources (see  for a survey of these methods). Few objective metrics have been established to evaluate these resources. Instead, paraphrases are typically evaluated using subjective manual evaluation or through task-based evaluations.
Different researchers have used different criteria for manual evaluations. For example, Barzilay and McKeown (2001) evaluated their paraphrases by asking judges whether paraphrases were "approximately conceptually equivalent." Ibrahim et al. (2003) asked judges whether their paraphrases were "roughly interchangeable given the genre." Bannard and Callison-Burch (2005) replaced phrases with paraphrases in a number of sentences and asked judges whether the substitutions "preserved meaning and remained grammatical." The results of these subjective evaluations are not easily reusable.
Other researchers have evaluated their paraphrases through task-based evaluations. Lin and Pantel (2001) measured their potential impact on question-answering. Cohn and Lapata (2007) evaluate their applicability in the text-to-text generation task of sentence compression. Zhao et al. (2009) use them to perform sentence compression and simplification and to compute sentence similarity. Several researchers have demonstrated that paraphrases can improve machine translation evaluation (c.f. Kauchak and Barzilay (2006), Zhou et al. (2006), Madnani (2010) and Snover et al. (2010)).
We introduce an automatic evaluation metric called PARADIGM, PARAphrase DIagnostics through Grammar Matching. This metric evaluates paraphrase collections that are represented using synchronous grammars. Synchronous treeadjoining grammars (STAGs), synchronous tree substitution grammars (STSGs), and synchronous context free grammars (SCFGs) are popular formalisms for representing paraphrase rules (Dras, 1997;Cohn and Lapata, 2007;Madnani, 2010;. We present two measures that evaluate these paraphrase grammars using gold standard sentential paraphrases drawn from a monolingual parallel corpus, which have been previously proposed as a good resource for paraphrase evaluation .
The first of our two proposed metrics calculates how often a paraphrase grammar is able to synchronously parse the sentence pairs in a test set. The second measure enumerates paraphrase rules from a monolingual parallel corpus and calculates the overlap between this reference paraphrase collection, and the paraphrase resource being evaluated.

Related work and background
The most closely related work is ParaMetric , which is a set of objective measures for evaluating the quality of phrase-based paraphrases. ParaMetric extracts a set of gold-standard phrasal paraphrases from sentential paraphrases that have been manually wordaligned. The sentential paraphrases used in Para-Metric were drawn from a data set originally created to evaluate machine translation output using the BLEU metric.  argue that these sorts of monolingual parallel corpora are appropriate for evaluating paraphrase systems, because they are naturally occurring sources of paraphrases.  calculated three types of metrics in ParaMetric. The manual word alignments were used to calculate how well an automatic paraphrasing technique is able to align the paraphrases in a sentence pair. This measure is limited to a class of paraphrasing techniques that perform alignment (like MacCartney et al. (2008)). Most methods produce a list of paraphrases for a given input phrase. So  calculate two more generally applicable measures by comparing the paraphrases in an automatically extracted resource to gold standard paraphrases extracted via the alignments. These allow a lower-bound on precision and relative recall to be calculated. Liu et al. (2010) introduce the PEM metric as an alternative to BLEU, since BLEU prefers identical paraphrases. PEM uses a second language as a pivot to judge semantic equivalence. This requires use of some bilingual data. Chen and Dolan (2011) suggest using BLEU together with their metric PINC, which uses n-grams to measure lexical difference between paraphrases.
PARADIGM extends the ideas in ParaMetric from lexical and phrasal paraphrasing techniques to paraphrasing techniques that also generate syntactic templates, such as Zhao et al. (2008), Lapata (2009), Madnani (2010) and . Instead of extracting gold standard paraphrases using techniques from phrasebased machine translation, we use grammar extraction techniques (Weese et al., 2011) to extract gold standard paraphrase grammar rules from ParaMetric's word-aligned sentential paraphrases. Using these rules, we calculate the overlap between a gold standard paraphrase grammar and an automatically generated paraphrase grammar.
Moreover, like ParaMetric, PARADIGM is able to do further analysis on a restricted class of paraphrasing models. In this case, PARADIGM evaluates how well certain models are able to produce synchronous parses of sentence pairs drawn from monolingual parallel corpora. PARADIGM's different metrics are explained in Section 4, but first we give background on synchronous parsing and synchronous grammars.

Synchronous parsing with SCFGs
Synchronous context-free grammars An SCFG (Lewis and Stearns, 1968;Aho and Ullman, 1972) is similar to a context-free grammar, except that it generates pairs of strings in correspondence. Each production rule in an SCFG rewrites a non-terminal symbol as a pair of phrases, which may have contain a mix of words and non-terminals symbols. The grammar is synchronous because both phrases in the pair must have an identical set of non-terminals (though they can come in different orders), and corresponding non-terminals must be rewritten using the same rule.
Much recent work in MT (and, by extension, paraphrasing approaches that use MT machinery) has been focused on choosing an appropriate set of non-terminal symbols. The Hiero model (Chiang, 2007) used a single non-terminal symbol X. Other approaches have read symbols from constituent parses of the training data (Galley et al., 2004;Galley et al., 2006;Zollmann and Venugopal, 2006). Labels based combinatory categorial grammar (Steedman and Baldridge, 2011) have also been used (Almaghout et al., 2010;. Wu (1997) Figure 1: PARADIGM extracts lexical, phrasal and syntactic paraphrases from parsed, word-aligned sentence pairs. that the average parse time can be significantly improved by using a two-pass algorithm. The question of whether a source-reference pair is reachable under a model must be addressed in end-to-end discriminative training in MT (Liang et al., 2006a;Gimpel and Smith, 2012). Auli et al. (2009) showed that only approximately 30% of training pairs are reachable under a phrase-based model. This result is confirmed by our results in paraphrasing.

Paraphrase grammar extraction
Like ParaMetric, PARADIGM extracts gold standard paraphrases from word-aligned sentential paraphrases. PARADIGM goes further by parsing one of the two input sentences, and uses the parse tree to extract syntactic paraphrase rules, following recent advances in syntactic approaches to machine translation (like Galley et al. (2004), Zollmann and Venugopal (2006), and others). Figure 1 shows an example of a parsed sentence pair. From that pair it is possible to extract a wide variety of non-identical paraphrases, which include lexical paraphrases (single word synonyms), phrasal paraphrases, and syntactic paraphrases that include a mix of words and syntactic non-terminal CC → and while VBP → want propose VBP → expect want DT → some some people S → him to step down him to resign VP → step down resign VP → to step down to resign VP → want to impeach him propose to impeach him VP → want VP propose VP VP → want to impeach PRP propose to impeach PRP VP → VBP him to step down VBP him to resign S → PRP to step down PRP to resign Figure 2: Four examples each of lexical, phrasal, and syntactic paraphrases that can be extracted from the sentence pair in Figure 1.
symbols. Figure 2 shows a set of four examples for each type that can be extracted from Figure 1. These rules are formulated as SCFG rules, with a syntactic left-hand nonterminal symbol and two English right-hand sides representing the paraphrase. The examples above include nonterminal symbols that represent whole syntactic constituents. It is also possible to create more complex non-terminal symbols that describe CCG-like non-constituent phrases. For example, we could extract a rule like S/VP → <NNS want him to, NNS expect him to> Using constituents only, we are able to extract 45 paraphrase rules from Figure 1. Adding CCG-style slashed constituents yields 66 additional rules.

PARADIGM: Evaluating paraphrase grammars
By considering a paraphrase model as a synchronous context-free grammar, we propose to measure the model's goodness using the following criteria: 1. What percentage of sentential paraphrases are reachable under the model? That is, given a collection of sentence pairs (a i , b i ) and an SCFG G, where each pair of a and b are sentential paraphrases, how many of the pairs are in the language of G? We evaluate this by producing a synchronous parse for the pairs, as shown in Figure 3.
2. Given a collection of gold-standard paraphrase rules, how many of those paraphrases exist as rules in G? To calculate this, we look at the overlap of grammars (described in  Figure 3: We measure the goodness of paraphrase grammars by determine how often they can be used to synchronously parse gold-standard sentential paraphrases. Note we do not require the synchronous derivation to match a gold-standard parse tree. Section 4.2 below), examining different categories of rules and thresholding based on how frequently the rule was used in the gold standard data.
These criteria correspond to properties that we think are desirable in paraphrase models. They also have the advantage that they do not depend on human judgments and so can be calculated automatically.

Synchronous parse coverage
Paraphrase grammars should be able to explain sentential paraphrases.
For example, Figure  3 shows a sentence pair that is synchronously parseable by one paraphrase grammar. In general, we say that the more such sentence pairs that a paraphrase grammar can synchronously parse, the better it is.
The synchronous derivation allows us to draw inferences about parts of the sentence pair that are in correspondence; for instance, in Figure 3, violent unrest corresponds to riots and mohammad corresponds to the islamic prophet.

Grammar overlap defined
We measure grammar overlap by comparing the sets of production rules for two different grammars. If the grammars contain rules that are equivalent, the equivalent rules are in the grammars' overlap.
We consider two types of overlapping, which we will call strict and non-strict overlap. For strict overlap, we say that two rules are equivalent if they are identical, that is, if they have the same left-hand side non-terminal symbol, their source sides are identical strings, and their target sides are identical strings. (This includes identical indexing on non-terminal symbols on the right hand sides of the rule.) To calculate non-strict overlap, we ignore the identities of non-terminal symbols in the left-hand and right-hand sides of the rules. That is, two rules are considered equivalent if they are identical after all the non-terminal symbols have been replaced by one equivalent symbol.
For example, in non-strict overlap, the syntactic rule If we are considering two Hiero grammars, strict and non-strict intersection are the same operation since they only have on non-terminal X.

Precision lower bound and relative recall
Callison-Burch et al. (2008) use the notion of overlap between two paraphrase sets to define two metrics, precision lower bound and relative recall. These are calculated the same way as standard precision and recall. Relative recall is qualified as "relative" because it is calculated on a potentially incomplete set of gold standard paraphrases. There may exist valid paraphrases that do not occur in that set. Similarly, only a lower bound on precision can be calculated because the candidate set may contain valid paraphrases that do not occur in the gold standard set.

Data
We extracted paraphrase grammars from a variety of different data sources, including four collections of sentential paraphrases. These included: • Multiple translation corpora that were compiled by the Linguistics Data Consortium  Barzilay and McKeown (2001). MSR data is from  and . ParaMertic data is from .
• Classic French Literature that were translated by different translators, and which were compiled by Barzilay and McKeown (2001).
• The MSR Paraphrase corpus which consists of sentence pairs drawn from comparable news articles drawn from different web sites in the same date rate. The sentence pairs were aligned heuristically aligned and then manually judged to be paraphrases.
• The ParaMetric data which consists of 900 manually word-aligned sentence pairs collected by . 300 sentence pairs were drawn from each of the 3 above sources. We use this to extract the gold standard paraphrase grammar.
The size of the data from each source is summarized in Table 1. For each dataset, after tokenizing and normalizing, we parsed one sentence in each English pair using the Berkeley constituency parser (Liang et al., 2006b). We then obtained word-level alignments, either using GIZA++ (Och and Ney, 2000) or, in the case of ParaMetric, using human annotations.
We used the Thrax grammar extractor (Weese et al., 2011) to extract Hiero-style and syntactic SCFGs from the paraphrase data. In the syntactic setting we allowed labeling of rules with either constituent labels or CCG-style slashed categories. The size of the extracted grammars is shown in Table 2.
We also used version 0.2 of the SCFG-based paraphrase collection known as the ParaPhrase DataBase or PPDB    2005) on bilingual parallel corpora containing over 42 million sentence pairs. The PPDB release includes a tool for pruning the grammar to a smaller size by retaining only high-precision paraphrases. We include PPDB grammars for several different pruning settings in our analysis.

Experimental setup
We calculated our two metrics for each of the grammars listed in Table 2.
To perform synchronous parsing, we used the Joshua decoder (Post et al., 2013), which includes an implementation of Dyer's two-pass parsing algorithm (2010). After splitting the LDC data into 10 equal pieces, we trained paraphrase models on nine-tenths of the data and parsed the other tenth.
Grammars trained from other sources (the MSR corpus, French literature domain, and PPDB) were also evaluated on the held-out tenth of LDC data.   Note that the LDC data contains 4 independent translations of each foreign sentence, giving 6 possible (unordered) paraphrase pairs. We evaluated coverage in two ways (corresponding to the two columns in Table 6): first, considering all possible sentence pairs from the test data, how many were able to be parsed?
Secondly, if we consider all the English sentences that correspond to one foreign sentence, how many foreign sentences had at least one pair of English translations that could be parsed synchronously?
For grammar overlap, we perform both strict and non-strict calculations (see Section 4.2) against a syntactic grammar derived from handaligned ParaMetric data.

Grammar overlap results
In Table 5 we see a breakdown of the types of paraphrases in the overlap for three of the models. Although the PPDB-xl overlap is much larger than the other two, about 80% of its rules are syntactic transformations. The LDC and MSR models have a much larger proportion of phrasal and lexical rules.
Next we will look at the grammar overlap num-  bers presented in Table 3 and Table 4. Note the non-intuitive result that for some grammars (notably PPDB), the non-strict overlap is smaller than the strict overlap. This is because rules with different non-terminals only count once in the non-strict overlap; for example, in PPDBsmall, NN → answer ; reply VB → answer ; reply count as separate entries when calculating strictly, but when ignoring non-terminals, they count as only one type of rule.
The fact that the non-strict overlaps are smaller means that there must be many rules in PPDB that are identical except for non-terminal labels. Figure 4 shows relative recall and precision lower bound calculated for various sizes of PPDB relative to the ParaMetric grammar. The x-axis represents the size of the grammar as we vary from keeping only the most probable rules to including less probable ones. Restricting to high probability rules makes the grammar much smaller, resulting in higher precision. Table 6 shows the percentage of sentence pairs that were reachable in a held-out portion of the LDC multiple-translation data.

Synchronous parsing results
We find that a grammar trained on LDC data vastly outperforms data from any other domain. This is not surprising -we shouldn't expect a model trained on French literature to be able to  Table 6: Parse coverage on held-out LDC data. The all column considers every possible sentential paraphrase in the test set. The any column considers a sentence parsed if any of its paraphrases was able to parsed.
handle some of the vocabulary found in news stories that were originally in Arabic or Chinese. The PPDB data outperforms both French literature and MSR models if we look all possible sentence pairs from test data (the column labeled "all" in the table). However, when we consider whether any pair from a set of 4 translations can be translated, the PPDB models do not do as well. This implies that PPDB tends to be able to reach many pairs from the same set of translations, but there are many translations that it cannot handle at all. By contrast, the literature-and MSR-trained models can reach at least one pair from 10% of the test examples, even though the absolute number of pairs they can reach is lower. Table 2 shows that the PPDB-derived grammars are much larger than the syntactic models derived from other domains. It may seem surprising that they should perform worse, but adding more rules to the grammar just by varying non-terminal labels isn't likely to help overall parse coverage. This suggests a new pruning method: keep only the top k label variations for each rule type. If we compare the syntactic models to the Hiero models trained from the same data, we see that their overall reachability performance is not very different. This implies that paraphrases can be annotated with linguistic information without necessarily hurting their ability to explain particular sentence pairs. Contrast this result, with, for example, those of Koehn et al. (2003), showing that restricting translation models to only syntactic phrases hurts overall translation performance. The comparable performance between Hiero and syntactic models seems to hold regardless of domain.

Correlation with human judgments
To validate PARADIGM, we calculated its correlation with human judgments of paraphrase quality on the sentence compression text-to-text generation task, which has been used to evaluate paraphrase grammars in previous research (Cohn and Lapata, 2007;Zhao et al., 2009;. We created sentence compression systems for five of the paraphrase grammars described in Section 5.1. We followed the methodology outlined by  and did the following: • Each paraphrase grammar was augmented with an appropriate set of rule-level features that capture information pertinent to the task. In this case, the paraphrase rules were given two additional features that shows how the number of words and characters changed after applying the rule. • Similarly to how the weights of the models are set using minimum error rate training in statistical machine translation, the weights for each of the paraphrase grammars using the PRO tuning method (Hopkins and May, 2011).
• Instead of optimizing to the BLEU metric, as is done in machine translation, we optimized to PRÉCIS, a metric developed for sentence compression that adapts BLEU so that it includes a "verbosity penalty"  to encourage the compression systems to produce shorter output.
• We created a development set with sentence compressions by selecting 1000 pairs of sentences from the multiple translation corpus where two English translations of the same foreign sentences differed in each other by a length ratio of 0.67-0.75.
• We decoded a test set of 1000 sentences using each of the grammars and its optimized weights with the Joshua decoder (Ganitkevitch et al., 2012). The selected in the same fashion as the dev sentences, so each one had a human-created reference compression.
We conducted a human evaluation to judge the meaning and grammaticality of the sentence compressions derived from each paraphrase grammar. We presented workers on Mechanical Turk with the input sentence to the compression sentence (the long sentence), along with 5 shortened outputs from our compression systems. To ensure that workers were producing reliable judgments we also presented them with a positive control (a reference compression written by a person) and a negative controls (a compressed output that was generated by randomly deleted words). We excluded judgments from workers who did not perform well on the positive and negative controls.
Meaning and grammaticality were scored on 5-point scales where 5 is best. These human scores were averaged over 2000 judgments (1000 sentences x 2 annotators) for each system. The systems' outputs were then scored with BLEU, PRÉCIS, and their paraphrase grammars were scored PARADIGM's relative recall and precision lower-bound estimates. For each grammar, we also calculated the average length of parseable sentences.
We calculated the correlation between the human judgements and the automatic scores, using Spearman's rank correlation coefficient ρ. This is methodology is the same that is used to quantify the goodness of automatic evaluation metrics in the machine translation literature (Przybocki et al., 2008;Callison-Burch et al., 2010). The possible values of ρ range between 1 (where all systems are ranked in the same order) and −1 (where the systems are ranked in the reverse order). Thus an automatic evaluation metric with a higher absolute value for ρ is making predictions that are more similar to the human judgments than an automatic evaluation metric with a lower absolute ρ. Table 7 shows that our PARADIGM scores correlate more highly with human judgments than either BLEU or PRÉCIS for the 5 systems in our evaluation. This suggests that it may be a better predictor of the goodness of paraphrase grammars than MT metrics, when the paraphrase grammars are used for text-to-text generation tasks.  Table 7: The correlation (Spearman's ρ) of different automatic evaluation metrics with human judgments of paraphrase quality for the text-totext generation task of sentence compression.

Summary
We have introduced two new metrics for evaluating paraphrase grammars, and looked at several models from a variety of domains. Using these metrics we can perform a variety of analyses about SCFG-based paraphrase models: • Automatically-extracted grammars can parse a small fraction of held-out data (≤30%). This is comparable to results in MT (Auli et al., 2009).
• In-domain training data is necessary in order to parse held-out data. A model trained on newswire data parsed 30% of held-out newswire sentence pairs, versus to <10% for literature or parliamentary data.
• SCFGs with syntactic labels perform just as well as simpler models with a single nonterminal label.
• Automatically-extracted syntactic grammars tend to have a reasonable overlap with grammars derived from human-aligned data, including more 45% of the gold-standard grammar's paraphrase rules that occurred at least twice.
• We showed that PARADIGM more strongly correlates with human judgments of the meaning and grammaticality of paraphrases produced by sentence compression systems than standard automatic evaluation measures like BLEU.
PARADIGM will help researchers developing paraphrase resources to perform similar diagnostics on their models, and quickly evaluate their systems.