Linear Neural Parsing and Hybrid Enhancement for Enhanced U niversal D ependencies (2020)

Abstract: To accomplish the shared task on dependency parsing we explore the use of a linear transition-based neural dependency parser as well as a combination of three of them by means of a linear tree combination algorithm. We train separate models for each language on the shared task data. We compare our base parser with two biaffine parsers and also present an ensemble combination of all five parsers, which achieves an average UAS 1.88 point lower than the top official submission. For producing the enhanced dependencies, we exploit a hybrid approach, coupling an algorithmic graph transformation of the dependency tree with predictions made by a multitask machine learning model.

## system overview the shared task is aimed at performing all the levels of linguistic analysis according to the ud guidelines, starting from raw text all the way to enhanced dependency graphs. all this in a multi-language setting for seventeen languages @xcite . in this endeavor, we concentrate on the syntactic parsing and enhancement stages, by exploiting existing tools for tokenization, sentence splitting, pos tagging and morphological analysis. for syntactic parsing we make experiments exploring different ideas, in an attempt to improve state-of-the-art parsers with linear complexity. a parser combination is then used for our official submission, exploiting the linear tree combination algorithm by @xcite , resulting in an overall linear algorithm. for the enhancement step, we build on previous work in writing an enhancer for ud, based on algorithmic graph transformation, that was used to produce the italian version of the enhanced dependencies @xcite . the script used language specific heuristics and lexical information, achieving a good degree of accuracy for italian and english. in this multi-language challenge, we have to deal with partial implementations of the expected enhancement types as well as with varying degree of compliance with the guidelines in the different languages. in order to address this additional complexity, we implement a new version of the script for making it modular, parametric, and language independent. for specific enhancement tasks, we integrate the output of machine learning classifiers, in an attempt to learn from the training data and make the heuristics more robust and general. ## syntactic parsing state of the art dependency parsers currently often adopt the graph-based model, based on neural networks for the choice of arcs and labels. we consider as current sota on the english ptb the graph dependency parsers listed in in particular the bi-lstm-based deep biaffine neural dependency parser by @xcite has been quite popular and used in three out of five of the top submissions to the conll 2018 shared task: multilingual parsing from raw text to universal dependencies @xcite , in particular in the top non-ensemble submission @xcite . the preference for such models leads to systems with high accuracy but possibly slower due to their o(n 2 ) complexity. for example, the original implementation of the dozat parser is rated at about 400 sents/sec on gpus, while for example the neural transition-based parser by @xcite is rated at 640 sents/sec just on cpus. our experiments attempt to find a parser with linear complexity and hence good speed performance. indeed the linear transition parser that we choose for our experiments (uuparser) is twice as fast as the parser uas las hpsg @xcite 96.09 94.68 @xcite 93.10 91.00 biaffine @xcite 95.74 94.08 pointer-td @xcite 95.87 94.19 pointer-lr @xcite 96.04 94.43 uuparser (de @xcite 94.63 92.77 @xcite 93.9 91.9 cm @xcite 91.80 89.60 ## enhanced dependencies for producing the enhanced dependencies we follow a "hybrid" approach, using a combination of an algorithmic graph transformation of the syntactic dependency tree coupled with predictions made by three machine learning classifiers. the basic enhancing script is an evolution of the work presented in @xcite to bootstrap enhanced dependencies for the italian treebank, also used for experiments in @xcite . one classifier is used to recognize the external subjects in xcomp constructions. the second classifier detects when a head should be propagated in conjunctions. the third classifier detects the case of propagation of dependents in conjunctions. the classifiers are trained jointly on the three tasks and produce three binary predictions. the script that adds the enhanced dependencies is modular, so that it can be adapted to perform just the required analysis depending on the kind of enhanced dependencies present in each language and to bypass those that were not implemented. in addition, the script is parametric with respect to predictions coming from machine learning classifiers, which can be taken into account or ignored. we describe below how the different kinds of enhancements are addressed. ## results the official results are those labeled unipi-003 in our submission, obtained through the combination of the parsers udify, uuparser and udpipe. after the submission deadline, we experimented with the biaffibe parsers stanza and zysite. stanza improves over uuparser by an average of 0.58 uas, 0.64 las, 1.05 clas, 4.26 mlas, 4.26 blex, 0.60 eulas, 0.42 elas, with notable improvements of +16.82 las on estonian, while a decrease of -28.52 las on lithuanian, and -9.95 las on polish is observed. zysite improves over uuparser by an average of 1.77 uas, 1.84 las, 1.97 clas, 0.27 mlas, 1.28 blex, 1.83 eulas and 1.63 elas, with notable improvements of +17.49 las on estonian, +5.02 on dutch, +3.23 on svedish, but with a significant drop of -14.48 las on arabic. these are encouraging results that show that a transition-based parser can be competitive with graph-based ones. we then produced a new run comb5 (unipi-comb5), as an ensemble of five parsers: uuparser, udify, udpipe, stanza and zysite. we report these unofficial results in the improvements on parsing by the ensemble of five parsers with respect to the single parser uuparser are summarized in the most significant improvements from the ensemble combinations are +13.07 uas on estonian, +5.31 on tamil, +5.11 on dutch, +3.59 on lithuanian, +4.37 on finnish. estonian, finnish, latvian, lithuanian turned out as the most difficult for our dependency parsers, with a difference between 4.2 and 6.5 points of uas with respect to the submission by kanerva and even 10.7 point lower on arabic. if we consider the average uas excluding the baltic languages, the average uas of the ensemble parsers is 89.82. as for the enhancement task, its difficulty, besides what we discussed in section 3.5, seems to be confirmed by a significant drop from our eu-las score (restricted to ud relations) to the elas score, which also takes into account label enhancements. the average drop is 6.26 points and for some languages more than 10 points. the effectiveness of our 'patch' strategy had been carefully assessed with the development data, but did not provide analogous results on the test set. our algorithm was poor in predicting the label extended with case information. perhaps a machine learning approach would have provided better results in this case. ## conclusions we experimented with both linear transition-based parsers and two implementations of graph-based biaffine parsers. all parsers have difficulties with baltic languages, finnish and arabic which somehow we were able to mitigate by combining them into an ensemble, except for arabic, which remains 8.2 points uas lower than the top submission. our enhanced version of uuparser, using bert embeddings, performs competitively well with respect to the biaffine zysite parser, except on estonian, tamil and dutch, while it outperforms it by +14 las on arabic. since all the parsers use the same base model, multilingual uncased of bert, it might be worthwhile to investigate how such models affect the performance on baltic languages. the implementation of the biaffine parser by zysite was a surprising discovery, since it is capable to outperform in speed all other parsers, possibly due to its use of a more efficient biaffine operation via torch.einsum(). for adding the enhanced relations to the output of the parser we opted for a hybrid approach, where for some languages, which appear to be more conforming to the guidelines, we applied an algorithmic solution, while for the rest we exploited machine learning classifiers. in principle the algorithmic approach should be sufficient as soon as languages adhere more strictly to the guidelines. in the meanwhile, we wonder whether it is worthwhile to develop techniques which are language specific in order to obtain better results, unless there are ways to devise a language agnostic solution.