are partitional, whereas the fifth approach is agglomerative., which is used
to cluster a collection of objects (in our case, lemmas) into a predetermined
number of clusters labeled $k$. We applied a methodology based on Caliński and
Harabasz (1974) and using cosine similarity and Cluto’s $\mathcal{H}_{2}$
metric to estimate the optimal amount of clusters.

We experimented with a number of different clustering configurations. The
variables we took into account were: a) the number of most frequent lemmas,
with the 10,000 to 15,000 most frequent lemmas giving the best results; b) the
inclusion of proper nouns or their substitution for their POS; and c)
considering the lemmas with and without their POS.

We evaluated the results of these configurations manually and opted for 15,000
lemmas with proper nouns grouped according to their POS tag (pn_n) and with
the POS tag assigned to the lemmas. This configuration gave an optimal $k$ of
1,500 clusters applying the Caliński and Harabasz (1974) method and the
$\mathcal{H}_{2}$ metric.

The inclusion of POS improves the internal consistency of the clusters. Since
the POS tagger does not distinguish between subclasses of proper names
(person, organization, place, etc.), grouping them according to the pn_n tag
also gives better results. Regarding the number of lemmas, all results
obtained using between 10,000 and 15,000 lemmas gave satisfactory results. The
choice of the number of lemmas determines the number and the content of the
clusters. In all cases, the quality of clusters obtained was acceptable. We
consider a cluster as acceptable when all or almost all words contained in it
share one of the following relations: synonymy, hypernymy, or hyponymy. This
would allow for the use of one or more configurations for the obtention of the
final lexico-syntactic patterns (see Section 3.3.6).

Using Cluto with the selected configuration, we obtained a set of clusters
$C=\\{c_{i}:1\leq i\leq k\\}$ from matrix $X$. Formally, the content of each
cluster $c_{i}\in C$ is defined in 3.2, where $le$ is a set of related lemmas
and $ctx$ is a set of contexts. Each lemma_pos only belongs to one cluster
(i.e., it can only be defined in one $le$), whereas a context_lemma can be in
several contexts ($ctx$) of different clusters.

$c_{i}=<le,ctx>$ (3.2)

Formally, a context (called $context\\_cluster$) in $ctx$ is described as
follows:

$context\\_cluster=<[dep\\_dir:dep\\_lab:context\\_lemma],score>$ (3.3)

where $dep\\_dir,dep\\_lab,context\\_lemma$ corresponds to the definition of a
context as shown in Section 3.3.3.2. The $score$ is the sum of the different
scores given by Cluto252525The sum of the twenty-five most descriptive and
discriminative scores given automatically by Cluto..

For example, Table 3.1262626 The translation to English of Tables 1 and 2, as
well as additional examples and clusters are available at
http://clic.ub.edu/corpus/ describes the lemmas, $le$, and the most scored
contexts, $ctx$, in cluster number 421_n (one of the clusters obtained in the
corpus analyzed).

Table 3.1: Example of a real cluster (421_n) in the Diana-Araknion corpus in
Spanish Cluster: 421_n
---
Lemmas ($c_{421\\_le}$) |  barba_n, bigote_n, cabellera_n, cabello_n, ceja_n, crin_n, melena_n, mostacho_n, patilla_n, pelaje_n, pelo_n, perilla_n, vello_n
|  [$<$ : dobj : erizar_v],11 |  [$<$ : oth : erizar_v],11 |  [$<$ : oth : rizar_v],10
|  [$<$ : subj : erizar_v],10 |  [$>$ : mod : espeso_a],9 |  [$>$ : oth : espeso_a],9
|  [$>$ : mod : negro_a],7 |  [$<$ : oth : negro_a],5 |  [$>$ : mod : gris_a],8
|  [$<$ : dobj : rizar_v],8 |  [$>$ : oth : gris_a],7 |  [$<$ : oth : pelo_n],6
Contexts |  [$>$ : mod : rubio_a],7 |  [$>$ : mod : barba_n],7 |  [$<$ : oth : atusar_v],7
($c_{421\\_ctx}$) |  [$>$ : mod : largo_a],4 |  [$>$ : oth : rubio_a],6 |  [$<$ : mod : pelo_n],2
|  [$>$ : mod : rojizo_a],4 |  [$>$ : oth : rojizo_a],6 |  [$>$ : oth : largo_a],3
|  [$<$ : oth : bigote_n],3 |  [$>$ : mod : blanco_a],3 |  [$>$ : mod : cano_a],5
|  [$>$ : mod : hirsuto_a],5 |  [$>$ : oth : hirsuto_a],2 |  [$>$ : oth : largo_a],3
|  [$>$ : oth : negro_a],2 |  [$>$ : mod : rojizo_a],2 |

######  3.3.4.1 Results of the Clustering Process

Following our configuration, we obtained a total of 1,500 clusters in the
clustering process ($k$=1500). It is worth noting that the clusters are highly
morpho-syntactically and semantically cohesive.

The clusters contain lemmas belonging mostly to the same POS. It is worth
mentioning that more than half of the clusters are nouns (54.20%), followed by
verbs (25.80%) and adjectives (16.67%). Clusters of adverbs make up only 3.33%
of the total.

Clusters contain relevant implicit information, in the sense that their lemmas
belong to well-defined semantic categories, often at a very fine-grained
level. For instance, we obtained clusters of adjectives with a Positive
Polarity (5) and with a Negative Polarity (6)26. These results encourage us to
tag all the clusters with one or more semantic labels. That will enrich the
obtained patterns.

  1. 5.

{$c_{111}$, Positive_Polarity adjectives: admirable_a, asombroso_a,
genial_a…}272727’admirable, amazing, great’

  2. 6.

{$c_{38}$, Negative_Polarity adjectives: atroz_a, aterrador_a,
espantoso_a…}282828’atrocious, scary, frightening’

#####  3.3.5 Generalization: Linking and Filtering Clusters

The process of generalization by linking clusters (see Step 4 in Figure 3.1)
is based on the set of clusters and contexts obtained using Cluto. The
processes of linking clusters and pattern generation detailed in Section 3.3.6
are the core steps of the DISCOver methodology. The process of linking
clusters uses the set of the twenty-five highest scored contexts in each
cluster. According to our pattern-construction hypothesis (see Section 3.3.1),
the goal of the linking of clusters is to establish the relationships between
clusters using their contexts, as defined in (3.3), obtaining as a result a
matrix of all possible contextual relations between clusters (see Section
3.3.5.1). Next, we apply a filtering process in order to select strongly
related links taking into account different criteria (see Section 3.3.5.2).

######  3.3.5.1 Linking Clusters and Building the Matrix of Related Clusters

Basically, the aim of the cluster linking process is to establish the
relationships between clusters and to store them in a matrix, $R\\_clusters$,
with $k$ rows and $k$ columns. The $k$-value corresponds to the number of
clusters obtained in the clustering step.

For building the matrix, for each origin cluster ($x$) each $dep\\_dir$ and
$dep\\_lab$ of the $context\\_cluster$ (defined in Equation 3.3) are converted
into a $contextual\\_$ $relation$ (see Equation 3.4), while the
$context\\_lemma$ of the $context\\_cluster$ is used to locate the cluster
($y$) in which it occurs. We obtain as a result a matrix, $R\\_clusters$, in
which clusters are related according to a set of contextual relations stored
in a $relation\\_set$. The sum of the scores of the $context\\_clusters$ in
3.3 are added together in a matrix, $R\\_scores$. The $R\\_scores$ matrix is
later used in the process for determining filtering thresholds.

$contextual\\_relation=<dep\\_dir,dep\\_lab>$ (3.4)

For the contextual relation, defined in 3.4, $dep\\_dir$ and $dep\\_lab$ are
the dependency direction and the dependency label defined in a context of
cluster $i$ related to cluster $j$. Note that the $relation\\_set$ of a
cluster in itself is empty as $R\\_clusters[i][i]=\emptyset$ and
$R\\_clusters[i][j]\neq R\\_clusters[j][i]$.

Following the example of cluster 421_n, described in Table 3.1, the result of
the cluster linking process for this particular cluster ($i=421\\_n$) is shown
in Table 3.2292929For the sake of simplicity, the contexts are not included in
the Table 2 and we only show a relation of each type. . The first column in
this table shows the related clusters, $j$, the second column shows the
relation_type that relates cluster 421_n to the related clusters $j$ (i.e.
strong, semi or weak, See 3.3.5.2), and finally the last column describes the
lemmas in the related clusters.

Table 3.2: Some examples of cluster linking process in cluster $i$=421_n (described in Table 3.1). Related |  Relation_ |  Lemmas
---|---|---
clusters($j$) |  type |  ($c_{j.le}$, where $c_{j}$ refers to the related cluster, $j$)
1223_a |  strong |  azabache_a, bermejo_a, cano_a, canoso_a, hirsuto_a, lacio_a, lustroso_a, ondulante_a, sedoso_a…
932_v |  Semi |  afeitar_v, atusar_v, cepillar_v, empolvar_v, enguantar_v, peinar_v, rasurar_v…
405_n |  weak |  contario_n, final_n, largo_n, menudo_n…

######  3.3.5.2 Filtering Related Clusters

In the $R\\_clusters$ matrix, not all contextual relationships between
clusters are accepted since they have a low $R\\_scores$. For this reason, we
established two criteria to automatically determine which relationships will
be maintained and which ones are filtered out in the pattern generation
process. For each criterion only those relations higher than a predetermined
score value will be considered. The criteria are the following:

  * •

Criterion 1: For each pair of clusters $i$ and $j$, we take into account those
relations that in each of their directions (i.e., $R\\_scores[i][j]$ or
$R\\_scores[j][i]$) have a score above a minimum predetermined value, that is,
$threshold_{1}$. This $threshold_{1}$ is automatically determined by finding a
score value that allows for the grouping of 30% of the clusters. The relations
that fulfill criterion 1 are called Strong relations.

  * •

Criterion 2: For each pair of clusters $i$ and $j$, we take into account those
relations in which the sum of scores in both directions (i.e.,
$R\\_scores[i][j]+R\\_scores[j][i]$) is higher than a predetermined value,
that is, $threshold_{2}$, which is determined by finding a value that allows
for the grouping of 50% of the clusters. The relations that fulfill criterion
2 are called Semi relations.

Considering the example of cluster 421_n, the result of the filtering process
is that, out of the three clusters linked to cluster 421_n in our example26
(1223_a, 932_v, and 405_n), we will only select those with strong and semi
relations, that is, 1223_a, and 932_v. Those labelled as weak (e.g., 405_n
shown in Table 3.2) are filtered out because they do not reach the established
thresholds.

#####  3.3.6 Pattern Generation

Once the process for automatically linking and filtering clusters was carried
out, we proceeded to generate the lexico-syntactic patterns to be considered
as candidates for constructions (see Step 5 in Figure 3.1). Each generated
pattern is defined as follows:

$pattern=<lemma_{i},dep\\_dir,dep\\_lab,lemma_{j}>$ (3.5)

where $lemma_{i}$ and $lemma_{j}$ are the lemmas contained in the related
clusters ($i$ and $j$), $dep\\_dir$ and $dep\\_lab$ are the dependency
direction and the dependency label between the related clusters. So, there is
a pattern for each $lemma_{i}$ and $lemma_{j}$ pair.

As we mentioned in Section 3.3.4, all possible configurations using between
10,000 and 15,000 lemmas gave acceptable related clusters. In order to
increase the number of patterns generated we carried out the same process with
a configuration using 10,000 lemmas. We combined the patterns obtained using
the 10,000 and 15,000 lemmas together and removed those that were shared by
both configurations. In Tables 3.3, 3.4 and 3.5, we show the number of
resulting clusters and patterns, after removing the overlapping patterns, for
the two configurations.

Table 3.3: Distribution of the number of related and unrelated clusters and their percentage | 10,000 lemmas | 15,000 lemmas
---|---|---
Relation | Clusters (%) | Clusters (%)
Strong | 441 (31.50%) | 461 (30.73%)
Semi | 339 (24.21%) | 396 (26.40%)
Total |  780 (55.71%) |  857 (57.13%)
Weak | 589 (42.07%) | 636 (42.40%)
Unrelated | 31 (2.21%) | 7 (0.47%)

As shown in Table 3.3 (second and third columns), more than 55% of the linked
clusters maintain Strong and Semi relationships, whereas only the 2.68% of the
clusters remain unrelated. Table 3.4 (second and third columns) shows the
distribution of linked clusters by POS in both configurations.

Table 3.4: Distribution of the number of related clusters and their percentage by POS | 10,000 lemmas | 15,000 lemmas
---|---|---
POS | Clusters (%) | Clusters (%)
N | 415 (53.21%) | 464 (54.14%)
V | 197 (25.26%) | 182 (12.24%)
A | 142 (18.21%) | 173 (20.19%)
R | 26 (3.30%) | 38 (4.43%)
Total |  780 (100%) |  857 (100%)

The total number of lexico-syntactic patterns obtained from the two
configurations of clusters (780 and 857 Strong and Semi related clusters) is
237,444. For the purpose of pattern generation, Strong and Semi clusters have
been treated equally. From these patterns, we removed 16,712 patterns, those
that were present in both sets of generated patterns, given as a result the
total number of 220,732 patterns (See Table 3.5).

Table 3.5: Distribution of the generated patterns  Lemmas | Attested-Patterns | Unattested-Patterns | Total
---|---|---|---
10,000 | 23,980 | 48,147 | 72,127
15,000 | 37,840 | 127,477 | 165,317
10,000 + 15,000 | 61,820 | 175,624 | 237,444
Overlapping | 8,531 | 8,181 | 16,712
Sum (no overlap) | 53,289 | 167,443 | 220,732

The DISCOver methodology allows for the generation of patterns that actually
occur in the corpus (Attested-Patterns), but also of lexico-syntactic patterns
that are not present in the corpus but which are highly plausible in Spanish
(Unattested-Patterns), since the components of the clusters are closely
semantically related. As a result, we are able to enlarge the descriptive
power of the source corpus. Among the patterns we generated, 61,820 were
Attested-Patterns, that is, patterns that are present in the source corpus,
and 175,624 were Unattested-Patterns, that is, new patterns (see Table 3.5).

Retaking the example of cluster 421_n and its related clusters we obtain
patterns such as those shown in (7)303030$<$moustachec_421 $<$:dobj:
to_brushc_932_v$>$; $<$manec_421 $<$:dobj: to_smoothc_1267_v$>$; $<$furc_421
$>$:mod: silkyc_1223_a$>$; $<$goeteec_421 $>$:mod: greyc_149_a$>$:

  1. 7.

$<$bigotec_421 $<$:dobj: cepillarc_932_v$>$

$<$melenac_421 $<$:dobj: alisarc_1267_v$>$

$<$pelajec_421 $>$:mod: sedosoc_1223_a$>$

$<$perillac_421 $>$:mod: grisc_149_a$>$

All of these patterns are Unattested-Patterns, that is, they do not occur in
the Diana-Araknion corpus but are generated applying our methodology and are
perfectly acceptable in Spanish. These patterns would not have been extracted
using, for example, a n-gram based method or plain statistical methods.

It is worth noting the high degree of semantic cohesion between the lemmas of
the same cluster and between the lemmas of the related clusters
((8)313131$<$accidentc_470 $<$:dobj to_causec_560$>$; $<$firec_470 $<$:dobj
to_avoidc_560$>$; $<$sinisterc_470 $<$:dobj to_producec_560$>$.,
(9)323232$<$accidentc_470 $<$:subj to_triggerc_560$>$, $<$ravagec_470 $<$:subj
to_producec_560$>$., (10)333333$<$chancellorc_70 $>$:mod argentinianc_1$>$;
$<$ambassadorc_70 $>$:mod belgianc_1$>$; $<$representativec_70 $>$:mod
chilianc_1$>$ and (11)343434$<$singer c_155 $>$:mod belgianc_1$>$; $<$song-
writerc_155 $>$:mod canadianc_1$>$; $<$pianistc_155 $>$:mod americanc_1$>$).

  1. 8.

$<$accidente c_470 $<$:dobj causarc_560$>$

$<$fuego c_470 $<$:dobj evitarc_560$>$

$<$siniestro c_470 $<$:dobj producirc_560$>$

  2. 9.

$<$accidente c_470 $<$:subj desencadenarc_560$>$

$<$destrozo c_470 $<$:subj producirc_560$>$

$<$incendio c_470 $<$:subj originarc_560$>$

  3. 10.

$<$canciller c_70 $>$:mod argentinoc_1$>$

$<$embajador c_70 $>$:mod belgac_1$>$

$<$mandatario c_70 $>$:mod chilenoc_1$>$

  4. 11.

$<$cantante c_155 $>$:mod belgac_1$>$

$<$compositor c_155 $>$:mod canadiensec_1$>$

$<$pianista c_155 $>$:mod estadounidensec_1$>$

This strong cohesion allows for a semantic annotation of the clusters to
obtain more abstract syntactico-semantic constructions that combine semantic
categories (12) and (13). The semantic labels associated with each cluster
have been manually added, taking into account the WordNet (Miller, 1995) upper
ontologies.

  1. 12.

$<$Event-nc_470 $<$:dobj Causative-v c_560$>$

$<$Event-n c_470 $<$:subj Causative-v c_560$>$

  2. 13.

$<$Person/Politician-n c_70 $>$:mod Nationality-a c_1$>$

$<$Person/Musician-n c_155 $>$:mod Nationality-a c_1$>$

In the end, we could obtain a hierarchy of candidates to be considered as
different types of constructions, ranging from the most abstract syntactico-
semantic constructions combining different semantic classes (12-13) to the
most concrete lexico-syntactic constructions (i.e., lemma combinations)
(8-11).

####  3.4 Evaluation

In this section we evaluate the quality of the results obtained through the
DISCOver methodology: the clusters obtained (see Section 3.4.1) and the
lexico-syntactic patterns (see Section 3.4.2).

#####  3.4.1 Clustering Evaluation

DISCOver is a methodology for discovering lexico-syntactic patterns.The
clusters of semantically related words are a by-product that we obtain as part
of the process. Since the focus of this work is the methodology used and the
patterns obtained, the evaluation of all possible representation and
clustering algorithms is outside the scope of this article. Nevertheless, we
prepared a cluster evaluation experiment in order to justify our choice and
show that the quality of the obtained vectors and clusters is at least
comparable with other state-of-the-art methods. As a baseline, we use standard
Word2Vec (Mikolov et al., 2013c), representations with the recommended built-
in k-means clustering algorithm. We evaluated the resulting clusters with
respect to two criteria: a) the POS purity of each cluster, calculated
automatically; and b) the semantic coherence of the lemmas in each cluster,
evaluated manually by experts. The criterium applied to determine the
coherence of cluster was to check if the words within the cluster held one of
the following semantic relations: synonymy, hypernymy or hyponymy.

CLUTO obtained much higher results in terms of both evaluation criteria. The
POS coherence of the obtained clusters was 98%, compared to 70% obtained by
Word2Vec. Manual evaluation shows that 99% of the clusters obtained by CLUTO
were more semantically coherent than the corresponding ones obtained by
Word2Vec. These results justify the representations and parameters as adequate
for the task and as comparable with the state of the art. Kovatchev et al.
(2016) present a more in-depth comparison of the clustering algorithms using
corpora of different sizes.

#####  3.4.2 Pattern Evaluation

Obtaining high quality lexico-syntactic patterns is the main objective of the
DISCOver methodology. In this section, we present two different evaluations of
the obtained patterns: (1) an automatic evaluation, applying statistical
association measures; and (2) a manual evaluation by expert linguists353535An
extrinsic evaluation has also been carried out in a text classification task
(See Section 3.5). . For these evaluations, we used the sum of the patterns of
both the 15,000 and 10,000 word configurations.

First, we evaluated the patterns automatically using statistical association
measures and a different, much larger, corpus (Diana-Araknion++). In Section
3.3.1, we define two main properties of constructions: 1) Syntactic-semantic
coherence and 2) Generalizability. “Syntactic-semantic coherence” entails that
the words in each pattern need to be syntactically and semantically related.
The “syntactic coherence” of the patterns is not evaluated explicitly, as it
is considered to be a by-product of the methodology: all linked clusters from
which the patterns are derived have a plausible syntactic relationship and a
high connectivity score (see Section 3.3.5.1). However, we need to evaluate
the semantic coherence of the patterns, that is, whether there is a semantic
relation between the two lemmas. Defining and evaluating “semantic
relatedness” is a non-trivial task, which often requires the use of external
resources, such as WordNet and BabelNet (Navigli and Ponzetto, 2012). However,
these resources are built considering the paradigmatic relationship between
words (such as synonymy, hypernymy, and hyponymy), while we are interested in
evaluating syntagmatic relationships.

Evert (2008) and Pecina (2010) discuss the use of association measures for
identifying collocations. They define collocations as “the empirical concept
of recurrent and predictable word combinations, which are a directly
observable property of natural language”. In the context of distributional
semantics, this definition corresponds to “semantic coherence”.

In the DISCOver process, we obtained two qualitatively different types of
candidates-to-be-constructions: Attested-Patterns, which are observed in the
corpus and Unattested-Patterns, which are obtained as a result of a
generalization process that includes clustering, linking and filtering. In
order to evaluate the quality of these candidates-to-be-constructions, we
formulate two hypotheses and disprove their corresponding null hypotheses.

  * •

Hypothesis 1: The two lemmas in each construction are semantically related.

Null hypothesis 1 (henceforth $H_{0}$1): The degree of statistical association
between the two lemmas in each of the Attested-Patterns, measured in a corpus
other than the one they were extracted from, is equal to statistical chance.

  * •

Hypothesis 2: Constructions can be generalized and/or derived from other
constructions through generalization. Unattested-Patterns (derived through a
generalization process) should be possible language expressions and have the
property of semantic coherence.

Null hypothesis 2.1 (henceforth $H_{0}$2.1): Unattested-Patterns are not
possible language expressions. They cannot appear in a corpus.

Null hypothesis 2.2 (henceforth $H_{0}$2.2): If Unattested-Patterns appear in
a corpus, they will not have the property of semantic coherence. That is, they
will have association scores equal to statistical chance.

In order to prove the two main hypotheses we needed to disprove the three null
hypotheses.

For a baseline of $H_{0}$1, we extracted a list of all bigrams (BI-Patterns)
from the original Diana-Araknion corpus. Each bigram contains at least one of
the 15,000 most frequent words. We removed all bigrams containing non-content
words. All of the Attested-Patterns and the BI-Patterns were found and
extracted from the Diana-Araknion 100M token corpus.

For a baseline of $H_{0}$2.1, we generated patterns by combining frequent
lemmas (FL-Patterns): FL-Patterns-15 contain all combinations of the most
frequent 15,000 lemmas found in the Diana-Arakion corpus; FL-Patterns-30
contain all combinations in which one lemma is among the 15,000 most frequent
lemmas and the other among the 30,000 most frequent ones; FL-Patterns-all
contain all word combinations which contain at least one of the 15,000 most
frequent lemmas363636The total number of lemmas used in the FL-Patterns (all)
is 422,000..

We use two different statistical methods (Evert, 2008): simple Mutual
Information (MI), which is an effect size measure, and the Z-score (Z-sc),
which is an evidence-based measure. Effect-size measures and evidence-based
measures are qualitatively different, and for evaluation can be used
complementarily. Our final experimental setup includes the following:

  * •

Attested-Patterns, in five different test groups, based on their observed
frequency in the Diana-Araknion corpus:

    * –

Att-Patterns-all with an original frequency of 1 or more

    * –

Att-Patterns-2 with an original frequency of 2 or more

    * –

Att-Patterns-3 with an original frequency of 3 or more

    * –

Att-Patterns-4 with an original frequency of 4 or more

    * –

Att-Patterns-5 with an original frequency of 5 or more

  * •

BI-Patterns, with an original frequency of 5 or more3737375,285 of the BI-
patterns coincide with Attested-Patterns.

  * •

Unattested-Patterns

  * •

FL-Patterns-15, FL-Patterns-30, FL-Patterns-all

Evaluating $H_{0}$1:

We calculated the MI and Z-sc association scores of the two words in each of
the Attested-Patterns and BI-Patterns in the Diana-Araknion++ 600M token
corpus. The association score was calculated based on the sentential co-
occurrence of the two words. Patterns that co-occurred less than 5 times
obtained a score of 0. First, we compared the obtained association with
standard thresholds, representing statistical chance: 0, 0.5, and 1 for MI; 0,
1.96, and 3.29 for Z-sc. Second, we compared the average association score of
the Attested Patterns with those of the BI-Patterns.

Table 3.6 shows what percentage of the Attested-Patterns in each group obtains
scores higher than statistical chance. Overall, the majority of the Attested-
Patterns outperform the statistical chance baseline. The results are
consistent for both the measures and their thresholds, even though they
measure the association in a qualitatively different manner. It is important
to note that filtering out the Attested-Patterns with a frequency of 1
significantly improves the results. We believe this factor should be taken
into consideration in future experiments.

Table 3.6: Association score of Attested-Patterns compared with statistical chance | MI | Z-sc
---|---|---
Patterns | >0 | >0.5 | >1 | >0 | >1.96 | >3.29
Att-Patterns-5 | 85% | 83% | 80% | 85% | 83% | 82%
Att-Patterns-4 | 84% | 82% | 79% | 84% | 82% | 80%
Att-Patterns-3 | 82% | 80% | 77% | 82% | 80% | 78%
Att-Patterns-2 | 78% | 76% | 72% | 78% | 76% | 73%
Att-Patterns-all | 68% | 66% | 62% | 68% | 65% | 62%

As a complementary evaluation, we directly compared the association scores of
the Attested-Patterns with those of the BI-Patterns. Table 3.7 shows the
average association scores for the two types of patterns383838The average is
calculated as a simple average of all patterns of the corresponding type.. The
Attested-Patterns have a much higher degree of association than the BI-
Patterns. In the case of MI, the Attested-Patterns obtain scores more than two
times higher than the BI-Patterns. In the case of Z-sc, the Attested-Patterns
obtain scores between 30% and 100% higher than the BI-Patterns.

Table 3.7: Average association score of Attested-Patterns and BI-patterns Patterns | Average MI | Average Z-sc
---|---|---
Attested-Patterns-5 | 3.90 | 52
Attested-Patterns-4 | 3.86 | 49
Attested-Patterns-3 | 3.80 | 46
Attested-Patterns-2 | 3.70 | 42
Attested-Patterns-all | 3.50 | 35
BI-Patterns | 1.72 | 27

The obtained results disprove $H_{0}$1 and confirm Hypothesis 1. That is, we
can conclude that the Attested-Patterns are semantically coherent.

Evaluating $H_{0}$2.1:

We checked how many of the Unattested-Patterns were present in Diana-
Araknion++. As a baseline we used the FL-Patterns. Both Unattested-Patterns
and FL-Patterns are not directly obtained, but are rather a result of
generalization and generation using different methodologies. For each group,
we calculated the percentage of the patterns that appear once and the
percentage of the patterns that appear at least five times. Table 3.8 shows
the results obtained.

Table 3.8: Occurrence of Unttested-Patterns and FL-Patterns Patterns | Occurred Once | Occurred Five Times
---|---|---
Unattested-Patterns | 54% | 24%
FL-Patterns-15 | 24% | 9%
FL-Patterns-30 | 11% | 4%
FL-Patterns-all | 4% | 0.6%

Unattested-Patterns appear much more frequently than the patterns generated by
simply combining frequent lemmas. 56% of the Unattested-Patterns were observed
in Diana-Araknion++. This is more than double the observance rate of the FL-
Patterns-15 and five times higher than for FL-Patterns-30. 24% of the
Unattested-Patterns appear in Diana-Araknion++ with a frequency of 5 or more.
This is almost three times higher than FL-Patterns-15 and six times higher
than FL-Patterns-30. The results of FL-Patterns-all are much lower, showing
that unfiltered pattern generation is not effective. Unattested-Patterns are
linguistic patterns given that they appear in a corpus with a much higher
probability than patterns generated using a simpler frequency based
methodology. These results disprove $H_{0}$2.1.

Evaluating $H_{0}$2.2:

We calculated the association score (MI and Z-sc) between the lemmas in each
of the Unattested-Patterns that occurred at least 5 times393939Calculating
this score for patterns with lower frequency is unreliable due to the low-
frequency bias in some of the measures. in Diana-Araknion++. We compared the
scores with the same thresholds we used when evaluating $H_{0}$1\. Table 3.9
shows the percentage of patterns with a score higher than the statistical
chance thresholds.

Table 3.9: Association scores of Unttested-Patterns | MI | Z-sc
---|---|---
Patterns | >0 | >0.5 | >1 | >0 | >1.96 | >3.29
Unattested-Patterns | 93% | 86% | 76% | 93% | 80% | 70%

The observed degree of association is very high. Over 90% of the observed
Unattested-Patterns obtained a positive association score with respect to both
measures. When comparing them with the statistical chance thresholds, the
obtained results are similar to those obtained by Attested-Patterns in
$H_{0}$1\. The Unattested-Patterns, when observed in a different corpus, are
semantically coherent. This disproves $H_{0}$2.2.

In conclusion, the automated statistical evaluation of the patterns obtained
by DISCOver shows that: (1) Attested-Patterns are semantically coherent, as
they outperform two baselines: statistical chance thresholds and BI-Patterns.
These results disprove $H_{0}$1.; (2) A significant percentage (56%) of the
Unattested-Patterns can be found in Diana-Araknion++, which is much higher
than the occurrence of FL-Patterns. These results disprove $H_{0}$2.1; (3)
Whenever Unattested-Patterns occur in Diana-Araknion++, the statistical
association between the lemmas in the patterns is much higher than the
statistical chance baseline. This disproves $H_{0}$2.2.

As we have disproved all 3 of the null hypotheses, we can conclude that the
patterns obtained by the DISCOver methodology have both properties of
constructions: syntactic and semantic coherence and generalizability.
Therefore they are good candidates-to-be-constructions.

We also performed a manual evaluation of the lexico-syntactic patterns. This
complementary validation reinforces the results obtained in the two
statistical evaluations. We prepared a dataset of 600 patterns for the manual
evaluation: 300 patterns obtained by applying the DISCOver methodology (the
patterns were randomly selected from all Attested and Unattested Patterns) and
300 of the FL-Patterns-15. Three experts were asked to classify each pattern
as a correct or incorrect construction. The instructions given to them were:
a) evaluate whether the pattern is a possible Spanish pattern in your
judgement as a native speaker; b) in case of doubt, consult the Google Search
engine to check whether it is used by users. Our research questions in this
evaluation were: 1) How do the experts evaluate the patterns obtained by
DISCOver?; 2) Are experts more likely to accept patterns obtained by DISCOver
than random patterns of frequent words?

The average percentage of agreement between the three annotators was 81.67%
(see Table 3.10), which is considered high for a semantic evaluation task. The
corresponding Fleiss Kappa score is 0.602 with expected agreement of 0.539,
which is statistically significant.

Table 3.10: Interannotator agreement test Annotators (A) | %Agreement
---|---
A1 and A2 | 85%
A1 and A3 | 80.17%
A2 and A3 | 79.83%
A1, A2 and A3 | 81.67%

The results of the evaluation are shown in Table 3.11. We use three pattern
quality categories. “Strict Positive” includes patterns that were annotated as
positive by all three annotators, “Positive” includes patterns that were
annotated as positive by at least two annotators and “Negative” groups
together patterns that were annotated as positive by one or none of the
annotators. The experts accepted the majority of the DISCOver patterns as
constructions. At the same time they rejected the majority of the FL-Patterns.
We also want to highlight that the percentage of “Strict Positive" patterns is
very similar to the percentage of patterns that obtain a high association
score. These findings confirm the results that we obtained in the automatic
evaluation (See Tables 3.6 and 3.9).

Table 3.11: Expert evaluation | DISCOver | FL-Patterns
---|---|---
Strict Positive | 84% | 14%
Positive | 93% | 38%
Negative | 7% | 62%

####  3.5 Conclusions and Future Work

This article describes DISCOver, an unsupervised methodology for automatically
identifying lexico-syntactic patterns to be considered as constructions. We
based this methodology on the pattern-construction hypothesis, which states
that the linguistic contexts that are relevant for defining a cluster of
semantically related words tend to be (part of) a lexico-syntactic
construction.

Following this assumption, we developed a bottom-up language independent
methodology to discover lexico-syntactic patterns in corpora. The DSM
developed allows us to model the contexts of words (lemmas) taking into
account their dependency directions and dependency labels. We applied a
clustering process to the resulting matrix to obtain clusters of semantically
related lemmas. Then we linked all the clusters that were strongly
semantically related and we used them as a source of information for deriving
lexico-syntactic patterns, obtaining a total number of 220,732 candidates to
be constructions. We evaluated the DISCOver methodology by applying different
evaluations. First, the patterns were automatically evaluated using
statistical association measures and a different, much larger, corpus. We
evaluated whether the patterns we generated obtained a significantly higher
association score than statistical chance. We also compared the asociation
scores of the DISCOver patterns with a baseline of bigrams. DISCOver obtained
better results with respect to both baselines. The patterns obtained by
generalization were additionaly evaluated against a baseline of randomly
generated patterns. DISCOver significantly outperforms these baselines.
Second, the patterns were manually evaluated by expert linguists obtaining
good results (89.33%).

This methodology only requires having at one’s disposal a medium-sized corpus
automatically annotated with POS tags and syntactic dependencies. Therefore,
our methodology can be easily replicated with other corpora and other
languages. For instance, the DISCOver patterns were also used in a text
classification task (Franco-Salvador et al., 2015). The patterns obtained
using our methodology have been compared to other representations (i.e., tf-
idf, tf-idf n-grams, and enriched graph). The use of these patterns results in
an accuracy of 91.69%, which outperfoms the representations based on tf-idf
(25.26%), tf-idf n-grams (79.26%) and an enriched graph (43.98%), proving to
be the best option to represent the content of the corpus.

Furthermore, our methodology increases the descriptive power of the source
corpus. First, the lexico-syntactic patterns generated constitute a structured
and formalized semantic representation of the corpus. Second, the linking
process enlarges the content of the initial data with new relationships not
directly present in the corpus (i.e., a total of 167,443 Unattested-Patterns).

The Diana-Araknion-KB404040Available at http://clic.ub.edu/corpus/ can be used
as a source of information to derive relevant linguistic information, such as
the selection restrictions of verbs, nouns and adjectives; to disambiguate
syntactic analysis in order to discard candidate parse trees; to provide a
knowledge base of related words with a high degree of association measures for
psycholinguistic research; and, to allow for a fine-grained corpus
comparision.

The methodology presented and the results obtained, which are available in the
Diana-Araknion-KB, open several lines of future research.

First, the Diana-Araknion-KB can be used as a source of information for the
development of patterns at different levels of abstraction, in such a way as
to obtain a hierarchy of patterns with components belonging to different
levels of linguistic knowledge, that is, combining lexical, morpho-syntactic
and semantic information. Second, since the same semantic category can be
shared by more than one cluster, we could group them into metaclusters
containing all the clusters with the same semantic category. Third, a further
cluster linking process could be carried out allowing all members of a
metacluster to combine with all the target clusters that are related with at
least one of the members of the metacluster. Fourth, constructions could be
linked in terms of transitivity to obtain larger structures. That is, if
cluster A combines with cluster B, and B combines with cluster C, we have the
candidate construction: A+B+C. Fifth, the methodology can be used to extract
and study patterns in corpora from a specific area, such as the Biomedical
domain.

To sum up, we consider that this methodology for discovering constructions
outperforms the results of other proposals in the sense that it is fully
automatic, language independent, and easily replicable in other corpora and
languages. The quality of the results obtained and their wide range of
possible applications confirm the DISCOver methodology as a promising line of
research and DSMs as a good choice for discovering linguistic knowledge.

##  Part II Paraphrase Typology and
Paraphrase Identification

###  Chapter 4 WARP-Text: a Web-Based Tool for Annotating Relationships
between Pairs of Texts

Venelin Kovatchev, M. Antònia Martí, and Maria Salamó

University of Barcelona

Published at

Proceedings of the
27th International Conference on Computational Linguistics: System
Demonstrations, 2018

pp.: 132-136

###### Abstract

We present WARP-Text, an open-source web-based tool for annotating
relationships between pairs of texts. WARP-Text supports multi-layer
annotation and custom definitions of inter-textual and intra-textual
relationships. Annotation can be performed at different granularity levels
(such as sentences, phrases, or tokens). WARP-Text has an intuitive user-
friendly interface both for project managers and annotators. WARP-Text fills a
gap in the currently available NLP toolbox, as open-source alternatives for
annotation of pairs of text are not readily available. WARP-Text has already
been used in several annotation tasks and can be of interest to the
researchers working in the areas of Paraphrasing, Entailment, Simplification,
and Summarization, among others.

####  4.1 Introduction

Multiple research fields in NLP have pairs of texts as their object of study:
Paraphrasing, Textual Entailment, Text Summarization, Text Simplification,
Question Answering, and Machine Translation, among others. All these fields
benefit from high quality corpora, annotated at different granularity levels.
However, existing annotation tools have limited capabilities to process and
annotate such corpora. The most popular state-of-the-art open source tools do
not natively support detailed pairwise annotation and require significant
adaptations and modifications of the code for such tasks.

We present the first version of WARP-Text, an open source111The code is
available at https://github.com/venelink/WARP under Creative Commons
Attribution 4.0 International License. web-based annotation tool, created and
designed specifically for the annotation of relationships between pairs of
texts at multiple layers and at different granularity levels. Our objective
was to create a tool that is functional, flexible, intuitive, and easy to use.
WARP-Text was built using PHP and MySQL standard implementation.

WARP-Text is highly configurable: the administrator interface manages the
number, order, and content of the different annotation layers. The pre-built
layers allow for custom definitions of labels and granularity levels. The
system architecture is flexible and modular, which allows for the modification
of the existing layers and the addition of new ones.

The annotator interface is intuitive and easy to use. It does not require
previous knowledge or extensive annotator training. The interface has already
been used in the task of annotating atomic paraphrases (Kovatchev et al.,
2018a) and is currently being used on two annotation tasks in Text
Summarization. The learning process of the annotators was quick and the
feedback was overwhelmingly positive.

The rest of this article is organized as follows. Section 4.2 presents the
Related Work. Section 4.3 describes the architecture of the interface, the
annotation scheme, the usage cases, and the two interfaces: administrator and
annotator. Finally, Section 4.4 presents the conclusions and the future work.

####  4.2 Related Work

In the last several years, the NLP community has shown growing interest in
tools that are web-based, open source, and multi-purpose: WebAnno (Yimam and
Gurevych, 2013), Inforex (Marcińczuk et al., 2017), and Anafora (Chen and
Styler, 2013). Other popular non web-based annotation systems include GATE
(Cunningham et al., 2011) and AnCoraPipe (Bertrán et al., 2008). These systems
are intended to be feature-rich and multi-purpose. However, in many tasks, it
is often preferable to create a specialized annotation tool to address
problems that are non-trivial to solve using the multi-purpose annotation
tools. One such problem is working with multiple texts in parallel. While
multi-purpose annotation tools can be adapted for such use, this often leads
to a more complex annotation scheme, complicates the annotation process,
requires additional annotator training and post-processing of the annotated
corpora. Toledo et al. (2014) and more recently Nastase et al. (2018),
Batanović et al. (2018), and Arase and Tsujii (2018) emphasize the lack of a
feature-rich open-source tool for annotation of pairs of texts222See also the
discussion about looking for tools for annotating pairs of texts in the
Corpora Mailing List (May 2017):
http://mailman.uib.no/public/corpora/2017-May/026526.html \-
http://mailman.uib.no/public/corpora/2017-May/026619.html. Some of these
authors develop simple custom-made tools with limited re-usability, designed
for for carrying out one specific annotation task. WARP-Text aims to address
this gap in the NLP toolbox by providing a feature rich system which could be
used in all these annotation scenarios.

To the best of our knowledge, the only existing multi-purpose tool that is
designed to work with pairs of text and allows for detailed annotation is CoCo
(España Bonet et al., 2009). It has already been used for annotations in
paraphrasing (Vila et al., 2015) and plagiarism detection (Barrón-Cedeño et
al., 2013). However, CoCo is not open source and is currently not being
supported or updated.

####  4.3 WARP-Text

By addressing various limitations of existing tools, WARP-Text fills a gap in
the state-of-the-art NLP toolbox. It offers project managers and annotators a
rich set of functionalities and features: the ability to work with pairs of
texts simultaneously; multi-layer annotation; annotation at different
granularity levels; annotation of discontinuous scope and long-distance
dependencies; and the custom definition of relationships. WARP-Text consists
of two separate web interfaces: annotator and administrator. In the
administrator interface the project manager configures the annotation scheme,
defines the relationships and sets all parameters for the annotation process.
The annotators work in the annotator interface.

WARP-Text is a tool for qualitative document annotation. It provides a wide
range of configuration options and can be used for fine-grained annotation. It
is best suited to medium sized corpora (containing thousands of small
documents) and is not fully optimized for processing, analyzing, searching,
and annotating large corpora (containing millions of documents). WARP-Text has
full UTF-8 support and is language independent in the sense that it can handle
documents in any UTF-8 supported natural language. So far it has been used to
annotate texts in English, Bulgarian (Cyrillic), and Arabic.

WARP-Text is a multi-user system and provides two different forms of
interaction between the different annotators. In the collaborative mode,
multiple annotators work on the same text and each annotator can see and
modify the annotations of the others. In the independent mode, the annotators
perform the annotation independently from one another. The different
annotations can then be compared in order to calculate inter-annotator
agreement.

#####  4.3.1 Annotation Scheme

The atomic units of the annotation scheme in WARP-Text are relationships. The
properties of the relationships are label and scope. The scope of a
relationship is a list of continuous or discontinuous elements in each of the
two texts. The granularity level of the scope determines the element type. An
element can be the whole text, a sentence, a phrase, a token, or can be
defined manually. A layer in WARP-Text is a set of relationships, whose scopes
belong to the same granularity level333There is no one-to-one correspondence
between granularity level and annotation layer. Each annotation layer is a
sub-task in the main annotation task. Multiple annotation layers can work at
the same granularity level. For example: at layer (1) the annotator annotates
the semantic relations between the tokens in the two texts; at layer (2) the
annotator annotates the scope of negation and the negation cues in the two
texts. Both layer (1) and layer (2) work at the token granularity level.. The
definition of relationships and their grouping into layers is fully
configurable through the administrator interface. WARP-Text supports multi-
layer annotation. That is, the same pair of texts can be annotated multiple
times, at different granularity levels and using different sets of
relationships.

#####  4.3.2 Administrator Interface

The administrator interface has three main modules: a) the dataset management
module, b) the user management module, and c) the layer management module. In
the dataset management module the project manager can: a) import a corpus, in
a delimited text format, for annotation; b) monitor the current annotation
status and statistics; and c) export the annotated corpus as an SQL file or an
XML file. In the user management module the project manager creates new users
and modifies existing ones. In this module the project manager also
distributes the tasks (pairs) among the annotators. In the layer management
module the project manager configures each of the layers and determines the
order of the layers in the annotation process. The project manager configures
for each individual layer: 1) the granularity level; 2) the relationships that
belong to the layer; 3) the sub-relationships or properties of the
relationships; 4) optional parameters such as “sentence lock” and “display
previous layers”.

#####  4.3.3 Annotator Interface

The annotator interface has three main modules: a) the annotation statistics
module, b) the review annotations module, and c) the annotation panel module.
In the annotation statistics module the annotator monitors the progress of the
annotation and sees statistics such as the number of annotated pairs, and the
remaining number of pairs. In the review annotations module the annotator
reviews the text pairs (s)he already annotated and introduces corrections
where necessary. The annotation panel module is the core of the annotator
interface. One of our main objectives in the creation of WARP-Text was to make
it easier to use for the annotators and to optimize the annotation time. For
that reason we have made the annotator panel module as automated as possible
and have limited the intervention of annotators to a minimum. The annotation
panel module is generated dynamically, based on the user and project
configuration. It loads the first text pair, assigned to the current annotator
and guides the annotator through the different layers in the order specified
by the project manager. Once the text pair has been annotated at all
configured layers, the module updates the database, loads the next pair and
repeats the process.

We illustrate the annotation process with the interface configuration that was
used in the annotation of the Extended Typology Paraphrase Corpus (ETPC)
(Kovatchev et al., 2018a). The annotation scheme of ETPC consists of two
layers: one layer that is configured for annotation at the text granularity
level; and one layer that is configured for annotation at the token
granularity level.

Figure 4.1: Annotating relationships at textual level.

The textual layer (Figure 4.1) displays the two texts and allows the annotator
to select the values for an arbitrary number of relationships between the
texts. In the case of ETPC, the two textual relationships that we were
interested in were: 1) “The semantic relationship between the two texts”:
“Paraphrases” or “Non-paraphrases”; and 2) “The presence of negation in either
of the two sentences”: “Yes” or “No”. In ETPC, both relationships had two
possible options, however WARP-Text supports multiple options for each
relationship. In this first layer, the scope of the relationship is the whole
text.

Figure 4.2: Annotating relationships at token level.

The second layer (Figure 4.2) has five functional parts, labeled in the figure
with numbers from 1 to 5. The annotator can see the two texts in (1), the
annotation at the previous layers in (2), and at the annotation at the current
layer in (4). (3) is the navigation panel between the different layers.
Finally, (5) is where the annotator can choose to add a new relationship. The
list of possible relationships is defined by the project manager in the
administrator interface. In the case of ETPC we organized the relationships in
a two-level hierarchical system based on their linguistic meta-category. The
token-layer annotation is more complex than the textual-layer annotation as it
requires the annotation of scope in addition to the annotation a label444The
token level annotation layer is an instance of the more general “atomic level
annotation layer”. The organization and work flow described here are the same
when the granularity level is “paragraph”, “sentence”, “phrase”, or custom
defined.. When the annotator chooses a relationship, the "Add Type" button
goes to the scope selection page (Figure 4.3). The scope can be discontinuous
and can include elements from one of the texts only or from both. In the case
of ETPC, the elements that the annotator can select are tokens. In other
configurations, they can be phrases or sentences.

Figure 4.3: Scope selection page.

The flexibility of WARP-Text makes it easy to adapt for multiple tasks. The
textual layer can be used in tasks such as the annotation of textual
paraphrases, textual entailment, or semantic similarity. The atomic level
annotation layer has even more applications. As we showed in ETPC, it can be
used to annotate fine-grained similarities and differences between pairs of
texts. It can also be used for tasks such as manual correction of text
alignment. Another possible use is, given a summary or a simplified text, to
identify in the reference text the exact sentences or phrases which are
summarized or simplified.

####  4.4 Conclusions and Future Work

In this paper we presented WARP-Text, a web-based tool for annotating
relationships between pairs of texts. Our software fills an important gap as
the high quality annotation of pairwise corpora at different granularity
levels is needed and can benefit multiple fields in NLP. Previously available
tools are not well suited for the task, require substantial modification, or
are hard to configure. The main advantages of WARP-Text are that it is
feature-rich, open source, highly configurable, and intuitive and easy to use.

As future work, we plan to add several functionalities to both interfaces. In
the administrator interface, we plan to offer project managers tools for
visualization and data analysis, and automatic calculation of inter-annotator
agreement. In the annotator interface, we plan to fully explore the advantages
of multi-layer architecture. By design, WARP-Text can support parent-child
dependencies between layers. However, the pre-built modules available in this
first release of the tool use only independent layers. That is, the annotation
at one layer does not affect the configuration of the other layers. We also
plan to explore the possibility of incorporating external automated pre-
processing tools.

###  Chapter 5 ETPC - a Paraphrase Identification Corpus Annotated with
Extended Paraphrase Typology and Negation

Venelin Kovatchev, M. Antònia Martí, and Maria Salamó

University of Barcelona

Published at

Proceedings of the
Eleventh International Conference on Language Resources and Evaluation, 2018

pp.: 1384-1392

###### Abstract

We present the Extended Paraphrase Typology (EPT) and the Extended Typology
Paraphrase Corpus (ETPC). The EPT typology addresses several practical
limitations of existing paraphrase typologies: it is the first typology that
copes with the non-paraphrase pairs in the paraphrase identification corpora
and distinguishes between contextual and habitual paraphrase types. ETPC is
the largest corpus to date annotated with atomic paraphrase types. It is the
first corpus with detailed annotation of both the paraphrase and the non-
paraphrase pairs and the first corpus annotated with paraphrase and negation.
Both new resources contribute to better understanding the paraphrase
phenomenon, and allow for studying the relationship between paraphrasing and
negation. To the developers of Paraphrase Identification systems ETPC corpus
offers better means for evaluation and error analysis. Furthermore, the EPT
typology and ETPC corpus emphasize the relationship with other areas of NLP
such as Semantic Similarity, Textual Entailment, Summarization and
Simplification.

###### Keywords

Paraphrasing, Paraphrase Typology, Paraphrase Identification

####  5.1 Introduction

The task of Paraphrase Identification (PI) consists of comparing two texts of
arbitrary size in order to determine whether they have approximately the same
meaning. The most common approach to PI is as a binary classification problem,
in which a system learns to make correct binary predictions (paraphrase or
non-paraphrase) for a given pair of texts. The task of PI is challenging from
more than one point of view. From the resource point of view, defining the
task and preparing high quality corpora is a non-trivial problem due to the
complex nature of “paraphrasing”. From the application point of view, for a
system to perform well on PI often requires a complex ML architecture and/or a
large set of manually engineered features. From the evaluation point of view,
the classical task of PI does not offer many possibilities for detailed error
analysis, which in turn limits the reusability and the improvement of PI
systems.

In the last few years, researchers in the field of paraphrasing have adopted
the approach of decomposing the meta phenomenon of “textual paraphrasing” into
a set of “atomic paraphrase” phenomena, which are more strictly defined and
easier to work with. “Atomic paraphrases” are hierarchically organized into a
typology, which provides a better means to study and understand paraphrasing.
While the theoretical advantages of these approaches are clear, their
practical implications have not been fully explored. The existing corpora
annotated with paraphrase typology are limited in size, coverage and overall
quality. The only corpus of sufficient size to date annotated with paraphrase
typology is the corpus by Vila et al. (2015), which contains 3900 re-annotated
“textual paraphrase” pairs from the MRPC corpus (Dolan et al., 2004).

The use of a paraphrase typology in practical tasks has several advantages.
First, “atomic paraphrases” are much more strict in their definition, which
makes the results more useful and understandable. Second, the more detailed
annotation can be useful to (re)balance binary PI corpora in terms of type
distribution. Third, annotating a corpus with paraphrase types provides much
better feedback to the PI systems and allows for a detailed, per-type error
analysis. Fourth, enriching the corpus and improving the evaluation can
provide a linguistic insight into the workings of complex machine learning
systems (i.e. Deep Learning) that are traditionally hard to interpret. Fifth,
corpora annotated with a paraphrase typology open the way for new research and
new tasks, such as “PI by type“ or “Atomic PI in context”. Finally,
decomposing “textual paraphrases” can help relate the task of PI to tasks such
as Recognizing Textual Entailment, Text Summarization, Text Simplification,
and Question Answering.

In this paper, we present the Extended Typology Paraphrase Corpus (ETPC), the
result of annotating the MRPC (Dolan et al., 2004) corpus with our Extended
Paraphrase Typology (EPT). EPT is oriented towards practical applications and
takes inspiration from several authors that work on the typology of
paraphrasing and textual entailment. To the best of our knowledge, this is the
first attempt to make a detailed annotation of the linguistic phenomena
involved in both the positive (paraphrases) and negative (non-paraphrases)
examples in the MRPC (for a total size of 5801 textual pairs). The focus on
non-paraphrases and the qualitative and quantitative comparison between
“textual paraphrases” and “textual non-paraphrases” provides a different
perspective on the PI task and corpora.

As a separate layer of annotation, we have identified all pairs of texts that
include negation and we have annotated the negation scope. This makes ETPC the
first corpus that is annotated both with paraphrasing and with negation.

The rest of this article is organized as follows. Section 5.2 is devoted to
the Related Work. Section 5.3 describes the proposed Extended Typology, the
reasons and the practical considerations behind it. Section 5.4 explains the
annotation process, the annotation scheme and instructions, the tool that we
used and the corpus preprocessing. Section 5.5 presents ETPC, with its
structure and type distribution. It discusses the results of the annotation
and outlines some of the practical applications of the corpus. Finally,
Section 5.6 concludes the article and outlines the future work.

####  5.2 Related Work

The task of PI is one of the classical tasks in NLP. Several corpora can be
used in the task for training and/or for evaluation. Traditionally, PI is
addressed using the MRPC corpus (Dolan et al., 2004). The MRPC corpus consists
of 5801 pairs, that have been manually annotated as paraphrases or non-
paraphrases. More recently, Ganitkevitch et al. (2013) introduce PPDB - a very
large automatic collection of paraphrases, which consists of 220 million
pairs. The introduction of PPDB allowed for the training of deep learning
systems, due to the significant increase of the available data. However, the
quality of the PPDB pairs is much lower than those of MRPC, which makes it
less reliable for evaluation. A common approach is to work on both datasets
simultaneously - using the PPDB for training, and the MRPC for development and
evaluation.

Closely related to the PI task is the yearly task of Recognizing Textual
Entailment (RTE) (Dagan et al., 2006), which has also produced various
datasets and multiple practical systems. The meta-phenomena of paraphrasing
and textual entailment are very similar and are often studied together at
least from a theoretical point of view. Androutsopoulos and Malakasiotis
(2010) present a summary of the tasks related to both paraphrasing and textual
entailment.

The idea of decomposing paraphrasing into simpler and easier to define
phenomena has been growing in popularity in the last few years. Bhagat (2009)
and later Bhagat and Hovy (2013) propose a simplified framework that
identifies several possible phenomena involved in the paraphrasing relation.
Vila et al. (2014) propose a more complex, hierarchically structured typology
that studies the different phenomena at the corresponding linguistic levels
(lexical, morphological, syntactic, and discourse). More recently, Benikova
and Zesch (2017) approach the problem by focusing on the paraphrasing at the
level of events, understood as predicate-argument structure.

A similar decomposition tendency is noticed in the field of Textual
Entailment. Garoufi (2007), Sammons et al. (2010), and Cabrio and Magnini
(2014) propose different frameworks for decomposing the textual “inference”
into simple, atomic phenomena. It is important to note that the similarity and
the relation between paraphrasing and textual entailment is even stronger in
the context of the decomposition framework and the resulting typologies. The
two most exhaustive typologies: Vila et al. (2014) for paraphrasing and Cabrio
and Magnini (2014) for textual entailment share the majority of their atomic
phenomena as well as the overall structure and organization of the typology.

One of the advantages of the decomposition approaches is that naturally they
work towards bridging the gap between the research at different granularity
levels. A corpora annotated with semantic relations at both the textual and
the atomic (morphological, lexical, syntactic, discourse) levels can be a
valuable resource for studying the relation between them. In this same line of
work, Shwartz and Dagan (2016) emphasize the importance of studying lexical
entailment “in context” and the lack of resources that can enable such work.
The corpora annotated with atomic paraphrase and atomic entailment phenomena
can be used for that purpose without adaptation or additional annotation.

The application of paraphrase typology for the creation of resources and in
practical tasks is still very limited. Most of the authors annotate a very
small subsamples of around 100 text pairs to illustrate the proposed typology.
The largest available corpus annotated with paraphrase types to date is the
one of Vila et al. (2015). Barrón-Cedeño et al. (2013) use this corpus to
demonstrate some possible uses of the decomposition approach to paraphrasing.

####  5.3 Extended Paraphrase Typology

We propose the Extended Paraphrase Typology (EPT), which was created to
address several of the practical limitations of the existing typologies and to
provide better resources to the NLP community. EPT ha better coverage than
previous typologies, including the annotation of non-paraphrases. This allows
for a more in-depth understanding of the meta-phenomena and of the relation
between “textual paraphrases” and “atomic paraphrases”.

#####  5.3.1 Basic Terminology

In order to discuss the issues and limitations of existing paraphrase
typologies, we first define “paraphrasing”, “textual paraphrase”, and “atomic
paraphrase”.

We understand “paraphrasing” to be a specific semantic relation between two
texts of arbitrary length. The two texts that are connected by a paraphrase
relation have approximately the same meaning. We call them “textual
paraphrases”. There is no limitation for “textual paraphrases” in terms of the
nature of the linguistic phenomena involved. The concept of “textual
paraphrases” is a practical simplification of a complex linguistic phenomenon,
which is adopted in most paraphrase-related tasks, datasets, and applications.
The original annotation of the MRPC and the PPDB corpora is built around the
notion of textual paraphrases. Another term that we use in the article is
“textual non-paraphrases”. With this term we refer to pairs of texts (of
arbitrary length), which are not connected by a paraphrase relation.

“Atomic paraphrases” are paraphrases of a particular type. They must satisfy
specific (linguistic) conditions, defined in the paraphrase typology. “Atomic
paraphrases” are identified by the linguistic phenomenon which is responsible
for the preservation of the meaning between the two texts. “Atomic
paraphrases” have a (linguistically defined) scope, such as a word, a phrase,
an event, or a discourse structure. The most complete typologies to date
organize “atomic paraphrases” hierarchically, in terms of the linguistic level
of the involved phenomenon. Unlike “textual paraphrases”, “atomic paraphrases”
cannot be of arbitrary length. Their length is defined and restricted by their
scope.

#####  5.3.2 From Atomic to Textual Paraphrases

The relation between textual and atomic paraphrases is not easy to define and
explore. It poses many challenges to the researchers, annotators, and
developers of practical systems. In this section, we illustrate several issues
that we want to address with the creation of the EPT and the ETPC.

The first issue to be addressed is that multiple atomic paraphrases can appear
in a single textual paraphrase pair. The two texts in 1a and 1b are textual
paraphrases111All examples in this subsection are from the MRPC corpus. When
we say that the texts are textual paraphrases or textual non-paraphrases, we
refer to the labels corresponding to these pairs in MRPC.. However, they
include more than one atomic paraphrase’: “magistrate” and “judge” are an
instance of “same polarity substitution”, while “A federal magistrate …
ordered” and “Zuccarini was ordered by a federal judge…” are an instance of
“diathesis alternation”222These types and annotation are from Vila et al.
(2015)..

  * 1a

A federal magistrate in Fort Lauderdale ordered him held without bail.

  * 1b

Zuccarini was ordered held without bail Wednesday by a federal judge in Fort
Lauderdale, Fla.

Second issue is that atomic paraphrases can appear in textual pairs that are
not paraphrases. The two texts in 2a and 2b as a whole are not textual
paraphrases, even if they have a high degree of lexical overlap and a similar
syntactic structure. However, “Microsoft” and “shares of Microsoft” are an
instance of “same polarity substitution” \- both phrases have the same role
and meaning in the context of the two sentences. This demonstrates the
possibility of atomic paraphrases being present in textual non-paraphrases.
333In fact, it is possible to find atomic paraphrases within pairs of texts
connected by various relations, such as entailment, simplification,
summarization, contradiction, and question-answering, among others. This is
illustrated by the significant overlap of atomic types in Paraphrase Typology
research and typology research in Textual Entailment.

  * 2a

Microsoft fell 5 percent before the open to $27.45 from Thursday’s close of
$28.91.

  * 2b

Shares in Microsoft slipped 4.7 percent in after-hours trade to $27.54 from a
Nasdaq close of $28.91.

Third issue is that in certain cases, the semantic relation between the
elements in an atomic paraphrase can only be interpreted within the context
(as shown in the work of Shwartz and Dagan (2016)). The two texts in 3a and 3b
are textual paraphrases. The out-of-context meaning of “cargo” and
“explosives” differs significantly, however within the given context, they are
an instance of “same polarity substitution”.

  * 3a

They had published an advertisement on the Internet on June 10, offering the
cargo for sale, he added.

  * 3b

On June 10, the ship’s owners had published an advertisement on the Internet,
offering the explosives for sale.

And finally, 4a and 4b illustrate an issue that is often overlooked in
theoretical paraphrase research: the linguistic phenomena behind certain
atomic paraphrases do not always preserve the meaning. The meanings of “beat”
and “battled” are similar, and play the same syntactic and discourse role in
the structure of the texts. Therefore, the substitution of “beat” for
“battled” fulfills the formal requirements of a “same polarity substitution”.
However, after this substitution, the resulting texts are not paraphrases as
they differ substantially in meaning.

  * 4a

He beat testicular cancer that had spread to his lungs and brain.

  * 4b

Armstrong, 31, battled testicular cancer that spread to his brain.

#####  5.3.3 Objectives of EPT and Research Questions.

We argue that the objectives behind a paraphrase typology are twofold: 1) to
classify and describe the linguistic phenomena involved in paraphrasing (at
the atomic level); and 2) to provide the means to study the function of atomic
paraphrases within pairs of texts of arbitrary size and with various semantic
relations (such as, textual paraphrases, textual entailment pairs,
contradictions, and unrelated texts).

Traditionally, the authors of paraphrase typologies have focused on the first
objective while the latter is mentioned only briefly or ignored altogether. In
our work, we want to extend the existing work on paraphrase typology in the
direction of Objective 2, as we argue that it is crucial for applications. We
pose four research questions, that we aim to address with the creation of EPT
and ETPC:

  * RQ1

what is the relation between atomic and textual paraphrases considering the
distribution of atomic paraphrases in textual paraphrases?

  * RQ2

what is the relation between atomic paraphrases and textual non-paraphrases
considering the distribution of atomic paraphrases in textual non-paraphrases?

  * RQ3

what is the role of the context in atomic paraphrases?

  * RQ4

in which cases do the linguistic phenomena behind an atomic paraphrase
preserve the meaning and in which they do not?

#####  5.3.4 The Extended Paraphrase Typology

The full Extended Paraphrase Typology is shown in Table 5.1. It is organized
in seven meta categories: “Morphology”, “Lexicon”, “Lexico-syntax”, “Syntax”,
“Discourse”, “Other”, and “Extremes”. Sense Preserving (Sens Pres.) shows

ID | Type |  | Sense
---
Pres.
Morphology-based changes
1 | Inflectional changes | \+ / -
2 | Modal verb changes | +
3 | Derivational changes | +
Lexicon-based changes
4 | Spelling changes | +
5 | Same polarity substitution (habitual) | +
6 | Same polarity substitution (contextual) | \+ / -
7 | Same polarity sub. (named entity) | \+ / -
8 | Change of format | +
Lexico-syntactic based changes
9 | Opposite polarity sub. (habitual) | \+ / -
10 | Opposite polarity sub. (contextual) | \+ / -
11 | Synthetic/analytic substitution | +
12 | Converse substitution | \+ / -
Syntax-based changes
13 | Diathesis alternation | \+ / -
14 | Negation switching | \+ / -
15 | Ellipsis | +
16 | Coordination changes | +
17 | Subordination and nesting changes | +
Discourse-based changes
18 | Punctuation changes | +
19 | Direct/indirect style alternations | \+ / -
20 | Sentence modality changes | +
21 | Syntax/discourse structure changes | +
Other changes
22 | Addition/Deletion | \+ / -
23 | Change of order | +
24 | Semantic (General Inferences) | \+ / -
Extremes
25 | Identity | +
26 | Non-Paraphrase | -
27 | Entailment | -
Table 5.1: Extended Paraphrase Typology

whether a certain type can give raise to textual paraphrases (+), to textual
non-paraphrases (-), or to both (+ / -)444A more detailed table of EPT, with
additional examples for each atomic type is available at
https://github.com/venelink/ETPC and in Appendix A of the thesis.. The
typology contains 25 atomic paraphrase types (+) and 13 atomic non-paraphrase
types (-). It is based on the work of Vila et al. (2014) and aims to extend it
in two directions in order to address the four Research Questions.

First, we have added three new atomic paraphrase types - we split the atomic
types “same polarity substitution” and “opposite polarity substitution” into
two separate types based on the nature of the relation between the substituted
words: “habitual” and “contextual”. We have also added the type “same polarity
substitution (named entity)”. While the principle behind all substitutions is
the same, in practice there is a significant difference whether the replaced
words are connected in their habitual meaning, contextually, or refer to
related named entities in the world. Instances of the new types can be seen in
sentence pairs 5 (“same polarity substitution (habitual)”), 6 (“same polarity
substitution (contextual)”), 7 (“same polarity substitution (named entity”), 8
(“opposite polarity substitution (habitual)”), and 9 (“opposite polarity
substitution (contextual)”)

  * 5a

A federal magistrate in Fort Lauderdale ordered him held without bail.

  * 5b

Zuccarini was ordered held without bail Wednesday by a federal judge in Fort
Lauderdale, Fla.

  * 6a

Meanwhile, the global death toll approached 770 with more than 8,300 people
sickened since the severe acute respiratory syndrome virus first appeared in
southern China in November.

  * 6b

The global death toll from SARS was at least 767, with more than 8,300 people
sickened since the virus first appeared in southern China in November.

  * 7a

He told The Sun newspaper that Mr. Hussein’s daughters had British schools and
hospitals in mind when they decided to ask for asylum.

  * 7b

“Saddam’s daughters had British schools and hospitals in mind when they
decided to ask for asylum – especially the schools,” he told The Sun.

  * 8a

Leicester failed in both enterprises.

  * 8b

He did not succeed in either case.

  * 9a

A big surge in consumer confidence has provided the only positive economic
news in recent weeks.

  * 9b

Only a big surge in consumer confidence has interrupted the bleak economic
news.

Second, we have introduced the “sense preserving” feature in 13 of the atomic
types. As we have shown in the previous section (examples 4a and 4b), the same
atomic linguistic transformation (such as substitution, diathesis alternation,
and negation switching) can give raise to different semantic relations at
textual level: paraphrasing, entailment, and contradiction, among others. This
idea has already been expressed by Cabrio and Magnini (2014) in the field of
Recognizing Textual Entailment. Building on this idea, we identify 13 atomic
types that can, in different instances, give rise to both paraphrases and non-
paraphrases. Sentence pairs 10 and 11 show an example of sense preserving and
non-sense preserving ”Inflection change” types. In 10a and 10b, both “streets”
and “street” are a generalization with the meaning “all streets”. In a similar
way, in 11b, “boats” has the meaning as “all boats”. However in 11a, “boat”
can have the meaning “one particular boat”, thus the inflectional change “boat
- boats” is not sense-preserving.

  * 10a

It was with difficulty that the course of streets could be followed.

  * 10b

You couldn’t even follow the path of the street.

  * 11a

You can’t travel from Barcelona to Mallorca with the boat.

  * 11b

Boats can’t travel from Barcelona to Mallorca.

The changes introduced in EPT allow us to work on all four Research Questions
(RQs) defined in Section 5.3.3 This is a clear advantage over the existing
paraphrase typologies, which are only suitable for addressing RQ1. For RQ1, we
annotated all atomic types in the positive (“paraphrases”) portion of MRPC and
measured their distribution. For RQ2, we annotated all atomic types in the
negative (“non-paraphrases”) portion of MRPC and compared the distribution of
the types in the positive and negative portions. For RQ3, the two newly added
“contextual” types allow us to distinguish and compare context dependent from
context independent atomic paraphrases. Finally, for RQ4, the addition of
“sense preserving” allows us to annotate, isolate and compare the sense
preserving and non-sense preserving instances of the same linguistic
phenomena.

####  5.4 Annotation Scheme and Guidelines

We propose the Extended Paraphrase Typology (EPT) with a clear practical
objective in mind: to create language resources that improve the performance,
evaluation, and understanding of the systems competing on the task of PI and
to open new research directions. We used the EPT to annotate the MRPC corpus
with atomic paraphrases. We annotated all 5801 text pairs in the corpus,
including both the pairs annotated as paraphrases (3900 pairs) and those
annotated as non-paraphrases (1901 pairs).

As a basis, we used the MRPC-A corpus by Vila et al. (2015), which already
contains some annotated atomic paraphrases. Our annotation consisted of three
steps, corresponding to the three different layers of annotation.

First, we annotated the non-sense preserving atomic phenomena (Section 5.4.1)
in the textual non-paraphrases. Second, we annotated the sense preserving
atomic paraphrase phenomena (Section 5.4.2) in both textual paraphrases and
textual non-paraphrases. And third, we identified all sentences in the corpus
containing negation, and explicitly annotated the negation scope (Section
5.4.4).

For the purpose of the annotation, we created a web-based annotation tool,
Pair-Anno, capable of annotating aligned pairs of discontinuous scopes in two
different texts555Screenshots of Pair-Anno can be seen at
https://github.com/venelink/ETPC.. As the scope of each atomic phenomena is
one or more sets of tokens, prior to the annotation we automatically tokenized
the corpus using NLTK (Bird et al., 2009).

#####  5.4.1 Non-Sense Preserving Atomic Phenomena

Textual non-paraphrases in the MRPC corpus typically have a very high degree
of lexical overlap and a similar syntactic and discourse structure. Normally,
they differ only by a few elements (morphological, lexical, or structural),
but the modification of these few elements leads to a substantial difference
in the meaning of the two texts as a whole. The annotation of non-sense
preserving phenomena aims to identify these key elements and study the
linguistic nature of the modification.

When annotating atomic phenomena, our experts identified and annotated the
type, the scope, and in some paraphrase types, the key element. Both the scope
and the key are kept as a 0-indexed list of tokens. Examples 12a and 12b show
a textual pair, annotated as non-paraphrase in the MRPC corpus. Table 5.2
shows the annotation of non-sense preserving atomic phenomena in 12a and 12b.
The key differences are “opposite polarity substitution (habitual)” (type id
10) of “slip” with “rise”, and the “same polarity substitution (named entity)”
(type id 7) of “Friday” with “Thursday”.

  * 12a

The loonie , meanwhile , continued to slip in early trading Friday .

  * 12b

The loonie , meanwhile , was on the rise again early Thursday .

type | pair | s1 scope | s2 scope | s1 text | s2 text
---|---|---|---|---|---
7 | 146 | 11 | 11 | Friday | Thursday
10 | 146 | 7 | 8 | slip | rise
Table 5.2: Non-sense preserving phenomena

The annotation of 12a and 12b illustrates one of the issues when annotating
non-sense preserving phenomena. In many textual pairs, there is more than one
“key” difference. In those cases, all of the phenomena were annotated
separately. Nevertheless, the annotators were instructed to be conservative
and only annotate phenomena that carry substantial differences in the meaning
of the two texts. Determining which differences are substantial, and which are
not was the main challenge for the annotators. Due to the difficulty of the
task, we selected annotators that were expert linguists with a high
proficiency of English666The full annotation guidelines for both sense
preserving and non-sense preserving phenomena can be found at
https://github.com/venelink/ETPC and in Appendix A of the thesis..

When the two texts were substantially different and it was not possible to
identify the atomic phenomena responsible for the difference, the pair was
annotated with atomic type “non-paraphrase” (examples 13a and 13b) or
“entailment” (examples 14a and 14b).

  * 13a

That compared with $35.18 million, or 24 cents per share, in the year-ago
period.

  * 13b

Earnings were affected by a non-recurring $8 million tax benefit in the year-
ago period.

  * 14a

The year-ago comparisons were restated to include Compaq results.

  * 14b

The year-ago numbers do not include figures from Compaq Computer.

#####  5.4.2 Sense Preserving Atomic Phenomena

For the annotation of the sense preserving atomic phenomena, we used the same
annotation scheme format as the one for the non-sense preserving phenomena.
Each phenomenon is identified by a type, a scope, and, where applicable, a
key. 15a and 15b show a textual pair, annotated as a paraphrase in the MRPC.
An example of a single annotated atomic phenomenon can be seen in Table 5.3

  * 15a

Amrozi accused his brother , whom he called “ the witness ” , of deliberately
distorting his evidence .

  * 15b

Referring to him as only “ the witness ” , Amrozi accused his brother of
deliberately distorting his evidence .

type | pair | s1 scope | s2 scope | s1 text | s2 text
---|---|---|---|---|---
6 | 1 | 5 | 1, 2 | whom | to him
Table 5.3: Sense preserving phenomenon

For the 3900 text pairs already annotated by Vila et al. (2015), we worked
with the existing corpus and we only re-annotated the 3 new sense preserving
paraphrase types introduced in EPT. For the 1901 textual non-paraphrases,
which were not annotated in MRPC-A, we performed a full annotation with all 25
sense preserving atomic types.

#####  5.4.3 Inter-Annotator Agreement

In this section, we present the measures for calculating the inter-annotator
agreement and the agreement score on the first two layers of annotation: non-
sense preserving atomic phenomena and sense preserving atomic phenomena.

The measure that we use is the IAPTA TPO, introduced by Vila et al. (2015). It
is a fine-grained measure, created specifically for the task of annotating
paraphrase types. It takes into account the agreement with respect to both the
label and the scope of the phenomena. It is a pairwise agreement measure,
obtained by calculating the Precision, Recall and F1 of one of the annotators,
while using another annotator as a gold standard. There are two versions of
the measure - TPO-partial, which requires that the annotators select the same
label and that the scopes overlap by at least one token; and TPO-total which
requires full overlap of label and scope.

The classical TPO measures are pairwise, they calculate the agreement between
two annotators. When the annotation process involves more than two annotators,
we first calculate the pairwise TPO measure between any two annotators and
then we use one of three different techniques for calculating the overall
agreement for the corpus. TPO (avg) is the most simple score, as it is the
average of all pairwise TPO scores. TPO (union) is the union of all pairwise
TPO agreement tables. That is, any phenomena that is annotated with the same
label and the same scope by any 2 annotators is part of the TPO (union).
Finally, TPO (gold) is the average F1 score of the three annotators, when
treating TPO (union) as a gold standard. TPO (union) and TPO (gold) are two
new measures, that we propose as part of this paper. TPO (union) represents
all the “high quality” phenomena (that is, phenomena annotated the same way by
multiple annotators). TPO (gold) represents the probability that any of our
annotators would annotate “high quality” phenomena.

The annotation of the sense preserving atomic paraphrases was carried out by
two expert annotators, while the annotation of the non-sense preserving atomic
phenomena was carried out by three expert annotators. For the purpose of
calculating the inter-annotator agreement, all experts were given the same 180
text pairs (roughly 10 % of all non-paraphrase pairs in the corpus). The pairs
were split in 3 equal parts and given to the annotators in three different
stages of the annotation: one at the beginning, one in the middle, and one at
the end of the annotation process. Table 5.4 shows the obtained scores, where
ETPC (-) stands for the non-sense preserving layer, ETPC (+) stands for the
sense-preserving layer of annotation and MRPC-A is the annotation of Vila et
al. (2015). For ETPC (+) we only had two annotators, so we were not able to
calculate TPO (union) and TPO (gold). Since these measures have been
introduced by us in the current paper, the MRPC-A corpus by Vila et al. (2015)
does not have values for them either.

Measure | ETPC (-) | ETPC (+) | MRPC-A
---|---|---|---
TPO-partial (avg) | 0.72 | 0.86 | 0.78
TPO-total (avg) | 0.68 | 0.68 | 0.51
TPO (union) | 0.77 | n-a | n-a
TPO (gold) | 0.86 | n-a | n-a
Table 5.4: Inter-annotator Agreement

ETPC (+) and MRPC-A are directly comparable as they measure the agreement on
the same task (annotation of sense-preserving atomic phenomena). The results
show much higher agreement score with respect to both TPO-partial (0.86
against 0.78) and TPO-total (0.68 against 0.51). ETPC (-) measures the
agreement on a different task (annotation of non-sense preserving phenomena).
The TPO-partial score of ETPC (-) is lower than both ETPC (+) and MRPC-A (0.72
against 0.86 and 0.78 respectively), however the TPO-total score is equal to
that of ETPC (+) and much higher than that of MRPC-A. It is interesting to
note that there is almost no difference between TPO-partial and TPO-total for
ETPC (-) (0.72 against 0.68), while for ETPC (+) and MRPC-A, the difference is
significant. The TPO (union) for ETPC (-) shows that 77% of all phenomena are
annotated the same way by at least 2 of the annotators. The TPO (gold)
indicates that the probability of any of our experts annotating a “gold”
example is 86%. Considering the difficulty of the task, the obtained results
indicate the high quality of the annotated corpus.

#####  5.4.4 Annotation of Negation

During the first two steps of the annotation, we identified all sentences that
contain negation. For every instance of negation we annotated the negation
cues and the scope of negation. 16a and 16b illustrate an example of annotated
negation.

  * 16a

(Moore had (no [negation marker]) immediate comment Tuesday [scope])

  * 16b

(Moore (did not [negation marker]) have an immediate response Tuesday [scope])

####  5.5 The ETPC Corpus

This section presents the results of the annotation of the ETPC corpus.
Section 5.5.1 shows the results of annotating non-sense preserving phenomena.
Section 5.5.2 shows the results of annotating sense preserving phenomena.
Section 5.5.3 discusses the results and the Research Questions, and Section
5.5.4 lists some applications of ETPC.

#####  5.5.1 Non-Sense Preserving Atomic Phenomena

Table 5.5 shows the distribution of the non-sense preserving phenomena. Type
Relative Frequency (Type RF) shows the relative distribution of the atomic
types. Occurrence Frequency (Type OF) shows the distribution of phenomena per
sentence, that is in how many textual pairs each phenomenon can be found777The
sum of all Occurrence Frequencies exceeds 100, as one sentence often contains
more than one atomic phenomenon.. The total number of non-sense preserving
phenomena is 3406 in 1901 text pairs.

Type | Type RF | Type OF
---|---|---
Inflectional | 0.02% | 0.04%
Same Polarity (con) | 9.3% | 15.5%
Same Polarity (ne) | 27.5% | 22.5%
Opp Polarity (hab) | 2.7% | 4.4%
Opp Polarity (con) | 0.01% | 0.02%
Converse | 0.01% | 0.02%
Diathesis | 0.01% | 0.01%
Negation | 0.02% | 0.03%
Direct/Indirect | 0% | 0%
Addition/Deletion | 52% | 65.5%
Semantic based | 0% | 0%
Non-paraphrase | 7.6% | 13.7%
Entailment | 0.02% | 0.04%
Table 5.5: Distribution of non-sense preserving phenomena

Both Type Relative Frequency (RF) and Occurrence Frequency (OF) indicate that
the non-paraphrase portion of the corpus is not well balanced with respect to
atomic phenomena. In 260 of the text pairs (13.7%), the annotators selected
“non-paraphrase” indicating that the two texts were substantially different.
In the rest of the pairs, the most common reason for the “non-paraphrase”
label at textual level was “Addition/Deletion” (52% RF, 65.5% OF), followed by
“Same polarity substitution (named entity)” (27% RF, 22.5% OF), “Same polarity
substitution (contextual)” (RF 9,3%, OF 15.5%), and “Opposite polarity
substitution (habitual)” (RF 2.8%, OF 4.6%). These are the only types with
Type Relative Frequency and Occurrence Frequency above 1%, and they constitute
over 99% of all non-sense preserving atomic phenomena annotated in the corpus.
Six of the atomic phenomena are represented only with a few examples, while
two are not represented at all.

#####  5.5.2 Sense Preserving Atomic Phenomena

Table 5.6 shows the distribution of sense preserving atomic phenomena in the
textual paraphrase and non-paraphrase portions of the corpus888At the time of
the submission of this paper, the annotation of the non-paraphrase portion was
not finished. The reported results are for 500 annotated pairs (about 30% of
the corpus). The full figures will be made available at
https://github.com/venelink/ETPC. For the textual paraphrase portion, we used
the numbers reported by Vila et al. (2015) with partial re-annotation to
account for the new types in ETPC. For “same polarity substitution”, 35% of
the phenomena were re-annotated as “habitual”, 47% as “contextual”, and 18% as
“named entity”. For “opposite polarity substitution” 21% of the phenomena were
“contextual” and 79% of the phenomena were “habitual”.

Type |  | Non
---
Paraphrase
Paraphrase
Inflectional | 2.13% | 2.78%
Modal verb | 0.59% | 0.83%
Derivational | 0.35% | 0.85%
Spelling changes | 1.30% | 2.91%
Same Polarity (hab) | 10.55% | 8.68%
Same Polarity (con) | 11.15% | 11.66%
Same Polarity (ne) | 7.11% | 5.08%
Format | 1.06% | 1.1%
Opp Polarity (hab) | 0% | 0.07%
Opp Polarity (con) | 0% | 0.02%
Synthetic/analytic | 7.82% | 3.80%
Converse | 0.12% | 0.20%
Diathesis | 0.83% | 0.73%
Negation | 0% | 0.09%
Ellipsis | 0.47% | 0.30%
Coordination | 0.24% | 0.22%
Subord. and nesting | 1.18% | 2.14%
Punctuation | 2.72% | 3.77%
Direct/Indirect | 0.24% | 0.30%
Sentence modality | 0% | 0%
Synt./Disc. structure | 1.30% | 1.39%
Addition/Deletion | 20.04% | 25.94%
Change of order | 3.08% | 3.89%
Semantic | 0% | 1.53%
Identity | 25.02% | 17.54%
Non-Paraphrase | 2.49% | 3.81%
Entailment | 0.12% | 0.37%
Table 5.6: Distribution of Sense preserving phenomena in textual paraphrases
and textual non-paraphrases

The results show that the distribution of sense-preserving phenomena is
relatively consistent between the two portions of the corpus. The most notable
differences between the two distributions are the frequencies of “same
polarity substitution (named entity)”, “synthetic/analytic”,
“addition/deletion”, and “identity”. Both distributions are not well balanced
in terms of atomic types, with 8 types (“addition/deletion”, “identity”, “same
polarity substitution (contextual)”, “same polarity substitution (habitual)”,
“synthetic/analytic”, “same polarity substitution (named entity)”, “change of
order”, and “punctuation”) responsible for over 80% of the phenomena.

#####  5.5.3 Discussion

In this section we briefly discuss the annotation results and the Research
Questions that we posed in Section 5.3.3

With respect to RQ1 and RQ2, we measured the raw frequency distribution of the
sense preserving atomic phenomena in both the paraphrase and non-paraphrase
portions of the corpus. We make two important observations from the data.
First, the corpus is not well balanced in terms of type distribution in either
of the portions. It can be seen in Table 5.6 that 8 of the types are
overrepresented while the rest are underrepresented. This imbalance is even
more significant in terms of meta-categories. The structure meta-types
“syntax” and “discourse” account for less than 10 % of all types. Second, the
raw frequency distribution of atomic phenomena in textual paraphrases and
textual non-paraphrases is very similar. This finding suggests that it is the
non-sense preserving phenomena that are mostly responsible for the relation at
textual level in this corpus. This makes the annotation of the non-sense
preserving phenomena even more important for the PI task.

With respect to RQ3, we annotated the “same polarity substitution
(contextual)” and “opposite polarity substitution (contextual) ” types in all
portions of the corpus. For “same polarity substitution”, over 40% of the
sense-preserving and over 25% of the non-sense preserving instances were
contextual. For “opposite polarity substitution”, 21% of the sense-preserving
instances were annotated as contextual, while in the non-sense preserving
portion we found almost no contextual instances.

With respect to RQ4, we measured the raw frequency distribution of the non-
sense preserving phenomena. If we compare it with the distribution of sense
preserving phenomena, we can see that the differences are noteworthy and we
can easily differentiate between the two distributions. Non-sense preserving
phenomena are even less balanced than sense preserving phenomena, with just 4
types responsible for almost all instances. The structure types “syntax” and
“discourse” are not represented at all, with all frequent types being either
“lexical”, “lexico-syntactic”, or “other”.

Finally, it is worht mentioning that 13% of the sentences in the textual
paraphrase portion of the corpus and 12% of the sentences in the textual non-
paraphrase portion contain negation. The relative distribution in the
paraphrase and in the non-paraphrase portion of the corpus is consistent. The
negation scope for each of these sentences has been annotated in a separate
layer.

#####  5.5.4 Applications of ETPC

The ETPC corpus has clear advantages over the currently available PI corpora,
and the MRPC in particular. It is much more informative and can be used in
several ways.

First, ETPC can be used as a single PI corpus. The annotation with atomic
types makes it much more informative for evaluation than any other existing PI
corpus. PI systems are currently evaluated in terms of binary Precision,
Recall, F1 and Accuracy. ETPC provides the developers with much more detailed
information, without requiring any additional work on the developers’ side.
Knowing which atomic types are involved in the correct and incorrect
classification helps the error analysis and should lead to an improvement in
the these systems’ performance. It also promotes reusability.

Second, ETPC can be used to provide quantitative and qualitative analysis of
the MRPC corpus, as we have already shown in section 5.5.3 By having a
detailed statistical analysis of the content of the corpus we can identify
possible biases and promote the creation of better and more balanced corpora.

Third, ETPC can be easily split into various smaller corpora built around a
certain atomic type or a class of types. Each of them can be used for a new
task of Atomic Paraphrase Identification. It can be used to study the nature
of the relation between atomic paraphrases and textual paraphrases.

Finally, ETPC can be used to study the role of negation in PI, a research
question that, to date, has received very little attention.

####  5.6 Conclusions and Future Work

In this paper we presented the ETPC corpus - the largest corpus annotated with
detailed paraphrase typology to date. For the annotation we used the new
Extended Paraphrase Typology, a practically oriented typology of atomic
paraphrases. The annotation process included three expert linguists and
covered the whole 5801 text pairs from the MRPC corpus. The full corpus is
publicly available in two formats: SQL and XML999We have also made publicly
available all complementary data, such as annotation guidelines, screenshots
of the interface, detailed statistics, as well as the ETPC_Neg corpus,
composed only from the paraphrase and non-paraphrase pairs containing negation
( https://github.com/venelink/ETPC )..

ETPC is a high quality resource for paraphrase related research and the task
of PI. It provides more in-depth analysis of the existing corpora and promotes
better understanding of the phenomena, the data, and the task. It also
identifies several problems, such as the under-representation of structure
based types and the over-representation of lexical based types. ETPC sets an
example for the development of new feature-rich corpora for paraphrasing
research. It also promotes collaboration between similar areas, such as PI,
RTE and Semantic Similarity.

Our work opens several lines of future research. First, the ETPC can be used
to re-evaluate existing state-of-the-art PI systems. This detailed evaluation
can lead to improvements of the existing PI systems and the creation of new
ones. Second, it can be used to create new corpora for paraphrase research,
which will be more balanced in terms of type distribution. Third, it can be
used to study the nature of the paraphrase phenomenon and the relation between
“atomic” and “textual” paraphrases. Finally, the EPT and ETPC can be extended
to other research areas, such as lexical and textual entailment, semantic
similarity, simplification, summarization, and question answering, among
others.

###  Chapter 6 A Qualitative Evaluation Framework for Paraphrase
Identification

Venelin Kovatchev, M. Antònia Martí, Maria Salamó, and Javier Beltran

University of Barcelona

Published at

Proceedings of the
Twelfth Recent Advances in Natural Language Processing Conference, 2019

pp.: 569-579

###### Abstract

In this paper, we present a new approach for the evaluation, error analysis,
and interpretation of supervised and unsupervised Paraphrase Identification
(PI) systems. Our evaluation framework makes use of a PI corpus annotated with
linguistic phenomena to provide a better understanding and interpretation of
the performance of various PI systems. Our approach allows for a qualitative
evaluation and comparison of the PI models using human interpretable
categories. It does not require modification of the training objective of the
systems and does not place additional burden on the developers. We replicate
several popular supervised and unsupervised PI systems. Using our evaluation
framework we show that: 1) Each system performs differently with respect to a
set of linguistic phenomena and makes qualitatively different kinds of errors;
2) Some linguistic phenomena are more challenging than others across all
systems.

####  6.1 Introduction

In this paper we propose a new approach to evaluation, error analysis and
interpretation in the task of Paraphrase Identification (PI). Typically, PI is
defined as comparing two texts of arbitrary size in order to determine whether
they have approximately the same meaning (Dolan et al., 2004). The two texts
in 1a and 1b are considered paraphrases, while the two texts at 2a and 2b are
non-paraphrases.111Examples are from the MRPC corpus (Dolan et al., 2004) In
1a and 1b there is a change in the wording (“magistrate” - “judge”) and the
syntactic structure (“was ordered” - “ordered”) but the meaning of the
sentences is unchanged. In 2a and 2b there are significant differences in the
quantities (“5%” - “4.7%” and “$27.45” - “$27.54”).

  * 1a

A federal magistrate in Fort Lauderdale ordered him held without bail.

  * 1b

He was ordered held without bail Wednesday by a federal judge in Fort
Lauderdale, Fla.

  * 2a

Microsoft fell 5 percent before the open to $27.45 from Thursday’s close of
$28.91.

  * 2b

Shares in Microsoft slipped 4.7 percent in after-hours trade to $27.54 from a
Nasdaq close of $28.91.

The task of PI can be framed as a binary classification problem. The
performance of the different PI systems is reported using the Accuracy and F1
score measures. However this form of evaluation does not facilitate the
interpretation and error analysis of the participating systems. Given the Deep
Learning nature of most of the state-of-the-art systems and the complexity of
the PI task, we argue that better means for evaluation, interpretation, and
error analysis are needed. We propose a new evaluation methodology to address
this gap in the field. We demonstrate our methodology on the ETPC corpus
(Kovatchev et al., 2018a) \- a recently published corpus, annotated with
detailed linguistic phenomena involved in paraphrasing.

We replicate several popular state-of-the-art Supervised and Unsupervised PI
Systems and demonstrate the advantages of our evaluation methodology by
analyzing and comparing their performance. We show that while the systems
obtain similar quantitative results (Accuracy and F1), they perform
differently with respect to a set of human interpretable linguistic categories
and make qualitatively different kinds of errors. We also show that some of
the categories are more challenging than others across all evaluated systems.

####  6.2 Related Work

The systems that compete on PI range from using hand-crafted features and
Machine Learning algorithms (Fernando and Stevenson, 2008; Madnani et al.,
2012; Ji and Eisenstein, 2013) to end-to-end Deep Learning models (He et al.,
2015; He and Lin, 2016; Wang et al., 2016; Lan and Xu, 2018b; Kiros et al.,
2015; Conneau et al., 2017). The PI systems are typically divided in two
groups: Supervised PI systems and Unsupervised PI systems.

“Supervised PI systems” (He et al., 2015; He and Lin, 2016; Wang et al., 2016;
Lan and Xu, 2018b) are explicitly trained for the PI task on a PI corpora.
“Unsupervised PI systems” in the PI field is a term used for systems that use
a general purpose sentence representations such as Mikolov et al. (2013b);
Pennington et al. (2014); Kiros et al. (2015); Conneau et al. (2017). To
predict the paraphrasing relation, they can compare the sentence
representations of the candidate paraphrases directly (ex.: cosine of the
angle), and use a PI corpus to learn a threshold. Alternatively they can use
the representations as features in a classifier.

The complexity of paraphrasing has been emphasized by many researchers (Bhagat
and Hovy, 2013; Vila et al., 2014; Benikova and Zesch, 2017). Similar
observations have been made for Textual Entailment (Sammons et al., 2010;
Cabrio and Magnini, 2014). Gold et al. (2019) study the interactions between
paraphrasing and entailment.

Despite the complexity of the phenomena, the popular PI corpora (Dolan et al.,
2004; Ganitkevitch et al., 2013; Iyer et al., 2017; Lan et al., 2017) are
annotated in a binary manner. In part it is due to lack of annotation tools
capable of fine-grained annotation of relations. WARP-Text (Kovatchev et al.,
2018b) fills this gap in the NLP toolbox.

The simplified corpus format poses a problem with respect to the quality of
the PI task and the ways it can be evaluated. The vast majority of the state-
of-the-art systems in PI provide no or very little error analysis. This makes
it difficult to interpret the actual capabilities of a system and its
applicability to other corpora and tasks.

Some researchers have approached the problem of non-interpretability by
evaluating the same architecture on multiple datasets and multiple tasks. Lan
and Xu (2018a) apply this approach to Supervised PI systems, while Aldarmaki
and Diab (2018) use it for evaluating Unsupervised PI systems and general
sentence representation models.

Linzen et al. (2016) demonstrate how by modifying the task definition and the
evaluation the capabilities of a Deep Learning system can be determined
implicitly. The main advantage of such an approach is that it only requires
modification and additional annotation of the corpus. It does not place any
additional burden on the developers of the systems and can be applied to
multiple systems without additional cost.

We follow a similar line of research and propose a new evaluation that uses
ETPC (Kovatchev et al., 2018a): a PI corpus with a multi-layer annotation of
various linguistic phenomena. Our methodology uses the corpus annotation to
provide much more feedback to the competing systems and to evaluate and
compare them qualitatively.

####  6.3 Qualitative Evaluation Framework

#####  6.3.1 The ETPC Corpus

ETPC (Kovatchev et al., 2018a) is a re-annotated version of the MRPC corpus.
It contains 5,801 text pairs. Each text pair in ETPC has two separate layers
of annotation. The first layer contains the traditional binary label
(paraphrase or non-paraphrase) of every text pair. The second layer contains
the annotation of 27 “atomic” linguistic phenomena involved in paraphrasing,
according to the authors of the corpus. All phenomena are linguistically
motivated and humanly interpretable.

  * 3a

A federal magistrate in Fort Lauderdale ordered him held without bail.

  * 3b

He was ordered held without bail Wednesday by a federal judge in Fort
Lauderdale, Fla.

We illustrate the annotation with examples 3a and 3b. At the binary level,
this pair is annotated as “paraphrases”. At the “atomic” level, ETPC contains
the annotation of multiple phenomena, such as the “same polarity substitution
(habitual)” of “magistrate” and “judge” (marked bold) or the “diathesis
alternation” of “…ordered him held” and “he was ordered by…” (marked
underline).

For the full set of phenomena, the linguistic reasoning behind them, their
frequency in the corpus, real examples from the pairs, and the annotation
guidelines, please refer to Kovatchev et al. (2018a).

#####  6.3.2 Evaluation Methodology

We use the corpus to evaluate the capabilities of the different PI systems
implicitly. That means, the training objective of the systems remains
unchanged: they are required to correctly predict the value of the binary
label at the first annotation layer. However, when we analyze and evaluate the
performance of the systems, we make use of both the binary and the atomic
annotation layers. Our evaluation framework is created to address our main
research question (RQ 1):

  * RQ 1

Does the performance of a PI system on each candidate-paraphrase pair depend
on the different phenomena involved in that pair?

We evaluate the performance of the systems in terms of their “overall
performance” (Accuracy and F1) and “phenomena performance”.

“Phenomena performance” is a novelty of our approach and allows for
qualitative analysis and comparison. To calculate “phenomena performance”, we
create 27 subsets of the test set, one for each linguistic phenomenon. Each of
the subsets consists of all text pairs that contain the corresponding
phenomenon222i.e. The “diathesis alternation” subset contains all pairs that
contain the “diathesis alternation” phenomenon (such as the example pair
3a–3b). Some of the pairs can also contain multiple phenomena: the example
pair 3a–3b contains both “same polarity substitution (habitual)” and
“diathesis alternation”. Therefore pair 3a–3b will be added both to the “same
polarity substitution (habitual)” and to the “diathesis alternation” phenomena
subsets. Consequentially, the sum of all subsets exceeds the size of the test
set.. Then, we use each of the 27 subsets as a test set and we calculate the
binary classification Accuracy (paraphrase or non-paraphrase) for each subset.
This score indicates how well the system performs in cases that include one
specific phenomenon. We compare the performance of the different phenomena and
also compare them with the “overall performance”.

Prior to running the experiments we verified that: 1) the relative
distribution of the phenomena in paraphrases and in non-paraphrases is very
similar; and 2) there is no significant correlation (Pearson r <0.1) between
the distributions of the individual phenomena. These findings show that the
sub-tasks are non-trivial: 1) the binary labels of the pairs cannot be
directly inferred by the presence or absence of phenomena; and 2) the
different subsets of the test set are relatively independent and the
performance on them cannot be trivially reduced to overlap and phenomena co-
occurrence.

The “overall performance” and “phenomena performance” of a system compose its
“performance profile”. With it we aim to address the rest of our research
questions (RQs):

  * RQ 2

Which are the strong and weak sides of each individual system?

  * RQ 3

Are there any significant differences between the “performance profiles” of
the systems?

  * RQ 4

Are there phenomena on which all systems perform well (or poorly)?

####  6.4 PI Systems

To demonstrate the advantages of our evaluation framework, we have replicated
several popular Supervised and Unsupervised PI systems. We have selected the
systems based on three criteria: popularity, architecture, and performance.
The systems that we chose are popular and widely used not only in PI, but also
in other tasks. The systems use a wide variety of different ML architectures
and/or different features. Finally, the systems obtain comparable quantitative
results on the PI task. They have also been reported to obtain good results on
the MRPC corpus which is the same size as ETPC. The choice of system allows us
to best demonstrate the limitations of the classical quantitative evaluation
and the advantages of the proposed qualitative evaluation.

To ensure comparability, all systems have been trained and evaluated on the
same computer and the same corpus. We have used the configurations recommended
in the original papers where available. During the replication we did not do a
full grid-search as we want to replicate and thereby contribute to
generalizable research and systems. As such, the quantitative results that we
obtain may differ from the performance reported in the original papers,
especially for the Supervised systems. However, the results are sufficient for
the objective of this paper: to demonstrate the advantages of the proposed
evaluation framework.

We compare the performance of five Supervised and five Unsupervised systems on
the PI task, including one Supervised and one Unsupervised baseline systems.
We also include Google BERT (Devlin et al., 2019) for reference.

The Supervised PI systems include:

  * [S1]

Machine translation evaluation metrics as hand-crafted features in a Random
Forest classifier. Similar to Madnani et al. (2012) (baseline)

  * [S2]

A replication of the convolutional network similarity model of He et al.
(2015)

  * [S3]

A replication of the lexical composition and decomposition system of Wang et
al. (2016)

  * [S4]

A replication of the pairwise word interaction modeling with deep neural
network system by He and Lin (2016)

  * [S5]

A character level neural network model by Lan and Xu (2018b)

The Unsupervised PI systems include:

  * [S6]

A binary Bag-of-Word sentence representation (baseline)

  * [S7]

Average over sentence of pre-trained Word2Vec word embeddings (Mikolov et al.,
2013b)

  * [S8]

Average over sentence of pre-trained Glove word embeddings (Pennington et al.,
2014)

  * [S9]

InferSent sentence embeddings (Conneau et al., 2017)

  * [S10]

Skip-Thought sentence embeddings (Kiros et al., 2015)

In the unsupervised setup we first represent each of the two sentences under
the corresponding model. Then we obtain a feature vector by concatenating the
absolute distance and the element-wise multiplication of the two
representations. The feature vector is then fed into a logistic regression
classifier to predict the textual relation. This setup has been used in
multiple PI papers, more recently by Aldarmaki and Diab (2018). While the
vector representations of BERT are unsupervised, they are fine-tuned on the
dataset. Therefore we put them in a separate category (System #11).

####  6.5 Results

#####  6.5.1 Overall Performance

ID | System Description | Acc | F1
---|---|---|---
SUPERVISED SYSTEMS
1 | MTE features (baseline) | .74 | .819
2 | He et al. (2015) | .75 | .826
3 | Wang et al. (2016) | .76 | .833
4 | He and Lin (2016) | .76 | .827
5 | Lan and Xu (2018b) | .70 | .800
UNSUPERVISED SYSTEMS
6 | Bag-of-Words (baseline) | .68 | .790
7 | Word2Vec (average) | .70 | .805
8 | GLOVE (average) | .72 | .808
9 | InferSent | .75 | .826
10 | Skip-Thought | .73 | .816
11 | Google BERT | .84 | .889
Table 6.1: Overall Performance of the Evaluated Systems

Table 6.1 shows the “overall performance” of the systems on the 1725 text
pairs in the test set. Looking at the table, we can observe several
regularities. First, the deep systems outperform the baselines. Second, the
baselines that we choose are competitive and obtain high results. Since both
baselines make their predictions based on lexical similarity and overlap, we
can conclude that the dataset is biased towards those phenomena. Third, the
supervised systems generally outperform the unsupervised ones, but without
running a full grid-search the difference is relatively small. And finally, we
can identify the best performing systems: S3 (Wang et al., 2016) for the
supervised and S9 (Conneau et al., 2017) for the unsupervised. BERT largely
outperforms all other systems.

The “overall performance” provides a good overview of the task and allows for
a quantitative comparison of the different systems. However, it also has
several limitations. It does not provide much insight into the workings of the
systems and does not facilitate error analysis. In order to study and improve
the performance of a system, a developer has to look at every correct and
incorrect predictions and search for custom defined patterns. The “overall
performance” is also not very informative for a comparison between the
systems. For example S3 (Wang et al., 2016) and S4 (He and Lin, 2016) obtain
the same Accuracy score and only differ by 0.06 F1 score. With only looking at
the quantitative evaluation it is unclear which of these systems would
generalize better on a new dataset.

#####  6.5.2 Full Performance Profile

Table 6.2 shows the full “performance profile” of S3 (Wang et al., 2016), the
supervised system that performed best in terms of “overall performance”. Table
6.2 shows a large variation of the performance of S3 on the different
phenomena. The accuracy ranges from .33 to 1.0. We also report the statistical
significance of the difference between the correct and incorrect predictions
for each phenomena and the correct and incorrect predictions for the full test
set, using the Mann–Whitney U-test333 The Mann–Whitney U-test is a non-
parametric equivalence of T-test. The U-Test does not assume normal
distribution of the data and is better suited for small samples. (Mann and
Whitney, 1947).

Ten of the phenomena show significant difference from the overall performance
at p <0.1. Note that eight of them are also significant at p <0.05. The
statistical significance of “Opposite polarity substitution (habitual)”, and
“Negation Switching” cannot be verified due to the relatively low frequency of
the phenomena in the test set.

The demonstrated variance in phenomena performance and its statistical
significance address RQ 1: we show that the performance of a PI system on each
candidate-paraphrase pair depends on the different phenomena involved in that
pair or at least there is a strong observable relation between the performance
and the phenomena.

The individual “performance profile” also addresses RQ 2. The profile is
humanly interpretable, and we can clearly see how the system performs on
various sub-tasks at different linguistic levels. The qualitative evaluation
shows that S3

OVERALL PERFORMANCE
---
Overall Accuracy | .76 |
Overall F1 | .833 |
PHENOMENA PERFORMANCE
Phenomenon | Acc | p
Morphology-based changes
Inflectional changes | .79 | .21
Modal verb changes | .90 | .01
Derivational changes | .72 | .22
Lexicon-based changes
Spelling changes | .88 | .01
Same polarity sub. (habitual) | .78 | .18
Same polarity sub. (contextual) | .75 | .37
Same polarity sub. (named ent.) | .73 | .14
Change of format | .75 | .44
Lexico-syntactic based changes
Opp. polarity sub. (habitual) | 1.0 | na
Opp. polarity sub. (context.) | .68 | .14
Synthetic/analytic substitution | .77 | .39
Converse substitution | .92 | .07
Syntax-based changes
Diathesis alternation | .83 | .12
Negation switching | .33 | na
Ellipsis | .64 | .07
Coordination changes | .77 | .47
Subordination and nesting | .86 | .01
Discourse-based changes |
Punctuation changes | .87 | .01
Direct/indirect style | .76 | .5
Syntax/discourse structure | .83 | .05
Other changes |
Addition/Deletion | .70 | .05
Change of order | .81 | .04
Contains negation | .78 | .32
Semantic (General Inferences) | .80 | .21
Extremes |
Identity | .77 | .29
Non-Paraphrase | .81 | .04
Entailment | .76 | .5
Table 6.2: Performance profile of Wang et al. (2016)

performs better when it has to deal with: 1) surface phenomena such as
“spelling changes”, “punctuation changes”, and “change of order”; 2)
dictionary related phenomena such as “opposite polarity substitution
(habitual)”,  “converse substitution”, and “modal verb changes”. S3 performs
worse when facing phenomena such as “negation switching”, “ellipsis”,
“opposite polarity substitution (contextual)”, and “addition/deletion”.

Phenomenon | Paraphrase Identification Systems
---|---
| Supervised | Unsupervised |
| S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 | S11
OVERALL | .74 | .75 | .76 | .76 | .70 | .68 | .70 | .72 | .75 | .73 | .84
Inflectional | .77 | .76 | .79 | .79 | .75 | .79 | .75 | .76 | .78 | .80 | .84
Modal verb | .84 | .89 | .90 | .89 | .91 | .92 | .89 | .84 | .81 | .89 | .92
Derivational | .80 | .83 | .72 | .73 | .84 | .80 | .88 | .86 | .80 | .77 | .87
Spelling | .85 | .83 | .88 | .90 | .89 | .85 | .89 | .88 | .85 | .89 | .94
Same pol. (hab.) | .74 | .77 | .78 | .76 | .76 | .76 | .76 | .75 | .76 | .76 | .85
Same pol. (con.) | .74 | .74 | .75 | .74 | .70 | .71 | .71 | .71 | .73 | .73 | .81
Same pol. (NE) | .74 | .72 | .73 | .75 | .64 | .67 | .65 | .70 | .73 | .66 | .80
Change Format | .80 | .79 | .75 | .84 | .85 | .82 | .81 | .80 | .80 | .71 | .91
Opp. pol. (hab.) | 1.0 | 1.0 | 1.0 | .50 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
Opp. pol. (con.) | .77 | .84 | .68 | .84 | .52 | .84 | .61 | .77 | .65 | .52 | .71
Synth./analytic | .73 | .73 | .77 | .77 | .74 | .70 | .72 | .71 | .73 | .74 | .83
Converse sub. | .93 | .93 | .92 | .86 | .93 | .86 | .79 | .79 | .93 | .79 | .86
Diathesis altern. | .77 | .85 | .83 | .77 | .83 | .89 | .85 | .83 | .84 | .81 | .85
Negation switc | 1.0 | .67 | .33 | .33 | .33 | .67 | .33 | .67 | .33 | .67 | .33
Ellipsis | .77 | .71 | .64 | .74 | .80 | .65 | .81 | .74 | .61 | .71 | .81
Coordination | .92 | .92 | .77 | .92 | .77 | .92 | .85 | .85 | .92 | .92 | .92
Subord. & Nest. | .83 | .84 | .86 | .84 | .81 | .81 | .85 | .86 | .80 | .85 | .93
Punctuation | .88 | .90 | .87 | .87 | .86 | .87 | .89 | .89 | .89 | .88 | .93
Direct/indirect | .84 | .84 | .76 | .80 | .76 | .80 | .80 | .84 | .80 | .80 | .92
Syntax/Disc. | .80 | .83 | .83 | .81 | .78 | .81 | .80 | .80 | .76 | .78 | .82
Add./Del. | .69 | .68 | .70 | .72 | .67 | .64 | .65 | .66 | .70 | .67 | .82
Change of order | .82 | .83 | .81 | .81 | .77 | .82 | .82 | .82 | .83 | .84 | .89
Contains neg. | .78 | .74 | .78 | .79 | .78 | .72 | .74 | .78 | .75 | .76 | .85
Semantic (Inf.) | .80 | .89 | .80 | .81 | .88 | .90 | .90 | .92 | .76 | .79 | .90
Identity | .74 | .75 | .77 | .77 | .73 | .72 | .73 | .73 | .76 | .74 | .85
Non-Paraphrase | .76 | .77 | .81 | .75 | .71 | .55 | .67 | .68 | .77 | .79 | .88
Entailment | .80 | .80 | .76 | .76 | .88 | .80 | .84 | .88 | .92 | .88 | .76
Table 6.3: Performance profiles of all systems

#####  6.5.3 Comparing Performance Profiles

Table 6.3 shows the full performance profiles of all systems. The systems are
identified by their IDs, as shown in Table 6.1. In addition to providing a
better error analysis for every individual system, the “performance profiles”
of the different systems can be used to compare them qualitatively. This
comparison is much more informative than the “overall performance” comparison
shown in Table 6.1. Using the “performance profile”, we can quickly compare
the strong and weak sides of the different systems.

When looking at the “overall performance”, we already pointed out that S3
(Wang et al., 2016) and S4 (He and Lin, 2016) have almost identical
quantitative results: 0.76 accuracy, 0.833 F1 for S3 against 0.76 accuracy,
0.827 F1 for S4. However, when we compare their “phenomena performance” it is
evident that, while these systems make approximately the same number of
correct and incorrect predictions, the actual predictions and errors can vary.

Looking at the accuracy, we can see that S3 performs better on phenomena such
as “Converse substitution”, “Diathesis alternation”, and “Non-Paraphrase”,
while S4 performs better on “Change of format”, “Opposite polarity
substitution (contextual)”, and “Ellipsis”.

We performed McNemar paired test comparing the errors of the two systems for
each phenomena. Table 6.4 shows some of the more interesting results. Four of
the phenomena with largest difference in accuracy show significant difference
with p <0.1. These differences in performance are substantial, considering
that the two systems have nearly identical quantitative performance.

Phenomenon | #3 | #4 | p
---|---|---|---
Format | .75 | .84 | .09
Opp. Pol. Sub (con.) | .68 | .84 | .06
Ellipsis | .64 | .74 | .08
Non-Paraphrase | .81 | .75 | .07
Table 6.4: Difference in phenomena performance between S3 (Wang et al., 2016)
and S4 (He and Lin, 2016)

We performed the same test on systems with a larger quantitative difference.
Table 6.5 shows the comparison between S3 and S5 (Lan and Xu, 2018b). Ten of
the phenomena show significant difference with p <0.1 and seven with p <0.05.
These results answer our RQ 3: we show that there are significant differences
between the “performance profiles” of the different systems.

Phenomenon | #3 | #5 | p
---|---|---|---
Derivational | .72 | .84 | .03
Same Pol. Sub (con.) | .75 | .70 | .02
Same Pol. Sub (NE) | .73 | .64 | .01
Format | .75 | .85 | .03
Opp. Pol. Sub (con.) | .68 | .52 | .10
Ellipsis | .64 | .80 | .10
Addition/Deletion | .70 | .67 | .02
Identity | .77 | .73 | .01
Non-Paraphrase | .81 | .71 | .01
Entailment | .76 | .88 | .08
Table 6.5: Difference in phenomena performance: S3 (Wang et al., 2016) and S5
(Lan and Xu, 2018b)

#####  6.5.4 Comparing Performance by Phenomena

The “phenomena performance” of the individual systems clearly differ among
them, but they also show noticeable tendencies. Looking at the performance by
phenomena, it is evident that certain phenomena consistently obtain lower than
average accuracy across multiple systems while other phenomena consistently
obtain higher than average accuracy.

In order to quantify these observations and to confirm that there is a
statistical significance we performed Friedman-Nemenyi test (Demšar, 2006).
For each system, we ranked the performance by phenomena from 1 to 27,
accounting for ties. We calculated the significance of the difference in
ranking between the phenomena using the Friedman test (Friedman, 1940) and
obtained a Chi-Square value of 198, which rejects the null hypothesis with p
<0.01. Once we had checked for the non-randomness of our results, we computed
the Nemenyi test (Nemenyi, 1963) to find out which phenomena were
significantly different. In our case, we compute the two-tailed Nemenyi test
for k = 27 phenomena and N = 11 systems. The Critical Difference (CD) for
these values is 12.5 at p <0.05.

Figure 6.1 shows the Nemenyi test with the CD value. Each phenomenon is
plotted with its average rank across the 11 evaluated systems. The horizontal
lines connect phenomena which rank is within CD of each other. Phenomena which
are not connected by a horizontal line have significantly different ranking.
We can observe that each phenomenon is significantly different from at least
half of the other phenomena.

Figure 6.1: Critical Difference diagram of the average ranks by phenomena

We can observe that some phenomena, such as “opposite polarity substitution
(habitual)”, “punctuation changes”, “spelling”, “modal verb changes”, and
“coordination changes” are statistically much easier according to our
evaluation, as they are consistently among the best performing phenomena
across all systems. Other phenomena, such as “negation switching”,
“addition/deletion”, “same polarity substitution (named entity)”, “opposite
polarity substitution (contextual)”, and “ellipsis” are statistically much
harder, as they are consistently among the worst performing phenomena across
all systems. With the exception of “negation switching” and “opposite polarity
substitution (habitual)”, these phenomena occur in the corpus with sufficient
frequency. These results answer our RQ 4: we show that there are phenomena
which are easier or harder for the majority of the evaluated systems.

####  6.6 Discussion

In Section 6.3.2 we described our evaluation methodology and posed four
research questions. The experiments that we performed and the analysis of the
results answered all four of them. We briefly discuss the implications of the
findings.

By addressing RQ 1, we showed that the performance of a system can differ
significantly based on the phenomena involved in each candidate-paraphrase
pair. By addressing RQ 4, we showed that some phenomena are consistently
easier or harder across the majority of the systems. These findings
empirically prove the complexity of paraphrasing and the task of PI. The
results justify the distinction between the qualitatively different linguistic
phenomena involved in paraphrasing and demonstrate that framing PI as a binary
classification problem is an oversimplification.

By addressing RQ 2, we showed that each system has strong and weak sides,
which can be identified and interpreted via its “performance profile”. This
information can be very valuable when analyzing the errors made by the system
or when reusing it on another task. Given the Deep architecture of the
systems, such a detailed interpretation is hard to obtain via other means and
metrics. By addressing RQ 3, we showed that two systems can differ
significantly in their performance on candidate-paraphrase pairs involving
particular phenomenon. These differences can be seen even in systems that have
almost identical quantitative (Acc and F1) performance on the full test set.
These findings justify the need for a qualitative evaluation framework for PI.
The traditional binary evaluation metrics do not account for the difference in
phenomena performance. They do not provide enough information for the analysis
or for the comparison of different PI systems. Our proposed framework shows
promising results.

Our findings demonstrate the limitations of the traditional PI task definition
and datasets and the way PI systems are typically interpreted and evaluated.
We show the advantages of a qualitative evaluation framework and emphasize the
need to further research and improve the PI task. The “performance profile”
also enables the direct empirical comparison of related phenomena such as
“same polarity substitution (habitual)” and “(contextual)” or “contains
negation” and “negation switching”. These comparisons, however, fall outside
of the scope of this paper.

Our evaluation framework is not specific to the ETPC corpus or the typology
behind it. The framework can be applied to other corpora and tasks, provided