1
00:00:01,480 --> 00:00:05,253
We previously used the variable
elimination algorithm as a way of proving

2
00:00:05,253 --> 00:00:08,721
the correctness of the clique tree
algorithm. It turns out that this

3
00:00:08,721 --> 00:00:12,750
relationship can also be used to answer
another fundamental question regarding

4
00:00:12,750 --> 00:00:16,677
clique trees. Which is the question of
where clique trees come from. Or rather,

5
00:00:16,677 --> 00:00:20,502
how we might construct a little clique
tree. In order to do that, what we're

6
00:00:20,502 --> 00:00:24,480
going to do is we're going to look at a
run of variable elimination, and we're

7
00:00:24,480 --> 00:00:28,458
going to see how we might reinterpret it
as a clique tree, as a clique tree

8
00:00:28,458 --> 00:00:32,527
run. In order to do that, let's
look at the variable elimination

9
00:00:32,527 --> 00:00:37,273
algorithm, and try and take a clique tree
view of what it's doing. So the variable

10
00:00:37,273 --> 00:00:41,960
elimination algorithm, as a reminder,
starts by, take a series of steps, where in

11
00:00:41,960 --> 00:00:45,886
each step, it creates a large factor,
which, for the purposes of this

12
00:00:45,886 --> 00:00:50,398
discussion, we're going to call lambda I.
And what it does, and it does that by

13
00:00:50,398 --> 00:00:55,468
taking a bunch of factors, and multiplying
them together. When that is done, we

14
00:00:55,468 --> 00:01:00,984
eliminate a variable from lambda I, and
that gives us a new smaller scope factor,

15
00:01:00,984 --> 00:01:06,638
which we're going to call Tau I. And Tau I
is put into the pool of factors that we

16
00:01:06,638 --> 00:01:12,223
have available to us. Which means that, at
some point, we're going to use it in the

17
00:01:12,223 --> 00:01:17,670
context of computing another large factor,
Lambda J, when we multiply a bunch of,

18
00:01:17,877 --> 00:01:24,453
factors together. So now let's think about
this process in terms of passing messages

19
00:01:24,453 --> 00:01:31,389
in, in in-between computational entities
in the same way that we had when we were

20
00:01:31,389 --> 00:01:37,680
doing message passing algorithms. So we're
going to look at these intermediate

21
00:01:37,680 --> 00:01:44,293
factors lambda I as the clique in a clique
tree. And the tau I's that are used, that

22
00:01:44,293 --> 00:01:50,694
are produced in the context of one clique.
And utilized by a different clique, we're

23
00:01:50,694 --> 00:01:57,033
going to consider that to be a message. So
these little factors that are produced by

24
00:01:57,033 --> 00:02:03,296
one lambda and consumed by another lambda
can be viewed as a message that's passed

25
00:02:03,296 --> 00:02:09,560
from the clique that corresponds to the
first lambda, and received by the second

26
00:02:09,560 --> 00:02:15,220
lambda. So, summarizing, the variable
elimination algorithm defines the graph.

27
00:02:15,580 --> 00:02:21,551
You're going to have a cluster CI for
every factor lambda. We're going to draw

28
00:02:21,551 --> 00:02:27,598
an edge between CI and CJ if the factor
that was generated in a computation in

29
00:02:27,598 --> 00:02:33,493
which I multiply together all the factors
to produce lambda I is used in the

30
00:02:33,493 --> 00:02:39,595
computation of lambda J. And so we can
think of it as CI. Which corresponds to

31
00:02:39,595 --> 00:02:46,510
Lambda I, passing a message to CJ, which
corresponds to Lambda J, and that message

32
00:02:46,510 --> 00:02:53,391
is the Tau I that was produced by, by the
Lambda I computation. So now let's look at

33
00:02:53,391 --> 00:02:58,898
this in the context of an example. We're
going to go through the variable

34
00:02:58,898 --> 00:03:04,766
elimination process that we had for our
network that we had earlier, the enhanced

35
00:03:04,984 --> 00:03:11,360
student network. And so the first variable
elimination step multiplies together the C

36
00:03:11,360 --> 00:03:17,339
factor and CD factor. And that gives us,
this is my Lambda one. And lambda one

37
00:03:17,339 --> 00:03:25,388
produces a clique whose scope is CD, and so that
this clique over here. The next step

38
00:03:25,388 --> 00:03:32,282
eliminates D and the way in which it does
that it takes tau one and then it

39
00:03:32,282 --> 00:03:39,011
multiplied it, multiplies that my one of
my original factors phi G. And so now we have

40
00:03:39,011 --> 00:03:48,131
a, a lambda two. This is my lambda two. And
that gives me a clique whose scope is GIB,

41
00:03:48,131 --> 00:04:00,358
and since GIB used tau one. Then we have
an edge from CD to GID, whose scope is the

42
00:04:00,358 --> 00:04:09,783
variable D. The next step in the analysis
that we did before, eliminated the variable

43
00:04:09,783 --> 00:04:16,818
I and again used two of the original
factors, phi I and phi F. And it also used

44
00:04:16,818 --> 00:04:23,973
tau two. And so now we have a factor,
lambda three, whose scope is G, S and I

45
00:04:23,973 --> 00:04:30,300
because those are the variables in this
scope over here. And the message, GI, is,

46
00:04:30,300 --> 00:04:36,707
that we see here, this edge between GID
and GSI corresponds to this tau-two that

47
00:04:36,707 --> 00:04:42,799
was produced by lambda two and consumed by
lambda three. The next elimination step

48
00:04:42,799 --> 00:04:46,970
didn't use any of the, pro- factors
produced by the other, by other

49
00:04:46,970 --> 00:04:51,439
cliques. It just used one of the
original cliques, so just used phi H.

50
00:04:51,439 --> 00:04:55,909
And so note that it's currently not
connected to anything, just sitting all

51
00:04:55,909 --> 00:05:04,185
there by its lonesome. And the next step
now gets to use a, gets to use factors

52
00:05:04,185 --> 00:05:12,067
that were produced in two separate
computations, so notice. But this,

53
00:05:12,067 --> 00:05:21,702
computation for tal, for tal, for lambda
5, which is this guy. Used both,

54
00:05:21,702 --> 00:05:34,004
tau three. And tau 4. Which is why we have both
an edge from cluster three and an edge

55
00:05:34,004 --> 00:05:45,007
from cluster four. The next step that we
took. Marginalize out, s is multiplied in

56
00:05:45,007 --> 00:05:56,095
tau five. And one of the original
factors JLS and so now we have a message

57
00:05:56,095 --> 00:06:04,022
here. That's passed between cluster five
and cluster six. And finally there was the

58
00:06:04,022 --> 00:06:12,773
marginalization of l and so we have a jl
cluster. Now if you look at this. Graph,

59
00:06:12,773 --> 00:06:19,165
this clique tree, you'll notice that it's
bigger than the clique tree that we had

60
00:06:19,165 --> 00:06:25,557
for this network to begin with. And one of
the, and the reason for that is that we

61
00:06:25,557 --> 00:06:32,107
actually have three adjacent cliques where
one is a subset of the other. So JL is a

62
00:06:32,107 --> 00:06:38,289
subset. Of JSL which in turn is a subset
of GJSL. Now if you think about it,

63
00:06:38,289 --> 00:06:44,284
there's really no point to including three
cliques where one is a subset of the other

64
00:06:44,284 --> 00:06:49,929
because you might as well do all of the
computation in the first clique to begin

65
00:06:49,929 --> 00:06:55,714
with. There's no value to sort of breaking
it out into separate data structures. And

66
00:06:55,714 --> 00:07:00,942
so a typical post-processing step is to
then go ahead and remove redundant

67
00:07:00,942 --> 00:07:07,529
cliques. And just basically collapse, them
and their factors into, into the one, the

68
00:07:07,529 --> 00:07:13,634
biggest clique that subsumes them. So, in
this case, since, we had PHI JLS, which

69
00:07:13,634 --> 00:07:19,511
originally was utilized in Tau six. We're
now going to move that, and put that

70
00:07:19,511 --> 00:07:25,464
instead, in, sorry, it was used in lambda
six. We're now going to stick that into

71
00:07:25,464 --> 00:07:32,471
clique five. And so we've seen how we can
take a variable elimination process, a run

72
00:07:32,471 --> 00:07:38,965
of variable elimination, and use that to
produce what looks like a clique tree. But

73
00:07:38,965 --> 00:07:45,138
is it a clique tree? So what properties
can we prove about this output from a

74
00:07:45,138 --> 00:07:51,471
variable elimination run? Well, first is
the fact that it is in fact a tree. We

75
00:07:51,471 --> 00:07:57,744
want it to be a clique tree it better be a
tree. Why is it a tree? Because in

76
00:07:57,744 --> 00:08:04,585
variable elimination, every intermediate
factor tau, once you produce it, it gets

77
00:08:04,585 --> 00:08:09,892
consumed exactly once. Once it gets
consumed, remember, in the Variable

78
00:08:09,892 --> 00:08:15,248
Elimination Algorithm, it gets taken out
of the set of factors. And then it

79
00:08:15,248 --> 00:08:20,822
disappears, because it gets multiplied in.
And so, if you think about this as a

80
00:08:20,822 --> 00:08:26,251
directed tree, it starts out, and it
produces factors, and each factor speeds

81
00:08:26,251 --> 00:08:32,331
up into only a single other parent. And
so, as a directed tree it means that every

82
00:08:32,331 --> 00:08:43,760
cluster has. Exact- has at most one parent.
And in fact every cluster except the last

83
00:08:43,760 --> 00:08:48,248
one has exactly one parent, because
eventually everything has to be consumed

84
00:08:48,248 --> 00:08:53,090
because everything is multiplied together.
And so the variable elimination process

85
00:08:53,090 --> 00:08:57,106
induces a directed tree where we
subsequently forget about the

86
00:08:57,106 --> 00:09:04,966
directionality of the edges. The second
property that is again not difficult to

87
00:09:04,966 --> 00:09:11,055
show is of that the tree is family
preserving. And that is because each of

88
00:09:11,055 --> 00:09:17,321
the original factors was in my original
factor set. These are my original factors,

89
00:09:17,321 --> 00:09:23,510
phi, in my original factor set, big phi,
was somewhere in the variable elimination

90
00:09:23,510 --> 00:09:29,930
process. And that means it must have been
used at some point, because eventually I'm

91
00:09:29,930 --> 00:09:35,732
multiplying all factors together. And
therefore it must be contained in the

92
00:09:35,732 --> 00:09:45,543
scope of one of the, sorry this should be,
lambda I. And that lambda I by force has a

93
00:09:45,543 --> 00:09:57,340
scope. That contains. The scope. Of phi,
which is what we need for the family

94
00:09:57,340 --> 00:10:05,083
preservation property. The final property
that we had that we would like to show

95
00:10:05,083 --> 00:10:11,371
hold, is that the tree, respects or obeys the
running intersection property. And so, as

96
00:10:11,371 --> 00:10:17,350
a reminder, that property says that if you
have two clusters, CI and CJ, with a

97
00:10:17,350 --> 00:10:23,483
variable X that is present in both. Then X
needs to be in each cluster and each

98
00:10:23,483 --> 00:10:29,260
sepset in the unique path between CI and
CJ. First of all, let's convince ourselves

99
00:10:29,260 --> 00:10:34,291
that, that running intersection property
holds here and we have already seen that

100
00:10:34,291 --> 00:10:39,261
because this is actually the familiar
clique tree that we have for this example.

101
00:10:39,447 --> 00:10:44,541
In fact, we've produce that clique tree by
variable elimination using exactly the

102
00:10:44,541 --> 00:10:52,502
process that I've shown you before.
[sound]. Now let's show that however more

103
00:10:52,502 --> 00:10:57,899
generally, so we want to prove to
ourselves that if P is a tree of clusters

104
00:10:57,899 --> 00:11:03,296
that was induced by a run of variable
elimination, then P obeys the running

105
00:11:03,296 --> 00:11:09,050
intersection property. And so now remember
that this tree came from a directed run.

106
00:11:09,050 --> 00:11:13,457
And so what I'm showing you here is
actually a directed tree, where we see how

107
00:11:13,457 --> 00:11:18,260
the clusters communicate. But this is not
the same tree that we had in our example.

108
00:11:18,260 --> 00:11:22,950
It's a more complicated one to illustrate
the, sort of to make the theorem a little

109
00:11:22,950 --> 00:11:27,357
bit more interesting to show. So, in one
of those sepsets, and in exactly one of

110
00:11:27,357 --> 00:11:31,200
those sepsets, the variable X is
eliminated, because this is a run of

111
00:11:31,200 --> 00:11:36,892
variable elimination. Every variable is
eliminated exactly once. So let's imagine

112
00:11:36,892 --> 00:11:51,026
that x is eliminated, here. So this clique
over here. >> Is the last to see X, where, so

113
00:11:51,026 --> 00:12:06,955
C4 has X in it. X is in C4 and x is not in C6.
Now let's take any other Cluster that

114
00:12:06,955 --> 00:12:17,690
contains x. So, for example, assume that
cluster seven contains x. Well, if cluster

115
00:12:17,690 --> 00:12:24,276
seven contains X, and X wasn't eliminated
on this edge, because it's eliminated

116
00:12:24,276 --> 00:12:31,199
exactly once, it means that it needs to be
in the sepset, which means it was in the

117
00:12:31,199 --> 00:12:37,953
message tau that C seven produced, so it's
in tau seven. X is in the scope of tau

118
00:12:37,953 --> 00:12:43,690
seven. Which means that x also needs to be
in the scope of C3 because it was

119
00:12:43,690 --> 00:12:48,820
multiplied in. If it was multiplied in,
then it has to be in that scope. And so,

120
00:12:48,820 --> 00:12:55,826
by continuing this in exactly the same
inductive argument, we know that since X

121
00:12:55,826 --> 00:13:02,920
has to be in C3. It also needs to be in
this sepset, and so on. And so we've shown

122
00:13:02,920 --> 00:13:09,660
that X needs to be on the path from C7 to
C4. And now, let's take a different

123
00:13:09,660 --> 00:13:16,754
cluster that contains C5, contains X, for
example, C5. We can similarly show that X

124
00:13:16,754 --> 00:13:24,242
needs to be on every step along the path.
And since this is a tree. Means it needs

125
00:13:24,242 --> 00:13:32,494
to be on the path between c7 and c5. And
so that argument shows that for any pair

126
00:13:32,494 --> 00:13:38,869
of clusters, or cliques, that contain X, X
has to be on every step of the path

127
00:13:38,869 --> 00:13:48,353
between them. So to summarize. A run of
variable elimination implicitly defines a

128
00:13:48,353 --> 00:13:53,816
correct clique tree. Which means, that you
can, if you want to get a clique tree

129
00:13:53,816 --> 00:13:59,192
that has the required properties. Family
preservation and running intersection, we

130
00:13:59,192 --> 00:14:03,941
can simply simulate a run of variable
elimination. What does it means to

131
00:14:03,941 --> 00:14:09,275
stimulate? It doesn't mean that we run the
variable elimination because that would be

132
00:14:09,275 --> 00:14:14,609
an expensive process. We just figure out
what factors that would multiply and what

133
00:14:14,609 --> 00:14:19,944
scopes they would have and therefore at
what factor get used where and that gives

134
00:14:19,944 --> 00:14:25,310
me the cliques. And the connections
between them. And this is the exact

135
00:14:25,310 --> 00:14:32,127
process that we did in the simple example
that we had. And. That clique tree has a

136
00:14:32,127 --> 00:14:37,851
computational cost which is essentially
equivalent to the cost of running the

137
00:14:37,851 --> 00:14:43,355
variable elimination algorithm. Because,
if you think about the sizes of the

138
00:14:43,355 --> 00:14:49,079
cliques that are produced, they correspond
exactly to the sizes of the factors

139
00:14:49,079 --> 00:14:54,949
produced by variable elimination. So these
costs are directly comparable to each

140
00:14:54,949 --> 00:15:00,635
other. Except as we showed before, the
clique tree used dynamic programming or

141
00:15:00,635 --> 00:15:07,137
storing or caching of the messages so we
don't need to recompute the same message

142
00:15:07,137 --> 00:15:12,605
more than once. And that allows us to
produce marginals over all of the

143
00:15:12,605 --> 00:15:18,590
variables in the network at only twice
the cost of running variable elimination.

144
00:15:18,590 --> 00:15:27,930
So taking yet one other step backward,
what that means is if you care to get the

145
00:15:27,930 --> 00:15:34,988
values of the marginals for. Even not,
not necessarily even all variable but

146
00:15:34,988 --> 00:15:39,866
multiple variables, one efficient way of
doing that is to take variable

147
00:15:39,866 --> 00:15:45,499
elimination, do this simulation to figure
out what clique tree we want to build or

148
00:15:45,499 --> 00:15:50,927
how to build a clique tree and then use
that clique tree to compute all of the

149
00:15:50,927 --> 00:15:56,487
marginal by appropriate massage passing,
and. We talked about variable elimination

150
00:15:56,487 --> 00:16:01,768
and how to construct to use heuristic
solutions to construct a good variable

151
00:16:01,768 --> 00:16:07,324
elimination ordering one that gives us
relatively small factor [inaudible] along

152
00:16:07,324 --> 00:16:12,674
the way and that exact same set of
heuristics is also useful for constructing

153
00:16:12,948 --> 00:16:18,024
a small efficient clique tree to the
extent that's possible given a graph.