OK, so in this lecture, we will be looking at another application of Markov models.
This time we will be using Markov models to generate text instead of just classifying text.
So one important distinction to make is this when you are classifying text, that's an example of supervised
learning because we're using labeled data to build our model.
In this example, we will be doing unsupervised learning because we will not require labeled text.
Now, one factor that might be interesting to some of you is that when we built our base classifier,
that was an example of what we call a generative model.
In particular, we can split up supervised models into two categories based on the kind of distribution
we learn.
These categories are discriminative and generative at a high level discriminative.
Models learn P of Y given X directly.
That is, there's no need to apply Bayes rule because the model already gives us P of Y given X.
Some examples of this are logistic regression and neural networks.
Generative models are the opposite, as you saw.
This involves learning X given Y and later we find P of Y given X using Bayes rule.
So the reason why this is interesting is because this lecture will help us understand why we call these
generative models in the first place by learning P of X, given Y or, in other words, a model of the
data, we will be able to use that distribution to generate more data.
And because this distribution can be used to generate data, we call it a generative model.
OK, so in order to understand how we can use Markov models to generate data, we need to understand
the concept of sampling most of you taking this course will already know how this works, but I'm going
to review it with you just in case.
So let's consider how we might draw a sample from the normal distribution with mean zero and variance
one.
This is the usual Nampai function and spit out random dot random.
OK, so that's an example of how to sample from a continuous distribution.
What about a discrete distribution?
Well, suppose we'd like to draw a sample from the newly which you can think of like a coin toss.
The result can only be zero or one.
Well, one option is to call out random choice, passing in either a list containing zero and one or
passing in the integer to both will yield the same results.
But what if we have more than two options?
Let's suppose we want to draw the numbers zero up to nine.
In this case, we can still use that random choice again, but passing in a 10 instead.
OK, but these examples are too simplistic because they always assign equal probability to each outcome.
What if we want to Bernoulli where the probability of heads is zero point eight?
In this case, we need to make use of the argument, which allows you to assign a probability to every
possible value.
So in the newly case, we would pass in a list containing zero point two and zero point eight in order
to have the probability of sampling a one be 80 percent.
As you recall, this is exactly what we need to sample words from a distribution of words since we are
storing our words as integers.
So as a simple example, suppose that our vocabulary size is three and it contains the words cat, dog
and mouse.
These have the probabilities zero point two, zero point five and zero point three, respectively.
Then supposing that we know how to map the integers zero, one and two to their corresponding word,
we can just use and put out random choice.
Now, please note that there are many more ways to generate samples from a distribution and even to
store a distribution.
So if you had any other ideas, please feel free to use them instead.
Remember that these exercises are for you to do.
You should really be using these opportunities to explore your coding abilities.
So do not treat my code as the target for what you must do, but simply as an example of what you could
do.
So for this lecture, we will be extending our knowledge of the Markov model just a little bit.
In particular, you've seen so far how we can make the mark of assumption where the current state depends
only on the previous state.
However, that's pretty restrictive.
Consider, for example, these two sentences.
I made myself a peanut butter sandwich and I'll go and see her myself.
Now, suppose that we just generated the word myself and we'd like to now generate the next word.
Well, we can see that a peanut butter sandwich is a feasible continuation of the word myself.
Furthermore, we can see that I'll go and see her myself as a feasible start of a sentence containing
the word myself.
However, we can also see that if we only focus on one word at a time, we could end up generating a
sentence like I'll go and see her myself a peanut butter sandwich.
Of course, this sentence does not make sense.
Now consider the sentence the peanut is not a nut.
Again, suppose we just generated the words I made myself a peanut.
If we only focus on the word peanut.
We can see that it is feasible to end with the other sentence.
But altogether, this sentence does not make sense.
I made myself a peanut is not a nut.
This sentence is incomprehensible.
So here's one way to extend the Markov model instead of only depending on a one pass the state, we
can depend on two past states.
In this context, we referred to the number of past states as the model order.
So a model where the current state depends on two past states is called Second Order Markov, a model
where the current state depends on only one party state is called the First Order markup.
OK, so why would you want to do this?
Well, the hope is that by including more information from the past, we can make better predictions
about the future.
Of course, it remains to be seen whether or not this will help.
As always, the model is machine learning is experimentation, not philosophy.
So it's worth thinking about how we will actually implement a second order Markov model, as you recall,
we need to have a new state transition distribution where the current state depends on the previous
two states.
We can write the says price of T equals K given us of T minus one equals J.
And this of T minus two equals I.
So analogously, with our first order Markov model, we can store this in a three dimensional array
we call a with the subscript i, j and K.
Now here's something that should concern you.
We know that each of the indices I, J and K can take on any of the M states as before.
This means our E matrix will have the shape M by M by M or MQ and by Matrix I really mean a tensor.
So what should be concerning about this is that the size of this tensor seems to grow exponentially
with the number of extra previous terms.
So if you want to add another past state, you'll have to the power four.
If you want to have another past state, you'll have enter the power five and so forth.
Of course, it then becomes infeasible to include it too many past states.
Not only would it be computationally intensive to store in memory, you will reach a point where you
don't even have enough data to estimate the values.
The next thing to discuss is that like the first order Markov model, we still need a first order state
transition matrix.
So just to disambiguate between First Order and Second Order, we'll call the First Order Matrix A1
and we'll call the Second Order Tensor a a.
One will have the indices, I.J and A2 will have the indices IDGC.
And of course, these are both in addition to the initial state distribution pie.
This makes sense since when we want to generate the first word in a sentence, we will use pie.
When we want to generate the second word in a sentence, we will use A1.
Since there is only one previous word after this, we will use A2 since at this point, every word will
be preceded by at least two words.
However, note that this version of A1 is not like the transition matrix in a first order Markov model.
This is because A1 is only being used as a model for the second word in a sentence.
Not any word after that.
I also want to do a little preview at this point, which is to think about this in the context of neural
networks.
What you will learn when you study deep learning is that firstly, there is no need to make the mark
of assumption.
But furthermore, almost magically, there is essentially no increase in computational cost.
When you add more previous words now, this is not quite accurate, since the increase will depend on
the type of neural network you use.
But for the purpose of this discussion, you can think of it as linear.
Either way, it's still much more efficient than exponential as we've seen when we do naive accounting,
and we try to measure each probability value one by one.
There is an exponential growth in the computational cost.
So it's a good exercise to think about what is a neural network actually doing that allows this to happen.