-
Today we're gonna introduce the topic of
language modeling, one of the most
-
important topics in natural language
processing. The goal of language modeling
-
is to assign a probability to a sentence.
Why would we want to assign a probability
-
to a sentence? This comes up in all sorts
of applications. In machine translation,
-
for example, we'd like to be able to
distinguish between good and bad
-
translations by their probabilities. So,
"high winds tonight" might be a better
-
translation than "large winds tonight"
because high and winds go together well.
-
In spelling correction, we see a phrase
like "fifteen minuets from my house". That's
-
more likely to be a mistake from "minutes".
And one piece of information that lets us
-
decide that is that "fifteen minutes from"
is a much more likely phrase than "fifteen
-
minuets from". And in speech recognition, a
phrase like "I saw a van" is much more
-
likely than a phrase that sounds
phonetically similar, "eyes awe of an". But
-
it's much less likely to have that
sequence of words. And it turns out
-
language modelings play a role in
summarization, and question answering,
-
really everywhere. So the goal of a
language model is to compute the
-
probability of a sentence or a sequence of
words. So given some sequence of words w1
-
through wn, we're gonna compute their
probability P of w, and we'll use capital W
-
to mean a sequence from w1 to wn. Now, this is
related to the task of computing the
-
probability of an upcoming word, so P of w5
given w1 through w4 is very related to the
-
task of computing P(w1, w2, w3, w4, w5). A
model that computes either of these
-
things, either P(W), capital W, meaning a
string, the joint probability of the whole
-
string, or the conditional probability of
the last word given the previous words,
-
either of those, we call that a language
model. Now it might have better to call
-
this the grammar. I mean technically what
this is, is telling us something about how
-
good these words fit together. And we
normally use the word grammar for that,
-
but it turns out that the word "language
model", and often we'll see the acronym LM,
-
is standard, so we're gonna go with that.
So, how are we going to compute this joint
-
probability? We want to compute, let's say the
probability of the phrase "its water is so
-
transparent that", this little part of a
sentence. And the intuition for how
-
language modeling works is that you're
going to rely on the chain rule of
-
probability. And just to remind you about
the chain rule of probability. Let's think
-
about the definition of conditional
probability. So P of A given B
-
Equals P of A comma B over P of B.
And we can rewrite that, so P of A
-
given B times P of B
equals P of A comma B, or turning it
-
around, P of A comma B equals P of A
given B (I'll make sure it's a "given") times P
-
of B. And then we could generalize this to
more variables so the joint probability of
-
a whole sequence A B C D is the
probability of A, times B given A, times C
-
conditioned on A and B, times D
conditioned on A B C. So this is the chain
-
rule. In a more general form of the chain
rule we have here the probability of any,
-
joint probability of any sequence of
variables is the first, times the
-
condition of the second and the first,
times the third conditioned of the
-
first two, up until the last conditioned
on the first n minus one. Alright, the
-
chain rule. So now, the chain rule can be
applied to compute the joint probability
-
of words in a sentence. So let's suppose
we have our phrase, "its water is so
-
transparent". By the chain rule, the
probability of that sequence is the
-
probability of "its" times the probability
of "water" given "its", times the probability
-
of "is" given "its water", times the
probability of "so" given "its water is", and
-
finally times the probability of
"transparent" given "its water is so". Or, more
-
formally, the probability, joint
probability of a sequence of words is the
-
product over all i of the probability of
each word times the prefix up until that
-
word. How are we gonna estimate these
probabilities? Could we just count and
-
divide? We often compute probabilities by
counting and dividing. So, the probability
-
of "the" given "its water is so transparent
that", we could just count how many times
-
"its water is so transparent that the"
occurs and divide by the number of times
-
"its water is so transparent" occurs. So we
could divide this by this. And get a
-
probability. We can't do that. And the
reason we can't do that is there's just
-
far too many possible sentences for us to
ever estimate these. There's no way we could
-
get enough data to see all the counts of
all possible sentences of English. So what
-
we do instead is, we apply a simplifying
assumption called the Markov assumption,
-
named for Andrei Markov. And the Markov
Assumption suggest that we estimate the
-
probability of "the" given "its water is so
transparent that" just by computing instead
-
the probability of "the" given the word "that",
or-- The very last "that", "that" meaning the
-
last word in the sequence. Or maybe we
compute the probability of "the" given "its
-
water is so transparent that" given just
the last two words, so "the" given
-
"transparent that". That's the Markov
Assumption. Let's just look at the
-
previous or maybe the couple previous
words rather than in the entire context. More
-
formally, the Markov Assumption says: The
probability of a sequence of words is the
-
product for each word of the
conditional probability of that word,
-
given some prefix of the last few words.
So, in other words, in the chain rule
-
product of all the probabilities we're
multiplying together, we estimate the
-
probability of wᵢ, given the entire prefix
from one to i-1 by a simpler to
-
compute probability: wᵢ given just the
last few words. The simplest case of a
-
Markov model is called the unigram model.
In the unigram model, we simply estimate
-
the probability of a whole sequence of
words by the product of probabilities of
-
individual words, "unigrams". And if we
generated sentences by randomly picking
-
words, you can see that it would look like
a word salad. So here's some automatically
-
generated sentences generated by Dan Klein,
and you can see that the word "fifth", the
-
word "an", the word "of" -- this doesn't look
like a sentence at all. It's just a random
-
sequence of words: "thrift, did, eighty,
said". That's the properties of the unigram
-
model. Words are independent in this
model. Slightly more intelligent is a
-
bi-gram model where we condition on the
single previous word. So again, we
-
estimate the probability of a word given
the entire prefix from the beginning to
-
the previous word, just by the previous
word. So now if we use that and generate
-
random sentences from a bigram model, the
sentences look a little bit more like
-
English. Still, something's wrong with
them clearly. "outside, new, car", well, "new
-
car" looks pretty good. "car parking" is
pretty good. "parking lot". But together,
-
"outside new car parking lot of the
agreement reached": that's not English. So
-
even the bigram model, by giving up this
conditioning that English has, we're
-
simplifying the ability to model, to model
what's going on in a language. Now we
-
can extend the n-gram model further to
trigrams, that's 3-grams. Or 4-grams
-
or 5-grams. But in general, it's
clear that n-gram modeling is an
-
insufficient model of language. And the
reason is that language has long-distance
-
dependencies. So if I want to, say, predict
"The computer which I had just put into the
-
machine room on the fifth floor", and I
hadn't seen this next word, and I want to
-
say, what's my likelihood of the next
word? And I conditioned it just on the
-
previous word, "floor", I'd be very unlucky
to guess "crashed". But really, the "crashed" is
-
the main verb of the sentence, and "computer"
is the subject, the head of the subject
-
noun phrase. So, if we know "computer" was
the subject, we're much more likely to
-
guess crashed. So, these kind of
long-distance dependencies mean that in the
-
limit of really good model of predicting
English words, we'll have to take into
-
account lots of long-distance information.
But it turns out that in practice, we can
-
often get away with these n-gram models,
because the local information, especially
-
as we get up to trigrams and 4-grams,
will turn out to be just constraining
-
enough that it in most cases it'll solve
our problems for us.
