So in this lecture, we will be discussing how a markov model is represented mathematically and by extension
in computer code.
As you recall, the Markov model is used for modeling sequences.
The question is sequences of what?
For the purpose of this section, we will be considering sequences of categorical symbols, which we
will simply call states.
So, for example, if we're modeling the weather, we might have three states sunny, rainy and cloudy.
If we're modeling language, then our states might be parts of speech tags, for example, noun, a
verb, adjective, and so forth.
Okay, so these are examples of states which are categorical symbols.
And by creating a markov model for these symbols, we will have a model for sequences of these states.
In this section, we will use the letter S to mean state.
Note that in other resources you may see other letters being used such as Z or X, depending on the
context.
But in this section we will use the letter s, since that seems to be a neutral symbol.
Now, given this letter s, we can use the notation s of T to mean the state at timestamp t in this
course.
Time will also be discrete.
So we'll have time, step one at time, step two, and so forth.
But we won't have something like time.
Step 1.5.
Okay, so one convention we will use is that we are going to number the states from one up to M where
M is the total number of possible states.
So for the example where the states are a cloudy, rainy and sunny M would be three.
In general, when we want to refer to a specific state, we'll use the letter I or J.
So for example, press of T equals I translates to the probability that the state at time t is equal
to I.
Now, of course, we can have such a probability for all values of AI from one up to m.
This gives us M different probabilities, and together they form a probability distribution.
This distribution has a special name.
We call it the state distribution.
So, for example, the state distribution would answer the question What is the probability that the
weather is rainy on Sunday?
Note that as shorthand we may simply write parts of T to refer to this distribution.
Now, as you recall, Markov models are all about modelling sequences where each state depends only
on the previous state we came from.
So using mathematical symbols we can write p of us of t equals j given as of t minus one equals II.
So what does this mean?
If we translate this into words, it translates to the probability that the state at time t is equal
to j.
Given that the state of time t minus one was equal to.
I note that this is a conditional distribution.
Now, one question we can consider is this How many of these conditional probability values exist?
Well, we must have a value for every possible ie from one up to M and every possible j from one up
to M.
Therefore, we should have m times m values which is m squared.
Now you may have noticed that it's quite tedious to write down PV as a t equals j given as of t minus
one equals II.
In fact, we normally avoid writing this.
Instead, we can simply store all these values in a matrix called a.
We call this the State Transition Matrix.
Our convention is that AJ is equal to the probability that the previous state was I.
And the next state is J.
Thus the first index corresponds to the previous state, and the second index corresponds to the next
state.
And clearly it has the shape M by M.
It has m rows and columns.
Now, you might have noticed something weird about our definition of that.
If we look closely, we can recognize that, in fact, one variable is missing.
The variable that's missing is the time.
T So what happens to t?
So in general, these conditional distributions may change over time.
That is to say they will be functions of T, but for the Markov model, this is usually not the case.
Instead, we will assume that the same probabilities hold for all values of t that is across all time.
When this is true, we say that the Markov process is time homogeneous.
For us, this will always be the case.
Now, although this will not be very useful for us in terms of applying market models.
I thought it was worth mentioning since students often like seeing pictures.
So one way of representing a markov model is with a state transition diagram.
In this type of picture, we have one circle for each possible value of the state.
The arrows represent the probability of transitioning from one state to the next.
So, for example, the probability of it going from sunny to sunny is 0.8.
The probability of going from cloudy to sunny is 0.2.
Note that this diagram assumes that the Markov model is time homogeneous.
Since these probabilities hold, no matter what time step we are at as an exercise, try to figure out
what the state transition matrix for this Markov model would be.
Now, if all we have is the state transition matrix, A is our picture complete?
The answer is no.
You see, A only tells us the probability of moving from one state to the next.
But every sequence starts somewhere, each value, and tells us the probability of going from the previous
state to the next state.
But if we're looking at the very first state in a sequence, there is no previous state.
So for a concrete example of this, just think about a sentence, which is a sequence of words.
Suppose our sentence is the quick brown fox jumps over the lazy dog.
The first word in the sentence is the.
And nothing comes before this word.
To handle this issue, we need to define another distribution called the initial state distribution.
Typically, we use the Greek letter pie to represent this distribution.
So pi a vi z equal to this one equals II.
In this case, we say a sub one.
Because we're assuming that time one is the first time step in the sequence.
Note that since I can take on the values from one up to m pi as a vector of size m.
Okay.
So let's recap what we've learned so far.
We've learned that a markov model is described by two distributions, the state transition matrix A
and the initial state distribution pie.
Given these two objects, we can ask some interesting questions.
Here are two questions we're going to try to answer in this lecture.
The first question is given a and pie and the sequence s of one of two s of t.
What is the probability of this sequence?
And the second question we're going to answer is very practical.
How do we find a n py in the first place as usual?
Because this is machine learning, we'll be given a dataset and using this dataset will determine some
procedure for estimating the best values of and py.
Okay.
So let's start by tackling the first question.
Given a sequence of states in the Markov model, which is an PI, how do we find the probability of
that sequence?
Luckily, we've already discussed this.
In general, we could apply the chain rule of probability, but thanks to the Markov property, this
simplifies to the product of state transitions.
The difference now is that we will be using our new variables in PI to represent our answer.
It's also important at this point to start thinking about how you would do this in a computer.
Inside a computer, a will be a matrix or a 2D array and pi will be a vector or a1d array.
Thus you should consider how you would write some code to carry out this computation.
Multiplying the required components of Pioneer, perhaps in some kind of loop.
Okay.
So the next question we want to answer is how do we train a markov model now to fully derive this rigorously,
take some work.
So for now, we'll only discuss the intuition.
But the intuition is very easy to understand.
In fact, it requires nothing but counting.
So to begin.
Suppose that we flip a coin a bunch of times, which is a sequence of heads and tails.
And we would like to know what is our best guess for the probability of heads?
Well, we all know the answer to this question.
It's the number of heads divided by the total number of coin tosses.
As you recall, this is a binary distribution, also known as a Bernoulli.
But in our case, we can have M greater than two.
For example, each state is a word in the English dictionary.
In this case, the answer is similar.
Suppose that we've taken all of Wikipedia and we would like to know what is our best guess for the probability
of seeing the word cat.
The answer is the number of times the word cat appears divided by the total number of words in the text.
Okay.
So how can we apply this principle to estimating an pi in a mark of model?
Let's start with pie since that's a bit simpler.
Pie a VI is equal to the number of times each sequence started with State I divided by the total number
of sequences in our dataset.
Of course, this requires that our dataset consists of multiple sequences to begin with.
Otherwise our estimate would not be very good.
Okay, so what about AJ?
Our best guess for AJ is the number of times we transition from state AI to state j divided by the total
number of times we were in State II.
Now, just in case this is a bit confusing, let's think of an example.
Suppose that we're working with the English language and each state is a word.
We would like to know what is the probability of seeing the word cat following the word the.
This is simply the number of times we see the sequence the cat divided by the total.
Number of times we see the word the by itself.
Okay.
So let's summarize what we've learned in this lecture since we've covered quite a lot of new content.
In this lecture, we learn that using more generic terms, our job is to model a sequence of states.
Our Markov model is made up of two objects the state transition matrix A and the initial state distribution
pie.
At this point, you know what these probabilities represent.
We also learn how to answer it.
Two important questions concerning Markov models.
The first question we learn to answer is Given a sequence of states and a mark of model, find the probability
of that sequence.
The second question we learn to answer is given a dataset of sequences.
Find the best fitting Markov model, which means find a in pie.
Note that because this is machine learning, we call the process of finding a in pie, the learning
process or the training process.
Now, again, it's always useful to think about how you would implement this in computer code.
So as an exercise, consider thinking about how you would take a bunch of sentences like what you would
find on Wikipedia or your favorite book and compute a pie.
In fact, if you really want to test your understanding, you should write the code to actually do this.