Using Brackets to Improve Search for Statistical Machine Translation

Using Brackets to Improve Search for Statistical Machine Translation Dekai WU� Cindy NG HKUST Department of Computer Science Hong Kong University of Science & Technology Clear Water Bay, Hong Kong dekaiacs .ust shk Abstract We propose a method to improve search time and space complexity in statistical machine translation architectures, by employing linguistic bracketing information on the source language sentence. It is one of the advantages of the probabilistic formulation that competing translations may be compared and ranked by a principled measure, but at the same time, optimizing likelihoods over the translation space dictates heavy search costs. To make statistical architectures practical, heuristics to reduce search computation must be incorporated. An experiment applying our method to a prototype Chinese-English translation system demonstrates substantial improvement. 1 Introduction The work we discuss here is embedded within the SILC project at HKUST (Wu 1994; Fung Wu 1994; Wu & Fung 1994; Wu & Xia 1995; Wu 1995a; Wu 1995b; Wu 1995c) which focuses on problems of machine translation learning. We are developing machine learning techniques to bear upon the shortage of adequate knowledge resources for natural language analysis, particularly for Chinese where there is relatively little previous computational linguistics research from which to draw. It is one of our objectives to investigate the suitability for Chinese of the statistical translation model originally proposed by IBM (Brown et al. 1990; Brown et al. 1993) for Indo-European languages. Henceforth we will therefore use "Chinese" to refer to the source language and "English" to refer to the target language, reflecting the . prototype SILC system. An inherent characteristic of the basic IBM stochastic channel model is the large search space, due to the wide range of distortions that must be allowed in order to successfully transfer sentences of one language to the other. The underlying generative model maps target•language strings into source-language strings (i.e., in the reverse direction from trans- lation). During translation, a maximum likelihood target•language string is sought for the 195 input source-language string, according to Bayes' formula: (1)� argmax Pr(elc) = argmax Pr(cle) Pr(e) e� e The distortion operations in the channel model are chosen to permit sufficient flexibility to map English strings into Chinese translations that have greatly different word order. (It is a simplifying assumption of the model that the only sentence translations considered are those where the majority of words can be translated by lexical substitution.) The scheme admits many implausible mappings along with the legitimate translations, but thereby gains robustness. During the recognition process, legitimate translations will be selected so long as the implausible mappings have lower likelihoods. The IBM model employs an A* search strategy on the space of translation hypotheses using incremental hypothesis expansion. The distance-to-goal heuristic is not admissible but reasonable estimates can be made yielding good performance. This approach arguably provides the highest possible accuracy assuming that no additional information is available. In reality, however, additional information can usually be made available. The method we propose here exploits one such type of information, namely, that …

Content truncated to 500 words