So in this lecture, we will be discussing the mark of property, which is the essential ingredient
that we need for the Markov model.
So what is the mark of property?
Well, in order to understand the mark of property, we need to discuss what are we normally trying
to do in machine learning when we have a sequence?
As you recall, a sequence can be any ordered list of values or symbols, like a time series or a sentence,
which is a sequence of words.
So one common and intuitive thing to do is to ask What is the probability of a sequence that is given
a sequence X1 up to x t?
What is the probability of seeing x one up to 60?
Using this, we can do all sorts of useful things.
For example, if we only know the values from x one up to x t minus one, we can ask the question What
is the distribution of X of T given all the previous values?
This is useful if you want to forecast the next value in a time series or predicts the next word in
a sentence.
So the mark of property is a very restrictive assumption on the dependency structure of the joint probability
distribution.
Basically, it says that each symbol X of T depends only on the symbol at the previous time Step X of
T minus one.
It does not depend on X of T minus two x of T minus three or any other X in the past or in the future.
OK, so x of T depends only on one thing, and that's the X at the preceding timestamp.
So what does this mean in terms of our joint probability distribution?
Well, it means that the distribution of X one up to X T is equal to a p of X one times B of X to give
an x one times p of x three given x two and so on, up to T given x t minus y.
Note that the first symbol of one is not conditioned on anything since we're assuming nothing comes
before X1.
So here's another way to write the markoff property.
We start with the general form on the left, where we have X of T given X of T minus one X of C minus
two all the way down to X of one.
This is equal to X of T given X of T minus one only.
And this is if the of property is true.
Another way of saying this is X of T is independent of X of T minus two x of T minus three and so forth.
Another interesting question we can ask is what if the markoff property was not true in this case,
we can still factor out the joint distribution.
It just doesn't look as nice as it did in the markoff case.
To see how we can do this, it helps to start with a simple example with just two variables x one,
an x two.
In this case, we can say p of x one and X two is equal to one times Pivac's to give an x one, as you
recall.
This is just Bayes rule or the rule of conditional probability.
Now, what if we have three variables x one next to an X three?
In this case, we can still do the same thing.
We can start by saying p of X one and X two and X three is equal to one times p of x two x three given
x one.
Of course, the next thing to do is to split up the X two x three term, which gives us P of X to give
an X one times B of x three given x one.
And next to this is just the application of Bayes rule once again.
So in general, this is called the chain rule of probability.
Essentially, what we do is repeatedly split up the distribution, starting with X one, then X to the
next three and so forth.
And each time we split up the distribution, the next symbol depends on more and more passed symbols.
So you see, we've kind of learned about the mark of property backwards.
In fact, what you are seeing here is the most general form.
But if we assume that the mark of property is true, then this simplifies, since each X term does not
depend on any other X terms, except of the immediate preceding term.
So now that you know what the mark of property is, let's think about why it's useful.
So imagine that we would like to build a model of the English language.
Suppose that in our model we consider the most commonly used English words, which number around two
thousand.
Now, suppose that we would like to build a probability distribution for the tenth word in a sentence,
given the previous nine words.
So this distribution has 10 variables in total x one x two all the way up to ten.
But each of these ten variables has two thousand possible values.
So what is the total dimensionality of this distribution?
Well, it's two thousand times two thousand times two thousand and so on.
Ten times.
As you can imagine, this is a pretty large number.
As an exercise, you may want to try to calculate how large this number is.
So what's the problem with this being such a large number?
Well, this is the number of probabilities that we have to estimate.
In order to estimate all these numbers, we must have a sufficient amount of data to learn from as another
bonus exercise, consider whether or not a sufficient amount of data actually exists.
Now we often call them Mark Property, the mark of assumption.
This is because we often assume that the mark of property holds, even when we know it does not.
For example, with language, it's pretty obvious that the next word in a sentence doesn't only depend
on the preceding word.
Consider the following two sentences I like Green Eggs and Ham, and I like to code in C++ and Python.
If the mark of property were true, this is saying that the words ham and python only depend on the
word end.
But clearly, this is not true.
We can see that the word ham becomes more likely because Green Eggs appeared earlier in the sentence.
We can also see that the word python becomes more likely because code in C++ appeared earlier in the
other sentence.
So using this simple example, it is clear that the mark of property does not hold for language, even
though this is a very popular use case of Markov chains.
However, there is a popular quote in statistics that helps to shed some light on this issue.
The famous statistician George Box, once said all models are wrong, but some are useful.
That is, we know that the mark of assumption is wrong, but despite this, it still turns out to be
useful anyway.
As mentioned, it's been successfully applied in language finance, reinforcement learning and biological
sequence analysis.
So although the mark of assumption appears to be very restrictive, it is still useful in the real world.