1
00:00:00,000 --> 00:00:05,343
We describe to believe propagation
algorithm as passing message over cluster

2
00:00:05,343 --> 00:00:10,755
graph. But we left unspecified how that
cluster graph would be constructed, and

3
00:00:10,755 --> 00:00:16,098
what properties it needs to satisfy to
support reasonable message passing. So,

4
00:00:16,098 --> 00:00:21,580
let's remind ourselves what cluster graphs
are. A cluster graph is an undirected

5
00:00:21,580 --> 00:00:26,784
graph whose nodes are clusters that
involves subset of variables and edges

6
00:00:26,784 --> 00:00:33,952
involve a sepset Sij. Which is a
subset of the, two clusters on the two end

7
00:00:33,952 --> 00:00:41,351
points. What are some properties that the
cluster graph has to satisfy? The first

8
00:00:41,351 --> 00:00:47,595
property is one called family
preservation, an obvious value. Where,

9
00:00:47,595 --> 00:00:54,620
remember that we need, given the set of
factors Phi, we need to be able to assign

10
00:00:54,620 --> 00:01:01,559
each phi k to some cluster. C alpha k such
that the fact such as the cluster can

11
00:01:01,559 --> 00:01:08,820
accommodate. The scope so it can
accommodate Phi K, oops, accommodate.

12
00:01:12,560 --> 00:01:18,664
Well, in order for the cluster graph to
allow this to be done, we need to have an

13
00:01:18,664 --> 00:01:24,539
appropriate cluster in the cluster graph.
So this imposes a constraint on the

14
00:01:24,539 --> 00:01:30,719
cluster graph that says that for every
factor phi k in my set of factors Phi, there

15
00:01:30,719 --> 00:01:39,108
exists some cluster, Ci, that, such that
Ci accommodates phi k, which means that

16
00:01:39,108 --> 00:01:45,240
you can put phi k inside this cluster.
That's the family preservation property.

17
00:01:45,600 --> 00:01:50,481
The second property's a little bit
trickier to understand, it's called the

18
00:01:50,481 --> 00:01:56,401
running intersection property. The running
intersection property, let's first read

19
00:01:56,401 --> 00:02:01,999
the definition and then understand what it
says. It says that, let's assume that we

20
00:02:01,999 --> 00:02:07,460
have a pair of clusters, Ci and Cj, and a
variable X that belongs to both of them.

21
00:02:07,460 --> 00:02:12,375
So, for example, we might have the
variable X sitting here in C 7 and

22
00:02:12,375 --> 00:02:18,064
the variable X sitting here in C 5.
This property says that there exists a,

23
00:02:18,064 --> 00:02:24,333
exists a unique path between Ci and Cj,
for which all clusters and steps that's

24
00:02:24,333 --> 00:02:30,681
along the path contain X. What does that
mean? It means that for example, should I

25
00:02:30,681 --> 00:02:38,192
choose this to be my unique path. It means
that X needs to sit here, here and here.

26
00:02:38,192 --> 00:02:44,112
So there is a connecting path that
involves X, and that path is along the

27
00:02:44,112 --> 00:02:49,494
entire route, and it involves, and that
path is unique. So let's try and

28
00:02:49,494 --> 00:02:54,407
understand the intuition between both
sides of this definition, the existence

29
00:02:54,407 --> 00:02:59,990
and the uniqueness. Imagine that I let's
do the existence first, and imagine that

30
00:02:59,990 --> 00:03:05,797
for whatever reason I decide that there is
not going to be a path over here. So there

31
00:03:05,797 --> 00:03:11,283
is no way for C7 to communicate to C3
about the variable X. Well that means that

32
00:03:11,283 --> 00:03:16,289
we now have these two separate isolated
communities each of which have some

33
00:03:16,289 --> 00:03:21,844
information about X and they can never
talk to each other about X so they're never

34
00:03:21,844 --> 00:03:27,330
going to get agree about X there's never
going to be any information transfer of

35
00:03:27,330 --> 00:03:32,817
these two, pieces of information. Well
so that's not very good which is why we need

36
00:03:32,817 --> 00:03:39,249
that path to exist. This left the exist
part. What about the unique part? The

37
00:03:39,249 --> 00:03:45,635
unique part is a little bit trickier to
understand but let's but let's try and,

38
00:03:45,860 --> 00:03:52,812
and, provide some intuition for it. Let's
imagine that I have two paths. That

39
00:03:52,812 --> 00:03:59,638
involve X. Well, so now we have to think
about this message passing algorithm. So

40
00:03:59,638 --> 00:04:06,269
C3 can send a message to C5,
with information about X. For example, I

41
00:04:06,269 --> 00:04:12,785
think X is taking the value one. I have a,
I have a factor that suggests that X takes

42
00:04:12,785 --> 00:04:18,370
the value one. Well, C5, you know,
integrates that with its own information,

43
00:04:18,370 --> 00:04:24,410
and sends it on to C2. Which sends it back
to C3. And now C3 hears from C2 that,

44
00:04:24,410 --> 00:04:29,732
ew, X needs to take the value one. Huh,
that reinforces it's beliefs that X needs

45
00:04:29,732 --> 00:04:34,717
to take the value one and so the
probability goes up. It now goes back and

46
00:04:34,717 --> 00:04:40,038
sends that information on to C5 which
sends it on to C2 which sends it back to

47
00:04:40,038 --> 00:04:45,629
C3 and then once probability in X taking
the value one goes up. And so we have this

48
00:04:45,629 --> 00:04:50,681
sort of self reinforcing loop that's going
to give rise to very extreme and very skewed

49
00:04:50,681 --> 00:04:57,575
probabilities in many examples. And so, a
way of avoiding that, is to, or at least

50
00:04:57,575 --> 00:05:05,008
reducing that risk, is to, is to prevent
These kinds of feedback loops. Now it's

51
00:05:05,008 --> 00:05:11,234
important to realize that by preventing
these loops that only reduces as opposed

52
00:05:11,234 --> 00:05:16,999
to eliminates the problem. And
specifically this is kind of a little bit

53
00:05:16,999 --> 00:05:23,225
of a digression but it's important to know,
is that imagine, for example, we have X

54
00:05:23,225 --> 00:05:37,566
and Y that are very strongly correlated.
So here we have, for example, X and Y. And

55
00:05:37,566 --> 00:05:51,297
here we have a path. That involves Y. Mm.
So now, what's going to happen is that C3

56
00:05:51,297 --> 00:05:57,447
sends information to C5 about X. C5
translates that to information about Y. Y

57
00:05:57,447 --> 00:06:03,192
should take the value one. That
information about Y goes back to C3 and

58
00:06:03,192 --> 00:06:09,827
increases the probability of X taking the
value one. Now, this is a little bit of a

59
00:06:09,827 --> 00:06:15,734
forward looking hint about some of the
issues that we'll see with belief

60
00:06:15,734 --> 00:06:23,370
propagation later on. Which is that belief
propagation does very poorly when we have

61
00:06:23,370 --> 00:06:37,468
strong correlations. And that's because of
these feedback loops. So, the more

62
00:06:37,468 --> 00:06:43,268
skewed the probabilities in your graphical
model, the harder time belief propagation

63
00:06:43,268 --> 00:06:49,768
has, in terms of the results that it gets.
So with that digression, aside, let's go

64
00:06:49,768 --> 00:06:54,675
back to the running intersection property.
And let's provide an alternative

65
00:06:54,675 --> 00:06:59,649
definition of the running intersection
property, just to give ourselves some

66
00:06:59,649 --> 00:07:04,360
additional intuition. The running
intersection property is equivalent to

67
00:07:04,360 --> 00:07:11,137
saying that, for any X. The set of
clusters and sepsets that contain X form a

68
00:07:11,137 --> 00:07:18,247
tree. So for example if we have X here,
here, here, here, here, and here We can

69
00:07:18,247 --> 00:07:23,888
see, that the set of a cluster is a subset
that contain X form a tree. It has to be

70
00:07:23,888 --> 00:07:29,876
connected because of the existence of the
path and it can't be a, a nontree because,

71
00:07:29,876 --> 00:07:35,517
because that will give us two different
paths. So that's a different view of this.

72
00:07:35,517 --> 00:07:41,088
As you can think of each, variable
inducing it's own little tree across which

73
00:07:41,088 --> 00:07:47,923
information about that variable flows in
the graph. So now let's go back with that

74
00:07:47,923 --> 00:07:53,235
definition and consider some cluster
graphs that we might adopt for this

75
00:07:53,235 --> 00:07:59,130
example that we've seen before. So here we
have our five clusters, and let's check

76
00:07:59,130 --> 00:08:04,515
whether it satisfies the running
intersection property. We've already done

77
00:08:04,515 --> 00:08:10,483
family preservation for a particular set
of factors, so let's consider for example

78
00:08:10,483 --> 00:08:15,895
the variable B. And we can see that we
have B here, here, here. Here. Here.

79
00:08:15,895 --> 00:08:26,697
Here. And Here. And we can see that that's
a tree. Here's my tree. Note very

80
00:08:26,697 --> 00:08:32,989
carefully that B isn't here. If B were
here, that wouldn't satisfy the running

81
00:08:32,989 --> 00:08:39,363
intersection property. That would be an
illegal cluster graph. [inaudible] on a

82
00:08:39,363 --> 00:08:45,655
subsequent slide. Here is an illegal
cluster graph. It violates the running

83
00:08:45,655 --> 00:08:54,000
intersection property. Why? Because here
is B, and here is a bunch of other B's.

84
00:08:56,760 --> 00:09:02,228
And there's no way to connect cluster two
to any of the others so this one violates

85
00:09:02,228 --> 00:09:13,240
the existence. This one which we just
talked about violates the uniqueness.

86
00:09:18,260 --> 00:09:28,754
Because, here we have. The, all of the
clusters and sepsets that involve B, and

87
00:09:28,754 --> 00:09:34,146
there's this nice little loop over here,
that has, two paths between say, cluster

88
00:09:34,146 --> 00:09:41,228
one and cluster four. If we wanted to take
the cluster graph, and still allow

89
00:09:41,228 --> 00:09:46,425
communication between B and C. So we want
to have, for example, we want cluster one

90
00:09:46,425 --> 00:09:52,135
and cluster two to be able to, transmit to
each other, information about how B and C

91
00:09:52,135 --> 00:09:58,673
are correlated with each other, which they
can't do, in this graph over here. So, one

92
00:09:58,673 --> 00:10:05,770
way to do that, is to, have, we have
eliminated in this case, this edge that we

93
00:10:05,770 --> 00:10:13,639
had over here that involved B, and now
once again we have B. Seeing a tree in the

94
00:10:13,639 --> 00:10:18,604
graph. Now focused on B here but it's not
difficult to convince yourselves that

95
00:10:18,604 --> 00:10:23,631
other that other nodes also satisfy, that
we satisfy the running intersection

96
00:10:23,631 --> 00:10:28,407
property also with respect to other
variables. So just as an example, here is

97
00:10:28,407 --> 00:10:33,497
the set of clusters and sepsets involved
in D, and that too is a tree and, here is

98
00:10:33,497 --> 00:10:38,085
the one's involving E, and that too is a
tree and so on. So and running

99
00:10:38,085 --> 00:10:43,336
intersection property needs to hold for
every, for every one of the variables. How

100
00:10:43,336 --> 00:10:49,220
do we construct a cluster graph that has,
has a desired properties? One very simple,

101
00:10:49,423 --> 00:10:54,719
And, in some ways, degenerate. But still,
because of its simplicity, very often

102
00:10:54,719 --> 00:10:59,948
used, is a cluster graph called the bethe
cluster graph. And that's a term from

103
00:10:59,948 --> 00:11:05,651
statistical physics, where people use this
kind of approximation to energy functions,

104
00:11:05,651 --> 00:11:11,287
in, in some, in some calculations, in, in
statistical physics. So, here we have, in

105
00:11:11,287 --> 00:11:16,583
the bethe cluster graph, we have two types
of clusters. We have big clusters and

106
00:11:16,583 --> 00:11:22,723
little clusters. The big clusters, these
are the big clusters. Correspond to

107
00:11:22,723 --> 00:11:37,950
factors. In Phi. So for each phi k we have
a cluster factor cluster whose scope is

108
00:11:37,950 --> 00:11:46,176
exactly the scope of phi k. That's the big
clusters. The little clusters correspond

109
00:11:46,176 --> 00:11:52,886
to individual variables. So for each Xi we
have a cluster who's scope is just the

110
00:11:52,886 --> 00:12:03,280
single variable Xi itself. Now, we're
going to connect Ck to Xi, exactly when Xi

111
00:12:03,280 --> 00:12:12,752
is a subset of Ck, is a member of Ck. So
if we consider the set of factors that we

112
00:12:12,752 --> 00:12:18,012
had before, we can now produce a different
cluster graph than the one that we had

113
00:12:18,012 --> 00:12:23,142
previously, this is a bethe cluster graph.
Notice that we have these big clusters

114
00:12:23,142 --> 00:12:29,692
this are these four, sorry these five. And
we have these little clusters

115
00:12:29,692 --> 00:12:35,776
corresponding to A, B, C, D, E and F. And
we can see that we have an edge for

116
00:12:35,776 --> 00:12:41,900
example between the ABC cluster and the A
cluster, the B cluster and the C cluster.

117
00:12:41,900 --> 00:12:47,074
And that's how messages are passed and you
can see that this graph is degenerate in

118
00:12:47,074 --> 00:12:51,941
the sense that it only allows information
about singletons to be passed and it

119
00:12:51,941 --> 00:12:56,992
loses, in every message passing step, any
information about the correlation between

120
00:12:56,992 --> 00:13:01,612
variables. But nevertheless, it's simple
to construct and it's guaranteed to

121
00:13:01,612 --> 00:13:06,294
satisfy the running intersection property.
Why is that? So let's consider for

122
00:13:06,294 --> 00:13:11,345
example, all of the factors that involve
the variable D. So here is, what are the

123
00:13:11,345 --> 00:13:16,447
clusters that involve the variable D?
Well, there's this one. And then there's

124
00:13:16,447 --> 00:13:23,353
this that, that, those are where we have
the sepsets, which I didn't mark and then

125
00:13:23,353 --> 00:13:30,690
these ones. And notice that it's a tree by
definition because D doesn't appear on any

126
00:13:30,690 --> 00:13:37,337
other sepsets except these ones. And so,
the tree is a start. It's the variable

127
00:13:37,337 --> 00:13:44,242
cluster plus the big factors that contain
the variable. So v is, in this case, the

128
00:13:44,242 --> 00:13:50,690
three clusters that contain it. So to
summarize. We have, we kno-, we, looked at

129
00:13:50,690 --> 00:13:55,228
the properties of the cluster graph, and
we see that's there's two of them that it

130
00:13:55,228 --> 00:13:59,323
needs to satisfy. The first is family
preservation, which allows the set of

131
00:13:59,323 --> 00:14:03,750
factors to be encoded. And the second is
the running intersection property, which

132
00:14:03,750 --> 00:14:08,011
serves two purposes. The first is to
connect all information about any single

133
00:14:08,011 --> 00:14:12,051
variable, so that it can all be
transmitted through the graph. But without

134
00:14:12,051 --> 00:14:15,925
creating tight feedback loops that are
going to give rise to the self

135
00:14:15,925 --> 00:14:20,174
reinforcement and highly inaccurate
answers. Is the bethe cluster graph is

136
00:14:20,174 --> 00:14:24,740
often the first default that people use
because it's easy. So the final is

137
00:14:24,740 --> 00:14:29,933
guaranteed to be correct. But richer
cluster graph structures of the type that

138
00:14:29,933 --> 00:14:35,062
we talked about can offer very different
and sometimes significantly better trade

139
00:14:35,062 --> 00:14:40,192
offs with respect to on the one hand the
computational cost, and on the other hand

140
00:14:40,380 --> 00:14:45,572
which of course is you start is increasing
the amount of the sizes of the messages

141
00:14:45,572 --> 00:14:50,451
that are passed that can grow more
expensive but at the same time, allow us

142
00:14:50,451 --> 00:14:55,291
to improve. The preservation of the
dependencies as messages are passed in the

143
00:14:55,291 --> 00:15:00,331
graph so that more information is actually
kept and not lost in this message passing