Parse Me if You Can: Artificial Treebanks for Parsing Experiments on Elliptical Constructions

In this work we focus on a particular linguistic phenomenon, ellipsis, and explore the latest parsers in order to learn about parsing accuracy and typical errors from the perspective of elliptical constructions. For this purpose we collected and processed outputs of several state-of-the art parsers that took part in the CoNLL 2017 Shared Task. We extended the official shared task evaluation software to obtain focused evaluation of elliptical constructions. Since the studied structures are comparatively rare, and consequently there is not enough data for experimentation, we further describe the creation of a new resource, a semi-artificially constructed treebank of ellipsis.


Introduction
Ellipsis, i.e. omission of linguistic content that is silently understood by both the speaker and the addressee, is a phenomenon present-in various forms-in many natural languages. Ellipsis obviously makes natural language understanding harder; but sometimes it also complicates syntactic parsing of the content that is not omitted. In dependency syntax (which is the framework within which we operate), a parent node may be missing while its dependents are present. One might either create an "empty" node for the missing word, or choose a substitute parent among the words that are not missing. Both options make parsing difficult: in the former case, the parser must learn where to generate empty nodes; in the latter, relations are drawn between nodes that would not be connected otherwise, hence they are not easily learned from data. In any case, modern dependency parsers are data-driven and they can hardly account for those types of ellipsis that are not represented in training data. If the data contains empty nodes, the parser can try to learn generating them. If the data does not contain any specific annotation of ellipsis, we have to hope that the parser learns to occasionally attach dependents to strange parents, even without knowing that it is ellipsis what caused the lack of better options. In this study we focus on elliptical constructions in the so-called basic representation of Universal Dependencies (UD) (Nivre et al., 2016). The annotation style of UD does not mark ellipsis explicitly when it does not have to: most types are solved by simply promoting one orphaned dependent to the position of its missing parent. Admittedly, there are treebanks that overtly annotate a wider range of elliptical structures. Our main reason for working with UD is practical: substantial data is available in this annotation style for several dozens of languages, and state-of-the art parsers have been trained and tested on UD. The one exception where UD explicitly marks ellipsis are certain types of gapping and stripping , where multiple orphaned dependents of a missing predicate have to be connected using a special relation called orphan (Figure 1). In the present work we inves-tigate how frequent are the orphan relations in data, how well can existing parsers learn to recognize them, and how can we extend the data to provide more training material and improve parsing accuracy.

Data
For the purpose of the experiments we use the system outputs from the CoNLL 2017 Shared Task , that are now available as a corpus. We chose 12 teams whose systems surpassed baseline results  on labelled attachment score (LAS): C2L2, darc, HIT-SCIR, IMS, Koç University, LATTICE, NAIST-SATO, Orange-Deskiñ, Stanford, TurkuNLP,ÚFAL-UDPipe 1.2 and UParse.

Experiments
The idea behind this work is to look closely at the current parsers regarding their ability to parse non trivial linguistic constructions such as elliptical constructions, and collect the information about typical errors, how they differ from parser to parser. For the purpose of this experiment we adapted and extended the evaluation script which had been created to evaluate system output files for the 2017 Shared Task. The main idea of such adaptation is to save evaluation techniques that were proposed and implemented by the 2017 task organizers. Since the data was selected relying on these techniques, we hope that following the same line, especially regarding word alignments and sentence segmentation, helps us to be more precise. The script is available at the Shared Task page. 1 The adapted script can be found on GitHub. 2 The adapted script provides information of two types: • Statistics on correctly predicted orphan relations; • Statistics on erroneously predicted or missed orphan relations and typical errors.  Table 1 shows the statistics on correctly predicted orphan relations. In these calculations we use the relative number of all orphan nodes for every team, which is based on alignment between system output words and gold standard words. In other words, only successfully aligned orphan nodes from gold standard are included in this number. It is clearly seen that both Recall and F-measure are rather low. At the same time, percentage of correctly predicted dependency labels for head nodes is quite high. Table 2 shows the statistics on erroneously predicted or missed orphan labels. For every parser that we selected for the experiment, we calculate error pairs "relation1-relation2", where the first relation was taken from the aligned gold word and the second relation was assigned by the system. Table 2 provides top 5 error pairs. Every cell contains the following information:

Evaluation
• the error pair; • the contribution of the pair to the number of all errors concerning orphan label (percentage); • the number of instances of the error type (frequency); • h.error shows erroneously predicted head nodes (percentage and absolute number).
It seems that parsers make mistakes in similar conditions: the error types and their frequencies are almost the same from parser to parser. What is important, the number of orphan labels is just a tiny fraction of all labels and the contribution of their low values of Recall and F-measure to the final figures calculated on the whole amount of data goes virtually unseen. Hence, the question is if the parsers perform really poorly on elliptical constructions or it is simply the lack of data.
To answer that question, we would need more data; since naturally occurring ellipsis is rare, we decided to artificially create a set of sentences that are structurally similar to natural elliptical constructions.

Creating Artificial Treebanks
Recent research Droganova and Zeman, 2017) provides a detailed overview of elliptical constructions within the UD framework and presents typical patterns that can be used for detection of elliptic constructions. This information allows us to develop a script that transforms non-elliptic UD style trees to elliptic trees. Figure 2 shows a subtree pattern that matches sentences where gapping (Johnson, 2009)  it did not, or at least it was not annotated following the UD guidelines, because there is no orphan relation). An example of an English sentence that matches the pattern: "But not always do those three agree, and not always are their decisions equal." Figure 3 provides the tree structure of this sentence. It matches the pattern because 1. its "root" node is a verb; 2. the verb has an "aux" child; 3. the verb is linked with another clause via a "conj" relation; 4. the other clause is headed by an adjective and has a "cop" (copula) dependent; 5. both clauses contain a "nsubj" (subject) and an "advmod" (adverbial modifier). After transformation the sentence would lose an adjective and its dependent. The new structure is shown in Figure 4. It should be mentioned that patterns do not require a particular word order, only particular dependents. Thus the sentence in Figure 5 is a match as well. The methodology requires manual efforts. After application of the script, the data have to be checked and corrected: • After artificial omission sentences must remain grammatically correct (Figure 10, Figure 11); • The patterns are designed to match as many instances as possible, so the erroneous instances have to be filtered out or manually corrected. All sentences at Fig

Input Data
Our methodology can in principle be applied to any UD treebank. The dataset and experiments presented in this paper are based on Czech, English and Finnish treebanks from UD 2.1 . In addition, large web corpora of the three languages (Zeman et al., 2017)  were parsed by two parsers (Stanford (Dozat et al., 2017) and Baseline UDPipe  entries in the CoNLL17 Shared Task on Multilingual Parsing from Raw Text to Universal Dependencies) and used as an additional source of trees to get more candidate material. After double parsing, only trees with identical analysis were kept to ensure the quality of the automatic parses. An informal manual inspection of these trees confirmed that the quality is sufficient. All input data are in the CoNLL-U format. 3 For English, there are four UD treebanks: "Original", LinES, ParTUT, PUD. For Czech, we used the training parts of "Original", CAC and FicTree. For Finnish, there are three treebanks in UD but only the "Original" UD Finnish was used in the present work, and only for development of the rules, which were then applied to the parsed web corpus to create the final artificial dataset.

Conversion
The conversion was performed using Udapi, an opensource framework that provides an application programming interface for processing Universal Dependencies data . Udapi components that were developed for the conversion are not integrated into the framework and cannot be obtained from the the official Udapi project repository due to their extremely narrow specialization. The components can be found on GitHub. 4 3 http://universaldependencies.org/format.
The algorithm consists of three steps. First, we use existing Udapi functionality to filter out sentences that cannot be converted into artificial sentences in any way. For this purpose we composed a filtering query that restricts the structure of a candidate sentence. For instance, gapping occurs in coordinate structures and typically the second clause contains a gap (Coppock, 2001), therefore a candidate sentence must contain at least two clauses and the candidate word must be in the second. By candidate word we mean the token that will be deleted or transformed in the next step.
Another example of a filtering rule is the requirement that the heads of both clauses have at least 3 dependents that are neither function words nor punctuation. (That is, they are arguments or adjuncts.) One of our observations suggests that elided elements can hardly be restored if some other clause is encountered between the two clauses. Therefore we delete such sentences in the first step. The filtering query simplifies visualization of candidate trees which is helpful for adjustment of the rules. Second, we use the Udapi components that we developed in order to propose the conversion. The first component analyzes candidate words within a sentence and duplicates the sentence if there are two or more words marked as candidate and not all of them are verbs. Simultaneously, the component leaves only one word marked as candidate for each copy. The verb restriction prevents such sentences from duplication: (1) Mary won gold, Peter won silver, and Jane won bronze.
This rule was designed for the following purposes: • If a candidate sentence contains three or more coordinate clauses, we do not want to allow gapping in the second clause if it does not occur in the third clause. Either both must be gapped or none of them.  Figure 6: An example of a sentence before Type 1 conversion.
• If a candidate sentence contains three or more coordinate clauses and some of them are copular clauses, due to the conversion rules the output sentence will contain different types of ellipsis. Consequently, the output structure is not parallel-dependent clauses do not repeat the structure of the main clause. Conversion rules accept copular clauses, but can convert only non-core ellipsis ( Figure 8) from such constructions and only if they have enough non-core dependents.
The second component analyzes candidate words and proposes the conversion according to the rules. The proposed conversion is stored in the CoNLL-U file 5 for every token that should be changed. The information contains either new position in the sentence, parent token and dependency relation, or a marker that the token should be deleted. The component proposes conversion of two types: • Type 1 (Core argument ellipsis)-a verb and its auxiliary verbs are marked as 'to be deleted'. Figure 6 and Figure 7 show an example of such conversion.
• Type 2 (Non-core argument ellipsis)-some or even all core arguments are marked as 'to be deleted'. If no rule can be applied to the sentence, the sentence is marked as 'to be deleted'. 5 The tenth column, MISC, allows for storing arbitrary additional annotation. Some additional markers were used during the conversion process to adjust the rules and to make sure that the rules cover most of the sentences present in the data. Third, we use the Udapi component that was developed to perform the final conversion: • Delete the sentences that are marked as 'to be deleted'; • Delete the tokens that are marked as 'to be deleted'; • Change the sentence structure according to the information that is stored in the MISC column; • Delete all markers that were added during conversion.

Complex Issues
We iteratively adjusted the conversion rules, manually checking output samples, making the rules more strict and precise, and re-running them. However, the output data is still not perfect. We attribute this issue to lack of information: Our rules do not have access to a dictionary and cannot always assess the degree to which the dependents of the two verbs are semantically compatible ( Figure 11). Some of the complex sentences may be correctly converted using grammatical cases (see section 5.4.). Some language-specific relation types may help, for instance, English has obl:tmod (temporal modifier), a subtype of obl (oblique argument or adjunct). Unfortunately, rules relying on relation subtypes are not always applicable to trees produced by parsers because some parsers are trained to only generate the main dependency type-obl in this case.
The service was friendly and fast , but this just does nt make up for the lack -luster product

Language-specific Rules
It is not possible to avoid language-specific rules, although some of them contradict each other. For instance, Finnish allows elliptic sentences with omitted subjects in both clauses and remaining objects (Figure 16, Figure 17), which hardly can be found in English. We thus maintain separate processing pipelines for each language.
An example of an English-specific rule is substitution of personal pronouns. The original sentence typically describes a sequence of actions performed by one actor. By   Table 2: Erroneously predicted or missed orphan labels and their frequencies substituting the second subject with a different pronoun, we create an elliptical sentence where two actors perform presumably the same action but with different patients (Figure 6, Figure 7). Another example would be a rule for copular constructions. If the main clause contains a copula, the sentence must be converted into Type 2 structure (Figure 8,  Figure 13. After deletion of the verb, the structure would have to be reconstructed as there was a copula (Figure 14). And in this case, if the copula is not repeated, the second clause is interpreted just as a clause with a nonverbal predicate ( Figure 15). In all languages it is important to check that the deleted predicate has at least two arguments or adjuncts whose type (e.g., "nsubj", "obj", "obl:agent") matches dependents of the first predicate; otherwise no gapping can occur. If the dependent is a prepositional phrase, the meaning of the prepositions must be compatible, too (note that it does not necessarily mean that the prepositions are identical). Furthermore, in Czech and Finnish the morphological case of the nouns is important. (English does not have cases, with the exception of personal pronouns.) Obviously, the rules described above filter out a substantial amount of sentences. Therefore, we currently do not check prepositions in English; instead, we manually fix sentences where prepositions are not compatible. A good Czech example from the parsed web corpus is in Figures 18 and 19. Both verbs take a directional adjunct with the preposition do "to" and a genitive noun, which makes the gapped sentence sound very natural.

Results
We provide artificial ellipsis treebanks for three languages, Czech, English and Finnish, using our processing pipeline explained in previous sections. Furthermore, the data for English and Finnish is manually checked and fixed to be grammatical and naturally-sound using UD Annotatrix (Tyers  good quality of the provided data. Table 3 provides information concerning the sizes of these three datasets.

Related Work
The idea of artificial generation or modification of corpora is not new and it has been occasionally applied to various areas of language learning, whenever the studied phenomenon is underrepresented in existing resources. To name just a few: In (van der Plas et al., 2009), creation of an artificial treebank from an existing text treebank helps to overcome domain differences. (Khoshnavataher et al., 2015) artificialy modify text to look like obfuscated plagiarism; the resulting corpus is used to train a plagiarismdetecting system for Persian. And (Gulordava and Merlo, 2016) Table 3: The size of the data. Initial: the size of the input data, tokens/sentences; Processed: the size of the data after the application of the conversion pipeline, tokens/sentences; Manual: the size of the data after manual correction, tokens/sentences pact of word order on parsing accuracy in twelve different languages.

Conclusion
We have presented experiments that provide a closer look at the current parsers regarding their ability to parse elliptical constructions. We have proposed and described a methodology for creation of artificial treebanks for parsing experiments. The parsing experiments with the artificial data are the natural next step, which we are going to take. The first version of the artificial elliptic UD treebanks is publicly available in CoNLL-U format via the LIN-DAT/CLARIN repository at http://hdl.handle. net/11234/1-2616.
The artificial data provides a decent amount of ellipsis-like structures. The number of sentences may not look large but it is still several times bigger than naturally occurring elliptical sentences in large treebanks. It will significantly increase the basis that can be used to train ellipsis-aware parsers.

Acknowledgements
The work was partially supported by the grant 15-10472S of the Czech Science Foundation (GAČR), by the GA UK grant 794417, Academy of Finland, and Nokia Foundation. The data is available via the LINDAT/CLARIN repository, which is part of a research infrastructure project funded by the Ministry of Education, Youth and Sports of the Czech Republic, Project No. LM2015071. Computational resources were provided by CSC -IT Center for Science, Finland.