1
00:00:00,000 --> 00:00:04,466
We define the notion of [inaudible] chain
Monte Carlo?s sampling as a general

2
00:00:04,466 --> 00:00:08,989
paradigm for generating samples from a
distribution from which it is otherwise

3
00:00:08,989 --> 00:00:13,263
difficult or perhaps intractable to
generate samples directly. Markov chain

4
00:00:13,263 --> 00:00:18,109
gives us a general way of, of approaching
this problem. But they, but the framework

5
00:00:18,109 --> 00:00:22,397
leaves open the question of where the
Markov chain comes from. That is, how do

6
00:00:22,397 --> 00:00:26,852
we design a Markov chain that has the
desired stationary distribution? We talked

7
00:00:26,852 --> 00:00:31,196
about the Gibbs chain as a general
solution to this problem in the context of

8
00:00:31,196 --> 00:00:35,763
graphical models. But we also mentioned
that the Gibbs chain has limitations in

9
00:00:35,763 --> 00:00:40,496
terms of its convergence rates for certain
types of graphical models. So what happens

10
00:00:40,496 --> 00:00:44,583
if we have a graphical model for which the
Gibbs chain. And doesn't have good

11
00:00:44,583 --> 00:00:48,680
convergence properties. How do we design a
market chain for that? Well, it turns out

12
00:00:48,680 --> 00:00:53,537
that there's a general class of, methods
called Metropolis-Hastings. And the

13
00:00:53,537 --> 00:00:58,580
Metropolis-Hastings algorithm gives us a
general approach for designing a Markov

14
00:00:58,580 --> 00:01:03,000
chain with a desired stationary
distribution. In fact it, for a given

15
00:01:03,000 --> 00:01:07,856
stationary distribution, we can construct
the whole family of different Markov

16
00:01:07,856 --> 00:01:12,900
chains that explore the space differently,
and then try and select among those, or

17
00:01:12,900 --> 00:01:17,320
construct one among those, that has good
convergence properties for our

18
00:01:17,320 --> 00:01:22,887
distribution. So the key insight behind
the metropolis hastings method is the

19
00:01:22,887 --> 00:01:28,496
notion of a reversible chain. So what does
it mean for a chain to be reversible?

20
00:01:28,496 --> 00:01:34,045
Imagine that we have a chain with a
particular stationary distribution pi. And

21
00:01:34,045 --> 00:01:39,324
we're going to consider two different
experiments. In the first experiment,

22
00:01:39,324 --> 00:01:44,472
we're going to pick a, a point in the
space. We're gonna pick a point in the

23
00:01:44,472 --> 00:01:49,950
state space, according to the probability
of distribution PI. So say we land on this

24
00:01:49,950 --> 00:01:55,230
one. And then we're going to pick a random
edge emanating from the state that we

25
00:01:55,230 --> 00:02:00,642
picked, according to the transition model
defined by the chain P. So say we pick

26
00:02:00,642 --> 00:02:05,981
this edge. That's the first experiment.
The second experiment is exactly the same

27
00:02:05,981 --> 00:02:11,443
thing. We're going to basically do the
this experiment twice. So now we are going

28
00:02:11,443 --> 00:02:17,500
to pick a. [inaudible] and once again
we're going to pick an outgoing.

29
00:02:19,350 --> 00:02:25,545
Transition from that state. A chain is
reversible if when I do this experiment,

30
00:02:25,545 --> 00:02:32,138
the probability of traversing this edge,
this red edge over here is in this process

31
00:02:32,138 --> 00:02:38,652
is exactly the same as the probability of
traversing this green edge in the other

32
00:02:38,652 --> 00:02:44,768
direction. That is, if picking I and then
traversing to J occurs with the same

33
00:02:44,768 --> 00:02:49,880
probability as picking J and then
traversing to I. So, written in,

34
00:02:50,125 --> 00:02:56,888
mathematical notation, this tells us that,
PI of X, which is a red state, times the

35
00:02:56,888 --> 00:03:03,488
transition along the red edge, is equal to
the probability of X prime. That was my

36
00:03:03,488 --> 00:03:10,170
green experiment. Times the probability of
transitioning in the opposite direction.

37
00:03:10,170 --> 00:03:15,439
Now, it's very easy to construct Markov
chains that are not reversible. So this is

38
00:03:15,439 --> 00:03:20,123
by no means, a universal property of
Markov chains. But it turns out that

39
00:03:20,123 --> 00:03:24,742
reversible Markov chains have elegant
properties that allow them to be

40
00:03:24,742 --> 00:03:29,556
constructed, so as to give rise to
particular stationary distributions. And

41
00:03:29,556 --> 00:03:34,760
specifically, we can show and it's not a
very difficult proof, we'll show it in a

42
00:03:34,760 --> 00:03:45,157
moment, that if this equation which is
called the detailed balance equation. If

43
00:03:45,157 --> 00:03:50,021
this equation holds and T is a regular
mark off chain. Then T has a unique

44
00:03:50,021 --> 00:03:55,673
stationary distribution which we know from
the fact that it's regular but furthermore

45
00:03:55,673 --> 00:04:02,234
that stationary distribution is pie. Let's
go ahead and prove it. And it turns out to

46
00:04:02,234 --> 00:04:09,771
be actually a very, a one line proof. So,
here we have, we take the two sides of the

47
00:04:09,771 --> 00:04:17,728
detailed balance equation, and we put one
of them on this side, and the other one on

48
00:04:17,728 --> 00:04:25,302
this side. And because the two sides are
equal, if we sum up over X, then the two

49
00:04:25,302 --> 00:04:32,779
summations are also equal. And now we
notice, by looking at the right hand side,

50
00:04:32,779 --> 00:04:41,329
that Pi of X prime doesn't depend on the
[inaudible] X. Alright, on variable x

51
00:04:41,329 --> 00:04:49,339
since, so we can move [inaudible] out of
destination. And so this can now be

52
00:04:49,339 --> 00:04:57,814
rewritten as pi of x prime time?s sum over
x t of x prime. X. And this information

53
00:04:57,814 --> 00:05:03,806
over here because P is a probability
distribution over it out going, over the

54
00:05:03,806 --> 00:05:10,265
edges that are out going from the X prime
is necessarily equal to one, and so if we

55
00:05:10,265 --> 00:05:16,646
rewrite what we've just proved in this one
line derivation, we just prove that the

56
00:05:16,646 --> 00:05:22,949
sum over X, [inaudible] of X, T of X to X
prime is equal to [inaudible] of X prime

57
00:05:22,949 --> 00:05:31,405
which is exactly the definition. Of the
stationary distribution. This is a one

58
00:05:31,405 --> 00:05:37,039
line proof that a reversible chain gives
me sorry, a chain that is reversible

59
00:05:37,039 --> 00:05:42,743
relative to a particular distribution of
pi necessarily has pi as its stationary

60
00:05:42,743 --> 00:05:48,518
distribution. Now, why is this a useful
transition between the definition of the

61
00:05:48,518 --> 00:05:54,292
stationary distribution of pi in terms of
this equation down at the bottom, versus

62
00:05:54,292 --> 00:05:59,457
this alternative definition of the
stationary distribution of pi? Because

63
00:05:59,457 --> 00:06:05,409
this distribution, this definition down at
the bottom involves the summation over

64
00:06:05,409 --> 00:06:11,360
what is in general an exponentially large
space. Whereas this one is, as we'll see

65
00:06:11,360 --> 00:06:17,458
in a minute, much more constructive in
that it allows us to construct P so as to

66
00:06:17,458 --> 00:06:23,938
match pi. And so, that is exactly the idea
behind the Metropolis Hastings, the

67
00:06:23,938 --> 00:06:30,754
definition of a Metropolis Hastings chain.
So how does a Metropolis Hastings chain

68
00:06:30,754 --> 00:06:37,238
work? It starts out by saying, well; we
want to move around broadly in the state

69
00:06:37,238 --> 00:06:43,056
space. So we're going to have a
distribution Q, which is kind of like a

70
00:06:43,056 --> 00:06:47,666
transition model. So this is my
[inaudible], this is my distribution q,

71
00:06:47,666 --> 00:06:52,707
and q is going to, to roam freely over the
state space. Unlike the Gibbs chain it's

72
00:06:52,707 --> 00:06:57,624
not going to necessarily take just little
local steps from one state to a state

73
00:06:57,624 --> 00:07:02,542
that's very nearby it can look very far
away and, and go into large into very

74
00:07:02,542 --> 00:07:07,706
distant parts of the state space. Now that
by itself of course is just going to give

75
00:07:07,706 --> 00:07:12,132
me a stationary distribution that has
absolutely no relationship to the

76
00:07:12,132 --> 00:07:17,049
stationary distribution pi that I care
about and so what I'm going to have is a

77
00:07:17,049 --> 00:07:21,630
critic. The critic is the guy who says,
whoa, wait a minute; you can't go there

78
00:07:21,630 --> 00:07:26,743
right now because it doesn't that's not
going to give you the right stationary

79
00:07:26,743 --> 00:07:31,555
distribution. So what does the critic do?
The critic listens to the proposal that

80
00:07:31,555 --> 00:07:36,427
was made by the proposal distribution
queue. So it says, oh you want to go from

81
00:07:36,427 --> 00:07:41,360
X to X prime, well what is the probability
with which I'm going to let you do that?

82
00:07:41,360 --> 00:07:46,247
That's the acceptance probability. And
that's a binary random variable for each x

83
00:07:46,247 --> 00:07:50,957
and x prime. What is the probability that
we accept that proposal? So that gives

84
00:07:50,957 --> 00:07:57,170
rise to the following process. I haven't
told you how to pick Q or A or anything

85
00:07:57,170 --> 00:08:02,409
yet. But let's just understand the
process. At each state X, we sample a

86
00:08:02,409 --> 00:08:08,471
potential successor state, X prime, from
my proposal distribution Q. So X, and we

87
00:08:08,471 --> 00:08:14,384
sort of have a proposal to go to X prime.
And I no-, denoted this using a dashed

88
00:08:14,384 --> 00:08:19,698
line. And now the [inaudible], the
acceptor says, do I accept that? And if

89
00:08:19,698 --> 00:08:25,875
the proposal is accepted. Then, I actually
make that transition and if the proposal

90
00:08:25,875 --> 00:08:32,337
is rejected, I just stay where I am. So
what transition model does this give rise

91
00:08:32,337 --> 00:08:37,552
to, because ultimately this just gives us
a transition model from x to x prime? So

92
00:08:37,552 --> 00:08:42,896
there's two cases. Case number one is if x
is not is the same, x prime is not x, that

93
00:08:42,896 --> 00:08:48,584
is x prime is a state other than x. Well
in this case, the only chance that I have

94
00:08:48,584 --> 00:08:54,706
of moving to X prime is if I proposed to
move to X prime and if that proposal was

95
00:08:54,706 --> 00:09:00,455
accepted. So I need to multiply these two
probabilities and that gives me the

96
00:09:00,455 --> 00:09:06,841
expression, this expression for the
transition. What about transition from X

97
00:09:06,841 --> 00:09:12,838
to X? Well, there's two different cases.
Either I propose a move to X, and it was

98
00:09:12,838 --> 00:09:18,927
accepted. Or, X also gets the benefit of
all of the transitions that were rejected

99
00:09:18,927 --> 00:09:24,791
by, the, from other states that were
proposed, but [inaudible], where the move

100
00:09:24,791 --> 00:09:30,329
wasn't accepted. And so what we have here
is Q. Of x to x which we assume is always

101
00:09:30,329 --> 00:09:34,894
accepted. That's sort of a one with the
exception of this model. And then we sum

102
00:09:34,894 --> 00:09:39,631
up over all possible other transitions of
the probability that they were proposed

103
00:09:39,631 --> 00:09:43,618
times the probability that they were
rejected which is one minus the

104
00:09:43,618 --> 00:09:47,893
probability that they were accepted.
[inaudible] give rise to a transition

105
00:09:47,893 --> 00:09:55,137
model. So this is a general definition of
a marcovchain but as stated, there's no

106
00:09:55,137 --> 00:10:00,803
reason to expect to have a particular
stationary distribution. And so, now this

107
00:10:00,803 --> 00:10:05,579
is where we bring back the intuition from
the detailed balance equation. And we're

108
00:10:05,579 --> 00:10:10,061
going to use the detail balance to
construct an acceptance probability that

109
00:10:10,061 --> 00:10:14,938
has the property that we want. And so,
here is a detailed balance equation

110
00:10:14,938 --> 00:10:20,721
rewritten. And now, let's write down, and
we're going to assume in this, in this

111
00:10:20,721 --> 00:10:26,720
particular example, that X is not equal to
X prime. And so, we're going to, because

112
00:10:26,720 --> 00:10:32,358
this is trivial for the case, X is= to X
prime, this equality always holds. Pi of

113
00:10:32,358 --> 00:10:38,141
X, P of XX is= to PI of X, P of XX. And so
let's look at the case, X is not equal to

114
00:10:38,141 --> 00:10:46,540
X prime. And our goal is to construct A.
So the goal is to construct A such that.

115
00:10:50,280 --> 00:11:01,400
Such that detailed balance. Old. Or Q. I'm
given Q; the setup is I'm given a proposal

116
00:11:01,400 --> 00:11:07,938
distribution Q. And now I'm going to pick
A, so as to make detailed balance hold.

117
00:11:07,938 --> 00:11:14,973
And if detailed balance holds, for Q, Pi,
then I'm going to, then that is going to

118
00:11:14,973 --> 00:11:21,387
guarantee that the process, overall, has
the correct stationary distribution. So,

119
00:11:21,387 --> 00:11:26,929
this is the quality that we want to have
happen. And now let's go ahead and just

120
00:11:26,929 --> 00:11:31,846
define this as a constraint on the
acceptance probabilities, so we have

121
00:11:31,846 --> 00:11:37,249
acceptance probability A, occurring on
both sides of the equation. So I'm going

122
00:11:37,249 --> 00:11:42,998
to divide, move both As to one side, move
everything else to the other side and so I

123
00:11:42,998 --> 00:11:48,539
get a constraint on the ratios, between
the acceptance probability from XX prime

124
00:11:48,539 --> 00:11:54,011
and the acceptance probability from X
prime X and that has to be equal to this

125
00:11:54,011 --> 00:11:59,319
ratio over here. And so I'm going to
assume, without loss of generality, that

126
00:11:59,319 --> 00:12:04,558
this ratio. Notice that this ra-, we have
we can decide this in any way that we

127
00:12:04,558 --> 00:12:09,298
want. We can either consider the ratio
from X to X prime is the numerator, or

128
00:12:09,298 --> 00:12:14,474
from X prime to X. I picked this one under
the assumption that this is a, some value

129
00:12:14,474 --> 00:12:18,840
[inaudible], sorry. This is equal to
[inaudible], which is less than one.

130
00:12:22,520 --> 00:12:40,745
[sound] And, so now if we. Kick a. So now
we need to pick the values of the two

131
00:12:40,745 --> 00:12:48,008
acceptance probabilities x and x prime so
as to make this equality hold. And one

132
00:12:48,008 --> 00:12:55,271
simple way to do that is to take the
smaller of the two which we assume was the

133
00:12:55,271 --> 00:13:02,624
numerator and we make A of x to x prime
equal of roll and we make A, x prime to x

134
00:13:02,624 --> 00:13:10,604
equal to one and that gives me immediately
that this [inaudible] hold. Now of course,

135
00:13:10,604 --> 00:13:15,552
we could have picked these probabilities
to be otherwise. We could have picked for

136
00:13:15,552 --> 00:13:20,138
example, AX to X prime to be half of
[inaudible], and A of X prime to X to be

137
00:13:20,138 --> 00:13:25,146
equal to half. But notice what that would
do. That would just reduce the probability

138
00:13:25,146 --> 00:13:29,792
that our proposals are accepted, which
would just make the chain move half as

139
00:13:29,792 --> 00:13:35,042
quickly, because you end up staying at the
same state twice as often as you would if

140
00:13:35,042 --> 00:13:39,809
the acceptance probability was higher. So
these are in fact, the highest numbers

141
00:13:39,809 --> 00:13:47,435
that we could possibly pick, while still
making this ratio constraint hold. And so,

142
00:13:47,435 --> 00:13:52,445
that gives me, when you actually put it
together, as a general formula for the

143
00:13:52,445 --> 00:13:57,585
acceptance probability, it gives us this
expression, which, if you look at it, you

144
00:13:57,585 --> 00:14:05,978
will see that it gives the right values
for both XX find and for X find X. So

145
00:14:05,978 --> 00:14:13,148
that's how many how to pick a given q. And
the question is what about q? How do I

146
00:14:13,148 --> 00:14:20,050
pick q? Well that turns out to be the
$64,000,000 question. Picking q is an art

147
00:14:20,050 --> 00:14:25,702
and it's not an easy choice in many
applications. But let's think about some

148
00:14:25,702 --> 00:14:31,355
conditions that Q must satisfy before we
think about how to pick one. So one

149
00:14:31,355 --> 00:14:36,934
condition on Q is derived simply by
looking at the formal expression for A.

150
00:14:36,934 --> 00:14:42,833
And we can see that this here involves a
ratio. And if you have a ratio then one

151
00:14:42,833 --> 00:14:48,731
condition is that you better not have a
denominator that's equal to zero. And so

152
00:14:48,731 --> 00:14:55,209
one of the cases that, one of the things
that we must guarantee regarding Q in

153
00:14:55,209 --> 00:15:01,936
order for this to be a valid set of
acceptance probabilities is that Q itself

154
00:15:01,936 --> 00:15:08,694
must be reversible in the following sense.
That is, if the If the denominator, if, if

155
00:15:08,694 --> 00:15:14,443
the numerator is greater than zero, then
the denominator is greater than zero, and

156
00:15:14,443 --> 00:15:20,264
vice versa. That is, if you can propose a
step from X to X prime, you better be able

157
00:15:20,264 --> 00:15:25,871
to propose a step from X prime to X, with
non zero probability, which guarantees

158
00:15:25,871 --> 00:15:34,449
that this ratio is always well defined.
Now the problem with this constraint on Q,

159
00:15:34,449 --> 00:15:44,061
is that it actually, induces an tension in
the design of Q. Now, on the one hand, we

160
00:15:44,061 --> 00:15:49,234
like you to be very broad. So if you're at
this state over here, we like to, we like

161
00:15:49,234 --> 00:15:54,344
you to go really, really far away from the
current state. Because the further away

162
00:15:54,344 --> 00:15:59,392
you can go, the faster you move around in
the state space. You don't want to stay

163
00:15:59,392 --> 00:16:03,997
local, you don't want make the same
mistakes that the Gibbs chain does by

164
00:16:03,997 --> 00:16:08,288
staying very near to the current
assignment. You want to move around

165
00:16:08,288 --> 00:16:14,216
quickly and that improves mixing. On the
hand, if you look at the implications that

166
00:16:14,216 --> 00:16:20,026
this formula has when the proposal
distribution is very broad. And so that

167
00:16:20,026 --> 00:16:26,777
you have one state that for example has
low pi and the other state has a very high

168
00:16:26,777 --> 00:16:33,640
value of pi. Which is what you get when
you move around from a hilly part of the

169
00:16:33,640 --> 00:16:40,690
space to a low part of the space. You have
very big differences in terms of height of

170
00:16:40,690 --> 00:16:47,408
the two stationeries. So what I'm drawing
here is the height of pi, and this is my

171
00:16:47,408 --> 00:16:52,508
space, space X. And if I move around very
far I'm liable to get into situations

172
00:16:52,508 --> 00:16:57,185
where pi of one state x might be
considerably larger than pi of x prime and

173
00:16:57,185 --> 00:17:01,985
if you think about what that implies
regarding the acceptance probability. The

174
00:17:01,985 --> 00:17:06,846
acceptance probability can get very, very
low which in turn implies slow mixing

175
00:17:06,846 --> 00:17:12,015
again because you might not, you might be
taking very global steps but you're taking

176
00:17:12,015 --> 00:17:16,446
very few of them. And so this is a real
sort of tension in the design of

177
00:17:16,630 --> 00:17:22,530
distributions, of proposal distribution
skill. Let's take an example of a Markov

178
00:17:22,530 --> 00:17:27,921
chain where proposal distributions can
make a very big difference. And this is a

179
00:17:27,921 --> 00:17:33,311
problem that you wouldn't necessarily
immediately think of as a graphical model

180
00:17:33,311 --> 00:17:38,701
but can be formulated as one and it's a
matching problem and we'll see it other

181
00:17:38,701 --> 00:17:44,073
settings as well. So here we have a bunch
of red dots as we see over here. And we

182
00:17:44,073 --> 00:17:50,274
have a bunch of blue dots. And we want. To
match. The red dots to the blue dots. And

183
00:17:50,274 --> 00:17:55,860
there's some sort of preference function.
So these edges over here are annotated.

184
00:17:56,037 --> 00:18:00,464
And I'm gonna mark them green, are
annotated with some kind of weights that

185
00:18:00,464 --> 00:18:05,304
tell us how happy is the red, is this red
dot to be matched with this blue dot? And

186
00:18:05,304 --> 00:18:09,908
this happens a lot, for example, in, in
various correspondence problems where

187
00:18:09,908 --> 00:18:14,335
we're trying to match sensor readings to
objects, for example, in a tracking

188
00:18:14,335 --> 00:18:19,411
application. It also happens in, in image
problems where you wanna match features in

189
00:18:19,411 --> 00:18:24,711
one image to features in another. So it's
a very common problem. So, one formulation

190
00:18:24,711 --> 00:18:31,620
of the matching problem as a graphical
model is that we have a variable x I for

191
00:18:31,620 --> 00:18:37,864
each red dot, so the green, so the red
dots are going to be the variables. The

192
00:18:37,864 --> 00:18:44,690
blue dots are going to represent values.
And we're going to have that x I is equal.

193
00:18:44,690 --> 00:18:54,225
J. If I match the I to J. [cough] So that
can now be written as a probability

194
00:18:54,225 --> 00:19:02,371
distribution over a space. And so we can
consider the probability of an assignment

195
00:19:02,371 --> 00:19:08,104
of. Values to, the variables. And we're
going to say that, first of all, has to be

196
00:19:08,104 --> 00:19:13,817
matching. So if we don't have that every
X, every red dot is matched to a different

197
00:19:13,817 --> 00:19:19,530
blue dot, that's probably zero assignment.
So this would be the case if you had two

198
00:19:19,530 --> 00:19:25,242
red dots that matched, to the same blue
dot. And otherwise we're going to define

199
00:19:25,242 --> 00:19:29,980
some kind of weighted combination of,
sorry, it's, it's going to be an

200
00:19:29,980 --> 00:19:35,693
exponential of the sum of the quality of
the matches between the red dots and the

201
00:19:35,693 --> 00:19:40,881
blue dots. So we are summing up the
quality of the edges that participate in

202
00:19:40,881 --> 00:19:54,568
matching. So for example if this is my
matching over here. And notice that I

203
00:19:54,568 --> 00:20:01,354
didn't get to match all the red dots.
That's, well, actually here. We're going

204
00:20:01,354 --> 00:20:08,774
to match all the red dots. So now we have
a matching on, on the, for each red dot we

205
00:20:08,774 --> 00:20:15,922
assigned a blue dot as a value. And now
the overall quality is the total sum of

206
00:20:15,922 --> 00:20:22,074
the, of the quality of the matching and
that defines, and that can be

207
00:20:22,074 --> 00:20:29,200
exponentiated to different probability
distribution. So and we're going to

208
00:20:29,200 --> 00:20:34,579
represent these qualities visually in this
example as, as distances so that we're

209
00:20:34,579 --> 00:20:40,223
going to assume for example that this red
dot prefers to be matched to this blue dot

210
00:20:40,223 --> 00:20:51,241
more then it prefers to be matched to this
further away blue dot. So, one can imagine

211
00:20:51,241 --> 00:20:58,854
running a Gibbs sampling distribution on
this model, by taking a variable and say

212
00:20:59,126 --> 00:21:06,286
one of the red dots and, picking a new
value for it that is a new blue dot that

213
00:21:06,286 --> 00:21:12,412
it wasn't attached to. This is going to
change things very, very slowly. Because

214
00:21:12,412 --> 00:21:17,424
most of the blue dots are going to be
taken by the for red dot. And so, those

215
00:21:17,424 --> 00:21:22,898
assignments where a red dot is matched to
a previously taken blue dot are going to

216
00:21:22,898 --> 00:21:27,646
have very well probability. Zero
probability. Okay. And so those are going

217
00:21:27,646 --> 00:21:32,658
to be impossible. So the only thing I can
do is I can make the red dot match

218
00:21:32,658 --> 00:21:37,604
different blue dot. Match one of the
unmatched blue dots. And that?s going to

219
00:21:37,604 --> 00:21:43,149
take a very long time for things to
change. Here is a different way of doing

220
00:21:43,149 --> 00:21:48,868
this, which is the Metropolis Hastings
which is one way of constructing a

221
00:21:48,868 --> 00:21:55,189
proposal distribution and using Metropolis
Hastings. And that's called an augmenting

222
00:21:55,189 --> 00:22:01,209
path proposal distribution. So what that
does is, let's assume that this is my

223
00:22:01,209 --> 00:22:07,681
current match, and I'm going to define the
following proposal. I'm going to pick one

224
00:22:07,681 --> 00:22:13,100
of the variables, XI, say this one. And
I'm going to say, I'm going to pick.

225
00:22:13,100 --> 00:22:19,547
Another value for it pretending that
everything is available. So I'm going to

226
00:22:19,547 --> 00:22:23,970
ignore the fact that this guy is already
matched. I'm going to pick this one. I

227
00:22:23,970 --> 00:22:27,827
would, I'm, I'm thinking it's
probabilistically, so I could have picked,

228
00:22:27,997 --> 00:22:32,534
a different one. I could have picked the
same one that I was matched to before. I

229
00:22:32,534 --> 00:22:36,900
could pick a further away one. But say I
pick this one. Well now, this guy, poor

230
00:22:36,900 --> 00:22:41,437
guy, this one is unmatched. Sorry, this
red guy over here. So [inaudible] has to

231
00:22:41,437 --> 00:22:48,166
pick a new partner. And so, say it picks
this one. This red guy is unmatched now.

232
00:22:48,166 --> 00:22:54,662
And so it might take one, and say fix this
one. And that leaves me with this red guy

233
00:22:54,662 --> 00:23:00,139
and say; this red guy picks this one and
notice that now I have a new legal

234
00:23:00,139 --> 00:23:06,127
matching. Every, I've closed the loop and
I've defined what's called an 'alternating

235
00:23:06,127 --> 00:23:12,189
cycle' where basically I can switch all of
the black edges to green edges and that

236
00:23:12,189 --> 00:23:18,710
gives me a new legal matching. And that's
my proposal. And with a little bit of,

237
00:23:18,925 --> 00:23:24,441
numerical calculation, one can figure out
the acceptance probability for this

238
00:23:24,441 --> 00:23:30,243
proposal distribution. And it turns out
that it's actually a really good proposal

239
00:23:30,243 --> 00:23:35,615
distribution. So let me show you some
examples on the next slide. So this is,

240
00:23:35,830 --> 00:23:41,632
the results on the chain. If I just apply
Gibb sampling. And you can see over here,

241
00:23:41,632 --> 00:23:47,362
four chains. So the four colors represent
the four chains. And what you see on, in

242
00:23:47,362 --> 00:23:53,734
the X axis, is numbered steps. And on the
y axis there's some kind of statistic that

243
00:23:53,734 --> 00:23:59,011
I'm tracking in order to gauge whether the
chain is mixing. As is happens it's the

244
00:23:59,011 --> 00:24:04,030
probability that the first red dot is
matched to the first blue dot but it

245
00:24:04,030 --> 00:24:08,985
doesn't matter. Any statistic would've
illustrated the point here. And you can

246
00:24:08,985 --> 00:24:13,940
see that there is a lot of long range
fluctuations in this chain. That is the

247
00:24:13,940 --> 00:24:19,153
probabilities change over time. The
probabilities by the way are computed over

248
00:24:19,153 --> 00:24:24,225
windows of size 500. From the samples in
that window. And you can see that the

249
00:24:24,225 --> 00:24:28,864
chain takes, that the chain takes a long
time to move from one region of the space

250
00:24:28,864 --> 00:24:33,921
to the other. The proposal distribution
that I just showed you by contrast is

251
00:24:33,921 --> 00:24:39,252
totally different. You can see that the
probabilities are almost totally flat. And

252
00:24:39,252 --> 00:24:44,139
that there is basically all four chains
are the same, and there is, almost the

253
00:24:44,139 --> 00:24:49,089
same and there is very little change in
windows overtime. And there is an even

254
00:24:49,089 --> 00:24:54,547
better proposal distribution that I didn't
show you that modifies the augmenting path

255
00:24:54,547 --> 00:25:02,133
by just a little bit. And that gives you
effectively perfect mixing across the

256
00:25:02,133 --> 00:25:08,239
entire time. If we look at the other
metric that we define for evaluating

257
00:25:08,467 --> 00:25:13,943
mixing, we, we can compare the
probabilities of these different statistic

258
00:25:13,943 --> 00:25:20,332
of, of, of different statistics across the
two chains. So for example this might be

259
00:25:20,332 --> 00:25:25,634
just for example, the red chain. And this
might be the green chain, and what we see

260
00:25:25,634 --> 00:25:30,638
here are the are the statistics that you
get for different kinds of probabilities.

261
00:25:30,638 --> 00:25:35,349
For the probability that this variable is
match, sorry, that this dot is match to

262
00:25:35,349 --> 00:25:39,941
that dot, for example. And you can see
that the [inaudible] change the estimate

263
00:25:39,941 --> 00:25:44,181
that you get are very noisy, and the
different chains give you divergent

264
00:25:44,181 --> 00:25:47,449
estimates. The second
Metropolis\u2013Hasting, sorry the first

265
00:25:47,449 --> 00:25:52,174
of the Metropolis\u2013Hastings gives you,
things that are almost on the diagonal,

266
00:25:52,174 --> 00:25:58,229
and here, things are effectively, exactly
on a diagonal, perfect mixing. But to

267
00:25:58,229 --> 00:26:02,789
summarize, Metropolis-Hastings is a very
general framework for building markup

268
00:26:02,789 --> 00:26:07,546
chains so that they are designed to have a
particular stationary distribution. It

269
00:26:07,546 --> 00:26:12,339
requires that you come up with a proposal
distribution. And that proposal

270
00:26:12,339 --> 00:26:17,548
distribution has, needs to have certain
properties in order to be valid. But once

271
00:26:17,548 --> 00:26:22,366
you give me such a proposal distribution,
the detail-balanced equation, which is

272
00:26:22,366 --> 00:26:27,428
this nice, simple equation, tells me how I
can construct the acceptance distribution

273
00:26:27,428 --> 00:26:33,669
so as to, enforce the fact. That we get
the right stationary distribution. So,

274
00:26:33,669 --> 00:26:38,077
this is great in some ways, because it
gives us this huge flexibility in

275
00:26:38,077 --> 00:26:42,975
designing proposal distributions that
explore the space quickly, and move around

276
00:26:42,975 --> 00:26:47,934
to faraway parts of the space. But as we
saw, picking the proposal distribution is

277
00:26:47,934 --> 00:26:52,954
actually a, an important design point, and
it makes a big difference to performance.

278
00:26:52,954 --> 00:26:57,913
And it's not, there isn't, like, a science
of how you should do this, effectively.

279
00:26:57,913 --> 00:27:03,178
And so there are, and so this is something
that is really an art and requires a non

280
00:27:03,178 --> 00:27:05,260
trivial amount of. Thought in engineering.