Learning context-sensitive synchronous rules

Learning context-sensitive synchronous rules⋆ Anders Søgaard Dpt. of Linguistics University of Potsdam soegaard@ling.uni-potsdam.de Abstract. Context-sensitive alignments are shown to be frequent in hand-aligned parallel corpora, e.g. in 24%–85% of the sentence pairs in the corpora documented in [GPCC08]. A O(|G|n6) time strict extension of inversion transduction grammars (ITGs) [Wu97] called (2,2)-BRCGs is proposed in [Søg08] that induces such alignments. The increase in generative capacity comes from the ability to copy strings in derivations, which means that the (i) intersection of two translations and (ii) the union of two alignment structures are easily defined. The problem for real-life applications is how to induce the grammars from available re- sources; in particular, how to learn when copying is needed. This paper presents a quadratic time algorithm that reduces the problem of how to induce (2,2)-BRCGs from m : n-alignments to the same problem for ITGs by unravelling alignment structures. The algorithm was run on a parallel corpus in the Copenhagen Dependency Treebank [BK07] (Danish–English); the ratio of new alignment structures over the number of sentence pairs was 38.08%. For the ones in [GPCC08], the size of the corpora increased by a factor of 1.74–2.0. 1 Introduction Consider the simple example of a translation from English into Danish below: 1. There was a discussion between two women. 2. Der fandt en diskussion sted mellem to kvinder. The discontinuous constituent in Danish, fandt sted (lit. ’found place’), is fully idiomatic and therefore necessarily a translation unit. The non-contiguous noun-preposition pairs, discussion between and diskussion mellem, are perhaps not idiomatic, but conventionalized and idiosyncratic in the sense that the in- formation that the nouns select the prepositions in question must be stored in their lexical entries. It is thus best to treat them as indivisible translation units. The most plausible alignment in this case is thus as follows: Th. was a disc. btw. tw. w. Der fandt en disk. sted ml. to kv. ⋆ This work was supported by the German Research Foundation in the Emmy Noether project Ptolemaios on grammar learning from parallel corpora. 12th EAMT conference, 22-23 September 2008, Hamburg, Germany 170 It is not difficult to see that this alignment cannot be induced by many formalisms for syntax-based machine translation, incl. inversion transduction grammar (ITG) [Wu97], synchronous context-free grammar (SCFG) [Chi07] and synchronous tree substitution grammar (STSG) [Eis03]. The important part of the alignment is this: ai aj bk bl bm bn The structure is called a cross-serial discontinuous translation unit (cross- serial DTU) below. The inability of the above theories to induce cross-serial DTUs follows from the observation that if bk and bm in the above are generated or recognized simultaneously in any of the above theories, bl and bn cannot be generated or recognized simulaneously. This is a straight-forward consequence of the context-freeness of the component grammars. Context-sensitivity does not, on the other hand, imply the ability to induce cross-serial DTUs. In synchronous tree-adjoining grammar (STAG) [SS90], for instance, the adjunction operation allows us to induce DTUs, but not cross-serial …

Content truncated to 500 words