An Efficient Generation Algorithm for Lexicalist MT

An Efficient Generation Algorithm for Lexicalist MT Victor Poznafiski, John L. Beaven &: Pete Whitelock * SHARP Laboratories of Europe Ltd. Oxford Science Park, Oxford OX4 4GA United Kingdom {vp ~i lb,pete } @sharp. co.uk Abstract The lexicalist approach to Machine Trans- lation 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 pro- vided that sufficient information can be transferred to ensure more determinism. 1 Introduction Lexicalist approaches to MT, particularly those in- corporating the technique of Shake-and-Bake gen- eration (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) ap- proaches. Unfortunately, the generation algorithms described to date have been intractable. In this pa- per, we describe an alternative generation compo- nent which has polynomial time complexity. Shake-and-Bake translation assumes a source grammar, a target grammar and a bilingual dictio- nary which relates translationally equivalent sets of lexical signs, carrying across the semantic dependen- cies 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 es- tablished by the parse to ensure adequate trans- lations. 2. A lexical-semantic transfer phase which em- ploys the bilingual dictionary to map the bag *We wish to thank our colleagues Kerima Benkerimi, David Elworthy, Peter Gibbins, Inn Johnson, Andrew Kay and Antonio Sanfilippo at SLE, and our anonymous reviewers for useful feedback and discussions on the re- search reported here and on earlier drafts of this paper. of instantiated source signs onto a bag of target language signs. 3. A generation phase which imposes an order on the bag of target signs which is guaranteed grammatical according to the monolingual tar- get grammar. This ordering must respect the linguistic constraints which have been trans- ferred into the target signs. The Shake-an&Bake generation algorithm of (Whitelock, 1992) combines target language signs using the technique known as generate-and-test. In effect, an arbitrary permutation of signs is input to a shift-reduce parser which tests them for grammatical well-formedness. If they are well-formed, the system halts indicating success. If not, another permutation is tried and the process repeated. The complexity of this algorithm is O(n!) because all permutations (n! for an input of size n) may have to be explored to find the correct answer, and indeed must be explored in order to verify that there is no answer. Proponents of the Shake-and-Bake approach have employed various techniques to improve generation efficiency. For example, (Beaven, 1992a) employs a chart to avoid recalculating the same combina- tions of signs more than once during testing, and (Popowich, 1994) proposes a more general technique for storing which rule applications have been at- tempted; (Brew, 1992) avoids certain pathological cases by employing …

Content truncated to 500 words