Statistical Machine Translation by Parsing

Statistical Machine Translation by Parsing I. Dan Melamed Computer Science Department New York University New York, NY, U.S.A. 10003-6806 � lastname � @cs.nyu.edu Abstract In an ordinary syntactic parser, the input is a string, and the grammar ranges over strings. This paper explores generalizations of ordinary parsing algo- rithms that allow the input to consist of string tu- ples and/or the grammar to range over string tu- ples. Such algorithms can infer the synchronous structures hidden in parallel texts. It turns out that these generalized parsers can do most of the work required to train and apply a syntax-aware statisti- cal machine translation system. 1 Introduction A parser is an algorithm for inferring the structure of its input, guided by a grammar that dictates what structures are possible or probable. In an ordinary parser, the input is a string, and the grammar ranges over strings. This paper explores generalizations of ordinary parsing algorithms that allow the input to consist of string tuples and/or the grammar to range over string tuples. Such inference algorithms can perform various kinds of analysis on parallel texts, also known as multitexts. Figure 1 shows some of the ways in which ordi- nary parsing can be generalized. A synchronous parser is an algorithm that can infer the syntactic structure of each component text in a multitext and simultaneously infer the correspondence relation between these structures.1 When a parser’s input can have fewer dimensions than the parser’s gram- mar, we call it a translator. When a parser’s gram- mar can have fewer dimensions than the parser’s input, we call it a synchronizer. The corre- sponding processes are called translation and syn- chronization. To our knowledge, synchronization has never been explored as a class of algorithms. Neither has the relationship between parsing and word alignment. The relationship between trans- lation and ordinary parsing was noted a long time 1A suitable set of ordinary parsers can also infer the syntac- tic structure of each component, but cannot infer the correspon- dence relation between these structures. translation synchronization synchronous parsing 1 parsing 3 2 2 3 1 ... ... ordinary I = dimensionality of input D = dimensionality of grammar synchronization (I >= D) parsing synchronous (D=I) word alignment translation (D >= I) ordinary parsing (D=I=1) generalized parsing (any D; any I) Figure 1: Generalizations of ordinary parsing. ago (Aho & Ullman, 1969), but here we articu- late it in more detail: ordinary parsing is a spe- cial case of synchronous parsing, which is a special case of translation. This paper offers an informal guided tour of the generalized parsing algorithms in Figure 1. It culminates with a recipe for using these algorithms to train and apply a syntax-aware statis- tical machine translation (SMT) system. 2 Multitext Grammars and Multitrees The algorithms in this paper can be adapted for any synchronous grammar formalism. The vehicle for the present guided tour shall be multitext grammar (MTG), which is a generalization of context-free grammar to the synchronous case (Melamed, 2003). We shall …

Content truncated to 500 words