MT Statistical
Uploaded by
api-3732490MT Statistical
Uploaded by
api-3732490
a statistical mt tutorial workbook
kevin knight
prepared in connection with the jhu summer workshop
april 30, 1999
1. the overall plan
we want to automatically analyze existing human sentence translations, with an eye toward building
general translation rules we will use these rules to translate new texts automatically.
i know this looks like a thick workbook, but if you take a day to work through it, you will know almost as
much about statistical machine translation as anybody!
the basic text that this tutorial relies on is brown et al, “the mathematics of statistical machine translation”,
computational linguistics, 1993. on top of this excellent presentation, i can only add some perspective and
perhaps some sympathy for the poor reader, who has (after all) done nothing wrong.
important terms are underlined throughout!
2. basic probability
we're going to consider that an english sentence e may translate into any french sentence f. some
translations are just more likely than others. here are the basic notations we'll use to formalize “more
likely”:
p(e) a priori probability. the chance that e happens. for example, if e is the english string “i like
snakes,” then p(e) is the chance that a certain person at a certain time will say “i like snakes” as opposed
to saying something else.
p(f | e) conditional probability. the chance of f given e. for example, if e is the english string “i like
snakes,” and if f is the french string “maison bleue,” then p(f | e) is the chance that upon seeing e, a
translator will produce f. not bloody likely, in this case.
p(e,f) joint probability. the chance of e and f both happening. if e and f don't influence each other, then
we can write p(e,f) = p(e) * p(f). for example, if e stands for “the first roll of the die comes up 5” and f
stands for “the second roll of the die comes up 3,” then p(e,f) = p(e) * p(f) = 1/6 * 1/6 = 1/36. if e and f
do influence each other, then we had better write p(e,f) = p(e) * p(f | e). that means: the chance that “e
happens” times the chance that “if e happens, then f happens.” if e and f are strings that are mutual
translations, then there's definitely some influence.
exercise. p(e,f) = p(f) * ?
all these probabilities are between zero and one, inclusive. a probability of 0.5 means “there's a half a
chance.”
3. sums and products
to represent the addition of integers from 1 to n, we write:
n
Σ i = 1 + 2 + 3 + ... + n
i=1
for the product of integers from 1 to n, we write:
n
Π i = 1 * 2 * 3 * ... * n
i=1
if there's a factor inside a summation that does not depend on what's being summed over, it can be taken
outside:
n n
Σ i * k = k + 2k + 3k + ... + nk = k Σ i
i=1 i=1
exercise.
n
Π i * k = ?
i=1
sometimes we'll sum over all strings e. here are some useful things about probabilities:
Σ p(e) = 1
e
Σ p(e | f) = 1
e
p(f) = Σ p(e) * p(f | e)
e
you can read the last one like this: “suppose f is influenced by some event. then for each possible
influencing event e, we calculate the chance that (1) e happened, and (2) if e happened, then f happened.
to cover all possible influencing events, we add up all those chances.
4. statistical machine translation
given a french sentence f, we seek the english sentence e that maximizes p(e | f). (the “most likely”
translation). sometimes we write:
argmax p(e | f)
e
read this argmax as follows: “the english sentence e, out of all such sentences, which yields the highest
value for p(e | f). if you want to think of this in terms of computer programs, you could imagine one
program that takes a pair of sentences e and f, and returns a probability p(e | f). we will look at such a
program later on.
e > ++
| | > p(e|f)
f > ++
or, you could imagine another program that takes a sentence f as input, and outputs every conceivable
string ei along with its p(ei | f). this program would take a long time to run, even if you limit english
translations some arbitrary length.
++ > e1, p(e1 | f)
f > | | ...
++ > en, p(en | f)
5. the noisy channel
memorize bayes rule, it's very important!
p(e|f) = p(e) * p(f | e) / p(f)
exercise: now prove it, using the exercise in section 2.
using bayes rule, we can rewrite the expression for the most likely translation:
argmax p(e | f) = argmax p(e) * p(f | e)
e e
exercise: what happened to p(f)?
that means the most likely translation e maximizes the product of two terms, (1) the chance that someone
would say e in the first place, and (2) if he did say e, the chance that someone else would translate it into f.
the noisy channel works like this. we imagine that someone has e in his head, but by the time it gets on to
the printed page it is corrupted by “noise” and becomes f. to recover the most likely e, we reason about
(1) what kinds of things people say any english, and (2) how english gets turned into french. these are
sometimes called “source modeling” and “channel modeling.” people use the noisy channel metaphor for
a lot of engineering problems, like actual noise on telephone transmissions.
if you want to think of p(e) in terms of computer programs, you can think of one program that takes any
english string e and outputs a probability p(e). we'll see such a program pretty soon. or, likewise, you can
think of a program that produces a long list of all sentences ei with their associated probabilities p(ei).
++
e > | | > p(e)
++
++ > e1, p(e1)
| | ...
++ > en, p(en)
to think about the p(f | e) factor, imagine another program that takes a pair of sentences e and f, and
outputs p(f | e). or, likewise, a program that takes a sentence e and produces various sentences fi along
with corresponding probabilities p(fi | e).
e > ++
| | > p(f|e)
f > ++
++ > f1, p(f1 | e)
e > | | ...
++ > fn, p(fn | e)
these last two programs are sort of like the ones in section 4, except p(f | e) is not the same thing as p(e |
f).
you can put the source and channel modules together like this:
++ ++
| | > e, p(e) > | | > f, p(f|e)
++ ++
there are many ways to produce the same french sentence f. each way corresponds to a different choice of
“source” sentence e. notice that the modules have arrows pointing to the right. this is called a generative
model because it is a theory of how french sentences get generated. the theory is, first an english sentence
is generated, then it gets turned into french. kind of a weird theory.
6. bayesian reasoning
even though the arrows point to the right, we will actually use this setup to translate french back into
english.
think of a sentence f like a crime scene. we want to reason about how this crime scene got to be. our
generative model might be something like: some person e decided to do the crime, and then that person
actually did the crime. so we start reasoning about (1) who might have made the decision (p(e): motive,
personality) and also (2) how they might have gone about it (p(f | e): transportation, weapons). in general,
these two things may conflict. you might have someone with a good motive, but without the means; or
you might have someone who could easily have done the crime, but has no motive.
or, think of a sentence f like a set of medical symptoms. there are many diseases that could give rise to
these symptoms. if we build a generative model, then we can reason about the probability of any disease e
occurring, as well as the probability that symptoms f will arise from any particular disease e. that's p(e)
and p(f | e) again. they may conflict: you may have a common disease that often gives rise to symptoms f,
and you may have a very rare disease that always gives rise to symptoms f. that's a tough call, right?
since biologists know roughly how diseases cause symptoms, i.e. p(f | e), it's possible to build computer
models of how this happens. it's not so obvious how to build a single model that reasons from symptoms
to diseases, i.e. p(e | f). furthermore, we may have independent sources of information about p(e) in
isolation, such as old hospital records.
7. word reordering in translation
if we reason directly about translation using p(e | f), then our probability estimates had better be very
good. on the other hand, if we break things apart using bayes rule, then we can theoretically get good
translations even if the probability numbers aren't that accurate.
for example, suppose we assign a high value to p(f | e) only if the words in f are generally translations of
words in e. the words in f may be in any order: we don't care. well, that's not a very accurate model of
how english gets turned into french. maybe it's an accurate model of how english gets turned into really
bad french.
now let's talk about p(e). suppose that we assign a high value to p(e) only if e is grammatical. that's
pretty reasonable, though difficult to do in practice.
an interesting thing happens when we observe f and try to come up with the most likely translation e.
every e gets the score p(e) * p(f | e). the factor p(f | e) will ensure that a good e will have words that
generally translate to words in f. various “english” sentences will pass this test. for example, if the string
“the boy runs” passes, then “runs boy the” will also pass. some word orders will be grammatical and
some will not. however, the factor p(e) will lower the score of ungrammatical sentences.
in effect, p(e) worries about english word order so that p(f | e) doesn't have to. that makes p(f | e) easier to
build than you might have thought. it only needs to say whether or not a bag of english words
corresponds to a bag of french words. this might be done with some sort of bilingual dictionary. or to put
it in algorithmic terms, this module needs to be able to turn a bag of french words into a bag of english
words, and assign a score of p(f | e) to the bagpair.
exercise. put these words in order: “have programming a seen never i language better”. this task is called
bag generation.
exercise. put these words in order: “actual the hashing is since not collisionfree usually the is less
perfectly the of somewhat capacity table”
exercise. what kind of knowledge are you applying here? do you think a machine could do this job? can
you think of a way to automatically test how well a machine is doing, without a lot of human checking?
exercise. put these words in order: “loves john mary”
the last exercise is hard. it seems like p(f | e) needs to know something about word order after all. it can't
simply suggest a bag of english words and be done with it. but, maybe it only needs to know a little bit
about word order, not everything.
8. word choice in translation
the p(e) model can also be useful for selecting english translations of french words. for example, suppose
there is a french word that either translates as “in” or “on.” then there may be two english strings with
equally good p(f | e) scores: (1) she is in the end zone, (2) she is on the end zone. (let's ignore other
strings like “zone end the in is she” which probably also get good p(f | e) scores). well, the first sentence
is much better english than the second, so it should get a better p(e) score, and therefore a better p(e) * p(f
| e) score. remember that the most likely translation is the one with the best p(e) * p(f | e) score.
exercise. write down a short foreignlanguage sentence. rearrange the words so that they appear in
“english word order.” use a bilingual dictionary to look up all possible translations of all the words. write
each word's translations in a column below the word. erase the original foreignlanguage words. ask a
friend (or enemy) to construct an english sentence by choosing a single word from each column.
9. language modeling
where do all these probability numbers come from?
later, we'll worry about p(f | e). first we need to build a machine that assigns a probability p(e) to each
english sentence e. this is called a language model.
we could build a program that knows a lot about the world, about the types of things people like to
discuss, about the grammatical structures that people use when describing certain events and objects, etc.
we could type in lots of numbers by hand at various points in the program, and they might get multiplied
or added together, at other points.
another idea is simpler just record every sentence that anyone ever says in english. suppose you record
a database of one billion utterances. if the sentence “how's it going?” appears 76,413 times in that
database, then we say p(how's it going?) = 76,413/1,000,000,000 = 0.000076413. we can use the web or
the online wall street journal if we don't want to do a lot of actual recording.
exercise. which has a higher probability: “i like snakes” or “i hate snakes”? type both in to
[Link] and find out (include quotation marks in your query to ensure that the words appear
together and in order in the retrieved documents).
exercise. what is the probability of: “i like snakes that are not poisonous”?
one big problem is that many perfectly good sentences will be assigned a p(e) of zero, because we have
never seen them before. this is bad. a great p(f | e) module may give us a nice bag of english words like
“not that like snakes poisonous i are.” but no matter what order we assign to these words, p(e) always
equal zero. that means “like poisonous i are that not snakes” will be considered just as likely a translation
as “i like snakes that are not poisonous.”
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.
10. ngrams
for computers, the easiest way to break a string down into components is to consider substrings. an n
word substring is called an ngram. 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 ngrams, then maybe it is a reasonable string. not necessarily, but
maybe.
let b(y | x) be the probability that word y follows word x. we can estimate this probability from online
text. we simply divide the number of times we see the phrase “xy” by the number of times we see the
word “x”. that's called a conditional bigram probability. each distinct b(y | x) is called a parameter.
a commonly used ngram estimator looks like this:
b(y | x) = numberofoccurrences(“xy”) / numberofoccurrences(“x”)
p(i like snakes that are not poisonous) ~
b(i | startofsentence) *
b(like | i) *
b(snakes | like) *
...
b(poisonous | not) *
b(endofsentence | poisonous)
in other words, what's the chance that you'll start a sentence with the word “i”? if you did say “i”, what's
the chance that you would say the word “like” immediately after? and if you did say “like”, is “snakes” a
reasonable next word? and so on.
actually, this is another case of a generative model (section 8). this model says that people keep spitting
out words one after another, but they can't remember anything except the last word they said. that's a
crazy model. it's called a bigram language model. if we're nice, we might allow for the possibility that
people remember the last two words they said. that's called a trigram language model:
b(z | x y) = numberofoccurrences(“xyz”) / numberofoccurrences(“xy”)
p(i like snakes that are not poisonous) ~
b(i | startofsentence startofsentence) *
b(like | startofsentence i) *
b(snakes | i like) *
...
b(poisonous | are not) *
b(endofsentence | not poisonous) *
b(poisonous | endofsentence endofsentence)
11. smoothing
ngram models can assign nonzero probabilities to sentences they have never seen before. it's a good
thing, like martha stewart says.
the only way you'll get a zero probability is if the sentence contains a previously unseen bigram or
trigram. that can happen. in that case, we can do smoothing. if “z” never followed “xy” in our text, we
might further wonder whether “z” at least followed “y”. if it did, then maybe “xyz” isn't so bad. if it
didn't, we might further wonder whether “z” is even a common word or not. if it's not even a common
word, then “xyz” should probably get a low probability. instead of
b(z | x y) = numberofoccurrences(“xyz”) / numberofoccurrences(“xy”)
we can use
b(z | x y) = 0.95 * numberofoccurrences(“xyz”) / numberofoccurrences(“xy”) +
0.04 * numberofoccurrences (“yz”) / numberofoccurrences (“z”) +
0.008 * numberofoccurrences(“z”) / totalwordsseen +
0.002
it's handy to use different smoothing coefficients in different situations. you might want 0.95 in the case
of xy(z), but 0.85 in another case like ab(c). for example, if “ab” doesn't occur very much, then the counts
of “ab” and “abc” might not be very reliable.
notice that as long as we have that “0.002” in there, then no conditional trigram probability will ever be
zero, so no p(e) will ever be zero. that means we will assign some positive probability to any string of
words, even if it's totally ungrammatical. sometimes people say ungrammatical things after all.
we'll have more to say about estimating those smoothing coefficients in a minute.
this ngram business is not set in stone. you can come up with all sorts of different generative models for
language. for example, imagine that people first mentally produce a verb. then they produce a noun to the
left of that verb. then they produce adjectives to the left of that noun. then they go back to the verb and
produce a noun to the right. and so on. when the whole sentence is formed, they speak it out loud.
12. evaluating models
a model often consists of a generative “story” (e.g., people produce words based on the last two words
they said) and a set of parameter values (e.g., b(z | x y) = 0.02). it's usually too hard to set the parameter
values by hand, so we look at training data. ngram models are easy to train basically, we just count n
gram frequencies and divide. the verbnounadjective model described at the end of the previous section
is perhaps not so easy to train. for one thing, you need to be able to identify the main verb of a training
sentence. and even if you could train it easily, it's not clear that it would “work better” than an ngram
model.
how do you know if one model “works better” than another? one way to pit language models against each
other is to gather up a bunch of previously unseen english test data, then ask: what is the probability of a
certain model (generative story plus particular parameter values), given the test data that we observe? we
can write this symbolically as:
p(model | testdata)
using bayes rule:
p(model | testdata) = p(model) * p(testdata | model) / p(data)
let's suppose that p(model) is the same for all models. that is, without looking at the test data, we have no
idea whether “0.95” is a better number than “0.07” deep inside some model. then, the best model is the
one that maximizes p(testdata | model).
exercise. what happened to p(data)?
fortunately, p(testdata | model) is something that is easy to compute. it's just the same thing as p(e),
where e = testdata.
now, anyone can come up with any crackpot computer program that produces p(e) values, and we can
compare it to any other crackpot computer program. it's a bit like gambling. a model assigns bets on all
kinds of strings, by assigning them high or low p(e) scores. when the test data is revealed, we see how
much the model bet on that string. the more it bet, the better the model.
a trigram model will have higher p(testset) than a bigram model. why? a bigram model will assign
reasonably high probability to a string like “i hire men who is good pilots”. this string contains good
word pairs. the model will lay some significant “bet” on this string. a trigram model won't bet much on
this string, though, because b(is | men who) is very small. that means the trigram model has more money
to bet on good strings which tend to show up in unseen test data (like “i hire men who are good pilots”).
any model that assigns zero probability to the test data is going to get killed! but we're going to do
smoothing anyway, right? about those smoothing coefficients there are methods for choosing values
that will optimize p(testdata | model). that's not really fair, though. to keep a level playing field, we
shouldn't do any kind of training on test data. it's better to divide the original training data into two sets.
the first can be used for collecting ngram frequencies. the second can be used for setting smoothing
coefficients. then we can test all models on previously unseen test data.
13. perplexity
if the test data is very long, then an ngram model will assign a p(e) value that is the product of many
small numbers, each less than one. some ngram conditional probabilities may be very small themselves.
so p(e) will be tiny and the numbers will be hard to read. a more common way to compare language
models is to compute
log (p(e)) / n
2
which is called the perplexity of a model. n is the number of words in the test data. dividing by n helps to
normalize things, so that a given model will have roughly the same perplexity no matter how big the test
set is. the logarithm is base two.
as p(e) increases, perplexity decreases. a good model will have a relatively large p(e) and a relatively
small perplexity. the lower the perplexity, the better.
exercise. suppose a language model assigns the following conditional ngram probabilities to a 3word
test set: 1/4, 1/2, 1/4. then p(testset) = 1/4 * 1/2 * 1/4 = 0.03125. what is the perplexity? suppose
another language model assigns the following conditional ngram probabilities to a different 6word test
set: 1/4, 1/2, 1/4, 1/4, 1/2, 1/4. what is its p(testset)? what is its perplexity?
exercise. if p(testset) = 0, what is the perplexity of the model?
why do you think it is called “perplexity”?
14. log probability arithmetic
another problem with p(e) is that tiny numbers will easily underflow any floating point scheme. suppose
p(e) is the product of many factors f1, f2, f3 ... fn, each of which is less than one. then there is a trick:
log(p(e)) = log(f1 * f2 * f3 * ... * fn) = log(f1) + log(f2) + log(f3) + ... + log(fn)
if we store and manipulate the log versions of probabilities, then we will avoid underflow. instead of
multiplying two probabilities together, we add the log versions. you can get used to log probabilities with
this table:
p log(p)
0.0 infinity
0.1 3.32
0.2 2.32
0.3 1.74
0.4 1.32
0.5 1.00
0.6 0.74
0.7 0.51
0.8 0.32
0.9 0.15
1.0 0.00
so (0.5 * 0.5 * 0.5 * 0.5 * ... * 0.5 = 0.5^n) might get too small, but ( 1 1 1 ... 1 = n) is manageable.
a useful thing to remember about logs is this: logbase2(x) = logbase10(x) / logbase10(2).
so far, we have done nothing with probabilities except multiply them. later, we will need to add them.
adding the log versions is tricky. we need a function g such that g(log(p1), log(p2)) = log(p1 + p2). we
could simply turn the two log probabilities into regular probabilities, add them, and take the log. but the
first step would defeat the whole purpose, because the regular probability may be too small to store as a
floating point number. there is a good approximate way to do it, and i'll make it an optional exercise (hint:
if there is a large distance between the two log probabilities, then one of them can be ignored in practice).
15. translation modeling
so much for p(e) now we can assign a probability estimate to any english string e.
next we need to worry about p(f | e), the probability of a french string f given an english string e. this is
called a translation model. we need to tell a generative “story” about how english strings become french
strings. remember that this p(f | e) will be a module in overall frenchtoenglish machine translation
system. when we see an actual french string f, we want to reason backwards ... what english string e is (1)
likely to be uttered, and (2) likely to subsequently translate to f? we're looking for the e that maximizes
p(e) * p(f | e).
how does english become french? a good story is that an english sentence gets converted into predicate
logic, or perhaps a conjunction of atomic logical assertions. these assertions clear away all of the
“illogical” features of language. for example, “john must not go” gets converted to
obligatory(not(go(john))) whereas “john may not go” gets converted to not(permitted(go(john))). notice
how the not operates differently despite the syntactic similarity of the two sentences. the other half of this
story is that predicate logic then gets converted to french. i like this story.
another story is that an english sentence gets parsed syntactically. that is, a binary tree diagram is placed
on top of the sentence, showing the syntactic relationships between heads and modifiers, for example,
subject/verb, adjective/noun, prepositionalphrase/verbphrase, etc. this tree diagram is then transformed
into a french tree ... phrases are swapped around, and english words are replaced by french translations.
this story is called “syntactic transfer.”
yet another story is that the words in an english sentence are replaced by french words, which are then
scrambled around. what kind of a crackpot story is that? that's the story we're going to use for the rest of
this workbook. we will refer to this story in somewhat sinister fashion as ibm model 3.
for one thing, this story is simple. we can set things up so that any english sentence can be converted to
any french sentence, and this will turn out to be important later. in the other stories, it is not so clear how
to get from here to there for any arbitrary pair of sentences. for another thing, remember that p(f | e)
doesn't necessarily have to turn english into good french. we saw in sections 7 and 8 that some of the
slack will be taken up by the independentlytrained p(e) model.
let's look at the story in more detail. we can't propose that english words are replaced by french words one
for one, because then french translations would always be the same length as their english counterparts.
this isn't what we observe in translation data. so we have to allow that an english word may produce more
than one french word, or perhaps no french words at all.
here's the story:
1. for each word ei in an english sentence (i = 1 ... l), we choose a fertility phii. the choice of fertility is
dependent solely on the english word in question. it is not dependent on the other english words in the
english sentence, or on their fertilities.
2. for each word ei, we generate phii french words. the choice of french word is dependent solely on the
english word that generates it. it is not dependent on the english context around the english word. it is not
dependent on other french words that have been generated from this or any other english word.
3. all those french words are permuted. each french word is assigned an absolute target “position slot.”
for example, one word may be assigned position 3, and another word may be assigned position 2 the
latter word would then precede the former in the final french sentence. the choice of position for a french
word is dependent solely on the absolute position of the english word that generates it.
is that a funny story, or what?
16. translation as string rewriting
you can think of this generative story as one of string rewriting. first you start with an english string like
this:
mary did not slap the green witch
then you assign fertilities. for fertility 1, you simply copy the word over. for fertility 2, you copy the word
twice. etc. for fertility zero, you drop the word. for example, we might assign fertility zero to the word
“did.” this yields another string:
mary not slap slap slap the the green witch
notice that “slap” got fertility 3. next you replace the english words with french words (let me use spanish
here, since i know spanish). at this point, the replacement can be oneforone:
mary no daba una botefada a la verde bruja
finally, we permute those words:
mary no daba una botefada a la bruja verde
exercise. start with the sentence “my child, you must go home” and transform it into a foreignlanguage
translation using the above generative story.
17. model 3
in language modeling, we began with a story like “people produce words based on the last word they said”
and wound up with a model with lots of parameters like b(snakes | like). we could obtain values for these
parameters by looking at language data. we're going to do the same thing now.
in thinking about what parameters to have, we need only look at the dependencies in the generative story.
for example, which french word to generate depends only on the english word that is doing generating. so
it is easy to imagine a parameter like t(maison | house), which gives the probability of producing
“maison” from “house.” likewise for fertilities. we can have parameters like n(1 | house), which gives the
probability that “house” will produce exactly one french word whenever “house” appears. and likewise
for what are called (in supersinister fashion) distortion parameters. for example, d(5 | 2) may give the
probability that an english word in position 2 (of an english sentence) will generate a french word that
winds up in position 5 (of a french translation). actually, model 3 uses a slightly enhanced distortion
scheme in which the target position also depends on the lengths of the english and french sentences. so
the parameters look like d(5 | 2, 4, 6), which is just like d(5 | 2) except also given that the english sentence
has four words and french sentence has six words. remember that the distortion parameters do not need to
place each french word carefully into a grammatical whole. it might be okay if this model generates bad
french.
model 3 has one more twist. this is really sinister. we imagine that some french words are “spurious.”
that is, they mysteriously appear in a french translation although no english word can really be held
responsible for them. for example, function words. consider the spanish word “a” in the example in the
last section. i assigned a fertility of 2 to the english word “the”, which ultimately generated the spanish
“a”. maybe it's better to assign a fertility of 1 to “the”, and let “a” be generated spuriously.
in modeling this phenomenon, we pretend that every english sentence contains the invisible word null in
the initial, zeroth position. we have parameters like t(maison | null) that give the probability of
generating various words spuriously from null.
we could also have parameters like n(3 | null), which would give the probability of there being exactly 3
spurious words in a french translation. but, model 3 worries that longer sentences will have more spurious
words. i know, this is like a sudden attack of scruples. weird. anyway, instead of n(0 | null) ... n(25 |
null), we're going to have a single floatingpoint parameter called p1. you can think of p1 like this. after
we assign fertilities to all the “real” english words (excluding null), we will be ready to generate (say) z
french words. as we generate each of these z words, we optionally toss in a spurious french word also,
with probability p1. we'll refer to the probability of not tossing in (at each point) a spurious word as p0 =
1 p1.
exercise. if the maximum fertility for english words were 2, how long is the longest french sentence that
can be generated from an english sentence of length l? (don't forget about nullgenerated words).
finally, we need to worry about distortion probabilities for nullgenerated words. i'm afraid it is too simple
to have parameters like d(5 | 0, 4, 6), i.e., the chance that the null word will generate a french word that
winds up in french position 5 as opposed to some other position. i mean, these words are spurious, man!
they can appear anywhere! it's fruitless to try to predict it! we'll instead (1) use the normalword
distortion parameters to choose positions for normallygenerated french words, and then (2) put the null
generated words into the empty slots that are left over. if there are three nullgenerated words, and three
empty slots, then there are 3! (“three factorial”), or six, ways for slotting them all in. we'll just assign a
probability of 1/6 for each way.
now we are ready to see the real generative model 3:
1. for each english word ei indexed by i = 1, 2, ..., l, choose fertility phii with probability n(phii | ei).
2. choose the number phi0 of “spurious” french words to be generated from e0 = null, using probability
p1 and the sum of fertilities from step 1.
3. let m be the sum of fertilities for all words, including null.
4. for each i = 0, 1, 2, ..., l, and each k = 1, 2, ..., phii, choose a french word tauik with probability t(tau
ik | ei).
5. for each i = 1, 2, ..., l, and each k = 1, 2, ..., phii, choose target french position piik with probability
d(piik | i,l,m).
6. for each k = 1, 2, ..., phi0, choose a position pi0k from the phi0 k + 1 remaining vacant positions in
1, 2, ... m, for a total probability of 1/phi0!.
7. output the french sentence with words tauik in positions piik (0 <= i <= l, 1 <= k <= phii).
if you want to think about this in terms of string rewriting, consider the following sequence:
mary did not slap the green witch (input)
mary not slap slap slap the green witch (choose fertilities)
mary not slap slap slap null the green witch (choose number of spurious words)
mary no daba una botefada a la verde bruja (choose translations)
mary no daba una botefada a la bruja verde (choose target positions)
18. model 3 parameters
you can see that the model has four types of parameters: n, t, p, and d.
n and t are twodimensional tables of floatingpoint numbers. d is a onedimensional table of floating
point numbers. p is a single floatingpoint number.
there's nothing mysterious about a model: it's mostly just a bunch of numbers!
exercise. if each floatingpoint number takes up four bytes of storage, how much space do you think we
need for all these tables?
19. wordforword alignments
now we need to think about two things. first, how can we automatically obtain parameter values from
data? second, armed with a set of parameter values, how can we compute p(f | e) for any pair of
sentences?
first let's think about automatically obtaining values for the n, t, p, and d parameters from data. if we had
a bunch of english strings and a bunch of stepbystep rewritings into french, then life would be easy. to
compute n(0 | did), we would just locate every instance of the word “did” and see what happens to it
during the first rewriting step. if “did” appeared 15,000 times and was deleted during the first rewriting
step 13,000 times, then n(0 | did) = 13/15.
exercise. take 10,000 english sentences and rewrite them into french, storing all intermediate strings. no,
make that a million english sentences! ha, ha, just kidding. don't do this exercise.
it will be very useful for us to consider a data structure that is simple, yet preserves most of the decisions
made by the model. this data structure is called a word alignment. here is a sample word alignment:
null and the program has been implemented
| | | | | | |
| | | | +++
| | | | | | |
le programme a ete mis en application
(notice the invisible english null word in initial, zeroth position.)
if we had a lot of sentence pairs aligned like this, then again, life would be easy. to compute n(0 | did), we
just see how many times “did” connected to zero french words. to compute t(maison | house), we count
up all the french words generated by all the occurrences of “house,” and see how many of those words are
“maison.”
the word alignments that best correspond to the model 3 story are those in which every french word is
connected to exactly one english word (either a regular word or null). so, it's never the case that two
english words jointly generate some french word. that's too bad, because sometimes that's a very intuitive
alignment.
since the computer doesn't like drawings very much, it will be convenient to represent at alignment as a
vector of integers. this vector has the same length as the french sentence, and each entry corresponds to a
particular french word. the value we store for each entry is the position of the english word that the
particular french word connects to in the alignment drawing. we can represent the sample word alignment
above as [2, 3, 4, 5, 6, 6, 6].
exercise. draw a wordforword alignment between the two sentences “mary did not slap the green witch”
and “mary no daba una botefada a la bruja verde.”
exercise. what is the vector representation for the alignment you drew in the previous exercise?
notice that the wordforword alignment does not quite preserve all of the model's decisions in
transforming an english sentence into a french one. for example, if a single english word x is connected to
french words y and z, then we don't really know whether they were generated in that order, or whether
they were generated as z and y, then permuted. this will have ramifications later, when we figure out how
to calculate p(f | e).
20. estimating parameter values from wordforword alignments
we mentioned above how to estimate n and t parameter values from aligned sentence pairs. it is also easy
to estimate d parameter values. every connection in an alignment contributes to the count for a particular
parameter such as d(5 | 2, 4, 6). once we obtain all the counts, we normalize to get the probabilistic
parameter values. for example, the count dc(5 | 2, 4, 6) would be 125 if we observed 125 times some
english word in position 2 generating some french word in position 5, when the respective lengths of the
sentences were 4 and 6. if “total” is the sum for all j of dc(j | 2, 4, 6), then d(5 | 2, 4, 6) = dc(5 | 2, 4, 6) /
total. or in the sum notation described in section 3:
dc(5 | 2, 4, 6)
d(5 | 2, 4, 6) =
25
Σ dc(j | 2, 4, 6)
j=1
the last thing to estimate is p1. to do this, we can consider the entire french corpus of n words. suppose
that m of those words were generated by null, according to the alignments provided. (the other nm were
generated by normal english words). then, we can imagine that after each normally generated french
word, a spurious word will be generated in m of the nm cases, so p1 = m / nm.
exercise. writes down estimates for n, t, p, and d parameter values based on the following wordaligned
corpus:
b c d b d
| | | |
| ++ | |
| | | | |
x y z x y
21. bootstrapping
to get good parameter value estimates, we may need a very large corpus of translated sentences. such
large corpora do exist, sometimes, but they do not come with wordforword alignments. however, it is
possible to obtain estimates from nonaligned sentence pairs. it's like magic. i was so happy when i
finally understood this concept. once i understood the concept in this application, i could apply it to many
other problems.
exercise. to get an intuitive feel for this, try to manually build alignments for the set of unaligned sentence
pairs on page 84 of the article “automating knowledge acquisition for machine translation,” kevin knight,
ai magazine, winter 1997.
a slightly more formal intuition is that pairs of english and french words which cooccur in sentence
translations may indeed be translations of each other. then again they may not be. but, if we had even a
rough idea about which english words corresponded with which french ones, then we could start to gather
information about distortion probabilities. we might notice, for example, that the first word in an english
sentence and the first word in a corresponding french sentence are frequently translations of each other,
leading us to hypothesize that d(1 | 1, l, m) is very high. moreover, when french sentences are much
longer than their english versions, we might guess that some of the words in those english sentences tend
to have large fertilities. but we're not sure which words exactly.
the idea is that we can gather information incrementally, with each new piece of information helping us to
build the next. this is called bootstrapping.
22. all possible alignments
alignments will be the key to our bootstrapping algorithm. if we had a single correct alignment for each
sentence pair, then we could collect parameter counts from those alignments directly. now suppose that
for one sentence pair, we couldn't decide on the single correct alignment. suppose that there were two
equally goodlooking alignments for that sentence pair. then, for just that one sentence pair, we could
decide to collect parameter counts from both alignments. but, since we aren't sure which alignment is
correct, we might want to discount the things we collect from that sentence pair, as opposed to other
sentence pairs that we are more certain about. for example, any count from one of the two equally good
looking alignments could be multiplied by 0.5. if the word “house” was connected with the word
“maison” in only one of those two alignments, then we would pretend that we observed “house”
connected to “maison” 0.5 times. that doesn't make much sense you can observe something happening
once, or twice, or three times, but how can you observe something happening 0.5 times? suspend your
disbelief! call these fractional counts.
in reality, we may not be able to narrow things down to just one or two possible alignments. in fact, at
some point, all alignments may be deemed possible for a given sentence pair.
exercise. in a sentence pair with l english words and m french words, how many alignments are possible?
(don't forget about the invisible null word).
exercise. what are all the ways to align the twoword english sentence “b c” with the twoword french
sentence “x y”? i have drawn some of them below fill in the others.
b c
| | alignment1
x y
b c
/| alignment2
x y
b c
alignment3
x y
b c
alignment4
x y
exercise. suppose that b = blue, c = house, x = maison, y = bleue. circle the alignment above that you
intuitively prefer.
23. collecting fractional counts
if we have two possible alignments for a given sentence pair, we might view them as equally good
looking. on the other hand, we might have cause to think that one is betterlooking to the other. in that
case, we may assign an alignment weight of 0.2 to one and 0.8 to the other. we can use these weights to
build fractional counts. because the second alignment has a higher weight, it “has more weight to throw
around” and will therefore have a bigger voice in the ultimate estimated values for n, t, p, and d.
here i have attached weights to the alignments we just saw:
b c
| | alignment1 weight = 0.3
x y
b c
/| alignment2 weight = 0.2
x y
b c
|\ alignment3 weight = 0.4
x y
b c
x alignment4 weight = 0.1
x y
consider estimating the value of n(1 | b), i.e., the chance that english word b generates exactly one french
word. how many times did this occur in the corpus? (this is a funny corpus it only has one sentence
pair). using fractional counts, we pretend that this occurred 0.3 + 0.1 times, instead of twice. so, nc(1 | b)
= 0.4. likewise, we observe nc(0 | b) = 0.2, and nc(2 | b) = 0.4. we can compute fertility estimates by
normalizing the observed nc counts. in this case, n(1 | b) = 0.4 / 0.4 + 0.2 + 0.4 = 0.4.
exercise. use fractional counts to estimate the value of the word translation parameter t(y | b).
with the corpus of many sentences, we do the same thing. we collect fractional counts over all alignments
of all sentence pairs. so, given alignment weights, we can estimate n, t, p, and d. i know, you are
thinking: where the heck are we going to get alignment weights?
24. alignment probabilities
let's ditch the idea of alignment weights in favor of alignment probabilities. that is, we ask for a given
sentence pair: what is the probability of the words being aligned in suchandsuch a way? for a given
sentence pair, the probabilities of the various possible alignments should add to one, as they do in the
example given in the previous section.
we'll write p(a | e,f) for the probability of a particular alignment given a particular sentence pair.
remember that an alignment a is just a vector of integers that identify the positions of english words that
various french words connect to.
what would make one alignment more probable than other? well, if someone magically gave us word
translation (t) parameter values, then we might use them to judge alignment probabilities. an alignment
would be probable to the extent that it connected english and french words that are already known to be
highprobability translations of each other. a low probability alignment would be one that connected
words with very low t values.
i will now execute a fancy manipulation:
p(a | e,f) = p(a,f | e) / p(f | e)
exercise. prove it. hint: p(a | e,f) = p(a,e,f) / p(e,f) = ? = p(a,f | e) / p(f | e).
so to compute p(a | e,f), we need to be able to compute the ratio of two terms. the first is p(a,f | e).
fortunately, we can compute p(a,f | e) using the generative story of model 3. given an english string e,
model 3 marches us through various decision points (fertilities, word translations, permutations, etc.).
these decisions determine both an alignment and a resulting french string. remember that an alignment,
by itself, is just a set of positional connectors. (you can have the same alignment and produce two
completely different french strings).
the second term is p(f | e). back at the beginning of section 19, we said we wanted to do two things. one
was estimate translation model parameters from data, and the other was to be able to compute p(f | e)
given some parameter values. we need the latter for our ultimate goal of frenchtoenglish translation, i.e.,
choosing a translation e that maximizes p(e) * p(f | e).
we're about to kill two birds with one stone. consider that there are many ways to produce the same french
sentence f from the same english sentence e. each way corresponds to an alignment that you might draw
between them. (you can have two different alignments that produce the same french string). therefore:
p(f | e) = Σ p(a,f | e)
a
so we have reduced both of our problems to computing a formula for p(a,f | e).
25. p(a,f | e)
the model 3 generative story doesn't mention anything about alignments, but an alignment is a way of
summarizing the various choices that get made according to the story. the probability of producing a
particular alignment and french string is basically the product of a bunch of smaller probabilities, such as
for choosing a particular fertility for a particular word (n), choosing a particular word translation (t),
moving a word from english position i to french position j (d), etc.
here's a first cut.
e = english sentence
f = french sentence
ei = the ith english word
fj = the jth french word
l = number of words in the english sentence
m = number of words in the french sentence
a = alignment (vector of integers a1 ... am, where each aj ranges from 0 to l)
aj = the english position connected to by the jth french word in alignment a
eaj = the actual english word connected to by the jth french word in alignment a
phii = fertility of english word i (where i ranges from 0 to l), given the alignment a
l m m
p(a,f | e) = Π n(phii | ei) * Π t(fj | eaj) * Π d(j | aj, l, m)
i=1 j=1 j=1
this formula accounts for the basic fertility, word translation, and distortion values implied by the
alignment and french string. there are a few problems, however.
the first problem is that we should only count distortions which involve french words that were generated
by “real” english words, and not by null. we should eliminate any d value for which aj = 0.
a related problem is that we forgot to include costs for generating “spurious” french words. any french
word fj for which aj = 0 is spurious. there are phi0 spurious french words, according to the definitions
above. observe that there are m phi0 nonspurious french words, i.e., ones that were generated by “real”
english words. after each of those m phi0 words, we have the option of generating a spurious word with
probability p1. how many ways are there to spit out phi0 spurious words under this process? that's the
same as asking how many ways there are to pull phi0 balls out of a box that contains (m phi0) balls.
for example, there is only one way to generate exactly zero spurious words always fail to exercise the
option. there are actually m 1 ways to generate a single spurious word. you could exercise the option
after the first “real” word, after the second word, etc., or after the mth word. so we have an additional
factor for p(a,f | e), which is:
m phi0
( )
phi0
let's not forget about the costs of taking each option. if we take the “add spurious” option phi0 times,
then we have an extra factor of p1^phi0. and if we take the “don't add spurious” option ((m phi0)
phi0) times, then we have an extra factor of p0^(m 2 * phi0).
exercise. why did i write ((m phi0) phi0) instead of just (m phi0)?
the third problem is that we forgot to include costs for permuting the spurious french words into their final
target positions. recall from section 17 that there are no distortion parameters of the form d(j | 0, l, m).
instead we slot the spurious words into empty french positions as the final step of generating the french
string. since there are phi0! possible orderings, all of which are deemed equally probable, then any
particular ordering we generate adds an additional factor of 1/phi0! to the computation of p(a,f | e).
a fourth problem is comes up because the alignment loses a bit of information about the generative
process that turned e into f. recall from section 19 that “... if a single english word x is connected to
french words y and z, then we don't really know whether they were generated in that order, or whether
they were generated as z and y, then permuted.” this distinction is lost in an alignment that simply
connects x to y and z. it's like if i rolled two dice and reported a result of 43, without reporting which die
came up 4 and which die came up 3. there are two ways to roll a “43.” consider three dice. how many
ways are there to roll a “641”? there are six: two ways if the first die is 6, two ways if the first die is 4,
and two ways in the first die is 1.
if english word x is connected to french words y, z, and w, then there are six ways this could have
happened according to the model 3 generative story. notice that all six ways are equally probable, because
the factors that get multiplied are always the same: n(3 | x), t(y | x), t(z | x), t(w | x), d(1 | 1,1,3), d(2 |
1,1,3), d(3 | 1,1,3), p0. multiplication doesn't care which order these factors come in. so in this case, p(a,f
| e) = 6 * all those factors.
this fourth problem arises exactly when any word has fertility greater than 1. so we will add a final factor
to our p(a,f | e) formula, namely:
1
Π phii!
i=0
here's our great new formula!
p(a,f | e) =
comb(m – phi0, phi0) * p0 ^ (m – 2phi0) * p1 ^ phi0 *
1 m m
Π n(phii | ei) * Π t(fj | eaj) * Π d(j | aj, l, m) *
i=1 j=1 j:aj <> 0
1
Π phii! * (1 / phi0!)
i=0
recall that we can express p(f | e) in terms of p(a,f | e):
p(f | e) = Σ p(a,f | e)
a
recall also that we can express p(a | f,e) in terms of p(a,f | e).
p(a | e,f) = p(a,f | e) / Σ p(a,f | e)
a
so that's the whole model 3 story boiled down to a math formula. if you can come up with a better story
and boil it down to a math formula, then maybe you can get better translations!
26. chicken and egg
the point of section 23 was this: if you have alignment probabilities, then you can compute parameter
estimates (using fractional counts). the point of section 25 was this: if you have parameter values, then
you can compute alignment probabilities. uh oh, what went wrong?
our big goal of being able to train p(f | e) from bilingual text seems just out of reach. to compute p(f | e),
we need to compute p(a,f | e), and to do that we need parameter values. we know how to get parameter
values we just need to be able to invoke p(a | f,e). to do that, we need p(a,f | e), and we're stuck in a
circle.
like they say, and egg is a chicken's way of making more chickens. (or something like that?)
27. now for the magic
the em algorithm can solve our problem. “em” stands for “estimationmaximization.” some people claim
it stands for “expectationmaximization.” that reminds me of the time that i couldn't remember how to
spell a certain word: was it “intractibility” or “intractability”? i queried altavista on both, and the latter
won out 78522. i'm not sure what my point is, but anyway, the em algorithm can solve our problem!
we will begin with uniform parameter values. that is, suppose there are 40,000 words in the french
vocabulary. then we begin with the assumption that t(f | e) = 1/40,000 for every pair of english and french
words. maybe “house” translates to “maison,” or maybe translates to “internationale.” at this point, we
have no idea.
exercise. with uniform distortion probabilities, what is the chance that an english word in position 4 will
produce a french word that winds up in position 7, assuming both sentences are 10 words long? i.e., d(7 |
4, 10, 10) = ?
we can pick a random value for p1, say 0.15, and we can assign every english word the same set of fertility
probabilities.
now that we have some values, we can compute alignment probabilities for each pair of sentences. that
means we can collect fractional counts. when we normalize the fractional counts, we have a revised set of
parameter values. hopefully these will be better, as they take into account correlation data in the bilingual
corpus. armed with these better parameter values, we can again compute (new) alignment probabilities.
and from these, we can get a set of evenmorerevised parameter values. if we do this over and over, we
may converge on some good values.
let's see how this works in practice. we'll illustrate things with a very simplified scenario. our corpus will
contain two sentence pairs. the first sentence pair is bc/xy (a twoword english sentence “b c” paired with
a twoword french sentence “x y”). the second sentence pair is b/y (each sentence contains only one
word).
exercise. what would you say to me if i claimed that “every time the english word c appears, the french
word y also appears, so they are translations of each other”?
we are also going to forget about the null word, require every word to have only fertility 1, and forget
about distortion probabilities. in that case, the sentence pair bc/xy has only two alignments:
b c b c
| | x
x y x y
exercise. which two alignments are we ignoring for the purposes of this scenario?
the sentence pair b/y only has one alignment:
b
|
y
given our simplifications, the only things that bear on the alignment probabilities are the word translation
(t) parameter values. so we'll pare down our p(a,f | e) formula:
m
p(a,f | e) = Π t(fj | eaj)
j=1
this is actually the p(a,f | e) formula for model 1. (although, unlike this scenario, model 1 generally works
with null and all possible alignments).
okay, here goes em:
step 1. set parameter values uniformly.
t(x | b) = 1/2
t(y | b) = 1/2
t(x | c) = 1/2
t(y | c) = 1/2
step 2. compute p(a,f | e) for all alignments.
b c
| | p(a,f | e) = 1/2 * 1/2 = 1/4
x y
b c
x p(a,f | e) = 1/2 * 1/2 = 1/4
x y
b
| p(a,f | e) = 1/2
y
step 3. normalize p(a,f | e) values to yield p(a | e,f) values.
b c
| | p(a | e,f) = 1/4 / 2/4 = 1/2
x y
b c
x p(a | e,f) = 1/4 / 2/4 = 1/2
x y
b
| p(a | e,f) = 1/2 / 1/2 = 1 ;; there's only one alignment, so p(a | e,f) will be 1 always.
y
step 4. collect fractional counts.
tc(x | b) = 1/2
tc(y | b) = 1/2 + 1 = 3/2
tc(x | c) = 1/2
tc(y | c) = 1/2
step 5. normalize fractional counts to get revised parameter values.
t(x | b) = 1/2 / 4/2 = 1/4
t(y | b) = 3/2 / 4/2 = 3/4
t(x | c) = 1/2 / 1 = 1/2
t(y | c) = 1/2 / 1 = 1/2
repeat step 2. compute p(a,f | e) for all alignments.
b c
| | p(a,f | e) = 1/4 * 1/2 = 1/8
x y
b c
x p(a,f | e) = 3/4 * 1/2 = 3/8
x y
b
| p(a,f | e) = 3/4
y
repeat step 3. normalize p(a,f | e) values to yield p(a | e,f) values.
b c
| | p(a | e,f) = 1/4
x y
b c
x p(a | e,f) = 1/4 / 2/4 = 3/4
x y
b
| p(a | e,f) = 1
y
repeat step 4. collect fractional counts.
tc(x | b) = 1/4
tc(y | b) = 3/4 + 1 = 7/4
tc(x | c) = 3/4
tc(y | c) = 1/4
repeat step 5. normalize fractional counts to get revised parameter values.
t(x | b) = 1/8
t(y | b) = 7/8
t(x | c) = 3/4
t(y | c) = 1/4
repeating steps 25 many times yields:
t(x | b) = 0.0001
t(y | b) = 0.9999
t(x | c) = 0.9999
t(y | c) = 0.0001
what happened? the alignment probability for the “crossing alignment” (where b connects to y) got a
boost from the second sentence pair b/y. that further solidified t(y | b), but as a side effect also boosted t(x
| c), because x connects to c in that same “crossing alignment.” the effect of boosting t(x | c) necessarily
means downgrading t(y | c) because they sum to one. so, even though y and c cooccur, analysis reveals
that they are not translations of each other.
em for model 3 is just like this, except we use model 3's formula for p(a | f,e), and we additionally collect
fractional counts for n, p, and d parameters from the weighted alignments.
exercise. carry out two or three iterations of model 1 em training on the following sentence pairs:
the blue house <> la maison bleue
the house <> la maison
just consider six possible alignments for the first sentence pair, and two possible alignments for the
second sentence pair. here is a start:
t(la | the) = 1/3
t(maison | the) = 1/3
t(bleue | the) = 1/3
t(la | blue) = 1/3
t(maison | blue) = 1/3
t(bleue | blue) = 1/3
t(la | house) = 1/3
t(maison | house) = 1/3
t(bleue | house) = 1/3
the blue house
| | | p(a,f | e) = 1/3 * 1/3 * 1/3 = 1/27
la maison bleue
the blue house
| x p(a,f | e) = 1/3 * 1/3 * 1/3 = 1/27
la maison bleue
...
28. what is em doing?
the em algorithm knows nothing about natural language translation, of course. it's simply trying to
optimize some numerical deal. what is that deal? to answer that, let's go back to the quantitative
evaluation of models that we discussed in section 12. in that section, we were discussing language
models, and we decided that a good language model would be one that assigned a high p(e) to
monolingual test data. likewise, a good translation model will be one that assigns a high p(f | e) to
bilingual test data. because model 3 does not include any dependencies from one sentence to the next, we
can take p(f | e) to be the product of all the p(f | e)'s of all the sentence pairs in the bilingual corpus. we
have a formula for p(f | e), so this is a quantitative notion. one set of parameter values for model 3 will be
better or worse than another set, according to this measure.
parameters set uniformly will produce a very low p(f | e). as it turns out, each iteration of the em
algorithm is guaranteed to improve p(f | e). that's the number that em is optimizing in its computations.
em is not guaranteed to find a global optimum, but rather only a local optimum. where em winds up is
therefore partially a function of where it starts.
it is more convenient to measure the goodness of a model with perplexity:
log (p(f | e)) / n
2
each em iteration lowers the perplexity.
imagine the following gambling game. i show you an english sentence e, and i sequester a certain french
translation f in my pocket. now i give you $100 to bet on various french sentences. you can spread the
$100 as you see fit. you can bet it all on one french sentence, or you can bet fractions of pennies on many
french sentences. spreading your bet is like spreading the unit mass of probability p(f | e) across many
sentences f.
then i reveal the french translation from my pocket. we see how much you bet on that sentence. if you bet
$100, you'll get a nice payoff. even if you bet a dime, you'll get a nice payoff. but if you bet nothing, then
you lose all your money. because in that case, you set p(f | e) = 0, and you made a big mistake.
at each iteration of the em algorithm, the computer can play this gambling game better and better. that's
what it learns to do. that's all it learns to do.
exercise. if you were very good at this game, do you think you would be a good translator? if you were a
good translator, would you be good at this game?
model 3 has at least two problems with this game. you should know about them. the first one is simple.
the distortion parameters are a very weak description of wordorder change in translation. words just fly
around all over the place. so model 3 will bet on lots of ungrammatical french sentences. we mentioned
above that p(e) will take up some of the slack. the second problem is that model 3 also lays bets on french
sentences that you wouldn't even recognize as natural language at all. in the generative model, remember
that we choose a target position slot for each french word (the permutation step). nothing in the generative
story prevents us from selecting target position 7 for every french word, in which case they will all pile up
on top of each other, leaving the other target positions empty. if you saw a sentence like that, you wouldn't
be able to read it, because it would look like the lot of white space surrounding a big blob of ink. because
model 3 lays bets on such nonstrings, better models will look down on it and called it deficient. don't
lose any sleep over this, though. we're not going to use model 3 to translate english into french. plus, if
we happened to see a french sentence with words piled on top of each other, we would be able to deal with
it most machine translation algorithms would just freak out, don't you think?
29. decoding
we can learn parameters values for computing p(e) from monolingual english text. we can learn
parameter values for computing p(f | e) from bilingual sentence pairs. to translate an observed french
sentence f, we seek the english sentence e which maximizes the product of those two terms. this process
is called decoding. it's impossible to search through all possible sentences, but it is possible to inspect a
highly relevant subset of such sentences. we won't go into the details of this heuristic search in this
workbook. ibm threatened to describe decoding in a “forthcoming paper” which never came forth. it is
described in their us patent.
30. practical problems with model 3 training
there are a couple of serious problems with the training algorithm we presented above. first, em does not
find a globally best solution. in practice, for example, it may seize upon imaginary regularities in word
distortion. it may decide that the best way to improve p(f | e) is to always link the first two respective
words in any sentence pair. in that case, distortion costs will be small, and wordtranslation costs will be
large, because a given english word will have very many possible translations. linguistically, it may make
more sense to have fewer word translations and higher distortion costs, but the em algorithm does not
know anything about linguistics. to solve this problem, we may want to hold the distortion probabilities at
uniform values until we update our translation probabilities through a few em iterations.
the second problem is more serious. as described above, the em algorithm needs to iterate over every
alignment of every sentence pair. if a sentence pair contains 20 words of english and 20 words of french,
then there are too many alignments to consider. (how many?). there's no way to iterate over all of them,
even for just this one sentence pair.
the solution is to iterate only over a subset of “goodlooking” (probable) alignments. for example, we
could collect fractional counts only over the best 100 alignments for each sentence pair. that brings up
two questions. first, how to find the best 100 alignments without enumerating them all. and second, how
to get the thing off the ground. at the first iteration, remember that the parameter values are set uniformly.
that means any alignment is just as probable as any other.
both problems can be addressed if we have a quickanddirty way of initializing parameter values. in fact,
model 1 provides such a way. it turns out that we can collect model 1 fractional t counts from all possible
alignments without having to enumerate all possible alignments.
31. efficient model 1 training
recall that training involves collecting fractional counts that are weighted by p(a | e,f). also recall:
p(a | e,f) = p(a,f | e) / p(f | e) = p(a,f | e) / Σ p(a,f | e)
a
consider the computation of the denominator above. using model 1, we can write it as:
m
Σ Π t(fj | eaj)
a j=1
since there are (l+1)^m possible alignments, we have to do m * (l+1)^m arithmetic operations to evaluate
this expression. for clarity, let's actually write it out in terms of t parameter values:
t(f1 | e0) * t(f2 | e0) * ... * t(fm | e0) +
t(f1 | e0) * t(f2 | e0) * ... * t(fm | e1) +
t(f1 | e0) * t(f2 | e0) * ... * t(fm | e2) +
...
t(f1 | e0) * t(f2 | e1) * ... * t(fm | e0) +
t(f1 | e0) * t(f2 | e1) * ... * t(fm | e1) +
t(f1 | e0) * t(f2 | e1) * ... * t(fm | e2) +
...
t(f1 | el) * t(f2 | el) * ... * t(fm | e0) +
t(f1 | el) * t(f2 | el) * ... * t(fm | e1) +
t(f1 | el) * t(f2 | el) * ... * t(fm | e2) +
...
t(f1 | el) * t(f2 | el) * ... * t(fm | el)
each row here corresponds to a particular alignment, and each column corresponds to a french word. in
the first row, all french words are connected to e0 (null). the second row is the same except that the final
french word fm is connected to e1 instead of e0. the last row represents the alignment in which all french
words are connected to the sentencefinal english word el. now you can clearly see that there are m *
(l+1)^m arithmetic operations required to compute p(f | e).
but we can take advantage of certain regularities in the above expression. for example, we can factor out
t(f1 | e0) from all of the rows (alignments) that contain it, yielding:
t(f1 | e0) * [ t(f2 | e0) * ... * t(fm | e0) +
t(f2 | e0) * ... * t(fm | e1) +
t(f2 | e0) * ... * t(fm | e2) +
...
t(f2 | e1) * ... * t(fm | e0) +
t(f2 | e1) * ... * t(fm | e1) +
t(f2 | e1) * ... * t(fm | e2) +
... ]
t(f1 | el) * t(f2 | el) * ... * t(fm | e0) +
t(f1 | el) * t(f2 | el) * ... * t(fm | e1) +
t(f1 | el) * t(f2 | el) * ... * t(fm | e2) +
...
t(f1 | el) * t(f2 | el) * ... * t(fm | el)
we just saved a bunch of multiplications. it's like the difference between “xy+xz” (3 operations) and
“x(y+z)” (2 operations). if we continue with this style of factoring out, we get:
[ t(f1 | e0) + t(f1 | e1) + ... + t(f1 | el) ] *
[ t(f2 | e0) + t(f2 | e1) + ... + t(f2 | el) ] *
...
[ t(fm | e0) + t(fm | e1) + ... + t(fm | el) ]
exercise. verify that this expression is equal to the expressions above.
in more compact notation:
m m l
Σ Π t(fj | eaj) = Π Σ t(fj | ei)
a j=1 j=1 i=0
this last expression only requires a quadratic number of arithmetic operations to evaluate (to be exact: l+1
* m operations). that means we can efficiently compute p(f | e) for model 1. it is not hard to figure out
how to collect fractional counts during em training efficiently as well.
32. best alignment for model 1
model 1 has another advantage. it is easy to figure out what the best alignment is for a pair of sentences
(the one with the highest p(a | e,f) or p(a,f | e)). we can do this without iterating over all the alignments.
remember that p(a | e,f) is computed in terms of p(a,f | e). in model 1, p(a,f | e) has m factors, one for each
french word. each factor looks like this: t(fj | eaj). suppose that the french word f4 would rather connect
to e5 that e6, i.e., t(f4 | e5) > t(f4 | e6). that means if we are given two alignments which are identical
except for the choice of connection for f4, then we should prefer the one that connects f4 to e5 no matter
what else is going on in the alignments. so we can actually choose an english “home” for each french
word independently.
for 1 <= j <= m,
aj = argmax t(fj | ei)
i
that's the best alignment, and it can be computed in a quadratic number of operations (l+1 * m).
exercise. find the best alignment for the sentence pair “bcd/xy.” first enumerate all nine alignments
(forget about null), and evaluate p(a | e,f) for each separately. then use the quadratic method above. verify
that the results are the same. use the following parameter values: t(x | b) = 0.7, t(y | b) = 0.3, t(x | c) = 0.4,
t(y | c) = 0.6, t(x | d) = 0.9, t(y | d) = 0.1.
unfortunately, the “best” alignment according to a fullytrained model 1 may not be very intuitively
satisfying. because each french word chooses its preferred english “home” independently, they may very
well all choose english word e5. according to the model 1 generative story (which i didn't write down for
you), that means e5 generates every french word.
33. back to model 3
our linguistic intuitions tell us that e5 generating every french word is a bit unlikely. in fact, model 3 can
penalize such an alignment by using its fertility probabilities. if it is unlikely that e5 has a huge fertility,
and it is unlikely that the rest of the words all coincidentally have zero fertility, then such alignment will
look bad. model 1 has no way to achieve this.
now we can see that the “fertility” idea is the result of linguistic intuitions. these intuitions must be tested,
of course. it may turn out that in real translation, fertilities are pretty random. we can always compare
model 1 to model 3 by inspecting their “best” alignments and seeing which are more intuitive. we can
also compare models by computing their respective perplexities (section 28).
fertilities might be good for modeling translation, but they're not good for efficient computation. we
cannot compute the best model 3 alignment using the trick from section 32, because french words cannot
choose their “homes” independently. if two words choose the same home, that may change the whole
p(a,f | e) value. furthermore, in computing p(f | e), we must iterate over all alignments. we cannot do the
factoring trick from section 31. all is not bleak: we can still compute p(a,f | e) for a specific alignment
fairly quickly, using the formula in section 25.
here is a practical plan for model 3 training. first i'll show a diagram, and then explain it.
uniform t values
|
model 1 iteration (collect fractional counts over all alignments)
|
revised t values
|
model 1 iteration (collect fractional counts over all alignments)
|
revised t values
|
...
|
revised t values uniform n, d, p values
| |
model 3 (collect fractional counts over a subset alignments,
identified with the help of the model 1 viterbi alignment)
|
revised t, n, d, p values
|
model 3 (collect fractional counts over a subset alignments,
identified with the help of the model 1 viterbi alignment)
|
revised t, n, d, p values
|
...
|
final t, n, d, p values
okay: we first train model 1 for several iterations. when that is done, we find the best alignment (also
called the viterbi alignment) for each sentence pair, according to model 1 parameter values. for each
sentence pair, we then rescore the model 1 viterbi alignment using the p(a,f | e) formula of model 3. (if
this is the first model 3 iteration, then we will have to use uniform fertility and distortion probabilities).
once we have a somewhat reasonable alignment and a model 3 score, we can consider small changes to
the alignment. (for example, changing the connection of f4 from e5 to e7). if a small change improves the
model 3 score, we make that change. we keep changing the alignment (hill climbing) until there is no
simple way to improve it anymore. we'll call this the “viterbi” alignment for model 3, even though we
don't know for a fact that this is the best alignment according to the p(a | e,f) formula of model 3.
now we consider this model 3 viterbi alignment together with its neighborhood those alignments that
look very similar to it (are obtainable from very small changes). this gives us a reasonable subset of
model 3 alignments. we can collect fractional counts only over that subset. when we normalize these
counts, we have new values of t, n, d, and p. we can then repeat the process. again we find the best
alignments according to model 1 and the t values, and we use these alignments to greedily find best model
3 alignments. notice that our new values for t feed back into model 1, and may actually yield new model 1
viterbi alignments.
if we want a larger variety of goodlooking alignments, we can start up several hill climbers each begins
at a variant of the model 1 viterbi alignment in which a certain connection is manually set and pegged for
the duration of the climb.
34. model 2
in the end, we're going to do something slightly different and somewhat more interesting. you knew that
there was a model 2, right? this model involves word translations (like model 1) but also distortions. as
with model 1, we can find viterbi alignments and collect fractional counts efficiently. the distortion
probabilities in model 2 are different from the ones in model 3. instead of
d(frenchposition | englishposition, englishsentencelength, frenchsentencelength)
we will use reversedistortion probabilities:
a(englishposition | frenchposition, englishsentencelength, frenchsentencelength)
i apologize profusely for using the notation “a” here. i realize that “a” usually stands for an alignment.
dreadfully, dreadfully sorry. if there's any way i can make it to you, please let me know. here's the p(a,f |
e) formula for model 2:
m m
p(a,f | e) = Π t(fj | eaj) Π a(aj | j,l,m)
j=1 j=1
this model might penalize an alignment that connects positions that are very far apart, even if the
connected words are good translations of each other. or during training, it might prefer to connect up
words on the basis of position, which might actually be good if the words in question are rare (not enough
cooccurrences to establish reliable wordtranslation probabilities).
to find best model 2 alignment, we select for each french word fj (independently) the english position i
that maximizes the wordtranslation and distortion factors:
for 1 <= j <= m,
aj = argmax t(fj | ei) * a(i | j,l,m)
i
to compute p(f | e) efficiently, we use factoringout to do the following rewrite:
m m l
Σ Π t(fj | eaj) * a(aj | j,l,m) = Π Σ t(fj | ei) * a(aj | j,l,m)
a j=1 j=1 i=0
exercise. convince yourself that this rewriting is correct.
it is not hard to extend this reasoning to algorithm that collects fractional counts efficiently over sentence
pairs.
35. transferring parameter values from one model to another
we could apply model 2 directly to the sentence pair corpus, bypassing model 1. as i mentioned earlier, it
might be better to settle on some reasonable wordtranslation probabilities before bringing distortions into
the picture. so we will run model 1 for several iterations, and then use the resulting “t” values as input to
the first model 2 iteration, instead of uniform t values. this simple idea is called transferring parameter
values from one model to another. for the first model 2 iteration, we will use uniform “a” values.
it's more interesting when we transfer parameter values from model 2 to model 3. we would like to use
everything we learned in model 2 iterations to set initial model 3 parameter values. while we could set up
a uniform distortion table d, it is fairly easy to set up better values. we can insert a “one time only”
special transfer iteration in between model 2 iterations and model 3 iterations. during this transfer, we can
do quadratictime count collection, but in addition to collecting t and a counts, we can collect d counts as
well.
how about fertilities? we could use some uniform (or other simple) initialization, but again, we would like
to use what we have learned in model 2 to set up better initial values. imagine that model 2 identified
some very highly probable alignments. in that case, we could inspect these alignments to get a reasonable
first idea about the fertility of a word like “house.” if, according to model 2, “house” tends to connect to a
single french word, then we can conclude that it tends to have fertility one. subsequent model 3 iterations
may modify this conclusion, of course.
unfortunately, there seems to be no quadratictime algorithm for turning t and a knowledge into fertility
(n) knowledge. we must give up on the idea of iterating over all alignments, so that option is out. but
there is a middle ground.
for purposes of explanation, let's forget about the “a” (reverse distortion) parameters, and just compute
initial fertility parameter values from previouslylearned model 1 (wordtranslation) “t” parameter values.
consider a corpus with the sentence pair bc/xy, and suppose that model 1 has learned the following:
t(x | b) = 0.8
t(y | b) = 0.2
t(x | c) = 0.2
t(y | c) = 0.8
let's entertain the following four alignment possibilities:
b c
| | alignment1
x y
b c
/| alignment2
x y
b c
|\ alignment3
x y
b c
x alignment4
x y
now we want to guess initial values for the fertility (n) table. we will look at four methods.
method one. assign uniform probabilities. we notice from the given alignments that the word b may have
a fertility of 0, 1, or 2. we therefore assign n(0 | b) = n(1 | b) = n(2 | b) = 1/3.
method two. collect fractional counts of fertilities over all alignments, but pretend that each alignment is
equally likely. of the four alignments, only alignment2 shows a zero fertility for word b, so n(0 | b) = 1/4.
this method can be applied efficiently to very long sentence pairs.
exercise. using this method, what are the values for n(1 | b) and n(2 | b)? do the results make sense to
you?
method three. collect fractional counts of fertilities over all alignments, but take wordtranslation
probabilities into account. this is like normal em training. for each alignment, we compute p(a | e,f) and
use this value for weighting counts that we collect. remember that p(a | e,f) = p(a,f | e) / sumovera p(a,f |
e), and for model 1, p(a,f | e) is the product of all the wordtranslation probabilities indicated by the
alignment.
p(alignment1 | e,f) = 0.8 * 0.8 > normalized > 0.64
p(alignment2 | e,f) = 0.2 * 0.8 > normalized > 0.16
p(alignment3 | e,f) = 0.8 * 0.2 > normalized > 0.16
exercise. what is p(alignment4 | e,f)?
now we collect fractional counts. alignment2 is the only one in which we observe b to have fertility zero.
so we collect a fertility count for zero with weight 0.16:
nc(0 | b) = 0.16
alignments 1 and 4 both show b with fertility one. so we add the two fractional counts:
nc(1 | b) = 0.64 + 0.04 = 0.68
nc(2 | b) = 0.16
in this case, the values of the nc counts happen to already add to one, so they remain as they are when
normalized: n(0 | b) = 0.16, n(1 | b) = 0.68, n(2 | b) = 0.16. the distribution 0.16/0.68/0.16 is better than
those obtained by methods one and two, because it takes into account what model 1 has learned, i.e., that
alignment1 is very probable, and hence both words probably have fertility one.
method four. we know that method three does not scale to long sentences, because we cannot enumerate
alignments. but we can get exactly the same results as method three with a computationally cheaper
algorithm:
l = length of english sentence
m = length of french sentence
ei = ith english word
fj = jth french word
t(f | e) = probability english word e translates to french word f
phimax = maximum fertility of any word
biggamma(n) = partition of n into a sum of integers all >= 1
(e.g., 1+2+4 is a partition of 7, and so is 1+1+1+1+3)
times(partition, k) = number of times integer k appears in partition
for i = 1 to l
for k = 1 to phimax
beta = 0.0
for j = 1 to m
beta += [ t(fj | ei) / (1 t(fj | ei) ]^k
alpha[i,k] = (1)^(k+1) * beta / k
for i = 1 to l
r = 1.0
for j = 1 to m
r = r * (1 t(fj | ei))
for phi = 0 to phimax
sum = 0.0
for each partition p in biggamma(phi)
prod = 1.0
for k = 1 to phi
prod = prod * alpha[i,k]^times(p,k) / times(p,k)!
sum += prod
c(phi | ei) += r * sum
you can verify by hand that this algorithm yields the same results on the example above as method three
does. you can make the algorithm work for model 2 by multiplying in an a(i | j,l,m) factor next to every
t(fj | ei) expression above. the proof of method four can be found after (brown et al, 1993)'s equation 108.
note that this equation has an error (please remove the factor of k! from the computation of alpha).
finally, there is a nice way to march through the partitions of an integer in linear time, without allocating
space for each one. almost as though i were a hip youngster, i found some pascal code on the world wide
web to do that.
you may be wondering: if we can compute fertility counts without having to iterate over all alignments,
then haven't we solved the model 3 training problem, without heuristic recourse to a “small subset” of
alignments? not really. the method above takes t and a values as input and produces fertility values. if we
try to iterate this same method, then we would have to throw away the fertility values the ones we just
learned! the only inputs are t and a. the method cannot accept one set of fertility values and then revise
them, which is what we want from model 3 training.
it is possible to use a similar method to determine an initial value for the parameter p1, but i suggest you
just assign it a value and wing it.
36. the final training scheme
in this new scheme, we will insert model 2 iterations as well as a special “one time only” transfer iteration
between models 2 and 3. to collect a subset of reasonable alignments for model 3 training, we will start
with the model 2 viterbi alignment, and use it to greedily search for the model 3 “viterbi” alignment (the
scare quotes indicate that we are not really sure it's the best, but it's the best we can find quickly). then we
collect up a neighborhood of reasonable alignments. here it is:
uniform t values
|
model 1 iteration (collect fractional counts over all alignments)
|
revised t values
|
model 1 iteration (collect fractional counts over all alignments)
|
|
revised t values uniform a values
| |
model 2 iteration (collect fractional counts over all alignments)
|
revised t and a values
|
model 2 iteration (collect fractional counts over all alignments)
|
revised t and a values
|
model 2>3 (one time only transfer of parameter values)
| |
revised t and a values initial n, d, p values
| |
model 3 (collect fractional counts over a subset of alignments,
identified with the help of the model 2 viterbi alignment)
|
revised t, a, n, d, p values
|
model 3 (collect fractional counts over a subset of alignments,
identified with the help of the model 2 viterbi alignment)
|
revised t, a, n, d, p values
|
... more and more iterations ...
|
final t, a, n, d, p values
notice that we continue to revise the “a” parameter values (“reverse distortion”) even during model 3
iterations. that's because model 3 needs to invoke model 2 scoring as a subroutine.
37. wow
with this primenumbered section, we draw a close to the proceedings. if you made it all the way, then i’ll
buy you a beer!
You might also like
- A Gentle Introduction To Neural Machine TranslationNo ratings yetA Gentle Introduction To Neural Machine Translation14 pages
- Overview of Machine Translation MethodsNo ratings yetOverview of Machine Translation Methods13 pages
- Statistical Machine Translation OverviewNo ratings yetStatistical Machine Translation Overview7 pages
- Machine Translation Approaches ExplainedNo ratings yetMachine Translation Approaches Explained42 pages
- Statistical Machine Translation OverviewNo ratings yetStatistical Machine Translation Overview81 pages
- Bhootpurv Translation in Machine LearningNo ratings yetBhootpurv Translation in Machine Learning14 pages
- Understanding Machine Translation TechniquesNo ratings yetUnderstanding Machine Translation Techniques58 pages
- Machine Translation Techniques ExplainedNo ratings yetMachine Translation Techniques Explained7 pages
- Machine Translation for Indian LanguagesNo ratings yetMachine Translation for Indian Languages29 pages
- Machine Translation & Post-Editing RisksNo ratings yetMachine Translation & Post-Editing Risks18 pages
- Corpus Based & Machine Based Translation # Roll No. 35No ratings yetCorpus Based & Machine Based Translation # Roll No. 3519 pages
- Understanding Machine Translation TypesNo ratings yetUnderstanding Machine Translation Types10 pages
- Machine Translation Systems For Indian Languages: Review of Modelling Techniques, Challenges, Open Issues and Future Research DirectionsNo ratings yetMachine Translation Systems For Indian Languages: Review of Modelling Techniques, Challenges, Open Issues and Future Research Directions29 pages
- Overview of Statistical Machine TranslationNo ratings yetOverview of Statistical Machine Translation104 pages
- Machine Translation - An Introductary Guide, ArnoldNo ratings yetMachine Translation - An Introductary Guide, Arnold323 pages
- Understanding Machine Translation TechniquesNo ratings yetUnderstanding Machine Translation Techniques12 pages
- Machine Translation: Theory & EvolutionNo ratings yetMachine Translation: Theory & Evolution44 pages
- Statistical vs Neural Machine TranslationNo ratings yetStatistical vs Neural Machine Translation12 pages
- Understanding Statistical Machine TranslationNo ratings yetUnderstanding Statistical Machine Translation4 pages
- Understanding Machine Translation ConceptsNo ratings yetUnderstanding Machine Translation Concepts42 pages
- SDL Learning and Development: Post-Editing Certification SDL ImtNo ratings yetSDL Learning and Development: Post-Editing Certification SDL Imt54 pages
- Statistical Machine Translation: Sinhala-TamilNo ratings yetStatistical Machine Translation: Sinhala-Tamil7 pages
- Get Instant Probability For Machine Learning Discover How To Harness Uncertainty With Python 1st Edition by Jason Brownlee Access Today100% (5)Get Instant Probability For Machine Learning Discover How To Harness Uncertainty With Python 1st Edition by Jason Brownlee Access Today221 pages
- Machine Translation Overview by ConlonovaNo ratings yetMachine Translation Overview by Conlonova31 pages
- Overview of Machine Translation TechnologiesNo ratings yetOverview of Machine Translation Technologies30 pages
- Language Translation Model Seminar ReportNo ratings yetLanguage Translation Model Seminar Report26 pages
- Overview of Machine Translation TechniquesNo ratings yetOverview of Machine Translation Techniques17 pages
- Overview of Machine Translation TechniquesNo ratings yetOverview of Machine Translation Techniques12 pages
- Statistical Machine Translation OverviewNo ratings yetStatistical Machine Translation Overview128 pages
- Probability For Machine Learning Discover How To Harness Uncertainty With Python 1st Edition by Jason Brownlee Download Link100% (1)Probability For Machine Learning Discover How To Harness Uncertainty With Python 1st Edition by Jason Brownlee Download Link172 pages
- Lesson Plan: Children's Prattle & PronounsNo ratings yetLesson Plan: Children's Prattle & Pronouns2 pages
- English Language and Literature SyllabusNo ratings yetEnglish Language and Literature Syllabus8 pages