Packed rules for automatic transfer-rule induction

Packed Rules for Automatic Transfer-rule Induction Yvette Graham and Josef van Genabith National Centre for Language Technology, School of Computing, Dublin City University, Dublin 9, ´Eire josef,ygraham@computing.dcu.ie Abstract We present a method of encoding transfer rules in a highly efficient packed structure us- ing contextualized constraints (Maxwell and Kaplan, 1991), an existing method of encod- ing adopted from LFG parsing (Kaplan and Bresnan, 1982; Bresnan, 2001; Dalrymple, 2001). The packed representation allows us to encode O(2n) transfer rules in a single packed representation only requiring O(n) storage space. Besides reducing space requirements, the representation also has a high impact on the amount of time taken to load large num- bers of transfer rules to memory with very little trade-off in time needed to unpack the rules. We include an experimental evaluation which shows a considerable reduction in space and time requirements for a large set of auto- matically induced transfer rules by storing the rules in the packed representation. 1 Introduction Probabilistic Transfer-Based Machine Translation is one of several current approaches to machine trans- lation that combine data-driven statistical methods with the use of linguistic information (Quirk et al., 2005; Koehn and Hoang, 2007; Ding and Palmer, 2005; Charniak et al., 2003; Lavie, 2008; Riezler and Maxwell, 2006; Bojar and Hajiˇc, 2008). Traditionally, transfer rules were manually de- veloped. Recently, methods of automatically in- ducing transfer rules from bilingual corpora have emerged (Hajiˇc et al., 2002; Eisner, 2003; Bojar and Hajiˇc, 2008; Riezler and Maxwell, 2006). Acquiring transfer rules automatically from bilingual corpora has several advantages. One obvious advantage is that automatic methods of rule induction are much quicker than manual rule development. This means that a much larger quantity of transfer rules can now be produced. Riezler and Maxwell (2006) use feature structures of the Lexical Functional Grammar (LFG) formal- ism (Kaplan and Bresnan, 1982; Bresnan, 2001; Dalrymple, 2001) for deep transfer. They impose a limit of a maximum of three primitive rules to con- struct a complex rule 1. We believe removing arbi- trary limits on the number of transfer rules induced could result in improved translations, and therefore we wish to induce as many different size rules as possible from a pair of parsed training sentences 2. Short rules 3 are needed for high coverage of un- seen sentences, but where possible larger rules 4 are preferred so as to increase the likelihood of a flu- ent target language sentence (all other things being equal). Another issue for transfer rule induction is the amount of linguistic information that should be kept in the transfer rules. We would like to investigate the effects of keeping all or most of the linguistic infor- mation in the rules. If we both increase the number of induced rules and increase the amount of infor- 1Riezler and Maxwell (2006) construct primitive transfer rules using SMT phrases and then construct larger rules by com- bining contiguous primitive rules. 2The notion of different size rules we refer to is related to different length phrases …

Content truncated to 500 words