Induction of Probabilistic Synchronous Tree-Insertion Grammars for Machine Translation

Induction of Probabilistic Synchronous Tree-Insertion Grammars for Machine Translation Rebecca Nesson, Stuart Shieber, and Alexander Rush Division of Engineering and Applied Sciences Harvard University Cambridge, MA 02138 {nesson,shieber,rush}@eecs.harvard.edu Abstract The more expressive and flexible a base formalism for machine translation is, the less efficient parsing of it will be. How- ever, even among formalisms with the same parse complexity, some formalisms better realize the desired characteristics for machine translation formalisms than others. We introduce a particular for- malism, probabilistic synchronous tree- insertion grammar (PSTIG) that we argue satisfies the desiderata optimally within the class of formalisms that can be parsed no less efficiently than context-free gram- mars and demonstrate that it outperforms state-of-the-art word-based and phrase- based finite-state translation models on training and test data taken from the Eu- roParl corpus (Koehn, 2005). We then ar- gue that a higher level of translation qual- ity can be achieved by hybridizing our in- duced model with elementary structures produced using supervised techniques such as those of Groves et al. (2004). 1 Introduction In this paper we identify a base formalism, probabilistic synchronous tree-insertion grammar (PSTIG), for a statistical machine translation system that we propose: 1. maximizes, within its efficiency class, the qual- ity of the MT system induced unsupervised from aligned sentence pairs; and 2. is suitable for hybridization with linguistically- motivated elementary structures (constructed manually, or obtained automatically with or without supervision). We begin with an argument from first principles for the choice of PSTIG as a base formalism for syntax-aware statistical machine translation (SMT). We then present our implementation of a system that induces a PSTIG unsupervised from data and show that it outperforms a state-of-the-art phrase- based SMT system in both automatic and human evaluation. We conclude by proposing a method for hybridizing our system to include linguistically- motivated elementary structures that draws on recent results in Data-Oriented Parsing. In Section 2 we place our work in the context of similar work in the field and argue for the efficacy of choosing a base formalism in the class of formalisms that can be processed no less efficiently than context-free grammars. In Section 3, we present a formalism, probabilistic synchronous tree-insertion grammar (PSTIG), that more fully satisfies the desired characteristics than context-free grammars. In Sections 4 and 5 we give the parsing algorithm and discuss how we induce a PSTIG grammar from data by synchronous parsing. We demonstrate in Section 6 that the induced model outperforms both word-based and phrase-based finite-state models on a subset of the EuroParl corpus. We suggest in Section 7 that, without increasing the expressivity of the base formalism beyond context-free, substantially higher quality translations can be produced by unsupervised induction systems that can easily be hybridized with 128 Proceedings of the 7th Conference of the Association for Machine Translation in the Americas, pages 128-137, Cambridge, August 2006. ©2006 The Association for Machine Translation in the Americas linguistically-motivated elementary structures gen- erated manually or though a supervised process. In particular, we propose a method of …

Content truncated to 500 words