How do purely statistical machine translators deal with different word orders?

Question

Even relatively closely related languages can differ greatly in word order. Take English and German for instance.

English is pretty boringly subject-verb-object whereas in German the finite verb must come second, all other verbs go to the end, and separable prefixes also all go to the end.

According to machine translation lore, the systems work better in inverse proportion to the number of linguists in the project.

So given a complete lack of understanding of the source language how do machine translation systems manage these different word orders?

Do they actually have to know some linguistics after all and hence are not so pure as touted? Or do they actually do worse that touted under these conditions. Or are there statistical methods that somehow take into account even word ordering differences without recourse to linguistic knowledge?

Answer 1

I won't claim to be an expert on statistical machine translation (SMT) by any means, but as I understand it (an understanding with which my cursory Googling appears to agree), differing word orders is actually quite a large problem in SMT, and causes many problems, as you expect. As with any difficult problem, there are dozens of solutions which have been attempted to varying degrees of success.

Theoretically, if your statistical language model is robust enough, these differences in word order would be accounted for even without any foreknowledge of either language. The problem is that a model that robust is expensive: not just in the traditional sense, but also in processing power. I imagine that evaluating texts with such a model would take a prohibitively long amount of time.

So basically, yes: all of the solutions of which I am aware are given at least some amount of data about the structure of a language, and then the statistical model expands from there. One approach which shows up in many results in my Google search is word reordering -- basically (at least as I understand it, and perhaps a bit oversimplified), finding the best 1:1 correspondence in word order and evaluating the texts with the statistical model from there.

Answer 2

There are several quite complex statistical models that try to deal with this, with various degrees of success. Phrase based systems, linguistically perhaps a misnomer as the phrases have nothing to do with syntax at all, tend to be able to alleviate this somewhat. Phrases are found by looking at paralell corpora. Hierarchal phrase based systems can work even better. Instead of translating word by word, the system tries to translate complete phrases. The trouble with all these models is that it's very difficult to estimate the parameters in an acceptable way, there just isn't enough data. Furthermore, the models quite quickly get computationally very expensive, both in time and space.

It is common though, to construct a big n-gram language model of the target language, and use that to rerank complete sentences. This can deal with small differences in word order, for instance if the adjective goes to the left or the right of the noun it modifies, as the correct word order will typically have a much higher likelihood assigned to it by the model. As n-grams have limited length in practice, the model fails when the movement is big, as in English to German. In that case, the language model reranking usually only works for short sentences, where the movement is inside the n of the n-grams.

Answer 3

Even though nominally, statistical MT is distinct from syntactical MT, at its simplest, statistical MT deals with word order (syntax by another name), by n-grams, collecting statistics on pairs of words (in order), triples, etc., with diminishing returns for effort the longer the sequences.

For example, 'of the' is a very common 2 word sequence, but 'the of' is (almost?) nonexistent, so if ever 'of' is translated to, then the word before it is not going to be 'the' and afterword a good chance of being 'the'.

Of course, part of speech tagging (using a plain lookup with some sequential context), can then be used with very short range order constraints.