Cross-Lingual Dependency Parsing by POS -Guided Word Reordering (2020)

Abstract: We propose a novel approach to cross-lingual dependency parsing based on word reordering. The words in each sentence of a source language corpus are rearranged to meet the word order in a target language under the guidance of a part-of-speech based language model (LM). To obtain the highest reordering score under the LM, a population-based optimization algorithm and its genetic operators are designed to deal with the combinatorial nature of such word reordering. A parser trained on the reordered corpus then can be used to parse sentences in the target language. We demonstrate through extensive experimentation that our approach achieves better or comparable results across 25 target languages (1.73% increase in average), and outperforms a baseline by a significant margin on the languages that are greatly different from the source one. For example, when transferring the English parser to Hindi and Latin, our approach outperforms the baseline by 15.3% and 6.7% respectively.

## introduction the rise of machine learning (ml) methods and the availability of treebanks @xcite for a wide variety of languages have led to a rapid increase in research on data-driven dependency parsing @xcite @xcite . however, the performance of dependency parsers heavily relies on the size of corpus. due to the great cost and difficulty of acquiring sufficient training data, ml-based methods cannot be trivially applied to low-resource languages. cross-lingual transfer is a promising approach to tackle the lack of sufficient data. the idea is to train a cross-lingual model that transfers knowledge learned in one or multiple high-resource source languages to target ones. this approach has been successfully applied in various tasks, including part-of-speech (pos) tagging @xcite , dependency parsing @xcite , named entity recognition @xcite , entity linking @xcite , question answering @xcite , and coreference resolution @xcite . a key challenge for cross-lingual parsing is the difficulty to handle word order difference between source and target languages, which often causes a significant drop in performance @xcite . inspired by the idea that pos sequences often reflect the syntactic structure of a language, we propose cursor (cross lingual parsing by word reordering) to overcome the word order difference issue in crosslingual transfer. specifically, we assume we have a treebank in the source language and annotated pos corpus in the target language foot_0 . we first train a pos-based language model on a corpus in the target language. then, we reorder words in each sentence on the source corpus based on the posbased language model to create pseudo sentences with target word order. the resulting reordered treebank can be used to train a cross-lingual parser with multi-lingual word embeddings. we formalize word reordering as a combinatorial optimization problem to find the permutation with the highest probability estimated by a pos-based language model. however, it is computationally difficult to obtain the optimal word order. to find a near-optimal result, we develop a population-based optimization algorithm. the algorithm is initialized with a population of feasible solutions and iteratively produces new generations by specially designed genetic operators. at each iteration, better solutions are generated by applying selection, crossover, and mutation subroutines to individuals in the previous iteration. our contributions are summarized as follows: ## related work many efforts @xcite @xcite have been devoted to cross-lingual dependency parsing via transfer learning, in which manually annotated corpora are no longer required for low-resource languages. one of the challenges is the word orders in source and target languages might be different (e.g., some languages are prepositional and some are postpositional). various studies have been dedicated to addressing this issue @xcite @xcite . in particular, some studies proposed to bypass word order issue by selecting source languages that have similar word orders to the target language @xcite . good source languages can be selected by measuring the similarity of pos sequences between the source and target languages @xcite , querying the information stored in topological databases @xcite , and formalizing such selection as a ranking problem @xcite . treebank translation @xcite tackles this problem by transforming an annotated source treebank to instances with target language grammar through machine translation. however, this method may suffer from imperfect word alignment between two languages. @xcite proposed to perform such syntactic transfer by code mixing in which only the confident words in a source treebank will be transformed. another interesting solution to cross-lingual transfer is an annotation projection @xcite @xcite . in this approach, source-side sentences of a parallel corpus are parsed by the parser trained on the source treebank, then the source dependencies are projected onto the target sentences using the results of word alignments. however, the resulting treebank could be highly noisy because the source dependency trees are constructed automatically and cannot be taken as ground truth. @xcite considered removing not well-aligned sentences to obtain high-quality data. täckström et al. (2013) trained a parser on multiple source languages instead of a single one. ponti et al. (2018) proposed a typologically driven method to reduce anisomorphism. ahmad et al. ( 2019 ) designed an order-free model to extract the order features from the source language. @xcite embraced the linguistic knowledge of target languages to guide the inference. some researchers also exploit lexical features to enhance the parsing models. cross-lingual word clusters @xcite , word embeddings @xcite @xcite , and dictionaries @xcite are used as the features to better transfer linguistic knowledge among different languages. our work is in line with a recently proposed solution, namely treebank reordering @xcite @xcite , which aims to rearrange the word order in source sentences to make them more similar to the target one. @xcite proposed to permute the constituents of an existing dependency treebank to make its surface pos statistics approximately match those of the target language. however, they used pos bigrams to measure the surface closeness between two languages, which is unable to capture global information. @xcite proposed two different syntactic reordering methods, one is based on the dominant dependency direction in the target language, the other learns a reordering classifier, but both methods rely on parallel corpus. in this study, we explore the feasibility of utiliz-ing a pos-based neural language model to guide treebank reordering. our approach does not require any parallel corpus, and can be applied to a pair of source and target languages as long as their pos tags are available. we designed a population-based optimization algorithm to deal with the combinatorial nature of word reordering. this algorithm is able to find the close-to-optimal results of reordering, which yields a new state-of-the-art for cross-lingual parsing in various languages. ## approach in this section, we first formalize the word reordering as a combinatorial optimization problem, and then present our method to solve the problem. ## experiments we evaluate cursor by transferring four different parsing models trained on english corpus to 30 target languages. we first introduce the experimental setup, then discuss the results as well as in-depth analysis, and finally, we propose a combined approach to further improve the performance. ## conclusion we propose a treebank reordering approach for cross-lingual dependency parsing. our approach does not require any parallel corpus and can be applied to any pair of source and target languages as long as their pos tags are available. extensive experimentation with different network architectures across 30 languages demonstrates that our approach can substantially improve the performance of the cross-lingual parsing.