Approximate Sentence Retrieval for Scalable and Efficient Example-Based Machine Translation

Proceedings of COLING 2012: Technical Papers, pages 1571–1586, COLING 2012, Mumbai, December 2012. Approximate Sentence Retrieval for Scalable and Efficient Example-based Machine Translation Johannes Leveling Debasis Ganguly Sandipan Dandapat Gareth J.F. Jones Centre for Next Generation Localisation (CNGL) School of Computing, Dublin City University Dublin, Ireland {jleveling, dganguly, sdandapat, gjones}@computing.dcu.ie ABSTRACT Approximate sentence matching (ASM) is an important technique for tasks in machine translation (MT) such as example-based MT (EBMT) which influences the translation time and the quality of translation output. We investigate different approaches to find similar sentences in an example base and evaluate their efficiency (runtime), effectiveness, and the resulting quality of translation output. A comparison of approaches demonstrates that i) a sequential computation of the edit distance between an input sentence and all sentences in the example base is not feasible, even when efficient algorithms to compute the edit distance are employed; ii) in-memory data structures such as tries and ternary search trees are more efficient in terms of runtime, but are not scalable for large example bases; iii) standard IR models which only cover material similarity (e.g. term overlap), do not perform well in finding the approximate matches, due to their lack of handling word order and word positions. We propose a new retrieval model derived from language modeling (LM), named LM-ASM, to include positional and ordinal similarities in the matching process, in addition to material similarity. Our IR based retrieval experiments involve reranking the top-ranked documents based on their true edit distance score. Experimental results show that i) IR based approaches result in about 100 times faster translation; ii) LM-ASM approximates edit distance better than standard LM by about 10%; and iii) surprisingly, LM-ASM even improves MT quality by 1.52% in comparison to sequential edit distance computation. KEYWORDS: Example-Based Machine Translation, Information Retrieval, Approximate Sen- tence Matching, Edit Distance. 1571 1 Introduction The quality of data-driven machine translation (MT) mostly depends on the size of parallel data available for training. Although statistical MT is considered as the state-of-the-art, its one lim- itation is that it discards the training data once the translation model and language model have been generated. This sometimes can lead to poor quality translations because translation context is limited by the value of n. In contrast, example-based MT (EBMT) usually stores the full sen- tence pairs in source and target data in an example base and uses translations of sentences similar to the input sentence as a template for translation. Thus, EBMT systems can often better cap- ture long range dependencies and rich morphology. State-of-the-art MT systems comprise both statistical and example-based MT components (Dandapat et al., 2012). Typical EBMT systems (Somers, 2003; Nagao, 1984) comprise three processing stages to translate an input sentence Q with information from an example base of sentence pairs (Si, Ti), where Si and Ti are in source and target language, respectively: i) Matching, where sentences similar to Q are identified, and the translation template Ti with the maximum similarity between Q and Si is used as …

Content truncated to 500 words