Statistical Syntax-Directed Translation with Extended Domain of Locality

Statistical Syntax-Directed Translation with Extended Domain of Locality Liang Huang University of Pennsylvania Philadelphia, PA 19104 lhuang3@cis.upenn.edu Kevin Knight USC/ISI Marina del Rey, CA 90292 knight@isi.edu Aravind Joshi University of Pennsylvania Philadelphia, PA 19104 joshi@cis.upenn.edu Abstract In syntax-directed translation, the source- language input is first parsed into a parse- tree, which is then recursively converted into a string in the target-language. We model this conversion by an extended tree- to-string transducer that has multi-level trees on the source-side, which gives our system more expressive power and flexi- bility. We also define a direct probabil- ity model and use a linear-time dynamic programming algorithm to search for the best derivation. The model is then ex- tended to the general log-linear frame- work in order to incorporate other features like n-gram language models. We devise a simple-yet-effective algorithm to gener- ate non-duplicate k-best translations for n- gram rescoring. Preliminary experiments on English-to-Chinese translation show a significant improvement in terms of trans- lation quality compared to a state-of-the- art phrase-based system. 1 Introduction The concept of syntax-directed translation was originally proposed in compiling (Irons, 1961; Lewis and Stearns, 1968; Aho and Ullman, 1972), where the source program is parsed into a tree rep- resentation that guides the generation of the object code. In other words, the translation is directed by a syntactic tree. In this context, a syntax-directed translator consists of two components, a source- language parser and a recursive converter which is usually modeled as a top-down tree-to-string transducer (G´ecseg and Steinby, 1984). This paper adapts the idea of syntax-directed translation to statistical machine translation (MT). We apply stochastic operations at each node of the source-language parse-tree and search for the best       S NP(1) ↓ VP VB(2) ↓ NP(3) ↓ , S VB(2) ↓ NP(1) ↓ NP(3) ↓       Figure 1: An example of complex reordering rep- resented as an STSG rule, which is beyond any SCFG. derivation (a sequence of translation steps) that converts the whole tree into some target-language string with the highest probability. However, the structural divergence across languages often re- sults in non-isomorphic parse-trees that is beyond the power of SCFGs. For example, the S(VO) structure in English is translated into a VSO word- order in Arabic, an instance of complex reordering not captured by any SCFG (Fig. 1). To alleviate the non-isomorphism problem, (synchronous) grammars with richer expressive power have been proposed whose rules apply to larger fragments of the tree. For example, Shieber and Schabes (1990) introduce synchronous tree- adjoining grammar (STAG) and Eisner (2003) uses a synchronous tree-substitution grammar (STSG), which is a restricted version of STAG with no adjunctions. STSGs and STAGs gener- ate more tree relations than SCFGs, e.g. the non- isomorphic tree pair in Fig. 1. This extra expres- sive power lies in the extended domain of locality (EDL) (Joshi and Schabes, 1997), i.e., elementary structures beyond the scope of one-level context- free productions. Besides being linguistically mo- tivated, the need …

Content truncated to 500 words