Disambiguation Strategies for Data-Oriented Translation

Disambiguation Strategies for Data-Oriented Translation Mary Hearne and Andy Way∗ National Centre for Language Technology, School of Computing, DCU, Dublin, Ireland {mhearne | away}@computing.dcu.ie Abstract The Data-Oriented Translation (DOT) model – originally proposed in (Poutsma, 1998, 2003) and based on Data-Oriented Parsing (DOP) (e.g. (Bod, Scha, & Sima’an, 2003)) – is best described as a hybrid model of translation as it combines examples, linguistic information and a statisti- cal translation model. Although theoretically interesting, it inherits the computational complexity associated with DOP. In this paper, we focus on one computational challenge for this model: efficiently selecting the ‘best’ translation to output. We present four different disambiguation strategies in terms of how they are implemented in our DOT system, along with ex- periments which investigate how they compare in terms of accuracy and efficiency. 1 Introduction The merits of combining the positive el- ements of the rule-based and data-driven approaches to MT are clear: a combined model has the potential to be highly ac- curate, robust, cost-effective to build and adaptable to different domains. Neverthe- less, how best to combine these techniques into a model which retains the positive char- acteristics of each approach, while inherit- ing as few of the disadvantages as possible, remains a challenging problem. One pos- sible solution is the Data-Oriented Trans- lation (DOT) model originally proposed in (Poutsma, 1998, 2003), which is based on Data-Oriented Parsing (DOP) (e.g. (Bod et al., 2003)) and combines examples, lin- guistic information and a statistical transla- tion model. Although DOT embodies many positive characteristics on a theoretical level, it also inherits the computational complexity asso- ciated with DOP. In this paper, we focus on one of the computational challenges: ef- ficiently selecting the ‘best’ translation to ∗This work was supported by Science Foundation Ireland grant 05/IN/1732. output. The DOT model calls for rank- ing of the output translations according to translation probability over a DOT gram- mar. However, this is analogous to the prob- lem of finding the most probable parse over a DOP grammar, which has been shown to be an NP-hard problem (Sima’an, 1996). As the exact solution to this problem cannot be found in an efficient way, we must ei- ther find a way of approximating the search for the most probable translation such that we do not perform an exhaustive search of the space of possible derivations, or we must choose a different criterion to maximise. In this paper, we consider both of these possibilities. We use random sampling to compute the most probable translation (MPT) for each input string without hav- ing to look at every derivation, and thus output the MPT as the best translation. However, algorithms which approximate an NP-hard search problem are generally not adopted if a deterministic alternative can be found which does not introduce an unac- ceptable degradation in performance. Thus, we also disambiguate by selecting for output the translation yielded by the most probable representation (or bilingual parse) (MPP), (a) S S NP VP NP VP he V NP …

Content truncated to 500 words