So in this lecture, I'm going to give you an official exercise prompt in order to prepare you for the
next lecture where we look at the code.
So to start, let's go for a basic outline of what the code should look like.
Firstly, you'll want to download.
The data will be using poems by Robert Frost.
Note that the yoro for this text corpus will be given in the coming notebook.
So feel free to grab it from there, but do not cheat by looking at the rest of the code.
The second step will be to read in the data and to use that data to form our second order Markov model.
Remember that there are many ways to do this, although we've spoken about Markov models in terms of
matrices.
The next quote example will allow you to explore another way to do this without using matrices.
So if you'd like to use an umpire raise, you can feel free to do so.
But please be aware that this is not the only way.
The third step is, once you have the Markov model, use the Markov model to generate poems in the coming
example will be generating four lines at a time, but you don't need to follow this constraint.
Now, I want to make note that this exercise is very open-ended.
As mentioned, we'll be using dictionaries to store word probabilities.
So for the rest of this lecture, I want to give you a brief outline of how that will work and why it's
useful.
So suppose I'd like to store the initial word distribution, which we've been calling PI.
In practice, all we really need is a dictionary where the key is the word and the value is the corresponding
probability for that word.
Note that in the coming example, we will not be using AD one smoothing.
So the number of key value pairs in the dictionary is only the number of words that are actually used
in the first line of a poem.
That is, although there may be very possible words in the vocabulary, the dictionary will only store
a subset of those words.
This is opposed to the full PI vector, which always has size V.
Now this brings us to the next important point, which is why might we want to use dictionaries instead
of an umpire raise?
This introduces us to the idea of sparsity.
As you recall, one reason we need to use add one smoothing is because many transitions simply do not
occur in the training corpus.
In fact, this gets worse and worse as the order of the model gets larger.
We refer to this as the curse of dimensionality.
The basic idea is, although the number of values grows exponentially with the number of words in the
sequence, we want to consider the amount of data we actually have gets smaller in comparison.
Put another way, our transition arrays will be mostly zeroes.
So although our second order mark of a ray, technically you should have size v by v by V.
Most of those values will just be zero.
But if we use a dictionary that only stores the words that we have actually seen in a sequence, then
the amount of values we need to store will be much smaller.
OK, so how should we saw the first order transitions, as you recall, these pertain to the second
word in each line.
So for this, what we will use is a dictionary of dictionaries.
Luckily, it's simpler than it sounds.
It helps to just see what it looks like.
So the key in the first dictionary will be the previous word that is the word at time T minus one.
The value this time will not be a probability, but instead another dictionary.
This nested dictionary will also store words as keys.
But this time, these keys correspond to the second word in a two word sequence.
Then the corresponding value will be the probability of that two words sequence occurring, given that
the first word already occurred.
So as an example, the first word here is the and the second word is cat.
This has the corresponding value zero point zero five.
Therefore, we can say that p of cat given there is zero point zero five as an exercise.
I'll leave you to think about how to store the second order transition probabilities using a similar
scheme.
Now, the next issue I want to consider in this lecture is given a dictionary with these word probability
pairs.
How can we sample these words using the corresponding probabilities?
Figuring out how to do this is part of your exercise for this course.
So I'm not going to fully explain how to do it before I show you the solution to the exercise.
What I will give you is the basic principle, which if you follow it, you should be able to implement
this successfully.
OK, so suppose I have three items A, B and C with probabilities zero point two, zero point five and
zero point three.
Now, suppose I draw a random number from the uniform distribution that is a number between a zero and
a one with equal probability for each outcome.
Now suppose that I bucket these outcomes according to the probabilities for A, B and C.
So if the number a sample is between a zero and zero point two, then I will produce an A..
If the number a sample is between 0.2 and 0.7, then I will produce a B. If the number a sample is between
0.7 and one, then I will produce a C.
You can see that that area covered by each of these ranges corresponds exactly to the given probabilities.
One hints that you're being given is that we are computing the cumulative some of these probabilities.
So zero point two is the first probability.
Therefore, that becomes the first boundary, zero point five is the second probability, and we add
that to the first one, which is zero point two.
So in total, we get zero point seven.
Therefore, zero point seven becomes the second boundary.
OK, so hopefully you understand the pattern.
One alternative, but less ideal way to do this exercise is to simply convert the values in the dictionary
into two lists, then use NPD at random, not choice as normal.
I consider this less ideal since it avoids the issue and doesn't give you practice with this kind of
thinking that I would consider crucial for data science.
OK, so please try to exercise and I will see you in the next lecture.