Flexible Non-Terminals for Dependency Tree-to-Tree Reordering

Proceedings of NAACL-HLT 2016, pages 11–19, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics Flexible Non-Terminals for Dependency Tree-to-Tree Reordering John Richardson†, Fabien Cromières‡, Toshiaki Nakazawa‡ and Sadao Kurohashi† †Graduate School of Informatics, Kyoto University, Kyoto 606-8501 ‡Japan Science and Technology Agency, Kawaguchi-shi, Saitama 332-0012 john@nlp.ist.i.kyoto-u.ac.jp, {fabien, nakazawa}@pa.jst.jp, kuro@i.kyoto-u.ac.jp Abstract A major benefit of tree-to-tree over tree- to-string translation is that we can use target-side syntax to improve reordering. While this is relatively simple for binarized constituency parses, the reordering prob- lem is considerably harder for dependency parses, in which words can have arbitrarily many children. Previous approaches have tackled this problem by restricting gram- mar rules, reducing the expressive power of the translation model. In this paper we propose a general model for dependency tree-to-tree reorder- ing based on flexible non-terminals that can compactly encode multiple insertion positions. We explore how insertion po- sitions can be selected even in cases where rules do not entirely cover the children of input sentence words. The proposed method greatly improves the flexibility of translation rules at the cost of only a 30% increase in decoding time, and we demon- strate a 1.2–1.9 BLEU improvement over a strong tree-to-tree baseline. 1 Introduction Translation is most commonly performed by splitting an input sentence into manageable parts, translating these segments, then arrang- ing them in an appropriate order. The first two steps have roughly the same difficulty for close and distant language pairs, however the reorder- ing step is considerably more challenging for lan- guage pairs with dissimilar syntax. We need to be able to make linguistic generalizations, such as learning to translate between SVO and SOV clauses and converting post-modifying preposi- tional and pre-modifying postpositional phrases (Quirk et al., 2005). Such generalizations often require syntactically motivated long-distance re- ordering. The first approaches to reordering were based on linear distortion (Koehn et al., 2003), which models the probability of swapping pairs of phrases over some given distance. The linear distance is the only parameter, ignoring any contextual information, however this model has been shown to work well for string-to-string translation. Linear reordering was improved with lexical distortion (Tillmann, 2004), which characterizes reordering in terms of type (mono- tone, swap, or discontinuous) as opposed to dis- tance. This approach however is prone to spar- sity problems, in particular for distant language pairs. In order to improve upon linear string-based approaches, syntax-based approaches have also been proposed. Tree-to-string translation has been the most popular syntax-based paradigm in recent years, which is reflected by a number of reordering approaches considering source-only syntax (Liu et al., 2006; Neubig, 2013). One particularly interesting approach is to project source dependency parses to the target side and then learn a probability model for reordering children using features such as source and target head words (Quirk et al., 2005). While tree-to-tree translation (Graehl and 11 Figure 1: Examples of tree-to-tree translation rules ex- tracted from an aligned and parsed bitext. Colored boxes represent aligned phrases and [X] is a non-terminal. …

Content truncated to 500 words