Bayes Daze Translation Bleus

With September on us, shadows lengthen at dusk, and thoughts turn to school, Bayes Daze II.   Recall from BD I that you, dear readers, had a homework assignment: run Le pomme a mangé le garçon (‘the apple ate the boy’)[1] through French-to-English Google Translate and see what pops out on the English end. And the answer?  Well, surprise! The Google sausage machine spits out, The boy ate the apple. But…Why? Well, this sin can be laid directly at the feet of Reverend Bayes. Dissecting this behavior a bit further and reverse-engineering Google Translate is a great exercise for those who aren’t familiar with the Bayes biz.  (If you already know this biz, you might want to skip it all, but even so you might still find the explanation intriguing.)  Don’t worry, you have nothing to fear; if you innocently violate some Google patent by figuring this out, we all know the motto “Don’t be evil.” Hah, right. 

OK, so let F1 = our specific French sentence to translate, i.e., le pomme a mangé le garcon. Now, how to find the English sentence E that’s the ‘best’ translation of F1? Well, what’s ‘best’? Let’s say ‘best’ means ‘maximum probability,’ i.e., the most likely translation of F1.  But what probability do we want to maximize?  The simplest idea is that this should be the maximum conditional probability, p(E|F1), the probability of  E given F1 – that is, let E run over all English sentences, and pick the English sentence that maximizes p(E|F1) as the ‘best translation’.[2] And it’s here that we invoke the dear Reverend, rewriting p(E|F1) via Bayes’ Rule as: p(F1|E) x p(E)/ p(F1). So, our job now is to find the particular E sentence that maximizes this new formula.  Note that since F1 (le pomme a…) is fixed, that maximizing p(F1|E) x p(E)/p(F1) is the same as maximizing just its numerator p(F1|E) x p(E),[3]  so we can ignore p(F1) and just maximize this product in the numerator. Why do we do this instead of just figuring out the maximum for p(E|F1) directly?  Well, it’s the familiar strategy of divide-and-conquer: If we tried to maximize p(E |F1) directly, then we must have very, very, very good estimates for all these conditional probabilities. Too hard! We can get a better translation by splitting this probability into the two parts, the first p(F1|E) and the second p(E), even these two probability estimates aren’t very good individually. 

How so?  Well, suppose we decide to give a high likelihood value to p(F1|E) only if the words in F1 are generally translations of words in E, where the words in F1 can be in any order.  Second, we assign p(E) a high likelihood if the sentence E is ‘grammatical.’ (We will say what this comes to momentarily.) Now when we put these two probability estimates together, look what happens! The factor p(F1|E) will help guarantee that a good E will have words that usually translate to the words in F1, irrespective of their order.  So, if E=the boy ate has a high probability score, then so will E=the ate boy.  Some word orders are good English and others aren’t. The factor p(E) has the job of lowering the probability of the ‘bad order’ sentences. As Kevin Knight puts it in his tutorial (from which I have unashamedly cribbed)[4], “p(E) worries about word order so that p(F1|E) doesn’t have to. That makes p(F1|E) easier to build than you may have thought. It only needs to say whether or not some bag of English words corresponds to a bag of French words.”  

In the statistical machine translation biz, the factor p(F1|E) is known as translation model while p(E) is known as the language model. The best translation of our French sentence is found by multiplying these two probabilities together. And so now you can already probably figure out for yourself why E=the boy ate the apple wins over the apple ate the boy: both include the same unordered bag of words, {the, apple, ate, the, boy}, but, just as you’d expect, the probability of p(E)= the boy ate the apple is much, much, much greater than p(E)= the apple ate the boy, which is never found in billions of sentences of English books scanned in by Google (see below)[5].  So the language model dominates the two product factors in such examples, to the virtual exclusion of worrying at all about actual ‘translation.’ Sacre bleu! In other words, you can work as hard as you want to perfect the translation model, really sweating out the details of what English words go with and what French words, but all to no avail. You’ll still get funny examples like this one –which is really only telling you the likelihood of some particular English sentence, essentially ignoring that there is any French there at all. (This is apparently exactly what the English would like everyone to believe anyway, as verified by the famous MPHG[6] corpus.) And if you think this all just a one-off, the list of funny examples can be expanded indefinitely: run Un hippopotame me veut pour Noë1 and you’ll get I want a hippopotamus for Christmas; the German Leute stehlen mein Weißes Auto surfaces as White people stole my car, and so on.[7] But even more strikingly, if you just forget about the translation model and spend all your energies on just the language model, you wind up with a better scoring translation system – at least if one applies the metric that has been conventionally used in such bake-offs, which is called, BLEU. So, then Google Translate beats out other machine translation systems, with the best BLEU scores.

In fact, it’s worth stepping back and thinking a bit more deeply about what’s going on here. How do we actually calculate p(E)?  Well, Knight continues, “People seem to be able to judge whether or not a string is English without storing a database of utterances.  (Have you ever heard the sentence “I like snakes that are not poisonous”?  Are you sure?).  We seem to be able to break the sentence down into components.  If the components are good, and if they combine in reasonable ways, then we say that the string is English…. For computers, the easiest way to break a string down into components is to consider substrings.  An n-word substring is called an n-gram.  If n=2, we say bigram.  If n=3, we say trigram.  If n=1, nerds say unigram, and normal people say word.  If a string has a lot of reasonable n-grams, then maybe it is a reasonable string.  Not necessarily, but maybe.”

Now you already know (in part) why Google has done all this work collecting n-grams! In fact, Google has even scanned enough books (over 5.2 million) to collect enough data to get statistical estimates for 5-grams, such as The boy ate the apple.  If you go here, to Google’s n-gram viewer, and type in The boy ate the apple, along with clicking the button ‘search lots of books’ you’ll see (low) but non-zero probability estimates for this particular 5-word sentence starting about 1900. (This value is actually # of occurrences per year, normalized by the # of books printed in each year. The value’s low because there are lots of other 5-word English sentences.)   But what about the probability for The apple ate the boy ? That has an estimated probability 0, since it never has turned up in any of the books in the database. In practice, since lots of 5-grams will have frequency 0, what you do is smooth the data, falling back in turn to 4-grams, trigrams, bigrams, and, if need be, single word frequencies until we find non-zero values: approximate the 5-gram The apple ate the boy as a weighted average of two 4-grams: p(the|The apple ate) and p(boy|apple ate the). (Note that this doesn’t change our Bayesian best-translation finder, since to play fair we’d have to do something comparable with The boy ate the apple.) In short, the language model is just n-grams. (There’s a lot to this smoothing biz, but that’s not our main aim here; see any recent NLP book such as Juravsky & Martin textbook. In fact, Bayesian inference generally is a kind of ‘smoothing’ method, as we’ll discuss next time.)  So, the more you improve your n-gram language model, the better your translation system’s BLEU score, as Ali Mohammed demonstrates (see note 7).  And for sure Google has the best (largest!) database of n-grams. The kicker is that Ali shows that what the BLEU score actually measures is simply the ability to memorize and retrieve ordered n-grams in the first place! 

And you also know now what the statistically-oriented mean when they talk about a language model: it is simply any probability distribution over a set of sentences. We can estimate this by, say, collecting lots of actually uttered or written sentences. Now in general, the likelihood of any particular sentence won’t completely depend on just whether it’s ‘grammatical’ simpliciter or not in the linguist’s classical sense (though you could try to calculate it this way) – rather, it totes up how frequently that sentence was actually used in the real world, which as we all know could depend on many other factors, like the actual conversational environment, whether you are going to vote for my cousin when he runs for governor of Massachusetts next year (he made me put this shameless plug in, sorry), what you had for breakfast – anything. Now, is this state of affairs a good thing or a bad thing?  Well, you tell me.  If one just goes around and counts up all the butterflies in the world, is that likely to arrive at a good ‘model for butterflies’?  On the other hand, for many (most/all) practical tasks, it’s proved difficult to beat trigrams – 3 word sequence frequencies – as a language model. That’s an interesting fact to ponder, because you may recall that on the minimalist account, nothing about linear order matters (only hierarchical structure, what Noam called in Geneva the ‘Basic Property,’ matters) while on the trigram account, everything about (local) linear order matters, and word triplets don’t give a hoot about the ‘Basic Property.’ Perhaps this is just some reflection of the collapse of local hierarchical structure onto the local linear sound stream. Whatever. In any case, one thing’s for sure: if you’re after some notion of “E-language” (as in, “extensional” or “external”), you simply can’t get any more “E” than this kind of language model: because what you hear and read (or scan) is E-xactly what you get.  

Well, a glance at my watch says that I’ve run out of time for today (cocktail hour’s long past, and Labor Day beckons), so I’ll return to the main theme of this thread – Baze III – in a daze or two, a meditation on linguistic origins and a relationship to traditional linguistic concerns; Bayesian inference as one among many possible smoothing methods; and even Bayes as a form of S-R reinforcement learning.  Until next time then: “Q: What’s a Bayesian?  A: Someone who expects a rabbit, sees a duck, and concludes a platypus.”

---

[1]Yes, yes, I know the HW assignment was to translate, le pomme mange le garcon.  I changed the example here to make the explanation a bit simpler.  I didn’t get any problem sets turned in anyway so nobody will lose points. 

[2]You might already see that since ‘all English sentences’ is a pretty large set that it might be hard to try out every single English sentence – even if you are one of those linguists who has curiously wavered between the view that the # of sentences in a language are beyond countably infinite to the view that E is merely finite – but we’ll return to this in just a bit below to see how this is computed in practice. 

[3]Because if for some English sentence pair, E E^*:

p(F1|E^′) x p(E^′)/ p(F1) > p(F1|E^*) x p(E)^*/ p(F1), then we can cancel p(F1) on both sides & get:

p(F1|E^′) x p(E^′)> p(F1|E^*) x p(E^*).  (Recall that probabilities are always non-negative so this works.) Therefore we only have to compute the numerators.

[4]Which you can read in full here.

[5]For example, you can use Google Search to find all occurrences of the string “the boy ate the apple” (in quotes! About 167,000 or so when I looked) vs. “the apple ate the boy,” with only 43 results.)  Now matter how you slice the apple, you’ll get the same yawning gap.

[6]Monty Python and the Holy Grail Corpus.  Obviously.  And a hell of a lot more fun than the Wall Street Journal sentences in the Penn Treebank. I swear, when I hear “Pierre Vinken…’” I reach for my gun. Well, depending on how deep your sense of irony runs, even the Wall Street Journal can be funny.  Not as funny as Monty Python, though.

[7]All these examples have been taken from the wonderful thesis by Ali Mohammed at MIT, available here: http://dspace.mit.edu/handle/1721.1/75653. See Ali’s Table 3.2, p. 68. Some of Ali’s examples no longer ‘work as advertised’ because (it appears) since they have become widely known (Ali and many of his friends intern at Google, after all), special-purpose work-arounds (AKA ‘hacks’) have been installed.  George Bush n’est pas un idiot used to come out, George Bush is an idiot. By now, you should be able to figure out why this might happen.