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.
[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.
