1
00:00:02,856 --> 00:00:05,711
An alternative class of algorithms to the
variable elimination algorithms, is the

2
00:00:05,711 --> 00:00:11,492
class of message passing algorithms. And
as we'll see this is a class that is in

3
00:00:11,492 --> 00:00:16,925
some ways closely related to the variable
elimination, but also offers us additional

4
00:00:16,925 --> 00:00:22,218
flexibility in how we do summation 
and factor product steps, so as to

5
00:00:22,218 --> 00:00:28,347
potentially come up with a lower complexity
than would be required by even the minimal

6
00:00:28,347 --> 00:00:34,678
elimination ordering. So let's consider
a simple Markov network of the following

7
00:00:34,678 --> 00:00:39,437
type. And let's assume that I don't want
to go to the cost of eliminating

8
00:00:39,437 --> 00:00:44,588
variables. Although, in this network, it's
not gonna be too expensive. And, instead,

9
00:00:44,588 --> 00:00:50,000
what we're going to do is we're going to
construct what we call a cluster graph.

10
00:00:50,000 --> 00:00:55,243
The cluster graph is something where... it's...
is a data structure in which

11
00:00:55,243 --> 00:01:00,292
we're going to take little bits of
knowledge from this graphical model. And

12
00:01:00,292 --> 00:01:05,600
we're going to place them in things called
clusters. So here we have four clusters.

13
00:01:06,160 --> 00:01:13,614
In this example, cluster one, is a cluster
whose jurisdiction of influence is, the,

14
00:01:13,614 --> 00:01:20,032
the pair of variables AB. Cluster two has
jurisdiction over B and C. Three is over C and

15
00:01:20,032 --> 00:01:24,655
D. And four is over A and D. And these
clusters are going to sit there and

16
00:01:24,655 --> 00:01:29,658
they're going to talk to each other. And
they're going to try and convince each

17
00:01:29,658 --> 00:01:34,344
other that what they think about a
variable that they both consider to be

18
00:01:34,344 --> 00:01:39,411
under their jurisdiction is correct. So
for example, cluster one is going to talk

19
00:01:39,411 --> 00:01:44,413
to cluster two about the variable B and
it's going to tell cluster two what it

20
00:01:44,413 --> 00:01:48,973
thinks about B so that cluster two might
become more informed about the

21
00:01:48,973 --> 00:01:54,854
distribution over B. And so, what we're
going to do is, initially, each cluster is

22
00:01:54,854 --> 00:02:00,876
going to have its own little piece of
information. So Phi 1 is going to go here.

23
00:02:00,876 --> 00:02:07,212
Phi 2 is going to go there. Phi 3 goes there
and Phi 4 goes there. And now the variables

24
00:02:07,212 --> 00:02:14,195
are going to communicate with each other
via these things called messages. So we're

25
00:02:14,195 --> 00:02:19,947
going to call we're going to slightly
rename things. We're going to call the

26
00:02:19,947 --> 00:02:26,355
[inaudible] initial set of beliefs, if you
will, or evidence that a factor that a

27
00:02:26,355 --> 00:02:32,181
cluster has over the variables in its
jurisdiction, we're going to those psi. In

28
00:02:32,181 --> 00:02:38,370
the example were just have psi were just
the phis of the original model but as will

29
00:02:38,370 --> 00:02:44,341
see sometimes it can become a little bit
complicated than that. So now factor...

30
00:02:44,341 --> 00:02:49,995
The cluster one has the factor of psi 1.
And cluster two has psi 2 and so on.

31
00:02:49,995 --> 00:02:55,253
And now lets imagine that psi 1 wants
to send a message. I'm sorry, that psi 2,

32
00:02:55,253 --> 00:03:00,111
that cluster two wants to send a
message to cluster one. So it has to

33
00:03:00,311 --> 00:03:05,968
figure out what it believes. A priori
we're going to assume that its just going

34
00:03:05,968 --> 00:03:10,627
to, we're going to start out by
initializing with a totally uninformed

35
00:03:10,627 --> 00:03:15,473
message. So because initially they haven't
even started talking to each other. So all

36
00:03:15,473 --> 00:03:20,680
messages are initialized to be one. But
now, cluster two can come back and say,

37
00:03:20,680 --> 00:03:26,736
okay. I'm going to take the information,
uninformative as it was, that I got from

38
00:03:26,736 --> 00:03:32,716
cluster two. And notice that I call this
message delta 2,1. Delta, 2 being the

39
00:03:32,716 --> 00:03:38,401
from. And 1 being the to, and so taken
delta 2,1, and now factor one, cluster

40
00:03:38,401 --> 00:03:44,178
one is going to say well I'm going to pick
that and I'm going to multiply it, with my

41
00:03:44,178 --> 00:03:49,343
current, thoughts about the variables A,B
and that's going to give me a more

42
00:03:49,343 --> 00:03:54,712
informed factor and now I'm going to
communicate that information to factor

43
00:03:54,712 --> 00:04:00,914
four, to cluster four. But cluster 4's
doesn't care about a, sorry cluster four

44
00:04:00,914 --> 00:04:06,901
doesn't care about B. And so what I'm
going to communicate to cluster four,

45
00:04:06,901 --> 00:04:13,375
which is this message delta 1,4, from one
to four, is the sum over B, which is the

46
00:04:13,375 --> 00:04:23,092
variable that four doesn't wanna hear
about, of the incoming message. Times my

47
00:04:23,092 --> 00:04:36,254
initial beliefs. For my initial factors.
Now this general process is what keeps the

48
00:04:36,254 --> 00:04:42,298
message passing algorithm going. So each
variable. Each cluster is going to send

49
00:04:42,298 --> 00:04:48,508
messages to its adjacent cluster that
reflect this exact same process. So for

50
00:04:48,508 --> 00:04:54,641
example, just take a different example
here is delta 3-4 so this is the message

51
00:04:54,641 --> 00:05:00,463
that goes from three to four and that
message takes onto consideration the

52
00:05:00,463 --> 00:05:06,673
evidence the two sent to three which is
this guy over here finds whatever three

53
00:05:06,673 --> 00:05:13,769
thought about CD to begin with. Notice,
and this is important, that the message

54
00:05:13,769 --> 00:05:20,031
that three sends to four doesn't take into
consideration, the information that it got

55
00:05:20,031 --> 00:05:25,234
from four. So there isn't in this
expression over here The contribution of

56
00:05:25,234 --> 00:05:29,827
delta 4,3. Because you want to
have, you want to avoid this case of I

57
00:05:29,827 --> 00:05:34,848
repeat back to you a rumor that you just
told me and we all become more convinced

58
00:05:34,848 --> 00:05:39,870
about the truth of this rumor because, oh,
you, I, I thought about this first but now

59
00:05:39,870 --> 00:05:45,075
you're reinforcing me by telling it to me
again and the beliefs are just going to go

60
00:05:45,075 --> 00:05:49,912
up and up. And so what happens here is
that we deliberately only restrict

61
00:05:49,912 --> 00:05:56,140
attention to evidence that comes in from other
sources. So three only uses evidence from

62
00:05:56,140 --> 00:06:02,541
two, when reporting to four. And it only
uses, conversely, evidence from four when

63
00:06:02,541 --> 00:06:09,782
reporting to two. And so now, this is this defines a set a, a communication

64
00:06:09,782 --> 00:06:15,002
protocol by which one factor or one
cluster rather in the graph can

65
00:06:15,002 --> 00:06:20,795
communicate information to its neighbors.
What do we do with this? So how do we

66
00:06:20,993 --> 00:06:26,350
generalize this message passing process?
Let's construct a more general version of

67
00:06:26,350 --> 00:06:31,840
this. So this uses a data structure called
a cluster graph. A cluster graph is an

68
00:06:31,840 --> 00:06:36,866
undirected graph whose nodes are not
variables any more, not as, not in, this

69
00:06:36,866 --> 00:06:42,157
is not a, you know graphical model of the
type that we've seen. The nodes in this

70
00:06:42,157 --> 00:06:47,183
undirected graph are clusters that
correspond to subsets of variables just

71
00:06:47,183 --> 00:06:57,893
like we had before. And we're going to
connect, two adjacent, two clusters, Ci

72
00:06:57,893 --> 00:07:05,682
and Cj. And this, this thing called the
sepset, is the variable that they choose

73
00:07:05,682 --> 00:07:16,404
to talk about. And clearly each one can
only talk about variables that it knows

74
00:07:16,404 --> 00:07:21,855
about which is why the sepset Sij has to
be a subset of both Ci and Cj. So once

75
00:07:21,855 --> 00:07:26,615
again, Ci is the jurisdiction of cluster i,
these are the variables that it

76
00:07:26,615 --> 00:07:32,480
understands, and Sij is the communication
between two adjacent clusters in the

77
00:07:32,480 --> 00:07:39,792
cluster graph. So, now, given a set
of factors Phi, we're going to initialize

78
00:07:39,792 --> 00:07:47,086
the, the model by giving each gra-, each
cluster in the graph a certain amount of

79
00:07:47,086 --> 00:07:53,924
information. So each of my initial
clusters, each of my initial factors phi k,

80
00:07:53,924 --> 00:08:05,667
in my graph, is going to be assigned to
one and only one cluster. And this is

81
00:08:05,667 --> 00:08:09,358
important. It needs to be at least one, so
that the information is taken into account

82
00:08:09,358 --> 00:08:12,873
somewhere. And it shouldn't be more than
one, because if you give it to more than

83
00:08:12,873 --> 00:08:16,169
one person, to more than one cluster,
they're going to, that you're going to

84
00:08:16,169 --> 00:08:19,684
double count the evidence. They're each
going to think it's an independent piece

85
00:08:19,684 --> 00:08:24,359
of evidence, and it's going to be counted
twice. Now where do we put the information

86
00:08:24,359 --> 00:08:29,940
corresponding to factor k? We put this
only in a fact, we can only put it in a

87
00:08:29,940 --> 00:08:35,811
cluster that understands every single
variable in that factor. So if we have a

88
00:08:35,811 --> 00:08:41,537
factor whose scope, has a certain, that
has a certain scope, that scope better be

89
00:08:41,537 --> 00:08:45,769
a subset. Of the variables that the
cluster understands, because otherwise we

90
00:08:45,769 --> 00:08:59,829
can't even talk about those variables. So,
[sound] So once we've done that. See if I

91
00:08:59,829 --> 00:09:09,192
can, erase this. Okay. We can now define
the initial beliefs of a particular

92
00:09:09,192 --> 00:09:21,755
cluster, as the product of all of the
factors that are assigned to it. Now some

93
00:09:21,755 --> 00:09:26,518
variables might, some clusters might be
assigned one factor. In which case psi is

94
00:09:26,518 --> 00:09:30,924
just equal to that phi. Some, because
that, that was the case in the example

95
00:09:30,924 --> 00:09:35,925
that we just saw. Some clusters might have
several factors assigned to them. In which

96
00:09:35,925 --> 00:09:40,687
case we need to multiply them to create a
single factor that is sorta the total

97
00:09:40,687 --> 00:09:45,688
informed beliefs of the cluster. And some
clusters might have no factors assigned to

98
00:09:45,688 --> 00:09:51,830
them. In which case this is a null product
and is equal to one. So now let's look at

99
00:09:51,830 --> 00:09:57,563
an example of the sum of more interesting
cluster graphs than the trivial one that

100
00:09:57,563 --> 00:10:02,882
we showed earlier. Here we have a set of
factors: phi-1 of ABC; phi-2 of BC; phi-3; phi-4;

101
00:10:02,882 --> 00:10:08,201
phi-6 and so on. So initially, we have to
figure out for each of those factors, a

102
00:10:08,201 --> 00:10:13,312
cluster in which to put it. For ABC,
there's really only one choice because

103
00:10:13,312 --> 00:10:18,907
there is only one cluster in this entire
graph that understands about all of A, B

104
00:10:18,907 --> 00:10:24,895
and C, and that is this cluster over here.
BC however, has two choices. It can go

105
00:10:24,895 --> 00:10:30,514
into cluster one, or it can go into
cluster two, because both cluster one and

106
00:10:30,514 --> 00:10:37,043
cluster two understand about B and C. We
are going to put it in cluster two. I mean

107
00:10:37,043 --> 00:10:43,175
you can put it in either one, both are
fine. Phi-3 has again two choices it can go

108
00:10:43,175 --> 00:10:49,457
into cluster two or it can go into cluster
three. We're going to go ahead and make a

109
00:10:49,457 --> 00:10:57,739
decision to put it in cluster two.
Cluster, phi-4, goes, has only, one choice,

110
00:10:57,739 --> 00:11:05,305
because only one cluster has both D and E
in its scope. So it goes here. Phi-5

111
00:11:05,305 --> 00:11:11,855
similarly. Only over here. BD again there
is more that one choice. We could put it

112
00:11:11,855 --> 00:11:18,652
in cluster two or we can put it in cluster
three. Let's, for simplicity, put it in

113
00:11:18,652 --> 00:11:25,203
cluster three, and BDF only one choice.
This is one possible way of assigning the

114
00:11:25,203 --> 00:11:31,836
cluster, the factors to clusters. There is
other alternatives, as I said, that would

115
00:11:31,836 --> 00:11:38,645
work. If we do this we end up, for
example, with psi 2. Being the product

116
00:11:38,645 --> 00:11:51,952
of phi2 times phi3. Where as psi 1 is
simply equal to phi1. And psi3. Is

117
00:11:51,952 --> 00:12:05,228
equal to phi, to phi6 times phi7.
Here is a different assignment of the same

118
00:12:05,228 --> 00:12:11,781
factors to different, to the clusters. And
we can see that it, that it also equally

119
00:12:11,781 --> 00:12:20,824
legitimate. >> Okay this was one cluster
graph for those set of factors. Here's another

120
00:12:20,824 --> 00:12:27,205
cluster graph ... >> So let's compare them
one two one two for different for the

121
00:12:27,205 --> 00:12:34,167
exact same set of factors. Then notice is
that even the clusters have never changed, what

122
00:12:34,167 --> 00:12:41,708
changed is the edges and the sepsets
between them. >> That's in cluster graph. Okay

123
00:12:41,708 --> 00:12:46,694
so now let's think about message passing
in the context of this more richly

124
00:12:46,694 --> 00:12:51,878
structured cluster graph to see what it
looks like here. So here for example if

125
00:12:51,878 --> 00:12:57,390
we're interested in passing a message
from. Cluster one to cluster four. We're

126
00:12:57,390 --> 00:13:02,942
going to take psi 1 which is the factor,
the set of factors that were initially

127
00:13:02,942 --> 00:13:08,767
assigned to cluster four. But we have to
take in the message that this cluster got

128
00:13:08,767 --> 00:13:14,388
from its other neighbor two. We're going
to multiply them together and then we're

129
00:13:14,388 --> 00:13:20,077
going to sum out all of the variables that
one understands but two doesn't. So here

130
00:13:20,077 --> 00:13:25,628
for example, one understands A and C and
two doesn't, so we have to sum out over A

131
00:13:25,628 --> 00:13:35,968
and C. And that is the message delta 1,4. What about Delta 4-1? Delta 4-1 is

132
00:13:35,968 --> 00:13:45,028
the message goes in the other direction.
And here, notice that four gets

133
00:13:45,028 --> 00:13:51,283
messages from all sorts of other
clusters. So in addition to its original

134
00:13:51,533 --> 00:13:57,845
factor of psi 4, it gets a message
from cluster two. It gets a message from

135
00:13:57,845 --> 00:14:04,297
cluster five then it gets a message from
cluster three each over its own scope. All

136
00:14:04,297 --> 00:14:09,549
of these are going to be multiplied
together to give the current, most

137
00:14:09,549 --> 00:14:14,725
informed beliefs about, about the
variables B and E, which are then

138
00:14:14,725 --> 00:14:20,652
marginalizing over E, which cluster one
doesn't understand to produce a message

139
00:14:20,652 --> 00:14:26,804
over B. And once again, we know that the
message from one is not used to inform the

140
00:14:26,804 --> 00:14:35,238
message that four sends back. So that
gives us overall the following expression

141
00:14:35,238 --> 00:14:42,636
for message passing, between cluster i and
cluster j so delta ij, over the scope of

142
00:14:42,636 --> 00:14:49,518
this which is the sepset, Sij and
that has the following general expression.

143
00:14:49,518 --> 00:14:56,571
It takes the factors initially assigned to
cluster i, multiplies in all of the

144
00:14:56,571 --> 00:15:11,469
incoming messages. Other than from j.
Multiply that all together, sums out the

145
00:15:11,469 --> 00:15:20,642
variables that cluster j doesn't know
about. So everything that's in the scope

146
00:15:20,642 --> 00:15:28,329
of Ci, but not in the scope of Cj. And
that gives us a factor over the sepset

147
00:15:28,329 --> 00:15:36,004
that is produced as a message. So putting
that together that gives us an algorithm

148
00:15:36,004 --> 00:15:41,007
which is generally called belief
propagation for the reasons that the

149
00:15:41,007 --> 00:15:46,285
clusters are propagating, if you will,
informed beliefs to each other. And here

150
00:15:46,285 --> 00:15:51,699
is the summary of the algorithm. Each
factor phi is first assigned to a cluster.

151
00:15:51,699 --> 00:15:56,908
That is used to construct our initial
potentials. These psi's that we talked

152
00:15:56,908 --> 00:16:03,633
about. We initialize all of the messages
before anybody starts communicating to be 1.

153
00:16:03,633 --> 00:16:09,689
And then we repeat the following process.
We select some edge in the graph between

154
00:16:09,689 --> 00:16:15,893
adjacent clusters and we pass the message
between cluster i and cluster j over that

155
00:16:15,893 --> 00:16:22,023
edge. Okay? And we repeatedly and this is
the expression for that message. It's the

156
00:16:22,023 --> 00:16:28,080
one that we saw on the previous slide. And
that process is repeated again and again.

157
00:16:29,640 --> 00:16:34,740
At the end of the process, we, now, a
cluster needs to know what to believe

158
00:16:34,740 --> 00:16:40,540
about the variables that it understands.
And so it takes all of the it takes its

159
00:16:40,540 --> 00:16:45,781
own initial beliefs, and all of the
information that it got from all of its

160
00:16:45,781 --> 00:16:54,470
neighbors. Multiplies it all together and
that produces these things which are called

161
00:16:54,470 --> 00:17:05,098
beliefs. Now there's several important,
aspects of this algorithm that are left

162
00:17:05,098 --> 00:17:12,348
undefined. And that we're gonna need to
talk about, later on. The first of these

163
00:17:12,348 --> 00:17:19,865
is repeat until when? When do we decide
that we're done, and that we can stop? And

164
00:17:19,865 --> 00:17:26,106
we'll talk about that in the context of
different variants of this algorithm,

165
00:17:26,106 --> 00:17:31,240
later on. The second thing that's left
undefined is how I select each of the

166
00:17:31,240 --> 00:17:36,542
edges, how do I select the edges, which
edge do I select to pass messages over? So

167
00:17:36,542 --> 00:17:41,645
here there is, you know, the obvious
simple thing, which is just to go in some

168
00:17:41,645 --> 00:17:47,079
prespecified order and that's one option,
is round robin message passing. But it

169
00:17:47,079 --> 00:17:52,580
turns out that there are better strategies
than that and we'll talk about that too.

170
00:17:54,400 --> 00:18:01,582
So, is this algorithm any good? Well, it
turns out that, you know, yes and no. So

171
00:18:01,582 --> 00:18:08,947
first of all, if you pass messages over a
graph like the one that I showed before.

172
00:18:08,947 --> 00:18:15,856
Like, the, you know, little A, B, C, D
loop. Eventually, you see that we achieve

173
00:18:15,856 --> 00:18:22,948
convergence. So this is, here we can see
that, eventually, we do converge to some

174
00:18:22,948 --> 00:18:31,165
probability. But, that probability is a
little bit off. That is, the answer is not

175
00:18:31,165 --> 00:18:36,402
exact. Now in general, with exceptions
that we'll talk about, this is an

176
00:18:36,402 --> 00:18:43,133
approximate algorithm. Which shows that
there's no free lunch. The problem was

177
00:18:43,133 --> 00:18:49,512
NP hard, it's not like I have an easy
way of solving it. So given all these

178
00:18:49,512 --> 00:18:54,022
problems with the belief propagation
algorithm, what makes us think that it's

179
00:18:54,022 --> 00:18:59,917
an effective algorithm to use? When the
algorithm was. [inaudible] discovered in

180
00:18:59,917 --> 00:19:05,013
the 1990s Murphy, Weiss, and Jordan, as
well as others looked at its performance

181
00:19:05,013 --> 00:19:09,919
in the context of real networks and
specifically networks that have a lot of

182
00:19:09,919 --> 00:19:14,888
loops, which is what causes [inaudible] to
misbehave. And so here is an example

183
00:19:14,888 --> 00:19:20,239
network. It's, it's called the pyramid
network. It's a network that is analogous

184
00:19:20,239 --> 00:19:25,526
to one that arises in image analysis. And
what we, what they showed is that when you

185
00:19:25,526 --> 00:19:29,562
compute on the one hand the exact
marginals. On the X axis. And for

186
00:19:29,562 --> 00:19:34,210
different marginals in the network. And on
the Y axis, we see the marginals computed

187
00:19:34,210 --> 00:19:38,522
by loopy belief propagation. We see
that the marginals, by and large, sit

188
00:19:38,522 --> 00:19:42,834
almost exactly on a straight line, with
few exceptions. So you'll see that the

189
00:19:42,834 --> 00:19:47,214
loopy belief propagation is very close to
accurate on this network. Here's another

190
00:19:47,214 --> 00:19:52,615
network, this is a simplified version of a
medical diagnostic network and once again

191
00:19:52,615 --> 00:19:57,952
you can see that the when it compared the
correct marginal on the x axis to the

192
00:19:57,952 --> 00:20:02,710
belief propagation marginals on y axis,
the marginal fit almost exactly on

193
00:20:02,710 --> 00:20:07,661
straight line which shows that again
they're very close... The propagation is

194
00:20:07,661 --> 00:20:13,341
very close to accuracy. So, to summarize,
the belief propagation algorithm passes

195
00:20:13,341 --> 00:20:19,065
messages over a graph of clusters that are
connected to each other via sepsets. The

196
00:20:19,065 --> 00:20:24,788
adjacent clusters pass information to each
other in these messages transmitting

197
00:20:24,788 --> 00:20:30,305
information only about the variables in
the sepset which are the ones that they

198
00:20:30,305 --> 00:20:36,288
have in common. The message that cluster-i
sends to cluster-j, summarizes everything

199
00:20:36,288 --> 00:20:42,036
that a i knows about the variables in the
sepset, except for information that it

200
00:20:42,036 --> 00:20:47,639
obtains from j, so that one avoid direct
double counting of the same piece of

201
00:20:47,639 --> 00:20:53,361
evidence where j gets his own information
back again by i. We've seen that the

202
00:20:53,361 --> 00:20:59,894
algorithm may not converge. And it can have
this oscillatory behavior, And that the

203
00:20:59,894 --> 00:21:06,052
resulting beliefs are pseudo-marginals, in
that they are not necessarily the exact

204
00:21:06,052 --> 00:21:11,759
marginals from a theoretical perspective.
But nevertheless, as we've seen, the

205
00:21:11,759 --> 00:21:17,917
algorithm actually performs quite well in
a range of practical applications, which

206
00:21:17,917 --> 00:21:20,320
is why it's quite commonly used.