Everyone and welcome back to this class natural language processing in Python.
In this lecture, you're going to get your first introduction to language modeling.
Intuitively, what we want is this we want to build some kind of model that will assign high probabilities
to real words and sentences and low probabilities to unreal words and sentences.
Let's look at an example.
In fact, let's just use the same example from before the phrase I like cats should have high probability
because it is a real sentence or as the phrase why in jail OBE should have low probability because it
is not a real sentence.
The idea is, if you decrypt the message correctly, then the result should have high probability.
If you decrypt the message incorrectly, then the result should have low probability.
Let's think about how we can build such a probability model.
The key concepts we require at this time are the engram and the markup model.
First, let's explain the Engram and Engram simply refers to a sequence of the tokens.
Now, if you've never heard of any of these words before, this probably sounds like gibberish to you.
So let's break it down first.
Tokens in the usual context would refer to individual words.
But in our code cracking example, tokens will actually refer to individual letters.
This makes sense because if we decode a sentence, each individual word must follow a logical sequence
of letters to be more specific.
Usually, we work with small values event.
For example, we might consider you anagrams, which are individual letters by themselves.
We can also consider by grams, which are sequences of two letters.
We can also consider tri grams, which are sequences of three letters.
We could do up to four grams or five grams and so forth.
But this would be unusual for our example we will stick with by grams and unit grams.
Now what does this have to do with Markov models?
In the abstract form, a mark of model is a probability model that says that the current state X of
T depends only on the previous state x of T minus one.
In other words, it does not depend on any previous state like X of T minus two x of C minus three and
so on.
This is how we can write it formally.
We see that p of X of T given X of T minus one x of T minus two and so forth is equal to p of X of T
given X of T minus one.
If you are afraid of math, don't worry this is actually very simple.
As you'll see in our case, the state simply refers to the letter.
So I want to know how often does one letter follow some other, possibly the same letter?
This model makes what is called the mark of assumption, because we assume that each letter depends
only on the previous letter and not on any others.
Of course, this assumption is probably false, but it is quite useful.
Let's think about what this means in a practical sense.
Think about the word cat as you can see, the letter A follows the letter C.
The letter T follows the letter A..
So I want to know P of a given C and T given A..
These are the two big diagrams that appear in this word.
This will tell me how often the Letter H follows a letter C and how often the letter T follows the letter
A..
If our data set only consists of the word cat.
Then of course, these probabilities are 100 percent because we only have these two examples.
But now imagine you have an entire corpus of data.
For example, you could take all the text on Wikipedia or all the text from a book like, say, Moby
Dick.
We would then be able to find a bigram probabilities for every combination of letters, ABC, ID and
so on.
In general, I can write this as follows the probability of the letter at position T, which we're calling
X.
Given the letter at position T minus one is measured by the number of times the letter at position T
follows the letter at position T minus one divided by the number of times the letter at position T minus
one appears in total.
As you can see, this is quite simple, but explaining it in words is a little complicated.
All you need to know how to do is count, which I think I can confidently assume all of you know how
to do well, just in case let's think of a concrete example, we can say that the probability that a
follow C is the number of times that a follow C divided by the number of CS in the dataset.
As a mini quiz question, consider this How many bigram probabilities will we have to calculate, given
that there are 26 letters in the alphabet?
I'll give you a minute to think about this, so please pause the video until you have the answer.
All right, so here's the answer.
The number of probabilities we have to calculate if we have v letters is v squared.
We need to consider AA a b a c all the way up to a z.
Then we need to consider it be a B-BBEE B.C. all the way up to B.C. We continue this pattern all the
way up to Z.
As you can see, this forms a square.
In other words, since there are 26 letters, we need to find a 776 different probabilities.
OK, so now that I have this bigram model, how can I use it?
Remember that what I would like to have is the probability of an entire sentence.
A sentence is made up of words.
So it would be helpful if we could first consider how I can find the probability of a single word.
First, let's recall the rule of conditional probabilities.
If I want to know the probability of the sequence, Abby, this is a joint probability.
It's equal to the probability that B follows a multiplied by the probability that A appears by itself.
Therefore, if I see a two letter word, this is how I can calculate the probability of that word.
Note that p of B given a is a bigram probability, whereas p of by itself is a unique grant probability.
What if I see a three letter word in this case, I can apply the chain rule of probability, which says
that P of ABC is equal to PFC, given a b times of be given a times PRV.
But remember, we are making the mark of assumption, which means that PFC given AB reduces to PFC given
B since we assume that C only depends on the previous letter and not on any letter before that.
So P of ABC as equal to PFC, given b type of be given a times b of a.
Now we have to buy grams and one unit gram.
In general, I can extend this to a word of any length.
So if I have a word of length Big T, then its probability is just a unique grand probability multiplied
by the product of each of the bigram probabilities.
Take a moment to look at this equation and make sure it makes sense.
Notice how the first letter is always represented by a unique grand probability.
That's because there are no previous letters that come before the first letter.
By definition.
And just to be super clear, the unit grand probabilities are only counted from letters that appear
as the first letter of a word.
These are not.
You anagram probabilities in the sense that these letters can appear anywhere in a word.
For all the subsequent letters, we use, their bigram probabilities.
We want to count up from T equals two rather than C equals one.
So that the first bigram probability we have to consider as p of x two given x one.
Finally, let's consider how we would extend this to a sentence which may contain multiple words since
each word is separate.
We can just consider the probability of each word separately and then multiply all those probabilities
together.
So that would give us the equation we see here.
And this notation each W represents one word.
And there are big N words and total indexed by little end.
The N-word has big tea event letters and will use the superscript on X to show which word it belongs
to, the subscript on X still refers to the position of the letter in that word.
So x subscript t superscript n means the position T in the end the word.
One thing you might wonder is we're only considering letters, but don't words also follow a certain
logical sequence.
For example, you wouldn't have a sentence that just says Cat, Cat Cat over and over again.
However, our model doesn't differentiate between a sentence that doesn't make sense, like cat, cat,
cat versus a sentence that actually does make sense, like I like cats in a more advanced model.
You might want to consider a language model over sequences of words alongside sequences of letters,
but you'll see that this actually isn't necessary for our example.
Now that we understand the basic language model, let's discuss some modifications will make in order
to improve how things work.
First, we're going to do something called one smoothing.
This is important.
Consider what would happen if there is some rare bigram that never occurs in our training corpus, but
does occur in the message we are trying to decrypt.
In that case, the probability of that bigram will be measured as zero.
The problem with zeros is that our sentence model is a product of individual probabilities.
And whenever you multiply by zero, the whole thing becomes zero.
That's not good, because it doesn't give us a good indication of whether the sentence as a whole is
probable or not.
The usual approach to fixing this problem is called + one smoothing.
Basically, this gives us a tiny probability of each transition occurring so that even if we encounter
something that never occurred in the training set, it won't make the whole sentence probability zero.
The idea is we want to add one to the numerator and we want to add Big V the total number of letters
in the alphabet to the denominator.
The reason we want to add Big V to the denominator is because of the rule that probabilities must sum
to one.
You can check this for yourself quite easily.
First, we consider the sum over all possible next letters, little we going up from one to big V,
then we replace the probability with the add ones moving expression.
We can see that the denominator doesn't depend on little v so we can pull it outside the sum.
Then we can simplify the terms inside the Sun for the first term.
The count of X of T minus one going to all possible letters is just the number of times X of T minus
one occurred.
For the second term, the sum of one v times is just V.
Therefore, the top is equal to the bottom and the sum is one as expected.
The next thing we have to consider is how do we use this model to actually decrypt the message?
Remember the intuition once we build our model by finding all these probabilities using an English text
corpus, we can then find that the probability of any sequence of letters or sentences.
So let's say I translate the message incorrectly and I get some gibberish output like G B G Q LRP.
This should give me a very low probability because it's not English.
Whereas if I translate the message correctly to I like cats, then I should get a very high probability
because this is correct English.
This is, in other words, like a maximum likelihood problem because we want to find a decoding such
that our output message has the maximum likelihood.
There is one practical consideration we have to make before moving on.
The problem with probabilities and language modeling is that they are very small.
Let's say on average that the probability of a transition is one tenth or zero point one.
I'm not sure how accurate that is, but let's suppose it's true.
What happens if I have a sentence that say 100 characters lower than my probability will be 10 to the
power minus 100, which is a very small number.
These probabilities are generally so small that the computer will just end up rounding them down to
zero.
That's not good because I can't find out which probability is the maximum if they all give me zero.
The solution to this is to take the log likelihood instead of the raw likelihood, since our likelihood
is just the product, the log likelihood becomes a sum due to the multiplication rule for the log function.
Why does this work?
Suppose I take the log of zero point one, then I get minus two point three.
But what if I take the log of a much smaller number?
I still only get minus twenty point seven, even though this number is somewhere around millions or
billions of times smaller than zero point one.
Now you might ask, want this change the answer?
In fact, it won't, because the log is a monotonically increasing function.
Remember that we don't care about the actual likelihood itself.
We only care that our translation is correct.
In other words, I don't want to know the value of the likelihood.
I only want to know which translation gives me the maximum likelihood.
In other words, I only care about their values relative to each other.
You can test this yourself to prove it's correct.
Take any two positive numbers A and B.
You can easily show that if B is greater than a, then log B is also greater than log.
There is no exception to this.
Therefore, if you find the decryption mapping that yields a log likelihood of log B and it's better
than the decryption mapping that yields a log likelihood of log AA, then you can be sure that B is
also greater than A.
All right, so this lecture was quite long, but the concepts are very simple and we can summarize them
concisely.
First, we're going to build a language model using you anagrams and Vikram's at the character level.
We can measure these probabilities using simple counting with add one smoothing.
If you can count, then you can do this.
We can count the letters in some standard English text corpus like Wikipedia or from books.
Then we can apply the intuition that real English sentences should have a higher probability than unreal
English sentences.
Therefore, if our description is correct, the decrypted message should have a higher probability than
an incorrectly decrypted message.