So in this lecture, we will consider a slight modification to our method of estimating a pie and also
how to compute the probability of a sequence using the Markov model.
In other words, we're going to consider slightly different ways to answer the two questions we previously
posed.
So the previous estimates we discussed are called the maximum likelihood estimates, since they are
the estimates that yield the maximum value of the likelihood given the dataset being trained on.
In this lecture, we will look at one potential problem of using this method and how to fix it.
So let's consider how we find the probability of a sequence using a PI from this expression, we can
see that it involves only one operation multiplication.
Now let's suppose that one of these values is zero, which can happen if we're trying to find the likelihood
of a sentence that contains pairs of words that never appeared in our training dataset.
This is entirely possible since our train set will be different from our test set.
Well, because this expression contains only multiplication and we know that anything times zero is
still zero.
This will make the entire expression zero, although this seems like it might be the right answer.
It's not because we probably don't want to conclude a sentence is impossible simply because it contains
a pair of words that did not appear in our training set.
So what should we do about this problem?
Intuitively, what we would like to do is give a small probability to every possible transition, even
if they never occur in the training set.
By doing this, we can avoid encountering any zeros during testing.
The easiest way to do this is called +1 one smoothing +1 one smoothing is exactly what it sounds like.
We simply out of fake count of one to every possible transition.
The resulting estimate for AIG then looks like this on the numerator.
We had a one on the denominator we had em, as you recall, for a probability distribution to be valid.
All of the probabilities must sum to one.
Since we had a one to each of the impossible values, we must also add em to the denominator as well.
You should convince yourself if it's not already obvious that this indeed results in each row of AIG,
something to one.
Note that it's also possible to use add one smoothing for pie as well.
Again, we add one to the top and we get em to the bottom.
One simple extension to add one smoothing is add Epsilon smoothing.
Perhaps we believe that adding one is a bit too biased in this case.
What we do instead is add a small fake accounts epsilon to the numerator and epsilon times m to the
denominator again by the same logic we use before we can conclude that this results in each row of AIG,
something to one.
And of course, the same thing applies to PI as well.
Furthermore, note that we can add even more smoothing to our estimate simply by making Epsilon greater
than one.
So thus far, we've considered how we might modify our answer to one of the questions we posed earlier.
How to find a pie given a training data set.
The next question we're going to consider in this lecture is how we can modify our answer to the other
question which was given a sequence.
How do we find the probability of that sequence?
So let's start by discussing our motivation for why we would want to do this again.
We'll begin by recognizing the fact that our joint probability involves only multiplying a bunch of
numbers together.
In particular, these numbers are probabilities.
In the case of language, these probabilities will be very small simply due to the fact that there are
so many words in the English language.
In many applications, it's not uncommon to consider a vocabulary of twenty thousand or fifty thousand
words.
So these probabilities will likely be very small.
Now what happens when you multiply many small numbers together?
The answer is they get even smaller.
So, for example, zero point one times zero point one is zero point zero one.
So as you multiply more and more of these small numbers together, you get closer and closer to zero.
Of course, computers do not have infinite precision.
Eventually, you're going to get so close to zero that the computer will just round the answer down
to zero.
This is very problematic since if we want to compare two sentences which are both very improbable,
if they both end up giving us zero, then our answer will not be valid.
Now, this might sound like a very weird problem to consider, but in practice, you should find that
this happens quite easily.
So I recommend if you don't believe that this is true.
Try it yourself in wait until you encounter it to convince yourself that it can and will happen.
So what's the solution to this issue?
The solution is to work in the log space instead.
That is, instead of finding probabilities directly, we can find a log probabilities.
Note that it's fine to do this transformation because what we often want to do is compare to probabilities.
So for example, if we have two sentences, we want to know which sentence is more likely or if we have
to Markov models, we might want to know under which Markov model does the sequence yield the largest
probability.
Also note that doing this transformation would not change the answer, since the log is a monotonically
increasing function.
If you don't believe this, I recommend trying it yourself using a calculator.
Choose any values and b then take the log of both A and B.
You should find that if A is greater than B, then log is also greater than log B, and this should
always be true.
Now you might ask, how does taking the law solve the under flow problem?
Well, suppose you have a very small value, say, 10 to the minus 10.
Suppose that we take the log based 10 of this value.
This simply gives us minus 10, which a computer has no problem representing.
Consider the number 10 to the minus 100.
This number is a factor of 10 smaller, but if we take the log of this, we get minus 100, which is
again easy to represent with a computer.
Now, under these circumstances, the log probability is very easy to compute.
As you recall, there is a rule for logarithms, which states that the log of a product is the sum of
logs.
In fact, if you know that you won't need the values of an PI directly, you can simply store their
logged values instead.
Note that you would not want to compute the product form and then take the log since you would end up
taking the log of zero, which doesn't solve a problem.
So the solution is to take the sum of the log probabilities instead.
Another thing to notice is that in a computer, doing this sum is more computationally efficient than
computing a product, as you recall, adding as much faster than doing multiplication.
So even if you do not have problems with under flow, you may still want to use log probabilities for
efficiency.