A Constraint Satisfaction Approach to Machine Translation

Proceedings of the 13th Annual Conference of the EAMT, pages 182–189, Barcelona, May 2009 A Constraint Satisfaction Approach to Machine Translation Sander Canisius∗,∗∗ and Antal van den Bosch∗ ∗Tilburg centre for Creative Computing, P.O. Box 90153, 5000 LE Tilburg, The Netherlands ∗∗The Netherlands Cancer Institute, P.O. Box 90203, 1006 BE Amsterdam, The Netherlands S.Canisius@nki.nl, Antal.vdnBosch@uvt.nl Abstract Constraint satisfaction inference is pre- sented as a generic, theory-neutral infer- ence engine for machine translation. The approach enables the integration of many different solutions to aspects of the output space, including classification-based trans- lation models that take source-side context into account, as well as stochastic compo- nents such as target language models. The approach is contrasted with a word-based SMT system using the same decoding al- gorithm, but optimising a different objec- tive function. The incorporation of source- side context models in our model filters out many irrelevant candidate translations, leading to superior translation scores. 1 Introduction The vast complexity of the translation task has led designers of machine translation systems to del- egate the task to multiple submodels. The cru- cial task in these systems is the integration of all available information in the best possible way. In this paper we advocate and present an eclec- tic, theory-neutral approach to machine translation that employs constraint satisfaction as the integra- tor method, and that regards the translation task as a structured prediction problem. Structured prediction is a relatively new and emerging field in machine learning in which generic techniques are developed that explicitly model structural properties of the output space (Bakir et al., 2007). Statistical machine translation systems can be seen as a forebearer of this field; conditional random fields (Lafferty et al., 2001) and Searn (Daum´e III, 2006) are more recent ex- ponents of the approach. The typical solution to a structured prediction problem is to regard it as c⃝ 2009 European Association for Machine Translation. a combinatorial optimisation in an output space that spans all possible outputs for a given input. One or more learning components are responsible for learning (parts of) an objective function, and a search (or inference) component finds the output structure that maximises the objective function. Within statistical machine translation systems, the probabilistic underpinning of all involved com- ponents acts as a kind of industrial standard. This has the positive effect that a substantial body of work could be built using the same universal lan- guage. At the same time, it makes the integra- tion of non-stochastic components into statistical machine translation systems sometimes unwieldy. Yet, recent experiments on mixing local classifi- cations of non-stochastic machine learners with statistical MT models (Carpuat and Wu, 2007; Stroppa et al., 2007), has shown its potential. Ar- guably, it makes sense to investigate the gathering of a mix of views on the objective function as in- put to the final search or inference process, and this mix should be eclectic—that is, theory-neutral—to allow extremely different but successful partial so- lutions to the objective function to participate. As we argue in …

Content truncated to 500 words