UNIVERSITÉ DE LORRAINE
IDMC

MASTER THESIS

# X-ParEval
A Multilingual Metric for Paraphrase Evaluation

Author:
William SOTO

Supervisor:
Claire GARDENT

Jury:
Maxime AMBLARD
Yves LAPRIE
Romain SÉRIZEL

A thesis submitted in fulfillment of the requirements
for the degree of MSc in Natural Language Processing
in the

SyNaLP
LORIA

September, 2021

<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>
Declaration of Authorship

I, William SOTO, declare that this thesis titled, "X-ParEval
A Multilingual Metric for Paraphrase Evaluation" and
the work presented in it are my own. I confirm that:

* This work was done wholly or mainly while in candidature for a research degree at this University.

* Where any part of this thesis has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated.

* Where I have consulted the published work of others, this is always clearly attributed.

* Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work.

* I have acknowledged all main sources of help.

* Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself.

Signed:

Date:
<figure><img src="image_3.png" /></figure>
"Men content themselves with the same words as other people use, as if the very sound necessarily carried the same meaning."

John Locke
<figure><img src="image_4.png" /></figure>
UNIVERSITÉ DE LORRAINE

Abstract

IDMC
LORIA

MSc in Natural Language Processing

X-ParEval

# A Multilingual Metric for Paraphrase Evaluation

by William SOTO

Paraphrase Evaluation is the task of assigning a score that represents how well a pair of texts paraphrase each other. This task is helpful to assess other tasks like Paraphrase Generation or Paraphrase Compilation. Despite its usefulness, there has been a lack of standardization which complicates comparability between studies. Some of the used approaches are language-dependent. Furthermore, most of the common approaches tend to omit some elements of good paraphrasing.

In this thesis, we propose X-ParEval, a multilingual metric for Paraphrase Evaluation that relies on embedding-based semantic similarity while penalizing surface similarity. Our metric outperforms other used metrics in terms of correlation with human judges and works well with various languages.

Finally, by providing a publicly available library to compute the score, we hope to encourage and facilitate comparability on future works that require Paraphrase Evaluation.
<figure><img src="image_5.png" /></figure>
Acknowledgements

This work would not have been possible without the close guidance of my supervisor Claire Gardent, for which I will always be grateful.

I would also like to thank the wonderful people from the SyNaLP team. Special thanks to Yannick Parmentier, Angela Fan, Liam Cripwell and Kelvin Han which, each in their own way, helped to the completion of this work.

Thanks to the professors of the IDMC that made sure to teach what was necessary to undertake this endeavour. Particularly to Maxime Amblard and Miguel Couceiro as directors of the program.

Finally, I want to thank my family, who has always supported me despite the difficulties.
<figure><img src="image_6.png" /></figure>
# Contents

<table><tr><td>Declaration of Authorship</td><td>iii</td></tr><tr><td>Abstract</td><td>vii</td></tr><tr><td>Acknowledgements</td><td>ix</td></tr><tr><td>1 Framework</td><td>1</td></tr><tr><td>1.1 Host Institution</td><td>1</td></tr><tr><td>1.2 Equipment and Software</td><td>2</td></tr><tr><td>2 Paraphrase Evaluation</td><td>3</td></tr><tr><td>2.1 Precision and Recall</td><td>4</td></tr><tr><td>2.1.1 BLEU</td><td>6</td></tr><tr><td>2.1.2 Google-BLEU</td><td>7</td></tr><tr><td>2.1.3 ROUGE</td><td>8</td></tr><tr><td>2.1.4 PARAMETRIC</td><td>8</td></tr><tr><td>2.1.5 PEM</td><td>9</td></tr><tr><td>2.1.6 PINC</td><td>11</td></tr><tr><td>2.1.7 PARADIGM</td><td>11</td></tr><tr><td>2.1.8 APEM</td><td>12</td></tr><tr><td>2.2 Cosine Similarity</td><td>12</td></tr><tr><td>2.2.1 PPDB Score</td><td>12</td></tr><tr><td>2.2.2 PARAGRAMPHRASE</td><td>13</td></tr><tr><td>2.2.3 Automatic Evaluation of Arabic Paraphrases</td><td>13</td></tr><tr><td>2.2.4 WEEM4PG</td><td>13</td></tr><tr><td>3 PAREVAL</td><td>15</td></tr><tr><td>3.1 Theoretical Proposal</td><td>15</td></tr><tr><td>3.2 Practical Implementation</td><td>16</td></tr><tr><td>3.2.1 Semantic Similarity</td><td>16</td></tr><tr><td>3.2.2 Surface Similarity</td><td>18</td></tr><tr><td>3.2.3 Multilinguality</td><td>18</td></tr><tr><td>3.2.4 Code</td><td>19</td></tr><tr><td>4 Experiments</td><td>21</td></tr><tr><td>4.1 Datasets</td><td>21</td></tr><tr><td>4.1.1 ULPC</td><td>21</td></tr><tr><td>4.1.2 MSRP</td><td>21</td></tr><tr><td>4.1.3 Human Labeled PPDB 2.0</td><td>21</td></tr><tr><td>4.1.4 Europarl AMR to Text</td><td>22</td></tr><tr><td>4.1.5 ParaPhraser</td><td>22</td></tr><tr><td>4.1.6 ArPC</td><td>22</td></tr><tr><td>4.1.7 TMUP</td><td>22</td></tr></table>
<table><tr><td>4.2 Comparing Metrics</td><td>22</td></tr><tr><td>4.3 Assessing X-ParEval</td><td>24</td></tr><tr><td>4.4 Paraphrase Generation</td><td>24</td></tr><tr><td>4.4.1 AMR to Text Generation</td><td>24</td></tr><tr><td>4.4.2 Many to Many Multilingual Translation</td><td>25</td></tr><tr><td>4.4.3 MBart-50</td><td>25</td></tr><tr><td>4.4.4 Results</td><td>27</td></tr><tr><td>5 Conclusions</td><td>29</td></tr><tr><td>A Metrics Implementation</td><td>31</td></tr><tr><td>A.1 BLEU</td><td>31</td></tr><tr><td>A.2 Google-BLEU</td><td>31</td></tr><tr><td>A.3 ROUGE</td><td>31</td></tr><tr><td>A.4 PEM</td><td>31</td></tr><tr><td>A.5 PINC</td><td>31</td></tr><tr><td>A.6 APEM</td><td>31</td></tr><tr><td>A.7 Cosine Similarity</td><td>32</td></tr><tr><td>A.8 Harmonic Mean</td><td>32</td></tr><tr><td>A.9 WEEM4PG</td><td>32</td></tr><tr><td>A.10 X-ParEval</td><td>32</td></tr><tr><td>Bibliography</td><td>33</td></tr></table>
List of Figures

<table><tr><td>3.1 X-ParEval score for different values of semantic similarity and surface similarity.</td><td>17</td></tr></table>
<figure><img src="image_7.png" /></figure>
List of Tables

<table><tr><td>4.1</td><td>Pearson's correlation and p-value between different metrics and different types of human evaluations on ULPC.</td><td>23</td></tr><tr><td>4.2</td><td>Metric comparison on test sentences from Sentence List 1.</td><td>23</td></tr><tr><td>4.3</td><td>Pearson's correlation and p-value between X-ParEval, its semantic similarity component, and its surface similarity component with equivalent human evaluations on different paraphrase data sets.</td><td>25</td></tr><tr><td>4.4</td><td>X-ParEval on the Europarl Test dataset.</td><td>27</td></tr></table>
<figure><img src="image_8.png" /></figure>
List of Abbreviations

<table>
   <tr>
    <td>AMR</td>
    <td>Abstract Meaning Representation</td>
   </tr>
   <tr>
    <td>APEM</td>
    <td>Automatic Paraphrase Evaluation using Morphological Analysis</td>
   </tr>
   <tr>
    <td>ArPC</td>
    <td>Arabic Paraphrase Corpus</td>
   </tr>
   <tr>
    <td>BT</td>
    <td>Back Translation</td>
   </tr>
   <tr>
    <td>BLEU</td>
    <td>Bilingual Evaluation Understudy</td>
   </tr>
   <tr>
    <td>BPNG</td>
    <td>Bag of Pivot language N-Ngrams</td>
   </tr>
   <tr>
    <td>CNRS</td>
    <td>Centre National de la Recherche Scientifique</td>
   </tr>
   <tr>
    <td>DP</td>
    <td>Direct Paraphrasing</td>
   </tr>
   <tr>
    <td>FN</td>
    <td>False Negative</td>
   </tr>
   <tr>
    <td>FP</td>
    <td>False Positive</td>
   </tr>
   <tr>
    <td>INRIA</td>
    <td>Institut National de Recherche en Informatique et en Automatique</td>
   </tr>
   <tr>
    <td>LCS</td>
    <td>Longest Common Sub-sequence</td>
   </tr>
   <tr>
    <td>LORIA</td>
    <td>Laboratoire Lorrain de Recherche en Informatique et ses Applications</td>
   </tr>
   <tr>
    <td>MSE</td>
    <td>Mean Square Error</td>
   </tr>
   <tr>
    <td>MSRP</td>
    <td>MicroSoft Research Paraphrase</td>
   </tr>
   <tr>
    <td>MT</td>
    <td>Machine Translation</td>
   </tr>
   <tr>
    <td>MTE</td>
    <td>Machine Translation Evaluation</td>
   </tr>
   <tr>
    <td>NLG</td>
    <td>Natural Language Generation</td>
   </tr>
   <tr>
    <td>NLP</td>
    <td>Natural Language Processing</td>
   </tr>
   <tr>
    <td>PARADIGM</td>
    <td>Paraphrase Diagnostic through Grammar Matching</td>
   </tr>
   <tr>
    <td>PARAMETRIC</td>
    <td>Paraphrase Metric</td>
   </tr>
   <tr>
    <td>X-ParEval</td>
    <td>Crosslingual Paraphrase Evaluation</td>
   </tr>
   <tr>
    <td>PE</td>
    <td>Paraphrase Evaluation</td>
   </tr>
   <tr>
    <td>PEM</td>
    <td>Paraphrase Evaluation Metric</td>
   </tr>
   <tr>
    <td>PI</td>
    <td>Paraphrase Identification</td>
   </tr>
   <tr>
    <td>PINC</td>
    <td>Paraphrase In N-gram Changes</td>
   </tr>
   <tr>
    <td>PG</td>
    <td>Paraphrase Generation</td>
   </tr>
   <tr>
    <td>PPDB</td>
    <td>Paraphrase Data Base</td>
   </tr>
   <tr>
    <td>PPDB</td>
    <td>Paraphrase Data Base</td>
   </tr>
   <tr>
    <td>ROUGE</td>
    <td>Recall-Oriented Understudy for Gisting Evaluation</td>
   </tr>
   <tr>
    <td>SCFG</td>
    <td>Synchronous Context-Free Grammars</td>
   </tr>
   <tr>
    <td>SyNaLP</td>
    <td>Symbolic and Statistical Natural Language Processing</td>
   </tr>
   <tr>
    <td>SVM</td>
    <td>Support Vector Machine</td>
   </tr>
   <tr>
    <td>TMUP</td>
    <td>Tokyo Metropolitan University Paraphrase</td>
   </tr>
   <tr>
    <td>TP</td>
    <td>True Negative</td>
   </tr>
   <tr>
    <td>TP</td>
    <td>True Positive</td>
   </tr>
   <tr>
    <td>ULPC</td>
    <td>User-Language Paraphrase Corpus</td>
   </tr>
   <tr>
    <td>UMR</td>
    <td>Unité Mixte de Recherche</td>
   </tr>
  </table>
<figure><img src="image_9.png" /></figure>
List of Symbols

|X| cardinality of X

[X] multiset of X

{X} set of X

X ∩ Y Intersection of X and Y

X ∪ Y Union of X and Y
<figure><img src="image_10.png" /></figure>
*To my parents.*
<figure><img src="image_11.png" /></figure>
# Chapter 1

# Framework

This thesis presents a study on Paraphrase Evaluation (PE) and a proposal for a new multilingual metric to perform that task. Chapter 1 presents the context of the research comprised by the hosting institution and the equipment used. Chapter 2 presents an overview of Paraphrase Evaluation techniques over time and comments on their pros and cons. Chapter 3 covers our proposal for a multilingual metric for Paraphrase Evaluation. Chapter 4 describes the methodology used to evaluate our metrics and the results obtained. Finally, Chapter 5 includes a discussion of our results and presents our conclusions.

## 1.1 Host Institution

The Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)<fnref n="1" /> is a mixed research unit (Unité Mixte de Recherche, UMR) comprised by members of three different institutions: the Centre National de la Recherche Scientifique (CNRS),<fnref n="2" /> the Université de Lorraine,<fnref n="3" /> and the Institut National de Recherche en Informatique et en Automatique (INRIA).<fnref n="4" />

The laboratory was officially founded in 1997 to research fundamental and applied computer sciences. It is a member of the Charles Hermite Federation,<fnref n="5" /> which groups the four most important research labs in Mathematics, Information and Communication Sciences, and Control and Automation.

Directed by Jean-Yves Marion, the LORIA has around 400 employees distributed on five departments and 30 teams covering a wide variety of fields:

* The Algorithmique, Calcul, Image et Géométrie department focuses on problems of algorithmic nature encountered particularly in fields related to geometry and symbolic computation.

* The Methodes Formelles department focuses on methodologies, techniques and tools to analyze, verify, and develope safe and secure software-based systems.

* The Réseaux, Systèmes et Services department tackles problems related to large parallel and distributed systems and the ability that they offer to work, manage, compute, and communicate seamlessly on a previously unknown scale, accuracy and spatial distribution.

<footnote n="1">¹https://www.loria.fr/en</footnote>

<footnote n="2">²http://www.cnrs.fr/en</footnote>

<footnote n="3">³https://www.univ-lorraine.fr/en</footnote>

<footnote n="4">⁴https://www.inria.fr/en</footnote>

<footnote n="5">⁵http://www.fr-hermite.univ-lorraine.fr/</footnote>
* The *Traitement Automatique des Langues et des Connaissances* department studies the three closely related fields of natural language, knowledge, and document processing.

* The *Systèmes Complexes, Intelligence Artificielle et Robotique* department studies complex systems, artificial intelligence, and robotics; it focuses on homogeneous and heterogeneous interactions in multi-scale complex systems across many areas.

This thesis was conducted for the Symbolic and Statistical Natural Language Pro-
cessing (SyNaLP)<fnref n="6" /> team from the *Traitement Automatique des Langues et des Connais-
sances* department. This team focuses on hybrid, symbolic and statistical approaches
to natural language processing (NLP) and applications built thereon. It includes
NLP for Man-Machine Dialog, Language Learning, and Data Verbalisation. Within
the SyNaLP, Claire Gardent supervises the XNLG Chair, which focuses on Natural
Language Generation (NLG). This thesis belongs to the research conducted as part
of that project.

## 1.2 Equipment and Software

The laboratory provided a Dell Latitude 5495 terminal for the research. Most of
the work consisted of the application, re-implementation, and comparison of Para-
phrase Evaluation metrics, and the implementation of our metric. Most of the work
was done in Google Colaboratory<fnref n="7" />, which allows users to write and execute python
code through their browser. When higher computational power was required, we
used Grid5000 [2], a cloud-based platform for experiments hosted by INRIA.

The code was developed using Python 3 [46]. Well-known libraries like Pandas [44], Scikit-Learn [31], Pytorch [29], and NLTK [4] were used. In addition to that, other libraries like Sentence-Transformers [37], Sacrebleu [33], and Rouge-Score<fnref n="8" /> were used.

<footnote n="6">⁶https://synalp.loria.fr/</footnote>

<footnote n="7">⁷https://colab.research.google.com/</footnote>

<footnote n="8">⁸https://pypi.org/project/rouge-score/</footnote>
# Chapter 2

## Paraphrase Evaluation

Paraphrases are different ways of writing the same idea. This concept applies to texts of all sizes, from words and short phrases to sentences and paragraphs. More specifically, a paraphrase has two main elements to take into account:

* Semantic similarity: this is how similar the meaning of both texts is.

* Surface dissimilarity: this is how differently the meaning is realized.

In general, good paraphrases should keep the meaning between each other as much as possible while having a different enough surface realization not to be considered just copies of one another.

To exemplify the relationship between sentences and their paraphrasing quality, consider **Sentence List 1**. By comparing the source sentence **Sentence 1a** with each of the other sentences, we can understand how paraphrasing can be evaluated. **Sentence 1b** changes just a couple of words; it paraphrases the source sentence, but not in a particularly impressive way. **Sentence 1c** shuffles the sentence's structure and adds some more word changes (notably the city's name for its acronym); this is a better paraphrase than **Sentence 1b**. In contrast, while **Sentence 1d**, **Sentence 1e**, **Sentence 1f**, and **Sentence 1g** are very similar to the source sentence and the already mentioned paraphrases, they are not paraphrases of the source sentence because the main meaning of the message has changed. From this basic example, we can infer that, while a good paraphrase requires both semantic similarity and surface dissimilarity, semantic similarity is the more relevant of the two.

(1) a. Every year millions of tourists go to New York City.

b. ✅ Each year millions of tourists visit New York City.

c. ✅ Millions of tourists visit NYC each year.

d. ❌ Every week millions of tourists go to New York City.

e. ❌ Every year millions of tourists go to Paris.

f. ❌ Each year millions of tourists visit Paris.

g. ❌ Millions of tourists visit Paris each year.

There are two main Natural Language Processing (NLP) tasks related to paraphrases, Paraphrase Identification and Paraphrase Generation. Paraphrase Identification consists of, given a pair of texts, deciding if they paraphrase each other. It has been used in plagiarism detection [3], text summarization [26], and Machine Translation (MT) evaluation [39]. Paraphrase Generation is the task in which, given an input text, a new text is generated, paraphrasing the first one. It has been shown to be useful for data augmentation [1], question answering [22], and dialogue systems [20].
In addition to those two, there exists another less explored task regarding paraphrases: Paraphrase Evaluation. It consists of, given a pair of texts, assigning a score representing how good they are as a paraphrase of each other. In its most basic form, this is equivalent to Paraphrase Identification, assigning 0 to non-paraphrases and 1 to paraphrases. However, Paraphrase Evaluation aims to generate a more informative score that correctly represents the quality of the paraphrasing between the two texts. Thus, it is particularly useful to evaluate Paraphrase Generation and Paraphrase Compilation algorithms. However, despite the variety of approaches to this task over the years, there is a lack of standardization across the literature, making it hard to achieve comparability. Furthermore, most of the used techniques omit aspects of paraphrasing, and, to our knowledge, none has been tested for multilingual evaluation.

In this chapter, we present an overview of some of the methods used to evaluate paraphrase generation. According to the core technique of each of these metrics, we group them in two categories: Precision and Recall Metrics and Cosine Similarity Metrics.

## 2.1 Precision and Recall

Precision and Recall are common metrics used to evaluate the performance of information retrieval systems [45]. They measure the relationship between Relevant Information and Retrieved Information. In this context, Precision deals with how relevant the Retrieved Information is, while Recall deals with how complete the Retrieved Information is. They are defined by Equation 2.1 and Equation 2.2, where $\{X\}$ denotes the set of unique elements in X and $|X|$ denotes the cardinality of X.

$$ \text{Precision} = \frac{|\{\text{Relevant Information}\} \cap \{\text{Retrieved Information}\}|}{|\{\text{Retrieved Information}\}|} \quad (2.1) $$

$$ \text{Recall} = \frac{|\{\text{Relevant Information}\} \cap \{\text{Retrieved Information}\}|}{|\{\text{Relevant Information}\}|} \quad (2.2) $$

If we see text generation systems as an information retrieval system that retrieves some text given a reference, we can apply these metrics to them. In this case, Relevant Information corresponds to the reference text and Retrieved Information to the generated text or hypothesis text. To obtain the Precision and Recall of these texts, we need to represent them in a way that allows us to perform mathematical operations on them. We will start by defining any text X as a sequence of n tokens such that $X = \langle x_1, x_2, ..., x_n \rangle$. Unlike in information retrieval, where the Relevant Information is a set of unique documents, the reference text is likely to contain multiple occurrences of the same tokens, and this information is important to evaluate the system's performance. Because of this, we will use the multiset [5] of each sequence instead of their set. We will denote the multiset of sequence X as $[X]$. Equation 2.3 shows an example of how this data structure keeps a count of how many times each element of a sequence occurs. Equation 2.4 shows an example of the cardinality of a multiset, which is the sum of the occurrences of all elements. Equation 2.5 shows an example of the intersection of two multisets, which is, for each element,
the minimum count between the intersecting multisets. Finally, Equation 2.6 shows an example of the union of two multisets, which is, for each element, the maximum count between the uniting multisets.

$$[\langle A, A, A, B, B, C \rangle] = \{\{A, B, C\}, \{(A,3), (B,2), (C,1)\}\} = A^3 B^2 C^1 \quad (2.3)$$

$$|A^3 B^2 C^1| = 3 + 2 + 1 = 6 \quad (2.4)$$

$$A^1 B^2 C^1 \cap A^1 B^3 = A^1 B^2 \quad (2.5)$$

$$A^1 B^2 C^1 \cup A^1 B^3 = A^1 B^3 C^1 \quad (2.6)$$

If we have a reference text $R = \langle r_1, r_2, ..., r_n \rangle$ and we have a hypothesis text $H = \langle h_1, h_2, ..., h_m \rangle$, their Precision is the count of tokens that co-occur in both texts divided by the count of tokens in the hypothesis, as shown in Equation 2.7, and their Recall is the count of tokens that co-occur in both texts divided by the count of tokens in the reference, as shown in Equation 2.8.

$$\text{Precision}_{\text{text}}(R, H) = \frac{|[R] \cap [H]|}{|[H]|} \quad (2.7)$$

$$\text{Recall}_{\text{text}}(R, H) = \frac{|[R] \cap [H]|}{|[R]|} \quad (2.8)$$

Another difference between traditional information retrieval systems and text generation systems is the relevance of the order. While Precision and Recall, as defined above, are entirely agnostic to the order of the elements, the order of tokens in text matters. Even though it is possible to rearrange the tokens of a text without altering its overall meaning, it is also possible to create completely nonsensical texts by rearranging the tokens of a valid text. While studying language modeling and trying to capture this idea of a usual order between the elements of a text, Shannon proposed using n-grams [41]. The n-grams of a sequence $X = \langle x_1, x_2, ..., x_n \rangle$ are all its contiguous subsequences of length $n$, as shown in Equation 2.9.

$$\text{NG}(X, n) = \langle x_{n+i} : i \le 1 + |X| - n \rangle \quad (2.9)$$

We can then define n-gram (ng) Precision and Recall as the Precision and Recall of the n-grams of sizes $n$ from the reference and hypothesis texts, as in Equation 2.10 and Equation 2.11.

$$\text{Precision}_{\text{ng}}(R, H, n) = \frac{|[\text{NG}(R, n)] \cap [\text{NG}(H, n)]|}{|[\text{NG}(H, n)]|} \quad (2.10)$$

$$\text{Recall}_{\text{ng}}(R, H, n) = \frac{|[\text{NG}(R, n)] \cap [\text{NG}(H, n)]|}{|[\text{NG}(R, n)]|} \quad (2.11)$$

Finally, while information retrieval has a unique assessment of Relevant Information, there are many ways of generating a valid text. It is possible to use a set of reference texts instead of just one to account for this variability. There are different ways to take the multiple references into account; for example, obtaining the union of the multisets of all references or selecting the reference that maximizes the outcome.
The rest of this section covers different metrics based on Precision and Recall used for Paraphrase Evaluation in the past.

### 2.1.1 BLEU

Bilingual Evaluation Understudy or BLEU [28], as it is most commonly referred to, is an algorithm for Machine Translation Evaluation proposed in 2002 by Papineni et al. It is a Precision-based metric that compares a hypothesis translation *H* with a set of reference translations *R*. The algorithm relies on two main elements: a modified n-gram Precision calculation and a brevity penalty.

As Papineni et al. indicate in their paper, simply applying the standard Precision metric to the n-grams of a text is not enough to evaluate a translation because of the over-generation problem of some text generation systems. To solve this, they proposed clipping the total count of n-grams on each hypothesis by its count on the reference. This calculation, which they call modified n-gram Precision, is equivalent to the Precision<sub>ng</sub> described in Equation 2.10. When there is a set of *p* references such that $R = \langle R_1, R_2, ..., R_p \rangle$ they are first joined into a single global reference that is then used to compute the n-gram precision, as shown in Equation 2.12. Using this method allows measuring how relevant the generated n-grams are while also penalizing translations longer than the references.

$$ \text{Precision}_{\text{bleu}}(R, H, n) = \frac{|\left[\bigcup_{RinR} \text{NG}(R, n)\right] \cap [\text{NG}(H, n)]|}{|[\text{NG}(H, n)]|} \quad (2.12) $$

To penalize translations that are too short, the authors propose a brevity penalty. This penalty is a factor that decreases exponentially faster the shorter the hypothesis gets. The penalty factor is described in Equation 2.13, where *c* is the average cardinality of the multisets generated by all the hypothesis of all sentences in the corpus and *r* is the average cardinality of the multisets generated by all the references of all the sentences in the corpus. Given this definition of *r*, the authors point out that BLEU is a corpus-level metric used to evaluate performance at the system-level. Although BLEU can be used at the sentence-level, this is equivalent to removing the brevity penalty which in turn is likely to reward outputs with missing information.

$$ \text{BP} = \begin{cases} 1 & \text{if } c > r \\ e^{1-r/c} & \text{if } c \le r \end{cases} \quad (2.13) $$

Finally, to obtain the BLEU score, the brevity penalty BP is multiplied by the geometric average of the modified n-gram Precisions with positive weights *W* = $\langle w_1, w_2, ..., w_n \rangle$ for n-grams of sizes from 1 to *N*, as shown in Equation 2.14. The original paper baseline used *N* = 4 and uniform weights $w_n = 1/N$

$$ \text{BLEU}(R, H, N, W) = \text{BP} \cdot \exp \left( \sum_{n=1}^{N} w_n \log \text{Precision}_{\text{mr-ng}}(R, H, n) \right) \quad (2.14) $$

Thanks to how easy it is to obtain the BLEU score, it quickly became a standard metric on Machine Translation research. However, papers would only report the score without giving any details about the parameters used to obtain it, like the maximum size of the n-grams (N), the weights of each group of n-grams (W), and the tokenization strategy used to turn text into a sequence of tokens. In 2018 Post
analyzed the impact of these changes, noting that the variance between configurations was even more significant than some of the gains reported across papers, and proposed SACREBLEU [33] as a possible solution. SACREBLEU is a library that standardizes the calculation of BLEU scores by using a fixed preprocessing pipeline, a standard tokenization procedure, and the default recommended parameters for BLEU. On top of that, it prints a small string with the configuration details that can be published along the results to make comparability very straightforward.

After BLEU became the standard for Machine Translation, thanks to the ease with which it could be obtained, it started to be used in other NLG tasks. Noticing this, in 2018, Reiter reviewed the correlation with human judges of BLEU across different tasks [38]. From his study, Reiter concluded that while BLEU performs well for diagnostic evaluation of Machine Translation systems, it performs considerably low in other tasks. Despite this, it is still a widely used metric among different NLG tasks, including Paraphrase Evaluation. In this case, BLEU is applied by using one of the two texts as a reference and the other as a hypothesis. While this captures some semantic information from the compared texts, a significant downside of this approach is that, ultimately, it only encourages surface similarity. Focusing only in this aspect of paraphrasing has the problem of giving the maximum possible score to identical sentences, which is not what we expect of good paraphrases.

## 2.1.2 Google-BLEU

As Papineni et al. indicated in the original BLEU paper and Reiter corroborated in his review of BLEU's validity, the metric is intended for system-level evaluation. It correlates well with humans at a corpus-level, but it has some undesirable properties at the sentence-level. Wu et al. proposed Google-BLEU [50] in 2016 as a solution to this problem. To calculate this metric, they first compute a combined n-gram Precision and Recall similar to Precision<sub>ng</sub> (Equation 2.10) and Recall<sub>ng</sub> (Equation 2.11), with the difference that all n-grams from sizes 1 to *n* are combined and counted together for the calculation. When there is a set of *p* references such that $R = \langle R_1, R_2, ..., R_p \rangle$ then the final value correspond to the precision and recall of the hypothesis and the reference that maximizes the output. Equation 2.15 and Equation 2.16 show the multi-reference combined n-gram (mr-cng) Precision and Recall.

$$ \text{Precision}_{\text{mr-cng}}(R, H, N) = \arg\max_{R} \frac{\sum_{n=1}^{N} |[\text{NG}(R, n)] \cap [\text{NG}(H, n)]|}{\sum_{n=1}^{N} |[\text{NG}(H, n)]|} \qquad (2.15) $$

$$ \text{Recall}_{\text{mr-cng}}(R, H, N) = \arg\max_{R} \frac{\sum_{n=1}^{N} |[\text{NG}(R, n)] \cap [\text{NG}(H, n)]|}{\sum_{n=1}^{N} |[\text{NG}(R, n)]|} \qquad (2.16) $$

Using these values the Google-BLEU is obtained by keeping the minimum of both of these metrics, as shown in Equation 2.17. Thus, by considering Precision
and Recall together, it accounts for both relevant results and complete results, and by keeping just the minimum of the two, they make sure not to give a high score to samples that under perform in any of them.

$$ \text{Google-BLEU}(\mathcal{R}, H, N) = \min \left( \text{Precision}_{\text{mr-cng}}(\mathcal{R}, H, N), \text{Recall}_{\text{mr-cng}}(\mathcal{R}, H, N) \right) \qquad (2.17) $$

This metric proved a high correlation with BLEU at the corpus-level while performing better at the sentence-level. In addition to that, when there is just one reference, the metric is symmetric, which means the result is the same regardless of which input is passed as the hypothesis and which is passed as the reference.

### 2.1.3 ROUGE

Recall-Oriented Understudy for Gisting Evaluation, better known as ROUGE [16], is a family of metrics for automatic evaluation of summaries first introduce in 2004 by Lin.

ROUGE-N is based on the n-gram Recall between a hypotheses summary and a set of reference summaries; as such, it corresponds with the n-gram Recall shown in Equation 2.11. Just like in Google-BLEU, when there is a set of p references such that $\mathcal{R} = \langle R_1, R_2, ..., R_p \rangle$ then the final value correspond to the recall of the hypothesis and the reference that maximizes the output.

ROUGE-L in turn is based on Longest Common Sub-sequence. Given two sequences of tokens $X = \langle x_1, x_2, ..., x_n \rangle$ and $Y = \langle y_1, y_2, ..., y_m \rangle$ we can define a common sub-sequence as a sequence $Z = \langle z_1, z_2, ..., z_p \rangle$ for which there are i, j, and k such that $z_i = x_{i+j} = y_{i+k}$ for every i. If the function LCS($X, Y$) returns the longest common sub-sequence of X and Y, for a hypotheses text H and a set of reference texts $\mathcal{R}$, we can compute the LCS Precision and Recall with Equation 2.18 and Equation 2.19.

$$ \text{Precision}_{\text{lcs}}(R, H) = \arg\max_{R} \left( \frac{|\text{LCS}(H, R)|}{|H|} \right) \qquad (2.18) $$

$$ \text{Recall}_{\text{lcs}}(R, H) = \arg\max_{R} \left( \frac{|\text{LCS}(H, R)|}{|R|} \right) \qquad (2.19) $$

Then, to compute ROUGE-L we obtain the $F_{\text{lcs}}$ score from this Precision and Recall, following Equation 2.20, where $\beta$ defines the relative importance of the precision over recall.

$$ \text{Rouge-L}(R, H) = \frac{(1 + \beta^2) \times \text{Recall}_{\text{lcs}}(R, H) \times \text{Precision}_{\text{lcs}}(R, H)}{\text{Recall}_{\text{lcs}}(R, H) + \beta^2 \times \text{Precision}_{\text{lcs}}(R, H)} \qquad (2.20) $$

As with BLEU, despite being intended for a different task, this metric is some times used for Paraphrase Evaluation by using one of the two texts to compare as the reference and the other as the hypothesis. Similarly, it shares the same drawbacks as BLEU; while it captures some semantic information, it only rewards surface similarity, assigning the best possible score to exact copies.

### 2.1.4 PARAMETRIC

PARAMETRIC [6] is, to our knowledge, the first set of automatic metrics proposed specifically for Paraphrase Evaluation. It was presented in 2008 by Callison-Burch,
Cohn, and Lapata and consisted in comparing the word alignments produced by an automatic paraphrasing technique and a gold standard set of manual word alignments.

First, phrase pairs are extracted from sentences in a test set using both sets of word alignments and the phrase pair extracting heuristic proposed by Och and Ney [27], denoted here as PP. The alignment accuracy is then calculated by obtaining their precision and Recall as shown in Equation 2.21 and Equation 2.22, where $e_1$ and $e_1$ correspond with a pair of sentences from the test set C, and M and S are the manual and system word alignments, respectively.

$$ \text{Precision}_{\text{align}}(C, M, S) = \frac{\sum_{<e_1, e_2> \in C} |\text{PP}(e_1, e_2, S) \cap \text{PP}(e_1, e_2, M)|}{\sum_{<e_1, e_2> \in C} |\text{PP}(e_1, e_2, S)|} \quad (2.21) $$

$$ \text{Recall}_{\text{align}}(C, M, S) = \frac{\sum_{<e_1, e_2> \in C} |\text{PP}(e_1, e_2, S) \cap \text{PP}(e_1, e_2, M)|}{\sum_{<e_1, e_2> \in C} |\text{PP}(e_1, e_2, M)|} \quad (2.22) $$

The authors note that most paraphrasing methods produce a list of paraphrases for a given input phrase instead of generating word alignments. Because of this, they also propose a variant of these scores that work to evaluate those systems. To do this, they compute the Precision and Recall between the set of paraphrases that a system produces for a given phrase *p* occurring in a sentence *s* and the paraphrase of the same sentence present in the manual annotations.

PARAMETRIC was the pioneer of the automatic Paraphrase Evaluation. It brought up the need for a metric to evaluate this task and presented a working solution. However, the requirement of a quality set of manual annotations makes it challenging to use in reality. Not to mention how much it complicates its use in less-resourced languages, given the difficulty of obtaining a phrase table with good language coverage.

### 2.1.5 PEM

Paraphrase Evaluation Metric, better known as PEM [18], was presented in 2010 by Liu, Dahlmeier, and Ng. This metric relies on three main features of paraphrasing: semantic similarity, fluency, and surface dissimilarity.

Semantic similarity refers to how much of the meaning of one text is present in the other. To measure it without relying on surface similarity, as BLEU and other metrics do, the authors propose to use a pivot language. First, generate word-level alignments from parallel text with sentence-level alignment. Then look how different words and phrases in the source language would align with the same phrase in the pivot language and use this distribution information to represent the semantic similarity between them.

Having obtained a semantic similarity measure for words and phrases, extend it to the sentence-level. First, the sentences must be segmented into phrases. The authors point out that the probability of any phrase *p* is given by the frequency of that phrase within the corpus, as shown in Equation 2.23, where $N(p, C)$ is the multiplicity of *p* in the multiset generated by the corpus C. They propose that the best segmentation of a text maximizes the probability of each of the phrases that
form it. Then, all single words are considered possible phrases, and $N(p, C)$ is set to 0.5 for words with a multiplicity of 0, allowing the handling of out of vocabulary words.

$$ Pr(p, C) = \frac{N(p, C)}{\sum_{p' \in \{C\}} N(p', C)} \qquad (2.23) $$

Knowing the probability of a single phrase, the probability of segmenting a sentence X into a sequence of phrases $\langle x_1, x_2, ..., x_n \rangle$ can be seen as the product of the probability of all the phrases times a normalizing constant ($Z(X)$), as shown in Equation 2.24.

$$ Pr(x_1, x_2, ..., x_n | X) = \frac{1}{Z(X)} \prod_{i=1}^{n} Pr(x_i, C) \qquad (2.24) $$

Once a sentence has been segmented, it is possible to obtain its semantic representation. To do that, the authors generate what they call the Bag of Pivot language N-Grams (BPNG). This BPNG is the set of n-grams of the pivot language sentence where every token corresponds to a phrase from the optimal segmentation instead of a word.

The F1 score between two texts R and H is computed following Equation 2.25, which uses the same multi-reference combined n-gram (mr-cng) Precision and Recall introduced in Equation 2.15 and Equation 2.16. To obtain a semantic similarity score, the authors propose computing the F1 agreement of $R_p$ and $H_p$ which are the sentences equivalent to R and H on the pivot language p.

$$ F_{1\text{PEM}}(\mathcal{R}, H) = \frac{2 \times \text{Precision}_{\text{mr-cng}}(\mathcal{R}, H, 4) \times \text{Recall}_{\text{mr-cng}}(\mathcal{R}, H, 4)}{\text{Precision}_{\text{mr-cng}}(\mathcal{R}, H, 4) + \text{Recall}_{\text{mr-cng}}(\mathcal{R}, H, 4)} \qquad (2.25) $$

To obtain a fluency score, the authors proposed the use of a normalized language model score $P_n$, as defined by Equation 2.26, where $Pr(S)$ is the probability of sentence S as given by a standard 4-gram language model.

$$ P_n = \frac{\log Pr(S)}{|S|} \qquad (2.26) $$

Finally, the authors obtain a measure of surface similarity from the F1 agreement of the Bag of N-Grams from the reference and hypothesis texts in their original language, following Equation 2.25. This value is the complement of the surface dissimilarity.

The authors realized that the relationship between these three scores and the quality of a paraphrase is not a linear combination. Because of that, simple approaches like taking their averages are not good enough; for example, two completely unrelated are likely to have a high surface dissimilarity which would increase the final average. They trained a Support Vector Machine (SVM) to solve this problem, taking the three scores as the input and using a human-assigned paraphrase quality score as the target.

PEM was, to our knowledge, the first Paraphrase Evaluation metric to address the need to consider both semantic similarity and surface dissimilarity separately. Furthermore, they pointed out that the relationship between these two components was not equivalent. On top of that, the authors made available an application to compute their metric, which encourages and facilitates comparability. Despite these
improvements, the public version of PEM was limited by the list of extracted para-phrases from their training corpus. While it is possible to train a custom PEM model for new domains or languages, it requires a large parallel corpus and a large set of paraphrases with human annotations for paraphrasing quality. On top of that, the results obtained with a new custom model will not be comparable with previously reported results, and these new models should be made public to allow future com-parability.

2.1.6 PINC

When collecting parallel data for Paraphrase Evaluation in 2011, Chen and Dolan [7] came across BLEU's limitations when dealing with surface dissimilarity. To overcome it, they use BLEU to compute semantic similarity and proposed Paraphrase In N-gram Changes (PINC) to measure the surface dissimilarity.

They describe PINC as the ratio of n-grams present in the hypothesis sentence but not in the source sentence. This score resembles the Jaccard distance or the complement of the n-gram Precision and is obtained with Equation 2.27.

$$ \text{PINC}(R, H, N) = \frac{1}{N} \sum_{n=1}^{N} 1 - \text{Precision}_{ng}(R, H, n) \qquad (2.27) $$

The authors propose to use PINC and BLEU separately instead of combining them and interpret them differently depending on the type of paraphrasing task. However, they do test some methods to combine them and find out that the best correlation with human judgment is obtained by getting the product of PINC and a sigmoid of BLEU, following the same intuition as Liu, Dahlmeier, and Ng about how the surface variation becomes relevant only when there is a high level of semantic similarity.

2.1.7 PARADIGM

In 2014, Weese, Ganitkevitch, and Callison-Burch proposed Paraphrase Diagnostics through Grammar Matching (PARADIGM [48]). They extended the ideas proposed in PARAMETRIC by extracting their gold standard paraphrases using grammar extraction techniques instead of phrase-based Machine Translation. They also use grammar extraction techniques to compare the results of the different paraphrasing systems.

As it happens with PARAMETRIC, this metric focuses on evaluating paraphrasing systems as a whole instead of isolated pairs of text. In this case, the paraphrasing systems are modeled as Synchronous Context-Free Grammars (SCFGs). The score of a system then is obtained based on two criteria:

* The proportion of sentential paraphrase pairs from a gold-standard set of true sentential paraphrases that can be synchronously parsed by following the grammar of the system.

* The number of gold-standard paraphrase rules present in the system.

As with PARAMETRIC, PARADIGM relies heavily on gold standard human annotations, including grammar annotations, which are hard to obtain. Furthermore, as we said, it performs evaluations at the system-level rather than the sentence level.
### 2.1.8 APEM

APEM [24] was presented in 2015 by Moon et al. as a way to evaluate Korean paraphrases using morphological analysis. APEM is a Precision-based metric that only considers what the author calls *meaningful* morphemes: morphemes with significant semantic content instead of morphemes denoting determiners, conjunctions, and other such words. For example, given $M_R$ the sequence of *meaningful* morphemes from a reference sentence $R$ and $M_H$ the sequence of *meaningful* morphemes from the hypothesis sentence $H$, APEM is obtained by computing the Precision (as per Equation 2.7) between $M_R$ and $M_H$ as shown in Equation 2.28.

$$ \text{APEM}(R, H) = \text{Precision}(M_R, M_H) \qquad (2.28) $$

Two other versions were presented: APEM_SD, where synonyms are considered to be the same element, and APEM_SDGD, where they use the number of Google search pages returned for each word to define a threshold for synonymity and normalize elements.

The basic APEM metric presents similar downsides as other Precision-based metrics already discussed in that it only rewards surface similarity between the paraphrases. The two proposed variations try to tackle this issue but they require a synonyms table or constantly querying Google, worst of all, these variations performed worse than the basic approach in the original paper.

## 2.2 Cosine Similarity

Instead of representing text as a sequence of tokens, we can represent it as a vector, which is a sequence of values which represent different characteristics of the text and encode information about it. It is then possible to compare two texts X and Y by computing the cosine similarity of the vectors that encode them $\vec{v}_X$ and $\vec{v}_Y$, as shown in Equation 2.29, where $||\vec{x}||$ is the magnitude of a vector.

$$ \text{Cosine Similarity}(\vec{v}_X, \vec{v}_Y) = \frac{\vec{v}_X \cdot \vec{v}_Y}{||\vec{v}_X|| \times ||\vec{v}_Y||} \qquad (2.29) $$

As it happens with Precision and Recall metrics, however, cosine similarity by itself would give a perfect score to exact copies since identical texts would be encoded by identical vectors.

The rest of this section covers some metrics based on cosine similarity used for Paraphrase Evaluation.

### 2.2.1 PPDB Score

When putting together the Paraphrase DataBase in 2013, Ganitkevitch, Van Durme, and Callison-Burch [12] proposed a way to score the quality of the paraphrases that they collected. They called this method the PPDB Score.

The authors first encoded each text with a numerical embedding in order to obtain this score. To do this, they computed embeddings for the 200 million most frequent phrases in the Google n-gram corpus[17]. These embeddings consist of n-gram-based context signatures, like features for words seen to the left and right of a phrase, as well as other richer linguistic signatures for 175 million phrases in the
Annotated Gigaword corpus [25]. Once the texts had been given a numerical embedding, the cosine similarity of their embeddings was used as a paraphrase quality score.

While PPDB provides a significant amount of data for phrasal paraphrasing, it does not cover sentential paraphrases. Additionally, the code to extract the features is not readily available, which makes comparability difficult.

### 2.2.2 PARAGRAMPHRASE

PARAGRAMPHRASE[49] was introduced by Wieting et al. in 2016 as a word embedding technique focused on paraphrasing. The authors proposed obtaining sentence embeddings by averaging the word embeddings of all the words in a sentence and then using their cosine similarity to measure the strength of the paraphrase relationship between them.

### 2.2.3 Automatic Evaluation of Arabic Paraphrases

In 2018 Al-Raisi, Bourai, and Lin proposed a technique to evaluate Arabic Paraphrases [34]. As in PEM and PINC, Al-Raisi, Bourai, and Lin pointed out the relevance of measuring both semantic similarity and surface dissimilarity.

The authors first generated sentence embeddings in order to obtain the semantic similarity of two texts. They did this by averaging the word embeddings from a sentence, following Wieting et al. work. Then the cosine similarity of these sentence embeddings is used as a measure of semantic similarity.

To measure the surface dissimilarity, each sentence is mapped into a common vocabulary space, and then the hamming distance between sentence vectors in that space is computed.

Finally, to obtain the paraphrasing score, both measurements are combined by obtaining their harmonic mean, as shown in Equation 2.30.

$$ score = 2 \frac{\text{Semantic Similarity} \cdot \text{Surface Dissimilarity}}{\text{Semantic Similarity} + \text{Surface Dissimilarity}} \qquad (2.30) $$

As Liu, Dahlmeier, and Ng pointed out when proposing PEM, the relationship between these two paraphrasing features is not equivalent since high surface dissimilarity is meaningless with low semantic similarity. Using the harmonic mean improves over more straightforward approaches like the arithmetic mean; however, it still presents both elements as equally important.

### 2.2.4 WEEM4PG

Hailu, Yu, Fantaye, et al. proposed a Word Embedding based Evaluation Metric for Paraphrase Generation (WEEM4PG) [13] in 2020. The authors also understand the importance of measuring both semantic similarity and surface dissimilarity.

In their case, the semantic similarity is obtained by getting the arithmetic mean of the cosine similarity between word embeddings. Given two sentences X and Y represented by the set of their word embeddings $V_X = \{\vec{v}_{X_1}, \vec{v}_{X_2}, \dots, \vec{v}_{X_n}\}$ and $V_Y = \{\vec{v}_{Y_1}, \vec{v}_{Y_2}, \dots, \vec{v}_{Y_m}\}$ the semantic similarity of X and Y is given by Equation 2.31.

$$ \text{WEEM4PG}_{\text{sem-sim}}(V_X, V_Y) = \frac{\sum_{i=1}^{n} \arg \max_{j} (\text{Cosine Similarity}(\vec{v}_{X_i}, \vec{v}_{Y_j}))}{|V_X|} \qquad (2.31) $$
To account for surface dissimilarity, the authors propose Equation 2.32, which decreases as the number of overlapping words between texts increases.

$$WEEM4PG_{\text{sur-dis}} = \frac{\sqrt{|[X] \cap [Y]|}}{|[X] \cap [Y]|} \qquad (2.32)$$

Both measurements are then combined in a final score by obtaining their product as per Equation 2.33.

$$WEEM4PG = WEEM4PG_{\text{sem-sim}} \times WEEM4PG_{\text{sur-dis}} \qquad (2.33)$$

The more overlapping words there are, the smaller the surface similarity score becomes, reducing the overall score. However, since the surface dissimilarity measurement does not consider the length of the sentences, it can penalize long sentences very harshly, even when they are significantly different. For example, in a long sentence with 0.9 semantic similarity and just four overlapping words, the WWEM4PG already drops to 0.45; because of that, it works well for word or phrasal paraphrasing but does not scale well into sentential paraphrasing.
# Chapter 3

## PAREVAL

After an in-depth look into the existing techniques for Paraphrase Evaluation, we encountered various shortcomings among them. Some, like PARAMETRIC and PARADIGM, were thought to evaluate Paraphrase Generation systems as a whole instead of single paraphrases. Some others, like PPDB Score and WEEM4PG, were good for word and phrasal paraphrasing but not for sentential paraphrasing. Most of them (excluding PEM, PINC, WEEM4PG, and the Arabic paraphrases evaluation metric) focused exclusively on measuring semantic similarity while ignoring surface dissimilarity, which translated into giving the highest scores to exact copies of the input text. Of those that took surface dissimilarity into account, the Arabic paraphrases evaluation metric did not consider that both elements are not equivalent factors of a good paraphrase. Finally, PARAMETRIC, PARADIGM, PPDB Score, and the Arabic paraphrases evaluation metric were difficult to replicate or not replicable at all due to a lack of publicly available code or, at the very least, enough implementation details, making it practically impossible to use them as sources of comparability between works.

From all the reviewed metrics, only PEM took into account both semantic similarity and surface similarity, and the intricacies of their relationship with the paraphrase quality. Software to use the same model from the article to obtain a PEM score for paraphrases is also publicly available. Despite that, PEM was limited by the technology of its time. The semantic similarity measure obtained relies on a limited phrase table extracted during the training, and the final SVM is only as good as the training dataset available then. Finally, as pointed out in Subsection 2.1.5, training a custom model that fits new requirements is demanding and affects future comparability.

On top of these concerns, we realized that current methods are tested on English text almost exclusively, with studies in different languages having to come up with their own evaluation techniques as APEM and the Arabic paraphrase evaluation metric did. With all those considerations in mind, we propose PAREVAL, a multilingual metric for Paraphrase Evaluation that attempts to improve existing standards.

### 3.1 Theoretical Proposal

Before diving into the technicalities of our implementation, we want to cover the theoretical reasoning behind it. Following PEM and other metrics, we want our proposal to consider both the semantic similarity and the surface dissimilarity. As discussed at the beginning of Chapter 2, keeping the original meaning as intact as
possible is fundamental to paraphrasing. From that we propose that the quality of a paraphrase should not be higher than the semantic similarity of the texts. We suggest our metric as a penalized semantic similarity, as shown in Equation 3.1.

$$ \text{PAREVAL} = \text{Semantic Similarity} - \text{Surface Similarity Penalty} \quad (3.1) $$

As has been covered in the previous chapter, the surface similarity is irrelevant if there is no semantic similarity. We address this paraphrasing characteristic by using a surface similarity penalty that consists of a surface similarity metric scaled by the semantic similarity. The higher the semantic similarity, the more relevant the penalty becomes. We also realized that the impact of surface similarity on paraphrasing quality is exponential; the more similar two texts are, the more this affects their paraphrasing quality. Finally, while texts with high surface similarity may be paraphrases, texts with low semantic similarity are not. Based on that, we propose that the penalty cannot completely overthrow the semantic similarity score. Equation 3.2 presents a surface similarity penalty that covers all those considerations.

$$ \text{Surface Similarity Penalty} = \frac{\text{Surface Similarity}^2 \times \text{Semantic Similarity}}{2} \quad (3.2) $$

Figure 3.1 depicts the behavior of X-ParEval across the possible values of semantic similarity and surface similarity. As proposed, the score is never greater than the semantic similarity; very dissimilar texts are not as penalized while very similar texts are.

## 3.2 Practical Implementation

Having laid the theoretical foundation of our metric, we can then discuss the practical details of our proposal. This section covers our selection of the semantic similarity and surface similarity measures that are ultimately used to compute the X-ParEval score.

### 3.2.1 Semantic Similarity

With the advent of neural networks for Natural Language Processing, notably the Transformer Architecture [47], and the subsequent boom of large pre-trained language models, using embeddings to encode textual information has become state of the art. Because of this, the semantic similarity component of our proposal will be based on the cosine similarity of text embeddings, following Equation 2.29.

These new technologies allow us to leave behind simple distributional properties of text and extract more abstract representations that capture a closer sense of meaning. Moreover, there are now many robust architectures to generate sentence embeddings, which take into account the sentence structure and not just its words. For example, using siamese BERT [8] models to generate sentence embedding and adjusting them to minimize error in cosine similarity or equivalence classification, Sentence-BERT [37] obtains high-quality sentence embeddings; because of the nature of its training, these embeddings are particularly good to obtain semantic similarity measures for our metric.

We decided to use python's sentence-transformers library since it provides an accessible and easy-to-use framework to generate sentence embeddings, providing a diversity of models to use for the task.
<figure><img src="image_12.png" /><figcaption>FIGURE 3.1: X-ParEval score for different values of semantic similarity and surface similarity.</figcaption></figure>
### 3.2.2 Surface Similarity

As we pointed out during our survey of Precision and Recall metrics in Section 2.1, most of them rewarded semantic similarity and surface similarity at the same time. Based on that, we decided to use them to measure surface similarity in our metric. Since we are only concerned by the surface realization of the text, Precision and Recall techniques that only use the multiset of tokens in the text seem to be the more suitable. Among them, Google-BLEU is the one with the best balance between the relevance of the tokens and their completeness. Furthermore, Google-BLEU was designed to work both at the system and the sentence-level, and its symmetric behavior allows our metric to be symmetric. To omit irrelevant surface differences, before applying Google-BLEU, we remove non-alphanumeric characters, apply Unicode normalization, and lowercase the text, like Scherrer did when collecting paraphrases for TaPaCo [40].

### 3.2.3 Multilinguality

Since the start, we envisioned our metric as a multilingual tool that would allow the study of paraphrasing to be carried out and compared in different languages without requiring the implementation of new models or versions. We believe our proposed equation to be simple enough to be applied across different languages, understanding that the performance might vary depending on the morphosyntactic properties of each language. Thus, to have a multilingual implementation, we need a multilingual way to compute the two elements of our equation.

Among the currently used metrics, when the semantic similarity is not obtained through Precision and Recall measurements of the text (which, as we have pointed out, leads to high scores on exact copies), there is a heavy language dependency on the models. PEM, PPDB Score, ParagramPhrase, the Automatic Evaluation of Arabic Paraphrases, and WEEM4PG all relied on language-specific sources to identify the semantic similarity. However, sentence embedding technology has advanced much during the last years. Reimers and Gurevych showed that, by minimizing the mean square error between the embeddings generated by a monolingual teacher model and the embeddings of a multilingual student model for the same sentence in different languages, it was possible to align sentence embeddings [36]. Using this method allows for uniform sentence embeddings that can be used to extract semantic similarity of texts in more than one language. In their paper, the best performing model was paraphrase-xlm-r, an XLM-R [15] multilingual student model trained with a Sentence-BERT teacher fine-tuned on paraphrasing data. This model is one of the few multilingual semantic similarity models available on the sentence-transformers library, which is why we decided to use it to generate our sentence embeddings.

Our surface similarity approach using Google-BLEU means that it is a Precision and Recall metric, making it language-agnostic for the most part. However, the tokenization process may affect its performance depending on the language, thus impacting its capacity to generalize. By using the Sentencepiece Tokenizer [15], which is a language-independent subword tokenizer, it is possible to tokenize each text appropriately regardless of its language, making the Google-BLEU calculation more reliable.
3.2.4 Code

To ensure replicability and comparability, an X-ParEval Python library was made. We followed the steps of Post, generating the resulting scores and providing a de-scriptive string about the configuration. The code will be made publicly available in the future, and it will be possible to install the library with the pip utility. Once installed, it will be possible to use it both as a console application and inside a script by importing the library.
<figure><img src="image_13.png" /></figure>
# Chapter 4

## Experiments

To put our metric to the test, we propose a Pearson's correlation study of the metric with human annotations in two different settings. First, we compared X-ParEval with some of the previous metrics, specifically, those for which the implementation is publicly available or, at the very least, for which re-implementing the metric in a meaningful way was possible. Then we used X-ParEval in a variety of datasets from different sources and languages and evaluated the significance and strength of its correlation. Finally, we tested the results by using them to compare different paraphrase generation baselines.

### 4.1 Datasets

Before performing the experiments, we collected as many paraphrase datasets with human annotations for the paraphrase quality as possible. This section contains a very brief description of each of the collected corpus.

#### 4.1.1 ULPC

The User-Language Paraphrase Corpus (ULPC) [21] consists of 1,998 English pairs of sentential paraphrases generated by American high school students. These pairs were then annotated by three undergraduate students working in a cognitive science laboratory after completing training for the task. The annotators added a score for ten different features of paraphrasing on a scale from 1 to 6. Relevant to our case, among those features are Semantic Completeness, Lexical Similarity, and Paraphrase Quality.

#### 4.1.2 MSRP

The Microsoft Research Paraphrase Corpus (MSRP) [9] has 5,801 pairs of English sentential paraphrases annotated by two evaluators as either paraphrases or not paraphrases, with a third annotator to break the disagreements. The annotators were given a guide to annotate the text but were allowed some freedom in the process. The paraphrase pairs were collected over 18 months from thousands of news sources on the web.

#### 4.1.3 Human Labeled PPDB 2.0

Along with PPDB 2.0 [30], Pavlick et al. released 26,455 pairs of English phrasal paraphrases that were evaluated by 5 different annotators on a scale from 1 to 5. The phrasal paraphrases were extracted from PPDB 1.0.
4.1.4 Europarl AMR to Text

Fan and Gardent [10] presented a model to generate text from Abstract Meaning Representations (AMRs) using Europarl [14]. To evaluate the quality of their results, they conducted a small human evaluation. The resulting dataset consists of 50 pairs of sentences in 17 languages (Bulgarian, Czech, Danish, Dutch, Estonian, Finnish, French, German, Greek, Hungarian, Italian, Latvian, Polish, Portuguese, Romanian, Spanish, Swedish) with a corresponding paraphrase. Each language was evaluated by 1 to 10 annotators, which assessed different features of the pairs on a scale of 1 to 3. Particularly useful for us are the annotations for semantic accuracy, which can be compared with our semantic similarity, and the paraphrasing score, which is the inverse of our surface similarity. Finally, they proposed a binary classification of the pairs as good paraphrases if they had 2 or 3 in both of the mentioned features or bad paraphrases otherwise, which can be compared with our final X-ParEval score.

4.1.5 ParaPhraser

The ParaPhraser Corpus [32] has 7,227 pairs of Russian sentences annotated as hav-
ing the same meaning, similar meaning, or different meaning by at least three anno-
tators. The sentences were extracted from news wires of Russian media.

4.1.6 ArPC

The Arabic Paraphrase Corpus (ArPC) [23] contains 1,331 Arabic sentence pairs an-
notated by three human evaluators as either paraphrase or not paraphrase. All the
evaluators were native Arabic speakers.

4.1.7 TMUP

The Tokyo Metropolitan University Paraphrase Corpus (TMUP) [42] contains 655 Japanese sentence pairs annotated by two human evaluators as either paraphrase or not paraphrase. The sentences were extracted from Wikipedia, and the paraphrases were generated using back-translation.

4.2 Comparing Metrics

To compare different metrics, we first had to select one of the different corpora we
collected to compare. We decided to use ULPC since we consider it to be the best
available dataset to assess Paraphrase Evaluation. This is because humans gener-
ated both the paraphrases and the annotations, trained people performed the anno-
tations, they covered different aspects of paraphrasing, and the evaluation is more
fine-grained than in the others.

When there was a publicly available version of the metrics, they were used; how-
ever, in their absence we tried to implement them ourselves. Appendix A details
how each of this metrics was calculated on our experiment.

**Table 4.1** shows the results of the different correlation measurements. We com-
pared the results of each metric against the three meaningful features of ULPC: se-
mantic completeness (semantic similarity), lexical similarity (surface similarity), and
<table><caption>TABLE 4.1: Pearson's correlation and p-value between different metrics and different types of human evaluations on ULPC. The cases that achieved the highest correlation on a specific measurement are in bold. The metrics marked with an asterisk (*) were re-implemented by us, more implementation details are available on Appendix A.</caption><thead><tr><th rowspan="2">Metric</th><th colspan="2">Semantic Similarity</th><th colspan="2">Surface Similarity</th><th colspan="2">Paraphrase Quality</th></tr><tr><th>Corr.</th><th>P</th><th>Corr.</th><th>P</th><th>Corr.</th><th>P</th></tr></thead><tbody><tr><td>BLEU</td><td>0.386</td><td>0.000</td><td>0.597</td><td>0.000</td><td>0.062</td><td>0.013</td></tr><tr><td>Google-BLEU</td><td>0.456</td><td>0.000</td><td>0.715</td><td>0.000</td><td>0.152</td><td>0.000</td></tr><tr><td>ROUGE-1</td><td>0.530</td><td>0.000</td><td>0.807</td><td>0.000</td><td>0.286</td><td>0.180</td></tr><tr><td>ROUGE-L</td><td>0.498</td><td>0.000</td><td>0.741</td><td>0.000</td><td>0.200</td><td>0.000</td></tr><tr><td>PEM</td><td>0.472</td><td>0.000</td><td>0.684</td><td>0.000</td><td>0.308</td><td>0.000</td></tr><tr><td>1 - PINC*</td><td>0.456</td><td>0.000</td><td>0.712</td><td>0.000</td><td>0.150</td><td>0.000</td></tr><tr><td>APEM*</td><td>0.530</td><td>0.000</td><td><strong>0.811</strong></td><td><strong>0.000</strong></td><td>0.343</td><td>0.000</td></tr><tr><td>Cosine Similarity*</td><td><strong>0.626</strong></td><td><strong>0.000</strong></td><td>0.787</td><td>0.000</td><td>0.486</td><td>0.000</td></tr><tr><td>Harmonic Mean*</td><td>0.427</td><td>0.000</td><td>0.668</td><td>0.000</td><td>0.140</td><td>0.000</td></tr><tr><td>WEEM4PG*</td><td>-0.071</td><td>0.002</td><td>-0.037</td><td>0.098</td><td>-0.005</td><td>0.819</td></tr><tr><td>X-ParEval*</td><td>0.577</td><td>0.000</td><td>0.688</td><td>0.000</td><td><strong>0.540</strong></td><td><strong>0.000</strong></td></tr></tbody></table>

paraphrase quality. Cosine Similarity gets the highest correlation with semantic similarity, and PINC's complement gets the highest correlation with surface similarity. Most importantly, X-ParEval outperforms all the other metrics on paraphrase quality.

We also computed all these metrics for the set of test sentences from Sentence List 1, first introduced at the beginning of Chapter 2, and replicated here.

(1) a. Every year millions of tourists go to New York City.

b. ✓ Each year millions of tourists visit New York City.

c. ✓ Millions of tourists visit NYC each year.

d. ✗ Every week millions of tourists go to New York City.

e. ✗ Every year millions of tourists go to Paris.

f. ✗ Each year millions of tourists visit Paris.

g. ✗ Millions of tourists visit Paris each year.

<table><caption>TABLE 4.2: Metric comparison on test sentences from Sentence List 1.</caption><thead><tr><th rowspan="2">Metric</th><th colspan="2">✓ Paraphrases</th><th colspan="4">✗ Non-Paraphrases</th></tr><tr><th>1b</th><th>1c</th><th>1d</th><th>1e</th><th>1f</th><th>1g</th></tr></thead><tbody><tr><td>BLEU</td><td>0.380</td><td>0.168</td><td>0.783</td><td>0.639</td><td>0.263</td><td>0.168</td></tr><tr><td>Google-BLEU</td><td>0.577</td><td>0.262</td><td>0.833</td><td>0.619</td><td>0.333</td><td>0.262</td></tr><tr><td>ROUGE-1</td><td>0.737</td><td>0.471</td><td>0.900</td><td>0.778</td><td>0.471</td><td>0.471</td></tr><tr><td>ROUGE-L</td><td>0.737</td><td>0.352</td><td>0.900</td><td>0.778</td><td>0.471</td><td>0.353</td></tr><tr><td>PEM</td><td>0.683</td><td>0.762</td><td>0.653</td><td>0.631</td><td>0.653</td><td>0.613</td></tr><tr><td>PINC*</td><td>0.176</td><td>0.473</td><td>0.104</td><td>0.272</td><td>0.427</td><td>0.511</td></tr><tr><td>APEM*</td><td>0.909</td><td>0.540</td><td>0.909</td><td>0.648</td><td>0.540</td><td>0.644</td></tr><tr><td>Cosine Similarity*</td><td>0.971</td><td>0.901</td><td>0.979</td><td>0.735</td><td>0.716</td><td>0.715</td></tr><tr><td>Harmonic Mean*</td><td>0.71</td><td>0.406</td><td>0.900</td><td>0.672</td><td>0.455</td><td>0.383</td></tr><tr><td>WEEM4PG*</td><td>0.32</td><td>0.376</td><td>0.319</td><td>0.342</td><td>0.360</td><td>0.360</td></tr><tr><td>X-ParEval*</td><td>0.812</td><td>0.870</td><td>0.639</td><td>0.594</td><td>0.676</td><td>0.690</td></tr></tbody></table>

Table 4.2 shows the results of this measurements. As expected BLEU, Google-BLEU, ROUGE-1, ROUGE-L, APEM, the Cosine Similarity, and the Harmonic mean,
all gave a higher score to the paraphrase most similar to the source sentence. Even more troubling BLEU, Google-BLEU, ROUGE-1, ROUGE-L, PINC, APEM, Cosine Similarity, and WEEM4PG gave an equal or higher score to at least one of the non-paraphrases over at least one of the true paraphrases. From all the tested metrics, only PEM and X-ParEval gave the highest score to the most different true paraphrases and gave a higher score to both paraphrases over the non-paraphrases. It is important to note, however, that the PEM scores are closer to one another between paraphrases and non-paraphrases than the X-ParEval scores.

As a side note, the results for *Sentence 1d* on Cosine Similarity, where it obtains a high score despite having a different meaning than the source sentence, shows a limitation of this technology. Since X-ParEval relies on this metric to measure Semantic Similarity, this limitation extends to our proposed metric.

## 4.3 Assessing X-ParEval

Once we verified that our metric was at least as good or better than other previous metrics, we moved on to evaluate our metric's overall performance in different settings. Using both phrasal and sentential datasets, graded in different scales, and covering a variety of languages, we present a comprehensive overview of the capabilities of our metric.

When there were human annotations for semantic similarity and surface similarity, we calculated their correlation with the equivalent components from Equation 3.1 and Equation 3.2.

Table 4.3 shows the results of this correlation analysis. Excluding the Czech and Polish subsets from the AMR to Text dataset, all other datasets showed some correlation with very high confidence. All datasets with more than a thousand samples present at least a medium correlation. ULPC, ParaPhraser, and ArPC perform the best, getting over 0.50 correlation. The smaller datasets present more variability and, in some cases, a very weak correlation. There is a noticeable correlation both in sentential and phrasal datasets.

## 4.4 Paraphrase Generation

Finally, we generated paraphrases with five basic approaches based on three different models. The generated results were then used to compare how X-ParEval worked with real Paraphrase Generation examples. In this section, we give a very brief description of each model and present the results obtained.

### 4.4.1 AMR to Text Generation

AMR to Text Generation consists of taking an AMR graph and producing a text from it. The model described by Fan and Gardent [10], which is publicly available<fnref n="1" /> achieved high performance on the AMR to Text task for more than 20 languages. It is a sequence to sequence model with a transformer encoder and decoder. In the paper, the authors obtain the AMR graph of an English sentence and then produced its text realization in a different language.

<footnote n="1">¹https://github.com/facebookresearch/m-amr2text</footnote>
<table><caption>TABLE 4.3: Pearson's correlation and p-value between X-ParEval, its semantic similarity component (cosine similarity), and its surface similarity component (Google-BLEU) with equivalent human evaluations on different paraphrase data sets. In bold the cases where X-ParEval has at least a 0.25 correlation with Paraphrase Quality with 95% confidence.</caption><thead><tr><th rowspan="2">Source</th><th rowspan="2">Language</th><th colspan="2">Semantic Similarity</th><th colspan="2">Surface Similarity</th><th colspan="2">Paraphrase Quality</th></tr><tr><th>Corr.</th><th>P</th><th>Corr.</th><th>P</th><th>Corr.</th><th>P</th></tr></thead><tbody><tr><td>ULPC</td><td>English</td><td>0.626</td><td>0.000</td><td>0.715</td><td>0.000</td><td><strong>0.540</strong></td><td><strong>0.000</strong></td></tr><tr><td>MSRP</td><td>English</td><td>—</td><td>—</td><td>—</td><td>—</td><td><strong>0.328</strong></td><td><strong>0.000</strong></td></tr><tr><td>PPDB 2.0</td><td>English</td><td>—</td><td>—</td><td>—</td><td>—</td><td><strong>0.436</strong></td><td><strong>0.000</strong></td></tr><tr><td rowspan="20">AMR to Text</td><td>Bulgarian</td><td>0.498</td><td>0.000</td><td>0.344</td><td>0.007</td><td><strong>0.308</strong></td><td><strong>0.000</strong></td></tr><tr><td>Czech</td><td>0.416</td><td>0.000</td><td>0.367</td><td>0.000</td><td>-0.015</td><td>0.857</td></tr><tr><td>Danish</td><td>0.523</td><td>0.000</td><td>0.359</td><td>0.000</td><td><strong>0.252</strong></td><td><strong>0.011</strong></td></tr><tr><td>Dutch</td><td>0.552</td><td>0.000</td><td>0.492</td><td>0.000</td><td><strong>0.355</strong></td><td><strong>0.000</strong></td></tr><tr><td>Estonian</td><td>0.675</td><td>0.000</td><td>0.783</td><td>0.000</td><td><strong>0.661</strong></td><td><strong>0.000</strong></td></tr><tr><td>Finnish</td><td>0.478</td><td>0.000</td><td>0.736</td><td>0.000</td><td><strong>0.315</strong></td><td><strong>0.000</strong></td></tr><tr><td>French</td><td>0.544</td><td>0.000</td><td>0.517</td><td>0.000</td><td><strong>0.404</strong></td><td><strong>0.002</strong></td></tr><tr><td>German</td><td>0.570</td><td>0.000</td><td>0.496</td><td>0.000</td><td><strong>0.334</strong></td><td><strong>0.000</strong></td></tr><tr><td>Greek</td><td>0.555</td><td>0.000</td><td>0.551</td><td>0.000</td><td><strong>0.312</strong></td><td><strong>0.000</strong></td></tr><tr><td>Hungarian</td><td>0.328</td><td>0.000</td><td>0.245</td><td>0.000</td><td>0.156</td><td>0.014</td></tr><tr><td>Italian</td><td>0.601</td><td>0.000</td><td>0.463</td><td>0.000</td><td><strong>0.299</strong></td><td><strong>0.000</strong></td></tr><tr><td>Latvian</td><td>0.385</td><td>0.000</td><td>0.404</td><td>0.000</td><td><strong>0.253</strong></td><td><strong>0.001</strong></td></tr><tr><td>Polish</td><td>0.326</td><td>0.001</td><td>0.526</td><td>0.000</td><td>-0.044</td><td>0.660</td></tr><tr><td>Portuguese</td><td>0.493</td><td>0.000</td><td>0.599</td><td>0.000</td><td><strong>0.297</strong></td><td><strong>0.000</strong></td></tr><tr><td>Romanian</td><td>0.539</td><td>0.000</td><td>0.580</td><td>0.000</td><td><strong>0.375</strong></td><td><strong>0.000</strong></td></tr><tr><td>Spanish</td><td>0.571</td><td>0.000</td><td>0.525</td><td>0.000</td><td><strong>0.265</strong></td><td><strong>0.000</strong></td></tr><tr><td>Swedish</td><td>0.486</td><td>0.000</td><td>0.480</td><td>0.000</td><td><strong>0.397</strong></td><td><strong>0.000</strong></td></tr><tr><td>ParaPhraser</td><td>Russian</td><td>—</td><td>—</td><td>—</td><td>—</td><td><strong>0.543</strong></td><td><strong>0.000</strong></td></tr><tr><td>ArPC</td><td>Arabic</td><td>—</td><td>—</td><td>—</td><td>—</td><td><strong>0.559</strong></td><td><strong>0.000</strong></td></tr><tr><td>TMUP</td><td>Japanese</td><td>—</td><td>—</td><td>—</td><td>—</td><td>0.179</td><td>0.000</td></tr></tbody></table>

Since the English sentences are aligned with translations in other languages, this can be seen as a special case of Back Translation where a sentence goes from its original language to English, then to AMR, and then back to its original language as a paraphrase.

### 4.4.2 Many to Many Multilingual Translation

The Many-to-Many Multilingual Translation model described by Fan et al. [11], better known as M2M-100, can translate directly between any pair of 100 languages.

Its multilingual nature allowed us to generate paraphrases with it in 2 different ways: 1) Back-Translation, which consists of translating a sentence from a source language S to a pivot language P and then back to S, and 2) Direct Paraphrasing, where we tell the model to translate a sentence from a source language S into S again.

### 4.4.3 MBart-50

Presented by Tang et al., MBart-50 [43] is a machine translation model that builds on top of MBart [19], a sequence to sequence auto-encoder, pre-trained on a large scale
monolingual corpora in many languages using the BART architecture. In addition, MBart-50 was fine-tuned on 50 languages simultaneously, which allows it to perform multilingual translation.

As with M2M-100, it is possible to generate paraphrases with MBart-50 by doing
Back-Translation and by doing Direct Paraphrasing.
4.4.4 Results

<table><caption>TABLE 4.4: X-ParEval on the Europarl Test dataset</caption><thead><tr><th rowspan="2">Language</th><th rowspan="2">AMR to Text</th><th colspan="2">M2M-100</th><th colspan="2">MBart-50</th></tr><tr><th>Direct</th><th>Back Translation</th><th>Direct</th><th>Back Translation</th></tr></thead><tbody><tr><td>Bulgarian</td><td>0.798</td><td>0.741</td><td><strong>0.812</strong></td><td>—</td><td>—</td></tr><tr><td>Czech</td><td>0.809</td><td>0.686</td><td><strong>0.820</strong></td><td>0.738</td><td>0.805</td></tr><tr><td>Danish</td><td>0.819</td><td>0.676</td><td><strong>0.822</strong></td><td>—</td><td>—</td></tr><tr><td>Dutch</td><td>0.805</td><td>0.761</td><td>0.829</td><td>0.855</td><td><strong>0.861</strong></td></tr><tr><td>Estonian</td><td>0.817</td><td>0.800</td><td><strong>0.846</strong></td><td>0.761</td><td>0.803</td></tr><tr><td>Finish</td><td>0.826</td><td>0.804</td><td><strong>0.856</strong></td><td>0.793</td><td>0.836</td></tr><tr><td>French</td><td>0.830</td><td>0.748</td><td>0.826</td><td>0.766</td><td><strong>0.834</strong></td></tr><tr><td>German</td><td>0.826</td><td>0.755</td><td><strong>0.844</strong></td><td>0.733</td><td>0.831</td></tr><tr><td>Greek</td><td>0.804</td><td>0.794</td><td><strong>0.830</strong></td><td>—</td><td>—</td></tr><tr><td>Hungarian</td><td>0.820</td><td>0.800</td><td><strong>0.840</strong></td><td>—</td><td>—</td></tr><tr><td>Italian</td><td>0.830</td><td>0.762</td><td>0.840</td><td>0.836</td><td><strong>0.873</strong></td></tr><tr><td>Latvian</td><td>0.807</td><td>0.754</td><td><strong>0.824</strong></td><td>0.735</td><td>0.767</td></tr><tr><td>Lithuanian</td><td>0.816</td><td>0.788</td><td><strong>0.840</strong></td><td>0.753</td><td>0.804</td></tr><tr><td>Polish</td><td>0.817</td><td>0.800</td><td><strong>0.849</strong></td><td>0.748</td><td>0.823</td></tr><tr><td>Portuguese</td><td>0.822</td><td>0.709</td><td>0.831</td><td>0.824</td><td><strong>0.863</strong></td></tr><tr><td>Romanian</td><td><strong>0.820</strong></td><td>0.723</td><td>0.782</td><td>0.731</td><td>0.777</td></tr><tr><td>Slovak</td><td>0.804</td><td>0.663</td><td><strong>0.810</strong></td><td>—</td><td>—</td></tr><tr><td>Slovenian</td><td>0.809</td><td>0.755</td><td>0.817</td><td>0.805</td><td><strong>0.844</strong></td></tr><tr><td>Spanish</td><td><strong>0.821</strong></td><td>0.574</td><td>0.798</td><td>0.500</td><td>0.783</td></tr><tr><td>Swedish</td><td>0.825</td><td>0.726</td><td>0.822</td><td>0.834</td><td><strong>0.848</strong></td></tr></tbody></table>

Table 4.4 shows the average X-ParEval score from each approach on the different languages from the Europarl dataset [14] that is available together with the AMR to Text model. Overall, the approaches that relied on Back Translation perform better than those that did Direct Paraphrasing; this behavior is expected since the Direct Paraphrasing approach is more likely to generate very similar sentences. In the same way, the model with more languages performed better than the others.
<figure><img src="image_14.png" /></figure>
# Chapter 5

## Conclusions

Throughout this thesis, we studied the history and development of automatic Paraphrase Evaluation metrics. We surveyed the most common approaches and provided an overview of their strengths and shortcomings. This exploratory work revealed the need for a metric that covered the most prominent elements of paraphrasing (semantic similarity and surface dissimilarity) while being easily accessible, replicable, and suitable to be used in a variety of languages.

Once the survey of the state of the art approaches was completed, we proceeded to describe X-ParEval, our theoretical approach to Paraphrase Evaluation, which consists of a simple equation that captures the main characteristics of what we consider good paraphrasing. This theoretical proposal was then realized using some of the newer and best performing NLP techniques. This practical implementation was then tested, first against previous metrics, then on various datasets for 21 languages.

The overall results of our experiments show that X-ParEval performs better than the previous metrics on English while working with varying degrees on other languages. Among the 21 languages analyzed, only two (Czech and Polish) showed a bad performance, while more studies are needed to figure out the real reason, we believe it to be related to the quality of the used datasets rather than the soundness of our proposal.

Finally, just like Post did when introducing SACREBLEU, we are going to release a readily available library to compute our X-ParEval score as well as produce a detailed string with the information about its computation.

While improving on previous techniques, our current approach still relies heavily on semantic similarity evaluation and thus is bounded by the limitations of existing models. When new and more accurate models for that task become public, it will be possible to upgrade X-ParEval to take advantage of new technologies.

Despite its shortcomings, we believe that X-ParEval helps to move forward the domain of Paraphrase Evaluation while also making it easier to compare results of Paraphrase Generation systems, which was the original motivation behind it.
<figure><img src="image_15.png" /></figure>
# Appendix A

## Metrics Implementation

This appendix includes a brief description of the implementation of metrics used for this thesis.

### A.1 BLEU

The `sentence bleu` function of Post's SacreBLEU [33] python library<fnref n="1" /> was used.

### A.2 Google-BLEU

The `sentence gleu` function of the NLTK [4] python library<fnref n="2" /> was used.

### A.3 ROUGE

Both ROUGE-1 and ROUGE-L were obtained with the `rouge-score` python library.<fnref n="3" />

### A.4 PEM

The `pem` software<fnref n="4" /> provided with the original paper [18] was used.

### A.5 PINC

Since the original PINC code was not publicly available, we re-implemented it following the equation of the original paper [7]. To obtain the n-grams the everygrams function of the NLTK library was used.

### A.6 APEM

Since the original APEM code was not publicly available, we re-implemented it following the equation of the original paper [24]. We used the morpheme extraction from the polyglot python library.<fnref n="5" /> However we could not compare it with the original used for Korean because the dataset was not available and we used a different morpheme extractor.

<footnote n="1">¹https://github.com/mjpost/sacrebleu</footnote>

<footnote n="2">²https://nltk.org</footnote>

<footnote n="3">³https://pypi.org/project/rouge-score</footnote>

<footnote n="4">⁴https://www.comp.nus.edu.sg/~nlp/software.html</footnote>

<footnote n="5">⁵https://github.com/aboSamoor/polyglot/</footnote>
## A.7 Cosine Similarity

We obtained sentence embeddings using the paraphrase-xlm-r-multilingual-v1 model [36] of the sentence-transformers [36] python library.<fnref n="6" /> We then computed their cosine similarity with that same library.

## A.8 Harmonic Mean

Following the proposal by Al-Raisi, Bourai, and Lin [34] we computed the harmonic mean of the cosine similarity and Google-BLEU.

## A.9 WEEM4PG

Since the original WWEM4PG code was not publicly available, we re-implemented it following the equation of the original paper [13]. We used Word2Vec embeddings from the gensim [35] python library,⁷ more precisely, word2vec-google-news-300 embeddings. We evaluated our implementation against the 26 455 PPDB 2.0 [30] phrasal paraphrases as the authors did in their original paper and obtained a slightly higher correlation than they did (0.45).

## A.10 X-ParEval

We used Equation 3.1 and Equation 3.2 from Chapter 3 with the Cosine Similarity and Google-BLEU described in this appendix.

<footnote n="6">⁶https://github.com/UKPLab/sentence-transformers.
⁷https://radimrehurek.com/gensim/</footnote>
Bibliography

[1] Viktar Atliha and Dmitrij Šešok. "Text Augmentation Using BERT for Image Captioning". In: *Applied Sciences* 10.17 (2020), p. 5978.

[2] Daniel Balouek et al. "Adding Virtualization Capabilities to the Grid'5000 Testbed". In: *Cloud Computing and Services Science*. Ed. by Ivan I. Ivanov et al. Vol. 367. Communications in Computer and Information Science. Springer International Publishing, 2013, pp. 3–20. ISBN: 978-3-319-04518-4. DOI: 10.1007/978-3-319-04519-1_1.

[3] Alberto Barrón-Cedeño et al. "Plagiarism meets paraphrasing: Insights for the next generation in automatic plagiarism detection". In: *Computational Linguistics* 39.4 (2013), pp. 917–947.

[4] Steven Bird, Ewan Klein, and Edward Loper. *Natural language processing with Python: analyzing text with the natural language toolkit*. " O'Reilly Media, Inc.", 2009.

[5] Wayne D. Blizard et al. "Multiset theory". In: *Notre Dame Journal of formal logic* 30.1 (1989), pp. 36–66.

[6] Chris Callison-Burch, Trevor Cohn, and Mirella Lapata. "Parametric: An automatic evaluation metric for paraphrasing". In: *Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)*. 2008, pp. 97–104.

[7] David Chen and William B Dolan. "Collecting highly parallel data for paraphrase evaluation". In: *Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies*. 2011, pp. 190–200.

[8] Jacob Devlin et al. "Bert: Pre-training of deep bidirectional transformers for language understanding". In: *Proceedings of NAACL-HLT*. 2019, pp. 4171–4186.

[9] Bill Dolan, Chris Quirk, and Chris Brockett. "Unsupervised Construction of Large Paraphrase Corpora: Exploiting Massively Parallel News Sources". In: *COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics*. Geneva, Switzerland: COLING, Aug. 2004, pp. 350–356. URL: https://www.aclweb.org/anthology/C04-1051.

[10] Angela Fan and Claire Gardent. "Multilingual AMR-to-Text Generation". In: *Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)*. Online: Association for Computational Linguistics, Nov. 2020, pp. 2889–2901. DOI: 10.18653/v1/2020.emnlp-main.231. URL: https://www.aclweb.org/anthology/2020.emnlp-main.231.

[11] Angela Fan et al. "Beyond english-centric multilingual machine translation". In: *Journal of Machine Learning Research* 22.107 (2021), pp. 1–48.

[12] Juri Ganitkevitch, Benjamin Van Durme, and Chris Callison-Burch. "PPDB: The paraphrase database". In: *Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies*. 2013, pp. 758–764.
[13] Tulu Tilahun Hailu, Junqing Yu, Tessfu Geteye Fantaye, et al. "Intrinsic and Extrinsic Automatic Evaluation Strategies for Paraphrase Generation Systems". In: *Journal of Computer and Communications* 8.02 (2020), p. 1.

[14] Philipp Koehn. "Europarl: A parallel corpus for statistical machine translation". In: *MT summit*. Vol. 5. Citeseer. 2005, pp. 79–86.

[15] Taku Kudo and John Richardson. "SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing". In: *Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations*. Brussels, Belgium: Association for Computational Linguistics, Nov. 2018, pp. 66–71. DOI: 10.18653/v1/D18-2012. URL: https://www.aclweb.org/anthology/D18-2012.

[16] Chin-Yew Lin. "ROUGE: A Package for Automatic Evaluation of Summaries". In: *Text Summarization Branches Out*. Barcelona, Spain: Association for Computational Linguistics, July 2004, pp. 74–81. URL: https://www.aclweb.org/anthology/W04-1013.

[17] Dekang Lin et al. "New tools for web-scale n-grams". In: *7th International Conference on Language Resources and Evaluation, LREC 2010*. European Language Resources Association (ELRA). 2010, pp. 2221–2227.

[18] Chang Liu, Daniel Dahlmeier, and Hwee Tou Ng. "PEM: A paraphrase evaluation metric exploiting parallel texts". In: *Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing*. 2010, pp. 923–932.

[19] Yinhan Liu et al. "Multilingual denoising pre-training for neural machine translation". In: *Transactions of the Association for Computational Linguistics* 8 (2020), pp. 726–742.

[20] François Mairesse et al. "Phrase-based statistical language generation using graphical models and active learning". In: *Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics*. 2010, pp. 1552–1561.

[21] Philip M McCarthy and Danielle S McNamara. "The user-language paraphrase challenge". In: *Retrieved January* 10 (2008), p. 2008.

[22] Kathleen McKeown. "Paraphrasing questions using given and new information". In: *American Journal of Computational Linguistics* 9.1 (1983), pp. 1–10.

[23] Alaa Altheneyan; Mohamed Menai. *ArPC a corpus for paraphrase identification in Arabic text*. 2019. DOI: 10.21227/jtmt-zg81. URL: https://dx.doi.org/10.21227/jtmt-zg81.

[24] Sung Won Moon et al. "APEM: Automatic paraphrase evaluation using morphological analysis for the Korean language". In: *2016 18th International Conference on Advanced Communication Technology (ICACT)*. IEEE. 2015, pp. 680–684.

[25] Courtney Napoles, Matthew R Gormley, and Benjamin Van Durme. "Annotated gigaword". In: *Proceedings of the Joint Workshop on Automatic Knowledge Base Construction and Web-scale Knowledge Extraction (AKBC-WEKEX)*. 2012, pp. 95–100.

[26] Courtney Napoles et al. "Paraphrastic sentence compression with a character-based metric: Tightening without deletion". In: *Proceedings of the Workshop on Monolingual Text-To-Text Generation*. 2011, pp. 84–90.
[27] Franz Josef Och and Hermann Ney. "The alignment template approach to statistical machine translation". In: *Computational linguistics* 30.4 (2004), pp. 417–449.

[28] Kishore Papineni et al. "Bleu: a Method for Automatic Evaluation of Machine Translation". In: *Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics*. Philadelphia, Pennsylvania, USA: Association for Computational Linguistics, July 2002, pp. 311–318. DOI: 10.3115/1073083.1073135. URL: https://www.aclweb.org/anthology/P02-1040.

[29] Adam Paszke et al. "PyTorch: An Imperative Style, High-Performance Deep Learning Library". In: *Advances in Neural Information Processing Systems* 32. Ed. by H. Wallach et al. Curran Associates, Inc., 2019, pp. 8024–8035. URL: http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.

[30] Ellie Pavlick et al. "PPDB 2.0: Better paraphrase ranking, fine-grained entailment relations, word embeddings, and style classification". In: *Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)*. 2015, pp. 425–430.

[31] F. Pedregosa et al. "Scikit-learn: Machine Learning in Python". In: *Journal of Machine Learning Research* 12 (2011), pp. 2825–2830.

[32] Lidia Pivovarova et al. "ParaPhraser: Russian paraphrase corpus and shared task". In: *Conference on Artificial Intelligence and Natural Language*. Springer. 2017, pp. 211–225.

[33] Matt Post. "A Call for Clarity in Reporting BLEU Scores". In: *Proceedings of the Third Conference on Machine Translation: Research Papers*. Brussels, Belgium: Association for Computational Linguistics, Oct. 2018, pp. 186–191. DOI: 10.18653/v1/W18-6319. URL: https://www.aclweb.org/anthology/W18-6319.

[34] Fatima Al-Raisi, Abdelwahab Bourai, and Weijian Lin. "Neural Symbolic Arabic Paraphrasing with Automatic Evaluation". In: *Computer Science & Information Technology* 1 (2018).

[35] Radim Rehurek and Petr Sojka. "Gensim–python framework for vector space modelling". In: *NLP Centre, Faculty of Informatics, Masaryk University, Brno, Czech Republic* 3.2 (2011).

[36] Nils Reimers and Iryna Gurevych. "Making Monolingual Sentence Embeddings Multilingual using Knowledge Distillation". In: *Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing*. Association for Computational Linguistics, Nov. 2020. URL: https://arxiv.org/abs/2004.09813.

[37] Nils Reimers and Iryna Gurevych. "Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks". In: *Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing*. Association for Computational Linguistics, Nov. 2019. URL: https://arxiv.org/abs/1908.10084.

[38] Ehud Reiter. "A Structured Review of the Validity of BLEU". In: *Computational Linguistics* 44.3 (Sept. 2018), pp. 393–401. DOI: 10.1162/coli_a_00322. URL: https://www.aclweb.org/anthology/J18-3002.

[39] Grazia Russo-Lassner, Jimmy Lin, and Philip Resnik. *A paraphrase-based approach to machine translation evaluation*. Tech. rep. University of Maryland, Institute for Advanced Computer Studies, 2005.
[40] Yves Scherrer. "TaPaCo: A Corpus of Sentential Paraphrases for 73 Languages". In: *Proceedings of The 12th Language Resources and Evaluation Conference*. 2020, pp. 6868-6873.

[41] Claude E Shannon. "Prediction and entropy of printed English". In: *Bell system technical journal* 30.1 (1951), pp. 50-64.

[42] Yui Suzuki, Tomoyuki Kajiwara, and Mamoru Komachi. "Building a non-trivial paraphrase corpus using multiple machine translation systems". In: *Proceedings of ACL 2017, Student Research Workshop*. 2017, pp. 36-42.

[43] Yuqing Tang et al. "Multilingual translation with extensible multilingual pre-training and finetuning". In: *arXiv preprint arXiv:2008.00401* (2020).

[44] The pandas development team. *Pandas 1.2.4*. Version v1.2.4. Apr. 2021. DOI: 10.5281/zenodo.4681666. URL: https://doi.org/10.5281/zenodo.4681666.

[45] Kai Ming Ting. "Precision and Recall". In: *Encyclopedia of Machine Learning*. Ed. by Claude Sammut and Geoffrey I. Webb. Boston, MA: Springer US, 2010, pp. 781-781. ISBN: 978-0-387-30164-8. DOI: 10.1007/978-0-387-30164-8_652. URL: https://doi.org/10.1007/978-0-387-30164-8_652.

[46] Guido Van Rossum and Fred L. Drake. *Python 3 Reference Manual*. Scotts Valley, CA: CreateSpace, 2009. ISBN: 1441412697.

[47] Ashish Vaswani et al. "Attention is all you need". In: *Advances in neural information processing systems*. 2017, pp. 5998-6008.

[48] Jonathan Weese, Juri Ganitkevitch, and Chris Callison-Burch. "PARADIGM: Paraphrase diagnostics through grammar matching". In: *Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics*. 2014, pp. 192-201.

[49] John Wieting et al. "Towards Universal Paraphrastic Sentence Embeddings". In: *4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings*. Ed. by Yoshua Bengio and Yann LeCun. 2016. URL: http://arxiv.org/abs/1511.08198.

[50] Yonghui Wu et al. "Google's neural machine translation system: Bridging the gap between human and machine translation". In: *arXiv preprint arXiv:1609.08144v2* (2016).