An Algorithm for Simultaneously Bracketing Parallel Texts by Aligning Words

An Algorithm for Simultaneously Bracketing Parallel Texts by Aligning Words Dekai Wu HKUST Department of Computer Science University of Science & Technology Clear Water Bay, Hong Kong dekai@cs, ust. hk Abstract We describe a grammarless method for simul- taneously bracketing both halves of a paral- lel text and giving word alignments, assum- ing only a translation lexicon for the language pair. We introduce inversion-invariant trans- duction grammars which serve as generative models for parallel bilingual sentences with weak order constraints. Focusing on Wans- duction grammars for bracketing, we formu- late a normal form, and a stochastic version amenable to a maximum-likelihood bracketing algorithm. Several extensions and experiments are discussed. 1 Introduction Parallel corpora have been shown to provide an extremely rich source of constraints for statistical analysis (e.g., Brown et al. 1990; Gale & Church 1991; Gale et al. 1992; Church 1993; Brown et al. 1993; Dagan et al. 1993; Dagan & Church 1994; Fung & Church 1994; Wu & Xia 1994; Fung & McKeown 1994). Our thesis in this paper is that the lexical information actually gives suffi- cient information to extract not merely word alignments, but also bracketing constraints for both parallel texts. Aside from purely linguistic interest, bracket structure has been empirically shown to be highly effective at con- straining subsequent training of, for example, stochas- tic context-free grammars (Pereira & ~ 1992; Black et al. 1993). Previous algorithms for automatic bracketing operate on monolingual texts and hence re- quire more grammatical constraints; for example, tac- tics employing mutual information have been applied to tagged text (Magerumn & Marcus 1990). Algorithms for word alignment attempt to find the matching words between parallel sentences. 1 Although word alignments are of little use by themselves, they provide potential anchor points for other applications, or for subsequent learning stages to acquire more inter- esting structures. Our technique views word alignment 1 Wordmatching is a more accurate term than word alignment since the matchings may cross, but we follow the literature. and bracket annotation for both parallel texts as an inte- grated problem. Although the examples and experiments herein are on Chinese and English, we believe the model is equally applicable to other language pairs, especially those within the same family (say Indo-European). Our bracketing method is based on a new formalism called an inversion.invariant transduction grammar. By their nature inversion-invariant transduction grammars overgenerate, because they permit too much constituent- ordering freedom. Nonetheless, they turn out to be very useful for recognition when the true grammar is not fully known. Their purpose is not to flag ungrammatical in- pots; instead they assume that the inputs are grammatical, the aim being to extract structure from the input data, in kindred spirit with robust parsing. 2 Inversion-Invariant Transduction Grammars A Wansduction grammar is a bilingual model that gen- erates two output streams, one for each language. The usual view of transducers as having one input stream and one output stream is more appropriate for restricted or deterministic finite-state machines. Although finite-state transducers have …

Content truncated to 500 words