1
00:00:00,000 --> 00:00:04,064
We previously defined the notion of a
Markov chain that allows us to generate

2
00:00:04,064 --> 00:00:09,041
samples from an intractable distribution,
but we left unanswered the question of,

3
00:00:09,041 --> 00:00:14,023
assuming we have a Markov chain that has
the desired stationary distribution, how

4
00:00:14,023 --> 00:00:19,024
do we go about using it, in the context of
concrete algorithmic procedure? Well let's

5
00:00:19,024 --> 00:00:25,037
imagine that somebody has provided us a
Markov chain. For a, a distribution.

6
00:00:25,037 --> 00:00:33,041
Sorry. Imagine that our goal is to compute
some probability relative to a

7
00:00:33,041 --> 00:00:40,097
distribution P. But, for whatever reason,
P is to hard to sample from directly. And

8
00:00:40,097 --> 00:00:46,099
so how do I, use the Markov chain to get
around that? First we construct the Markov

9
00:00:46,099 --> 00:00:52,057
chain P, whose unique stationary
distribution is P, so, so it needs to be a

10
00:00:52,057 --> 00:00:58,045
regular Markov chain usually. And then
we're going to generate samples from this

11
00:00:58,045 --> 00:01:04,056
distribution. So we're going to start off
by sampling my initial state from some

12
00:01:04,056 --> 00:01:10,064
arbitrary distribution p0. P0 is not the
same as p. So obviously I can't use the

13
00:01:10,064 --> 00:01:16,085
zero sample as a way of estimating an
event relative to p. And so what I do now,

14
00:01:16,085 --> 00:01:23,037
start walking along the chain starting
sampling x(t+1) from the transition

15
00:01:23,037 --> 00:01:29,050
model. And because the chain convergence
to stationary distribution, eventually

16
00:01:29,050 --> 00:01:35,065
I'll have a sample that is very close to,
to the to being sample from the

17
00:01:35,065 --> 00:01:43,032
distribution p that I care about. So now
here's the sticky issue, and this is

18
00:01:43,032 --> 00:01:50,079
really a sticky issue. When have we walked
long enough that we could actually use our

19
00:01:50,079 --> 00:01:57,033
samples? Because we don't want these
samples at the beginning because they're

20
00:01:57,033 --> 00:02:04,038
far from P, and so we need to walk around
long enough for the chain to get close to

21
00:02:04,038 --> 00:02:10,091
its stationary distribution. And that
state is called mixing. So mix is when P

22
00:02:10,091 --> 00:02:20,081
of P is close enough [to] Pi. So that your
time t distribution is close enough to the

23
00:02:20,081 --> 00:02:25,043
stationary. That's the point where I can
say, good enough, I can start collecting

24
00:02:25,043 --> 00:02:33,098
samples. So how do we know if a chain has
mixed or not? And the short answer is, you

25
00:02:33,098 --> 00:02:40,093
don't. And so this is, as I said, the
sticky part of a Markov chain method. So,

26
00:02:40,093 --> 00:02:47,044
in general, you can never really prove
that a chain has mixed. But, in some

27
00:02:47,044 --> 00:02:53,047
cases, you can show that is hasn't mixed.
And then, if you run lots and lots of

28
00:02:53,047 --> 00:02:59,006
tests, and none of them have convinced you
that the chain hasn't mixed, then you sort

29
00:02:59,006 --> 00:03:03,086
of resign yourself to assuming that it
has, in fact, mixed. But how do you

30
00:03:03,086 --> 00:03:08,099
convince yourself that a chain hasn't
mixed? You compute chain statistics, and

31
00:03:08,099 --> 00:03:13,099
we'll show some examples of that in a
moment, in different windows within a

32
00:03:13,099 --> 00:03:19,090
single run of the chain. So, for example,
here I have a single run of the chain. And

33
00:03:19,090 --> 00:03:28,054
they run for a while. And than I look at
little windows, usually they won?t be this

34
00:03:28,054 --> 00:03:34,037
small and I compare this window. To this
window, computing various statistics. For

35
00:03:34,037 --> 00:03:39,065
example, what is the probability of
hitting a particular state? And I say, is

36
00:03:39,065 --> 00:03:45,029
the probability of that in this window,
close to the probability of that in this

37
00:03:45,029 --> 00:03:50,030
window? And if it is, then maybe I've
reached this, at least some kind of

38
00:03:50,030 --> 00:03:57,005
convergence point. In terms of where the
chain is reached. Now this of course is

39
00:03:57,005 --> 00:04:04,031
not a sufficiently good answer because it
could also be derived in a chain that has

40
00:04:04,031 --> 00:04:11,027
these sort of two very high probability
regions. That are very hard to get from

41
00:04:11,027 --> 00:04:19,036
each other. And if the chain is kind of
ambling along in this part of the space

42
00:04:19,036 --> 00:04:24,050
and never hitting the other part of the
space, then you're still going to get very

43
00:04:24,050 --> 00:04:29,089
similar probabilities across a window of a
single run of the chain because all of the

44
00:04:29,089 --> 00:04:35,015
samples are taken from this part and none
of them are ever taken from that part and

45
00:04:35,015 --> 00:04:40,067
so we don't know that we haven't mixed.
So, a more reliable statistic, is to take

46
00:04:40,067 --> 00:04:45,083
these statis-, a more reliable evaluation
criterion is to take these statistics

47
00:04:45,083 --> 00:04:51,032
across different runs that are initialized
in different parts of the space. And then

48
00:04:51,032 --> 00:04:55,076
you might hope that one chain is
traversing, one run of the chain is

49
00:04:55,076 --> 00:05:01,012
traversing this region. And another run of
the chain is traversing this region. And

50
00:05:01,012 --> 00:05:06,002
so now, if the statistics, so now the
statistics would show a difference, and

51
00:05:06,002 --> 00:05:12,059
indicate that mixing hasn't taken place.
So, what statistics might, So how, what

52
00:05:12,059 --> 00:05:19,029
might we do it, more concretely. So let's
look at two examples. Here is, two example

53
00:05:19,029 --> 00:05:25,030
runs of a chain that we'll describe a
little bit later. And what we measure

54
00:05:25,030 --> 00:05:31,015
here, and this is the first statistic to
measure in Markov chains, is the log

55
00:05:31,015 --> 00:05:40,058
probability. Of, of a sample. So you
compute The log probability of sample.

56
00:05:40,058 --> 00:05:45,043
Now, you can't always compute the log
probability directly, might compute an

57
00:05:45,043 --> 00:05:50,080
un-normalized log probability as we'll
talk about, as we'll talk about later. But

58
00:05:50,080 --> 00:05:55,007
basically, you compute the log
probability, or some constant factor

59
00:05:55,007 --> 00:06:00,043
thereof. And now you can compare two runs.
And this is a run that's initialized from

60
00:06:00,043 --> 00:06:05,087
an arbitrary state. And this is one that's
initialized from a high probability state.

61
00:06:05,087 --> 00:06:10,091
And you look at those and you say, has it
mixed relative to this criterion, the

62
00:06:10,091 --> 00:06:17,060
answer is maybe. It looks okay but you're
not entirely sure. But we can look at

63
00:06:17,060 --> 00:06:23,094
other statistics. Oh, sorry. Let's look at
another example. What about this one? Here

64
00:06:23,094 --> 00:06:28,016
is again, again an example of two runs,
one of which is initialized from an

65
00:06:28,016 --> 00:06:32,061
arbitrary state, and initialized from a
high probability state. And you can see

66
00:06:32,061 --> 00:06:36,089
that the log probability values are
nowhere close to each other. And so the

67
00:06:36,089 --> 00:06:41,017
next case, the answer is definitely not.
These are two runs of the chain, and

68
00:06:41,017 --> 00:06:47,052
really neither is mixed. And so you need
to run for a lot longer, which, you know,

69
00:06:47,052 --> 00:06:52,033
this comes up, goes, this goes up to
600,000, so kind of indicates to you how,

70
00:06:52,053 --> 00:06:58,028
much time this might take. A different
statistic, a different way of looking at

71
00:06:58,028 --> 00:07:03,049
this, is for a different kind of
statistic. So now we have, for example,

72
00:07:03,049 --> 00:07:09,042
the probability relative to a window that
we compute in the chain. So remember, all

73
00:07:09,042 --> 00:07:15,050
of this is relative to a window in the
chain. After we hope that mixing has taken

74
00:07:15,050 --> 00:07:21,050
place. And now we compute the probability
that, within states of this region, what

75
00:07:21,050 --> 00:07:27,085
is the probability of, that. The states
are in subsets. So, for example, the set

76
00:07:27,085 --> 00:07:36,041
of states where. X3 is equal to two. And
now we compute, that statistic, using the

77
00:07:36,041 --> 00:07:43,044
two initializations of the chains. So this
is chain one, or run one, and this is

78
00:07:43,044 --> 00:07:50,066
run two. And now, we do a scatter-plot,
for, for different statistics. So each of

79
00:07:50,066 --> 00:07:57,009
these points. This is the probability,
say, of X3=, X3=value two. This might be

80
00:07:57,009 --> 00:08:04,058
the probability that X1 is=to zero. This
might be some other probability that, you

81
00:08:04,058 --> 00:08:12,027
know, X5 is=to seven. And so each of these
is a statistic. And what you see here is a

82
00:08:12,027 --> 00:08:19,086
scatter plot. One is the estimate that
they get from the one chain and from the

83
00:08:19,086 --> 00:08:25,098
other. And looking at this. It should be
obvious that this first chain has not,

84
00:08:25,098 --> 00:08:31,046
the, we have not gotten mixing on the
left-hand side. Because you can see that

85
00:08:31,046 --> 00:08:37,058
there are all these points here. But have
high probability in one of the two runs

86
00:08:37,058 --> 00:08:44,006
and a probability zero in the other. And
vise versa. Where here most of the

87
00:08:44,006 --> 00:08:48,096
estimates are clustered around the
diagonal, so you're getting similar

88
00:08:48,096 --> 00:08:56,022
estimates from the two chains. And so
again, this one is a, the first one is a

89
00:08:56,022 --> 00:09:02,091
clear no and the second one is, maybe. And
if I do a lot of these statistics and they

90
00:09:02,091 --> 00:09:09,084
all come up with maybe then I'm willing to
trust the answers and assume that mixing

91
00:09:09,084 --> 00:09:15,098
is taking place. So now that I've started
to collecting samples, how do I use these

92
00:09:15,098 --> 00:09:23,036
samples? Well, one important observation
to keep in mind is that once the chain is

93
00:09:23,036 --> 00:09:29,086
mixed. All of my samples are from a
stationary distribution, that is this X(t)

94
00:09:29,086 --> 00:09:36,045
is from Pi, so is X(t+one), T+2, T+3, and so on and so forth

95
00:09:36,045 --> 00:09:41,058
[sound], and so, we can. Use every single
one of those samples, because they are

96
00:09:41,058 --> 00:09:46,040
from the correct distribution. So once I
determine that a, that a sample is long

97
00:09:46,040 --> 00:09:50,085
enough for mixing or believed that a
sample are long enough for mixing, we

98
00:09:50,085 --> 00:09:55,090
should collect and use all the samples.
And in fact, there are you might need some

99
00:09:55,090 --> 00:10:00,072
papers and say I am going to collect every
hundredth sample. There are actually

100
00:10:00,072 --> 00:10:05,059
papers that prove that using every single
sample is better than collecting every

101
00:10:05,059 --> 00:10:10,020
hundredth sample. But then you might ask,
well why would those papers tell me that I

102
00:10:10,020 --> 00:10:14,033
should only collect every 100 samples,
opposed to collecting all the samples if

103
00:10:14,033 --> 00:10:19,000
they're all from the correct distribution.
Because and this is undoubtedly true,

104
00:10:19,000 --> 00:10:24,058
adjacent samples, ones that are nearby to
each other in time are correlated with

105
00:10:24,058 --> 00:10:30,037
each other. Because how even if X(t) is from
the right distribution pie and so is X(t+1)

106
00:10:30,037 --> 00:10:35,088
one, X(t+1) is still gonna be close to
T, close to X(t), and so you are not really

107
00:10:35,088 --> 00:10:41,032
getting two different sample, you are
getting two that are very close relatives

108
00:10:41,032 --> 00:10:46,080
to each other. Now, as I said, it's
important to recognize that phenomenon,

109
00:10:46,080 --> 00:10:52,037
because it's important to realize that
just because you've reached mixing and

110
00:10:52,037 --> 00:10:58,023
collected 1000 samples, doesn't mean you
have 1000 samples worth of information. So

111
00:10:58,023 --> 00:11:04,045
you shouldn't go back and apply the, apply
the, you know, one of the bounds that we

112
00:11:04,045 --> 00:11:12,019
saw in, assuming you have IID samples. The
samples are not. I, I d. So, but that

113
00:11:12,019 --> 00:11:18,090
doesn't mean you shouldn't use them. Using
them is still better than not. Now this is

114
00:11:18,090 --> 00:11:23,068
where you get bitten twice by the same
phenomenon. The worse a chain is to mix,

115
00:11:23,068 --> 00:11:28,034
so the longer you need to wait for the
initial, for the initial samples to be

116
00:11:28,034 --> 00:11:33,018
good enough, the more correlated the
samples are because the slower you moving

117
00:11:33,018 --> 00:11:38,009
around in space in general. And so, if the
chain is bad it's bad in two different

118
00:11:38,009 --> 00:11:42,080
ways. It's bad because you took longer to
mix and it's bad because the samples

119
00:11:42,080 --> 00:11:47,040
you're collecting are not as useful
because of the correlation structure

120
00:11:47,040 --> 00:11:53,051
between the samples. So to summarize,
first the algorithm and then the

121
00:11:53,051 --> 00:11:59,085
implications. Here's how we would actually
end up using a Markov chain. So first of

122
00:11:59,085 --> 00:12:06,011
all, I'm running C chains in parallel and
I'm going to sample an initial state from

123
00:12:06,011 --> 00:12:12,076
each of them. And then I'm going to repeat
until a reach some determination that

124
00:12:12,076 --> 00:12:19,046
mixing has taken place. And, what I do is
I forward march each of the chains using a

125
00:12:19,046 --> 00:12:25,083
random walk process, where I generate the
P plus the first sample from the peak

126
00:12:25,083 --> 00:12:33,002
sample for that corresponding chain. Then
I compare windows statistics of the type

127
00:12:33,002 --> 00:12:38,060
that we showed earlier in the different
chains to try and determine whether mixing

128
00:12:38,060 --> 00:12:45,074
has taken place. And then I repeat until I
am co-, confident in the mixing

129
00:12:45,074 --> 00:12:53,018
properties. With that, I now repeat, until
there is sufficient samples to collect

130
00:12:53,018 --> 00:12:59,066
data. So I start out with an empty sample
set, and then for each of my chains, I

131
00:12:59,066 --> 00:13:07,047
generate, a sample. And I put it in my
sample set. And I repeat until I have

132
00:13:07,047 --> 00:13:16,096
enough, enough samples. And then finally,
when I've collected enough samples. I can

133
00:13:16,096 --> 00:13:22,067
go ahead, and compute the expectation, in
anything that I care about. Whether it's

134
00:13:22,067 --> 00:13:30,034
an indicator function or a more
complicated function. Summarizing the

135
00:13:30,034 --> 00:13:35,086
implications. Markov chains are a very
general-purpose class of methods for doing

136
00:13:35,086 --> 00:13:41,023
approximate inference in a, in general
probabilistic models. Not even necessarily

137
00:13:41,023 --> 00:13:46,081
probabilistic graphical models. They're
often very easy to implement, because the

138
00:13:46,081 --> 00:13:52,026
local sampling that we're doing is often
quite straightforward to execute. And it

139
00:13:52,026 --> 00:13:57,070
has good theoretical properties as we
sample, as we generate enough samples that

140
00:13:57,070 --> 00:14:03,043
are, sufficiently far away from our
starting distribution. Unfortunately these

141
00:14:03,043 --> 00:14:09,000
theoretical guarantees are. Very
theoretical, in many cases. And so this

142
00:14:09,000 --> 00:14:14,077
method also has some significant cons.
First, it has a very large number of

143
00:14:14,077 --> 00:14:21,007
tunable parameters and design choices.
What's my mixing time? Which statistics do

144
00:14:21,007 --> 00:14:27,030
I measure? How close are the statistics to
each other, in order for me to declare

145
00:14:27,030 --> 00:14:33,082
that mixing has taken place? How many
samples do I collect? Do I, what window

146
00:14:33,082 --> 00:14:40,004
size do I use to evaluate mixing? All of
these are design choices, they all make a

147
00:14:40,004 --> 00:14:45,095
difference. And so there's a lot of
finicky tuning that needs to be done when

148
00:14:45,095 --> 00:14:52,042
running an MCMC method in practice. The
second is that depending on the design of

149
00:14:52,042 --> 00:14:57,087
the chain this can be quite slow to
converge because it's very difficult to

150
00:14:57,087 --> 00:15:03,040
design chains that have good mixing
properties. And finally it's very hard to

151
00:15:03,040 --> 00:15:09,000
tell whether a chain is working. That is,
it's not straightforward to determine

152
00:15:09,000 --> 00:15:14,016
whether the chain has mixed and how,
whether my samples are sufficiently

153
00:15:14,016 --> 00:15:19,098
uncorrelated with each other that I'm
getting a reliable estimate of whatever it

154
00:15:19,098 --> 00:15:25,017
is that I'm trying to figure out. So, a
lot of advantages, but also some

155
00:15:25,017 --> 00:15:27,016
significant disadvantages.