The next step is to create a function that will sample a word, given a dictionary of probabilities.
As you recall, from what we just did, this dictionary will be structured as follows.
The key will be each possible word and the value will be its corresponding probability.
As mentioned earlier, understanding this is one of the main goals of this exercise.
So do your best to implement this function yourself.
Furthermore, as you recall, there are various ways to implement this, but using the method I'm about
to show you makes use of first principles.
All you really have to understand in order to understand this is the picture we drew earlier.
OK, so as mentioned, the first step is to draw a sample from the uniform distribution.
We'll call this P0.
This will be a number between zero and one.
The next step is to create a variable called cumulative, which will store the cumulative sum of the
probabilities we encounter in the dictionary.
The next step is to live through each item in the dictionary.
So again, he is the token we might sample and pose its corresponding probability.
Inside the loop, we will first increment the cumulative sum by PEA, the next step is to check whether
P0 is less than the current cumulative sum.
If it is, we should return the current token tea again and draw a picture to convince yourself that
this works and follows the process we described earlier.
As a final sanity check note that we have an a circle outside the loop since our function should always
return a sample, we should never reach this line.
If we do reach this line, then our program will raise an exception and we'll know that we've done something
incorrect.
Now that we know how to sample a single word from a probability dictionary, the next step is to implement
a function to generate poems.
This function will generate four lines of a poem at a time.
So we start by answering a loop that runs four times inside the loop.
Well, initialize an empty list called sentence, which will store the tokens we generate.
The first step will be to generate the initial word since our dictionary called initial is already a
word probability dictionary, we can pass this into the sample word function we'll call the result zero.
The next step is to append W0 to our sentence list.
The next step is to sample the second word in our sentence.
As you recall, this should make use of our dictionary called First Order.
Now we want this to depend on the first word we generated, so we'll index First Order using zero.
This will again give us back a probability dictionary.
We can then pass this into our simple word function once again.
This will give us the second word in the sentence, which we will call W1.
The next step is to then appended W1 to our sentence list.
In the next block of code, we will continue to generate new words until we reach the special end token.
So we'll begin by entering an infinite loop inside a loop, we will use our second order dictionary
indexed by zero and one.
As you recall, the keys to this dictionary are two pools of two previous words.
Again, this gives us back a probability dictionary, which we can then pass into the sample word function.
We'll call the result W2.
The next step is to check whether or not W2 is equal to our fake and the token.
If it is, we don't want to print this out, but simply ends the loop by calling break.
Otherwise, if W2 is a real word, we will append W2 to our sentence list.
The final step in this loop is to update the variables zero and W1 one, which represent the most recent
previous two words in our sentence.
Once we are outside the loop, we have finished generating one line of a poem.
At this point, we print the line by joining the tokens into a single string.
OK, so the next step is to actually try our function.
So let's run this.
OK, so here's the first verse of our poem I went to bed alone and left me might just as empty, but
it isn't as if and that's not all the money goes so fast you couldn't call it living for.
It ain't OK.
So I think that's a pretty convincing poem.
Let's try this again.
One level higher than the Earth.
She has her spiel on every single lizard with whose vast wheels?
It's to say.
OK, so let's try this one more time.
I know up to pass a winter eve to make them out, and then someone actually, let's try this one more
time.
It's a, you know, a person so related to herself.
You take the polish off the ground.
No, I don't follow you in leaves.
No step had trodden black.
OK, so I think in most of these cases, the poems that were generated have been pretty convincing.
So the last thing I want to mention in this lecture is an optional exercise.
Recall that one advantage of storing our probability arrays as dictionaries is that they take advantage
of sparsity.
We know that there will be lots of zeros.
Recall that zero probability means something which is impossible, but for dictionaries, we don't have
to store any impossible transitions.
And thus, there are no zeros since we already know that any value which does not exist in the dictionary
has zero probability.
Thus, storing things this way is possibly more space efficient.
So let's suppose that we call our vocabulary size V.
We know that PI should be a 1D array of size v.
We know that A1 should be a 2D array of size V by V and A2 should be a 3D array of size, V by V by
V.
And this is the case whether they contain mostly zeros or not.
We call this a dense representation.
So your exercises this firstly determine the vocabulary size, which is V, then add up all the probability
values we actually stored in our three dictionaries above.
Then compare what we actually stored to what we would have stored.
How do we use full dense arrays?
It would be best to express these as a percentage.
So, for example, you could say for a two, only two percent of the possible 1000000 values were stored.
Also, as a bonus note for this lecture, notice another advantage of using dictionaries.
One of the more tedious parts of doing an LP is that we have to keep converting back and forth between
integer and text representation.
But since the key to a dictionary can be any kind of object, there's no need to convert our text into
integers first.
Therefore, there's no need to maintain a word to index dictionary, and we can simply use the words
themselves for the entire script.
All right, so there's just one more exercise I want to mention before we end this lecture.
As you've seen, we use two different strategies to build our probability dictionaries, in particular
for the initial state distribution.
We created a dictionary of counts directly.
We accumulated the counts as we traverse the dataset.
But for the First Order and Second Order models, we did something else for these.
We simply collected all the possible next words in a list only after we finished looping through the
whole dataset.
Did we convert them into dictionaries of counts.
However, note that this was not necessary.
We could have just created the dictionaries of accounts directly here as well.
So your exercises this modify this code so that we no longer need to collect each possible next word
in a list.
What you should end up with is that there is no longer any need for the list to predict function.
So please try these exercises and I'll see you in the next lecture.