Word Alignment with Stochastic Bracketing Linear Inversion Transduction Grammar

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 341–344, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Word Alignment with Stochastic Bracketing Linear Inversion Transduction Grammar Markus SAERS and Joakim NIVRE Computational Linguistics Group Dept. of Linguistics and Philology Uppsala University Sweden first.last@lingfil.uu.se Dekai WU Human Language Technology Center Dept. of Computer Science and Engineering HKUST Hong Kong dekai@cs.ust.hk Abstract The class of Linear Inversion Transduction Grammars (LITGs) is introduced, and used to induce a word alignment over a parallel cor- pus. We show that alignment via Stochas- tic Bracketing LITGs is considerably faster than Stochastic Bracketing ITGs, while still yielding alignments superior to the widely- used heuristic of intersecting bidirectional IBM alignments. Performance is measured as the translation quality of a phrase-based ma- chine translation system built upon the word alignments, and an improvementof 2.85 BLEU points over baseline is noted for French– English. 1 Introduction Machine translation relies heavily on word align- ments, which are usually produced by training IBM- models (Brown et al., 1993) in both directions and combining the resulting alignments via some heuris- tic. Automatically training an Inversion Transduc- tion Grammar (ITG) has been suggested as a viable way of producing superior alignments (Saers and Wu, 2009). The main problem of using Bracket- ing ITGs for alignment is that exhaustive biparsing runs in O(n6) time. Several ways to lower the com- plexity of ITGs has been suggested, but in this paper, a different approach is taken. Instead of using full ITGs, we explore the possibility of subjecting the grammar to a linear constraint, making exhaustive biparsing of a sentence pair in O(n4) time possible. This can be further improved by applying pruning. 2 Background A transduction is the bilingual version of a language. A language (Ll) can be formally viewed as a set of sentences, sequences of tokens taken from a speci- fied vocabulary (Vl). A transduction (Te,f) between two languages (Le and Lf) is then a set of sentence pairs, sequences of bitokens from the cross produc- tion of the vocabularies of the two languages being transduced (Ve,f = Ve × Vf). This adds an extra layer of complexity to finding transductions from raw bitexts, as an alignment has to be imposed. Simple (STG) and Syntax Directed (SDTG) Trans- duction Grammars (Aho and Ullman, 1972) can be used to parse transductions between context-free languages. Both work fine as long as a grammar is given and parsing is done as transduction, that is: a sentence in one language is rewritten into the other language. In NLP, interest has shifted away from hand-crafted grammars, towards stochastic gram- mars induced from corpora. To induce a stochas- tic grammar from a parallel corpus, expectations of all possible parses over a sentence pair are typically needed. STGs can biparse sentence pairs in polyno- mial time, but are unable to account for the complex- ities typically found in natural languages. SDTGs do account for the complexities in natural languages, but …

Content truncated to 500 words