Markov Chains

Loading...

From the course by National Research University Higher School of Economics

Bayesian Methods for Machine Learning

345 ratings

National Research University Higher School of Economics

Bayesian Methods for Machine Learning

345 ratings

Course 3 of 7 in the Specialization Advanced Machine Learning

People apply Bayesian methods in many areas: from game development to drug discovery. They give superpowers to many machine learning algorithms: handling missing data, extracting much more information from small datasets. Bayesian methods also allow us to estimate uncertainty in predictions, which is a desirable feature for fields like medicine. When applied to deep learning, Bayesian methods allow you to compress your models a hundred folds, and automatically tune hyperparameters, saving your time and money. In six weeks we will discuss the basics of Bayesian methods: from how to define a probabilistic model to how to make predictions from it. We will see how one can automate this workflow and how to speed it up using some advanced techniques. We will also see applications of Bayesian methods to deep learning and how to generate new images with it. We will see how new drugs that cure severe diseases be found with Bayesian methods.

From the lesson

Markov chain Monte Carlo

This week we will learn how to approximate training and inference with sampling and how to sample from complicated distributions. This will allow us to build simple method to deal with LDA and with Bayesian Neural Networks — Neural Networks which weights are random variables themselves and instead of training (finding the best value for the weights) we will sample from the posterior distributions on weights.

Monte Carlo estimation12:46

Sampling from 1-d distributions13:29

Markov Chains13:07

Gibbs sampling12:31

Example of Gibbs sampling7:54

Metropolis-Hastings8:17

Metropolis-Hastings: choosing the critic8:42

Example of Metropolis-Hastings9:56

Markov Chain Monte Carlo summary8:50

MCMC for LDA15:22

Bayesian Neural Networks11:05

Meet the Instructors

Daniil Polykovskiy
Researcher
HSE Faculty of Computer Science
Alexander Novikov
Researcher
HSE Faculty of Computer Science

[MUSIC]

In the previous videos we familiarised ourself with the Monte Carlo part.

So now, let's talk about the Markov Chain part.

Which is actually really cool idea on how to generate samples from

complicated multi-dimensional distributions efficiently.

So what is a Markov chain?

Imagine a frog which sits on a water lily.

And this frog has kind of a discrete time.

So at each time stamp, at each second, for example, it makes a decision,

whether to stay on its current lily or to jump to the other one.

And its decisions are kind of prefined in probabilistic way.

So if it's right now on the left water lily,

it will stay there with probability 0.3, and it will move with probability 0.7.

And if it's on the right one, it will stay or move of probability 0.5.

For example,

now we can say that we have kind of a dynamic system which has a state.

So the state will show us where the frog is now.

This dynamic system, it kind of evolves for time, its states changes.

And the rules by which these states changes are as follows.

So the probability to transition from left state to left state is 0.3 and etc.

So you can define the behavior of your dynamic system by using these transition

probabilities.

So we can simulate our dynamic system.

We can see that, for example, on the timestamp 1, the frog was on the left,

and then maybe jumped to the right on the timestamp 2.

And then maybe it stayed to the right.

Then maybe it went to the left, and then, for example, to the right.

And we can write down the path through the state space which our dynamic system made.

So it was left, right, right, left, right.

And this thing is called Markov chain because the next

state is kind of depends only on the previous state.

So the frog doesn't care where it was ten time steps ago,

the only thing it cares about is where it is now.

To make the decision, it just needs to know what is the state now.

Okay, so we can ask ourselves a question.

Like where the frog will be after 10 timestamps for example.

So let's say that we started from the timestamp 1, and the frog was on the left.

So with probability 1, it was on the left.

With probability 0, it was on the right.

What is the probability that will be on the left or

on the right in the timestamp 2?

Well, it's 0.3 and 0.7, right?

Okay, and what about the timestamp 3?

It's going to trigger because we don't know where it was before.

But using the rule of some of probabilities we can kind of check all

the possibilities for the previous state and

use that to compute the next probabilities.

So the law of some tells us that the value of the state of the timestamp

3 equals to the value of the state of the timestamp 3,

given that at the second timestamp it was on the left,

times the probability it was on the left on the second timestamp.

Plus the same thing, considering that the station,

it was on the right on the second timestamp.

And we can just, we know all these values because the conditional

probability is just the transition probability.

So the probability that the frog moves from left to right for example,

and the probability of x2 are computed in the previous line,

so it is what we have just computed.

And we can write it down, so it will be for probability of the left,

in the third timestamp.

It will be something like 0.3 because it's

the probability of transitioning from left to left,

hence the probability of 0.3.

So it's from the previous line of the table.

Plus the probability of the prior probability of being

on the right hand side of the previous timestamp,

which is 0.7 times the transition probability

of moving from right of, right to right, which is 0.5.

I'm sorry, from right to left which is 0.5.

And we can write the same thing for the for

being at the right state, in the timestamp 3, and

we'll have some numbers like is which are around 44 and 56.

And we can continue this table, for as long as we want.

And we'll found out that the table kind of

converged the numbers around 42 and 58.

So after 1 million steps,

the probability is that the frog is on the left is almost exactly 42.

And the probability that the frog is on the right is almost exactly 58.

Which basically means that we, if we stimulate our frog for long enough and

then write down where it ended up with the one millionth step.

Then we will kind of get a sample from this discreet distribution of the values.

So with probability 42 we'll get left, and with probability 58 we'll get right.

So let's look how it works.

Say we select our frog for like 1 million steps,

and the last step was for example left, okay?

We write down this left and then simulate another [INAUDIBLE] for the state space.

So begin simulation and the last state was for example right.

We are the down and by then phase several types.

We have a sample from distribution of the millionth step of

our dynamic system given that the frog started on the left.

And this thing will be close the probability 42 and 58.

So even here we can see that we have two out of five lefts,

and three out of five rights, which are close to 42 and 58.

So this way we can generate, it's a really lousy way to

generate samples from this distribution with the radius.

So there's a much simpler way which we have just discussed in the previous video.

But note that this way, so, build a dynamic system and simulate it and

see where it end up, works even for more complicated cases.

So what if you have for example ten lilies?

Or 1 billion lilies?

If you want to simulate your distribution by in naive way.

If you have billion values for in your variable, you'll have to spend

amount of time proportional to 1 billion to generate one sample from it.

If you use this kind of idea of simulate some dynamic system and

then write down the last position.

And if you do not that many steps like 1000 and hope that everything has

converged to the true distribution, then you can get a random number from this.

Complicated distribution without much trouble too much trouble

of the naive approach the example.

Or maybe a frog can be continuous, and

can jump from any point on your 2D plane to any other point.

In this case, you will be able to generate your samples from

a continuous distribution by simulating your dynamic system.

So the reason that you can still sample efficiently,

even if you have this continuous dynamic system,

by just writing down the path of this 2D plane, and writing down the last position.

So the idea Markov Chain simulation applied

to generating samples of random values is as follows.

We have a distribution we want to sample from.

It may be continuous, it may be discrete.

We build a Markov Chain that has this distribution,

that converges to this distribution, okay?

Then we start with from a initialization, x0, and then we simulate

our Markov Chain for long enough, for example for 1,000 iterations.

[COUGH] So we start with x0 then we generate x1,

by using the transition probability and etc.

And then we hope that after 1,000 steps,

you will converge to the true distribution p(x).

Because we built our Markov Chain this way.

Then, after these 1,000 steps,

you can throw away the first 1,000 samples, 1,000 states.

And then you can start writing down the states after these 1,000 steps.

Because they all will be from the distribution p(x),

or at least close to it, if your Markov Chain converged close enough.

Okay, so this is the general idea.

And in the following we'll discuss how to build Markov Chain with this property.

So how to build Markov Chain that converge to the distribution you want to

sample from.

Now let's first discuss a little bit about whether a Markov Chain converge anywhere.

So in which case it does converge, and which it doesn't.

Well, the first observation here is that the Markov chain doesn't

have to converge to anywhere.

So for example, if you take a dynamic system like this,

the frog will always swap the lily at each time stamp.

And so if you look at the table, it will look like this.

The permute of being on the left on the first time step was 1 and

the p on the right is 0.

And then you swap things, so you're will be on the right on the next time stamp and

you will certainly be on the left on the next time stamp, and etc.

This thing will never converge this table.

So it will always swap if the place.

So this thing does work for us.

We want something that converge to some distribution.

And the question of whether or not given a Markov chain is converged,

is converging to something, is actually, pretty well studied.

But first of all, we'll need a definition of what does it mean for

Markov chain to converge to something in mathematical terms?

So this is something called a stationary distribution.

And this is a distribution of pi called stationary for

Markov chain T If the following equation holds.

Which basically tells us that if you start the distribution y and

if you marginalize out the current position x, then you will get

basically the distribution over position on the next time stamp.

This has to be pi again.

So basically, if you start from pi, if you sample a state from pi,

and then if you make just one transition, so one timestamp of the Markov chain,

then the distribution you will get after that is, again, pi.

This means that if we converge to, if we encounter this

pi at any point of our sampling, then we will stay at it.

We will not change this distribution.

And there is a nice theorem that tells us that If the transition probability

is non-zero for any two states, so if we can jump from any state to any other one,

with non-zero probability, then there exists a unique pi which is stationary.

And we will converge to this pi from any starting point.

So if we build a Markov chain that has non-zero transition probabilities,

and that has a stationary distribution which we

want sample from, then no matter where we start,

if we simulate our Markov chain long enough,

we will get eventually samples from the desired distribution y, [SOUND]

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.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play