1
00:00:01,160 --> 00:00:06,752
So now, we're going to look more closely
into the belief propagation algorithm, and

2
00:00:06,752 --> 00:00:12,207
understand some of the improper, important
properties that it has. So here is our

3
00:00:12,207 --> 00:00:17,595
example cluster graph, with the four
clusters over the loop. And now, let's

4
00:00:17,595 --> 00:00:22,982
remind ourselves that the cluster beliefs
are defined to be the product of the

5
00:00:22,982 --> 00:00:28,438
cluster, of the factors assigned to the to
the clusters, psi 1 up to

6
00:00:28,438 --> 00:00:33,826
psi 4, times the product of the
messages that were incoming into the

7
00:00:33,826 --> 00:00:39,953
clusters. So for example, the beliefs over
cluster one is psi 1 of AB times the

8
00:00:39,953 --> 00:00:46,128
message coming in from cluster four, whose
scope is A and the message coming in from

9
00:00:46,128 --> 00:00:52,664
cluster two, whose scope is B. Now, a
cluster graph is said to calibrated. If

10
00:00:52,664 --> 00:00:57,582
the clusters agree with each other. So
specifically, if, in terms of their

11
00:00:57,582 --> 00:01:03,114
beliefs, beta i, if we were to ask cluster
one what it thinks about, say, a variable

12
00:01:03,114 --> 00:01:08,578
B. And we were to ask cluster two what it
thinks about the variable B, they would

13
00:01:08,578 --> 00:01:14,316
agree with each other. Formally, this says
that if we marginalize out the belief that

14
00:01:14,520 --> 00:01:19,984
say, cluster I. And marginalize out the
beliefs in cluster J. And we asked them

15
00:01:19,984 --> 00:01:25,169
what they agree about their joint
sepset. Sij, they would agree

16
00:01:25,169 --> 00:01:31,551
with each other in terms of the, marginal
beliefs. Now, an important property of

17
00:01:31,551 --> 00:01:37,212
cluster graph, belief propagation, is that
convergence of the belief propagation

18
00:01:37,212 --> 00:01:42,665
algorithm implies calibration. So to
understand why that's the case, let's, go

19
00:01:42,665 --> 00:01:47,911
through a simple derivation. So the
convergence of belief propagation occurs

20
00:01:47,911 --> 00:01:53,364
when the message at the next time step
equals the message at the previous time

21
00:01:53,364 --> 00:01:59,232
step. So, now let's see what the
implications of that are. So, if this is

22
00:01:59,232 --> 00:02:05,690
the, message at the next time step, it's
computed as, the product of the.

23
00:02:05,902 --> 00:02:11,580
psi i's, which are the factors
assigned to the, to the cluster i, times

24
00:02:11,580 --> 00:02:20,256
all of the messages. Other. Except for.
Cluster j. And those are all multiplied

25
00:02:20,256 --> 00:02:26,084
together and marginalized out over the
sepset. So now let's remind ourselves of

26
00:02:26,084 --> 00:02:32,206
what the beliefs would be at this point in
the process if you were to compute them.

27
00:02:32,206 --> 00:02:38,181
And that's derived from this expression
over here. So this is the same psi i that

28
00:02:38,181 --> 00:02:44,854
we have over here and this is the product
of all messages. So if this, if here, we

29
00:02:44,854 --> 00:02:51,344
have the product of psi i, and all messages
except one. And here we have psi i and all

30
00:02:51,344 --> 00:02:57,677
messages, we can equally well rewrite it
in this form over here, where we multiply

31
00:02:57,677 --> 00:03:03,775
in all of the messages, and then divide
out the one that wasn't included, delta j,i

32
00:03:03,775 --> 00:03:11,591
So now, because of convergence, we
have that this is equal to, this is equal

33
00:03:11,591 --> 00:03:19,467
to delta ij, because of this equality over
here. And so if we rewrite that, we can

34
00:03:19,467 --> 00:03:27,639
see that we have that delta ij times delta
ji is equal to this summation over here.

35
00:03:27,639 --> 00:03:35,515
Because we can multiply delta ji on the
right hand side by delta ij on the left

36
00:03:35,515 --> 00:03:42,796
hand side. So we have shown that delta ji
times delta ij is, is effectively the

37
00:03:42,796 --> 00:03:50,335
marginal over the beliefs at that point in
the process. But we can equally well using

38
00:03:50,335 --> 00:03:57,696
the identical argument, show that delta ji
times delta ij is also the marginal over

39
00:03:57,696 --> 00:04:04,637
the beliefs for cluster J. So if this is
the beliefs for cluster I. This is the

40
00:04:04,637 --> 00:04:11,083
beliefs for cluster J and so and, but
we've shown that in both cases. The

41
00:04:11,083 --> 00:04:16,119
marginals are equal to the same
expression, which is the product of the

42
00:04:16,119 --> 00:04:22,076
messages on both sides of the link. And so
because both expressions are equal to the

43
00:04:22,076 --> 00:04:27,750
same thing they must be equal to each
other and this is exactly the calibration

44
00:04:27,750 --> 00:04:33,636
property that we were trying to prove. So
we've shown the convergence of the belief

45
00:04:33,636 --> 00:04:39,523
propagation algorithm implies calibration.
This expression, which corresponds to the

46
00:04:39,736 --> 00:04:47,374
sepset beliefs. Cuz it's the marginal over
the cluster beliefs is called mu I j. And

47
00:04:47,374 --> 00:04:53,385
it's an expression that we'll use a little
bit later. In particular, one of the

48
00:04:53,385 --> 00:04:59,623
important properties that we get by
putting these pieces together. Is another

49
00:04:59,623 --> 00:05:05,780
property called reparameterization. Now that's a
bit of a mouthful. Let's first do the

50
00:05:05,780 --> 00:05:12,504
derivation and understand what the word
means. So remember that as we run belief

51
00:05:12,504 --> 00:05:19,284
propagation it'll be evident that we have
these beliefs over the clusters. Which are

52
00:05:19,284 --> 00:05:24,778
defined in this expression. So,
specifically for example we have for

53
00:05:24,778 --> 00:05:30,743
cluster one we have would have psi1
times delta 4-1 times delta 2-1 and

54
00:05:30,743 --> 00:05:37,022
similarly for these other clusters. We
also just now defined these cluster, these

55
00:05:37,022 --> 00:05:44,975
sepset beliefs. Which are, which we've
just shown are a product of two messages

56
00:05:44,975 --> 00:05:50,636
on the two differ-, going in each
direction. So, specifically here we would

57
00:05:50,636 --> 00:05:56,372
have, for example that mu of one two is
equal to delta one two times delta two

58
00:05:56,372 --> 00:06:02,011
one. Now if we look at this graph, with
all these, all these little factors

59
00:06:02,011 --> 00:06:07,946
attached to the clusters and the sepsets,
we see that there's a lot of repetition

60
00:06:07,946 --> 00:06:13,584
here. So delta 4-1 appears, for example,
here, but it also appears there. And, in

61
00:06:13,584 --> 00:06:19,222
fact, if we look at it, we see that each
of these expressions appears, each of

62
00:06:19,222 --> 00:06:25,379
these message expressions appears exactly
twice. So Delta 4-1 appears here and here.

63
00:06:25,379 --> 00:06:31,752
And, for example, delta 1-2 appears here
and, and here. And so if we write all of

64
00:06:31,752 --> 00:06:39,335
these together in, in a different form, we
can see that we, if we multiply all of the

65
00:06:39,335 --> 00:06:47,747
beliefs and divide by all of the sepsets.
We would end up with multiplying in delta

66
00:06:47,747 --> 00:06:55,841
four one, for example, on the on the
belief side but then canceling it out when

67
00:06:55,841 --> 00:07:03,914
we divide by nu one comma four. And
similarly delta one two would be

68
00:07:03,914 --> 00:07:11,095
multiplied in on. In terms of beta two,
but then canceling out in the denominator

69
00:07:11,095 --> 00:07:17,176
in Mu one two. So, if we wanted to write
this in a little bit of a broader,

70
00:07:17,425 --> 00:07:24,065
setting. So if we have a product of the
beliefs over here, multiplied, and then

71
00:07:24,065 --> 00:07:30,456
divided by a product of all of the
sepsets, we can see that this numerator is

72
00:07:30,456 --> 00:07:36,847
equal to the product over i, of psi i,
times the product of all of the incoming

73
00:07:36,847 --> 00:07:43,819
messages into clique i. The denominator is
simply equal to the product of all of the

74
00:07:43,819 --> 00:07:49,897
messages on each direction. And we can see
that, here, we're just counting the same

75
00:07:49,897 --> 00:07:55,795
message in two different ways. And so,
each message appears once in the numerator

76
00:07:55,795 --> 00:08:01,552
and once in the denominator, which means
that they all cancel with each other. And

77
00:08:01,552 --> 00:08:07,237
so what we end up with is the product of
all of the initial potentials psi i. And

78
00:08:07,237 --> 00:08:18,361
that product is simply the unnormalized.
Measure. And so. The implication of this

79
00:08:18,361 --> 00:08:24,020
is that this expression over here. This
ratio is simply a different set of

80
00:08:24,020 --> 00:08:29,893
parameters that captures the original
un-normalized measure that defines our

81
00:08:29,893 --> 00:08:35,918
distribution. And so we haven't lost
information. No information lost. As, as a

82
00:08:35,918 --> 00:08:42,019
result of belief propagation algorithm.
The representation of the unnormalized

83
00:08:42,019 --> 00:08:47,892
measure is still there just using a
different set of parameters, specifically

84
00:08:47,892 --> 00:08:53,845
the cluster sepsets, the cluster beliefs and
the sepset beliefs. So, to summarize.

85
00:08:53,845 --> 00:08:59,012
We've seen that, at convergence of belief
propagation. The cluster graph beliefs all

86
00:08:59,012 --> 00:09:03,790
agree with each other on the variables
that are shared among them. And as a

87
00:09:03,790 --> 00:09:09,153
consequence of that, the cluster graph
beliefs are simply an alternative

88
00:09:09,153 --> 00:09:14,516
parameterization of the original
un-normalized density. But one that has

89
00:09:14,516 --> 00:09:20,698
this nice calibration property, which
allows us to read, off information, about

90
00:09:20,698 --> 00:09:26,508
a variable from any clique in which it
appears. And so, we have reparameterized

91
00:09:26,508 --> 00:09:31,872
the original distribution into a more
convenient and easily usable form.