Loosely Tree-Based Alignment for Machine Translation

Loosely Tree-Based Alignment for Machine Translation Daniel Gildea University of Pennsylvania dgildea@cis.upenn.edu Abstract We augment a model of translation based on re-ordering nodes in syntactic trees in order to allow alignments not conforming to the original tree structure, while keep- ing computational complexity polynomial in the sentence length. This is done by adding a new subtree cloning operation to either tree-to-string or tree-to-tree align- ment algorithms. 1 Introduction Systems for automatic translation between lan- guages have been divided into transfer-based ap- proaches, which rely on interpreting the source string into an abstract semantic representation from which text is generated in the target lan- guage, and statistical approaches, pioneered by Brown et al. (1990), which estimate parameters for a model of word-to-word correspondences and word re-orderings directly from large corpora of par- allel bilingual text. Only recently have hybrid approaches begun to emerge, which apply prob- abilistic models to a structured representation of the source text. Wu (1997) showed that restrict- ing word-level alignments between sentence pairs to observe syntactic bracketing constraints signif- icantly reduces the complexity of the alignment problem and allows a polynomial-time solution. Alshawi et al. (2000) also induce parallel tree struc- tures from unbracketed parallel text, modeling the generation of each node’s children with a finite-state transducer. Yamada and Knight (2001) present an algorithm for estimating probabilistic parameters for a similar model which represents translation as a se- quence of re-ordering operations over children of nodes in a syntactic tree, using automatic parser out- put for the initial tree structures. The use of explicit syntactic information for the target language in this model has led to excellent translation results (Ya- mada and Knight, 2002), and raises the prospect of training a statistical system using syntactic informa- tion for both sides of the parallel corpus. Tree-to-tree alignment techniques such as prob- abilistic tree substitution grammars (Hajiˇc et al., 2002) can be trained on parse trees from parallel treebanks. However, real bitexts generally do not exhibit parse-tree isomorphism, whether because of systematic differences between how languages ex- press a concept syntactically (Dorr, 1994), or simply because of relatively free translations in the training material. In this paper, we introduce “loosely” tree-based alignment techniques to address this problem. We present analogous extensions for both tree-to-string and tree-to-tree models that allow alignments not obeying the constraints of the original syntactic tree (or tree pair), although such alignments are dispre- ferred because they incur a cost in probability. This is achieved by introducing a clone operation, which copies an entire subtree of the source language syn- tactic structure, moving it anywhere in the target language sentence. Careful parameterization of the probability model allows it to be estimated at no ad- ditional cost in computational complexity. We ex- pect our relatively unconstrained clone operation to allow for various types of structural divergence by providing a sort of hybrid between tree-based and unstructured, IBM-style models. We first present the tree-to-string model, followed by the tree-to-tree model, before moving on to align- ment results for …

Content truncated to 500 words