tailieunhanh - Báo cáo khoa học: "An Efficient Generation Algorithm for Lexicalist MT"

The lexicalist approach to Machine Translation offers significant advantages in the development of linguistic descriptions. However, the Shake-and-Bake generation algorithm of (Whitelock, 1992) is NPcomplete. We present a polynomial time algorithm for lexicalist MT generation provided that sufficient information can be transferred to ensure more determinism. | An Efficient Generation Algorithm for Lexicalist MT Victor Poznanski John L. Beaven Pete Whitelock SHARP Laboratories of Europe Ltd. Oxford Science Park Oxford 0X4 4GA United Kingdom vp jib pete @ Abstract The lexicalist approach to Machine Translation offers significant advantages in the development of linguistic descriptions. However the Shake-and-Bake generation algorithm of Whitelock 1992 is NP-complete. We present a polynomial time algorithm for lexicalist MT generation provided that sufficient information can be transferred to ensure more determinism. 1 Introduction Lexicalist approaches to MT particularly those incorporating the technique of Shake-and-Bake generation Beaven 1992a Beaven 1992b Whitelock 1994 combine the linguistic advantages of transfer Arnold et al. 1988 Allegranza et al. 1991 and interlingual Nirenburg et al. 1992 Dorr 1993 approaches. Unfortunately the generation algorithms described to date have been intractable. In this paper we describe an alternative generation component which has polynomial time complexity. Shake-and-Bake translation assumes a source grammar a target grammar and a bilingual dictionary which relates translationally equivalent sets of lexical signs carrying across the semantic dependencies established by the source language analysis stage into the target language generation stage. The translation process consists of three phases 1. A parsing phase which outputs a multiset or bag of source language signs instantiated with sufficiently rich linguistic information established by the parse to ensure adequate translations. 2. A lexical-semantic transfer phase which employs the bilingual dictionary to map the bag We wish to thank our colleagues K erima Benkerimi David Elworthy Peter Gibbins Ian Johnson Andrew Kay and Antonio Sanfilippo at SLE and our anonymous reviewers for useful feedback and discussions on the research reported here and on earlier drafts of this paper. of instantiated source signs onto a bag of .