Exact Decoding with Multi Bottom-Up Tree Transducers

Proceedings of the Tenth Workshop on Statistical Machine Translation, pages 164–171, Lisboa, Portugal, 17-18 September 2015. c⃝2015 Association for Computational Linguistics. Exact Decoding with Multi Bottom-Up Tree Transducers∗ Daniel Quernheim Institut f¨ur Maschinelle Sprachverarbeitung University of Stuttgart daniel@ims.uni-stuttgart.de Abstract We present an experimental statistical tree-to-tree machine translation system based on the multi-bottom up tree trans- ducer including rule extraction, tuning and decoding. Thanks to input parse forests and a “no pruning” strategy during decod- ing, the obtained translations are compet- itive. The drawbacks are a restricted cov- erage of 70% on test data, in part due to exact input parse tree matching, and a rel- atively high runtime. Advantages include easy redecoding with a different weight vector, since the full translation forests can be stored after the first decoding pass. 1 Introduction In this contribution, we present an implementation of a translation model that is based on ℓ-XMBOT (the multi bottom-up tree transducer of Arnold and Dauchet (1982) and Lilin (1978)).1 Intuitively, an MBOT is a synchronous tree sequence substitution grammar (STSSG, Zhang et al. (2008a); Zhang et al. (2008b); Sun et al. (2009)) that has discon- tiguities only on the target side (Maletti, 2011). From an algorithmic point of view, this makes the MBOT more appealing than STSSG as demon- strated by Maletti (2010). Formally, MBOT is expressive enough to express all sensible trans- lations (Maletti, 2012)2. Figure 2 displays sam- ple rules of the MBOT variant, called ℓ-XMBOT, ∗This work was supported by Deutsche Forschungsge- meinschaft grant MA/4959/1–1. 1The system presented in this paper is variant of the sys- tem presented at last year’s workshop (Quernheim and Cap, 2014), without morphological enhancements. 2A translation is sensible if it is of linear size increase and can be computed by some (potentially copying) top-down tree transducer. that we use (in a graphical representation of the trees and the alignment). Recently, a shallow ver- sion of MBOT has been integrated into the popular Moses toolkit (Braune et al., 2013). Our imple- mentation is exact in the sense that it does abso- lutely no pruning during decoding and thus pre- serves all translation candidates, while having no mechanism to handle unknown structures. (We added dummy rules that leave unseen lexical ma- terial untranslated.) The coverage is thus limited, but still considerably high. Source-side and target- side syntax restrict the search space so that decod- ing stays tractable. Only the language model scor- ing is implemented as a separate reranker. This has several advantages: (1) We can use input parse forests (Liu et al., 2009). (2) Not only is the out- put optimal with regard to the theoretical model, also the space of translation candidates can be ef- ficiently stored as a weighted regular tree gram- mar. The best translations can then be extracted using the k-best algorithm by Huang and Chiang (2005). Rule weights can be changed without the need for explicit redecoding, the parameters of the log-linear model can be changed, and even new features can be added. These properties are …

Content truncated to 500 words