Dividing and Conquering Long Sentences in a Translation System

Dividing and Conquering Long Sentences in a Translation System Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, Robert L. Mercer, and Surya Mohanty * IBM Thomas J. Watson Research Center Yorktown Heights, NY 10598 ABSTRACT The time required for our translation system to handle a sentence of length I is a rapidly growing function of i. We describe here a method for analyzing a sentence into a series of pieces that can be translated sequentially. We show that for sentences with ten or fewer words, it is pos- sible to decrease the translation time by 40% with almost no effect on translation accuracy. We argue that for longer sentences, the effect should be more dramatic. Introduction In a recent series of papers, Brown et aL intro- duce a new, statistical approach to machine transla- tion based on the mathematical theory of communi- cation through a noisy channel, and apply it to the problem of translating naturMly occurring French sen- tences into English [1, 2, 3, 4]. They develop a proba- bilistic model for the noisy channel and show how to estimate the parameters of their model from a large collection of pairs of aligned sentences. By treating a sentence in the source language (French) as a garbled version of the corresponding sentence in the target language (English), they recast the problem of trans- lating a French sentence into English as one of find- ing that English sentence which is most likely to be present at the input to the noisy channel when the given French sentence is known to be present at its output. For a French sentence of any realistic length, the most probable English translation is one of a set of "This work was supported, in part, by DARPA con- tract N00014-91-C-0135, administered by the Office of Naval Research. English sentences that, although finite, is nonetheless so large as to preclude an exhaustive search. Brown et aL employ a suboptimal search based on the stack algorithm used in speech recognition. Even so, as we see in Figure 1, the time required for their system to translate a sentence grows very rapidly with sentence length. As a result, they have focussed their attention on short sentences. 100 80 = 60 E 40 ~P E 20 0 I I I I I I T ± o_i -L _oo @ @ ~ 0 I t I I I I 4 6 8 10 12 14 Sentence Length Figure 1: Search time as a function of sentence length. The designatum of some French words is so spe- cific that they can be reliably translated almost any- where they occur without regard for the context in which they appear. For example, only the most con- trived circumstances could require one to translate the French techndtium into English as anything but technetium. Alas, this charming class of words is woe- fully small: for the great majority of words, phrases, and even sentences, the more we know of the context 267 in …

Content truncated to 500 words