Probabilistic graphical models (PGMs) are a rich framework for encoding probability distributions over complex domains: joint (multivariate) distributions over large numbers of random variables that interact with each other. These representations sit at the intersection of statistics and computer science, relying on concepts from probability theory, graph algorithms, machine learning, and more. They are the basis for the state-of-the-art methods in a wide variety of applications, such as medical diagnosis, image understanding, speech recognition, natural language processing, and many, many more. They are also a foundational tool in formulating many machine learning problems. This course is the second in a sequence of three. Following the first course, which focused on representation, this course addresses the question of probabilistic inference: how a PGM can be used to answer questions. Even though a PGM generally describes a very high dimensional distribution, its structure is designed so as to allow questions to be answered efficiently. The course presents both exact and approximate algorithms for different types of inference tasks, and discusses where each could best be applied. The (highly recommended) honors track contains two hands-on programming assignments, in which key routines of the most commonly used exact and approximate algorithms are implemented and applied to a real-world problem.
Markov Chain Monte Carlo
Loading...
From the course by Stanford University
Probabilistic Graphical Models 2: Inference
268 ratings
From the lesson
Sampling Methods
In this module, we discuss a class of algorithms that uses random sampling to provide approximate answers to conditional probability queries. Most commonly used among these is the class of Markov Chain Monte Carlo (MCMC) algorithms, which includes the simple Gibbs sampling algorithm, as well as a family of methods known as Metropolis-Hastings.
Meet the Instructors
Daphne KollerProfessor
School of Engineering
One of the most generally useful class of sampling methods one that's very commonly
used in practice is the class of Markov Chain Monte Carlo methods.
And those are methods that allows us to design an intuitive sampling process that
through a sequence of steps allows us to generate a sample from a desired target
distribution that might be intractable to sample from directly.
So what are these Markov chains and how do you use them.
So, a Markov Chain is a, is a method for
sampling from a distribution p that is intractable to sample from.
And so we see one example of such a distribution p.
if you'd like to sample from a from say Bayesian network.
Where we have some evidence. We don't really know how to sample from
that. If you'd like to sample from a Markov
network, we don't really know how to sample from that either, in general.
And so here we have examples of distributions p.
And we'd like to come up with a way of generating even one sample from that
distribution p. So mark up chain gives us a general
mechanism for doing that. And what the Markov Chain does is it
defines an iterative process by which the first sample that you generate is not
going to be from a distribution p but ultimately, as you move along,
you are going to get closer and closer to generating a sample from p.
So, so let's understand what that what that means so we have a Markov chain, and
a Markov chain is defined over a state space which we are going to use x's to
denote. And so here is an example of such a state
space. This is a very simple state space, it
starts with the zero point over here and you can imagine, and it has, I, the, four
negitive numbers to the left and four positive numbers to the left.
And a Markov chain defines a probabilistic transition model which,
given that I'm at a given state, x tells me how likely I am to transition to a
different state, x prime. And that is a probability distribution as
indicated in this formula here. So that's for any x, the probability, the
sum over the probability over the states you can transition is exactly one.
So for example if in this case we have our little grass, grasshopper that starts
out at state zero. We can see that it has a probability of
0.25 of transitioning to the right. A probability of 0.25 of transitioning to
the left. And a probability of 0.5 of not making
any progress and staying exactly where it is.
And in fact that same general probability distribution is actually in this example
replicated across the different states in the chain, with the exception of the
states at the end, where if the poor grasshopper tries to go to the left when
it's at negative four, it's going to hit the wall and it's going to end up staying
where it is regardless. And so the probability in this case of
staying is actually 0.75, corresponding to the two different cases that we just
talked about. But anyway, this is a Markov chain, and
it and you can imagine. Simulating a random process by which a
grasshopper traverses this chain. And so, initially, it starts out with at
say, at state zero. And then
and then, what happens, as. And then, as it moves, it selects to move
left with probability of quarter. Right with probability of quarter.
And and stay at the same place with probability 0.5.
Once the states move to the left, it now does exactly the same thing.
So let's think about the temporal dynamics of this type of process.
We can ask what is the probability that a time, that it's step t + 1 so this is the
step. what is the probability that at that
time-step the state, at time t1, + 1 is equal to some value x fine.
So we can get that by a recurrence relationship that looks at the state of
time T. So if we had previously computed the
probability distribution over where the grasshopper might be at time T.
We can sum up over all possible states where x, where the grasshopper might be
and ask if it was at state x at time t, what is the probability that it ends up
at being that it ends up going to x prime.
So this together gives me a distribution over pairs.
X comma X prime, where this, which, which measures the propability that at time, t
grasshopper is at state X and the T plus one is at X prime, and since I'm only
interested now in asking about T plus one, I sum up, or marginalize the time T
step, state X. So if we go back to our grasshopper
example, we can simulate this process. And here is the first three steps of it.
So at time zero, the grasshopper is at state zero with a probability of one.
At time one, it's going to be at negative one with a probability of a quarter and
it's positive one with a probability of a quarter, probability half it's stuck at
the same state. And now we can simulate the next step.
So, it's, at the next time step, the probability that it moves, manages to
move, all the way to -2 is 0.25 squared, because it considers two successful moves
to the left. Here you have two successful moves to the
right. At stage zero you have, for example, a
sum of different events, which is the probability that it stayed in the same
state twice. So.5 squared.
Plus the two events that correspond to moving to the left once and back to the
right, or moving to the right and back to the left, each of which happens with
probability 25^2.. So this is an example of how you would do
this. Now it turns out from many of these
chains and we'll describe conditions in a moment ultimately as the process evolves,
the probability distribution kind of equalizes which means that the
probability for the time t your at state x prime is almost the same as the
probability that at time t + one you're at x prime.
So sort of it kind of the distribution over where you might be tends to
equalize. And and so, we can then consider what's
called the limiting process, the limiting distribution that you would get as you
simulate the process for more and more steps.
And that is typically denoted by pie, which is called the stationary
distribution. It also has a bunch of other names.
But, stationary is the most common. And if you plugin.
You see, basically take out this approximate equality.
And you can see that what we have is a condition on Pi.
Is that the distribution of ti, at one time step is the needs to be at, the, the
probability of X prime in the stationary distribution needs to be equal to this
summation over here. Where Pi now appears both in the left
hand side and within the summation on the right hand side.
Now it turns out that this concept of the stationary distribution is actually at
the heart of Google's page rank algorithm.
So what they're actually computing. At least in the original page rank.
Is the probability that if you take a random walk on the web that you end up on
a particular website. So this notion of a stationary
distribution is actually quite powerful. As we've seen.
So, lets take a simple example, which is the three state mark off chain shown
here. So for example note that from state one
there's a probabliity of 0.75 of going to state two and a 0.25 of going to, staying
in the same state. And we can now write down a set of
equations that represent what the fix what property the fix distributions needs
to satisfy. And if you do that you're going to get
the following equations. So for example it tells me that pi of x1
has to be equal to 0.25 times pi of x1, because of the self transition here plus
oops zero point, yes, sorry.
pi of x1 is equal to 0.25 times pi of x1 + 0.5 times pi of x3,
okay? Because there, if you were at pi that,
you can end up in x1 in one of two ways. Either by starting out on x1 and staying
there, or by starting out at x3 and moving to x1 which happens with
probability 0.5. Similarly, pi is X two, you can end up
either by being at x2 and staying there, which is this transition or by being at
x3 and moving to x2 which happens with probability 0.5.
And so this is a set of three simultaneous equations and three
variables. this by itself is an underdetermined
system because you could multiply all of the pis by a factor of 100 and it would
still be a solution. But we can add to that the one constraint
that says that all of the pis have to be equal.
The sum of all of the pis has to be one, which is because it's a probability
distribution. And once you do that you end up with a
unique solution to the system of linear equations.
And it's not difficult to plug those pis into the system and confirm that indeed
this is the stationary distribution that satisfies these equations.
By the way, for the grasshopper example that we showed on the previous slide.
The stationary distribution is the uniformed distribution.
so this has to be one of the dumbest way of generated a sample from the uniform
distribution. But it does in fact generate eventually a
sample from something that's very closely uniformed distribution.
So, when does a Markov Chain converge into a stationary distribution, and I
said many of them do but it turns out that not all of them, and so a condition
that guarantees convergence to a stationary distribution is something
called regularity, so a Markov Chain is regular if the following condition holds.
And notice the order of the quantifiers. If there exists found number k, integer k
such that for every pair of states. So this is the universal quantifier.
The probability of getting from x to x prime in exactly k steps is greater zero.
Now, notice what that means. It means that you pick the K first.
And only, so you can't have a different K for different pairs of states.
You can pick K to be 1000, a million. It doesn't matter for this purpose.
But you need to pick it first and then there needs to be a way of getting from X
to x primes in exactly that number of steps, with probability greater than
zero. It turns out that is a sufficient not a
necessary but a sufficient condition to guarantee that the Markov chain converges
to a unique stationary distribution regardless of a starts date.
So it converges and it converges to a single stationary distribution that's
characterized by the equations that we saw on the previous line.
Now what are some sufficient conditions for regularity because this one is a
little bit hard to check. and so one sufficient condition for
regularity that people often use in practice is first that every pair of
states, x and x prime need to be connected with a path of probability
greater than one. Sorry with a probability greater than
zero. And, for every state there's a self
transition. So you can always transition from a state
to a self. So if you think about that, that means
that if you take K to be the diameter of this graph.
So if you set K to be the the distance between the furthest.
Pair of states. Then, you can get, between every pair of
states, using exactly k steps. Because you can take less than k, and
then just stick around for a while until you hit k, because of the self
transitions. So this is a way of guaranteeing that,
That, for this value k, you can get from every state to every state.
And that's what people typically do. They typically add these self transitions
to guarantee regularity. So to summarize, we've defined a notion
of a mark up chain. Which defines a general dynamical system,
or an iterative sampling process, from which we can sample trajectories that
traverse the space of the chain. Under certain conditions, such as the
regularity condition that we defined. Which is sufficient, although not
necessary. This iterative sampling process is
guaranteed to converge to a stationary distribution at at the limit.
That is, after we generate enough samples.
And so this provides us with a general approach to sample from a distribution
indirectly. Which means that if we have a
distribution from which it's intractable to sample this provides us with an
alternative mechanism.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
