1
00:00:00,000 --> 00:00:04,806
We've shown that the clique tree algorithm
has some pretty cool properties, that it

2
00:00:04,806 --> 00:00:09,144
guarantees that we achieve the correct
marginal, at every single clique, and

3
00:00:09,144 --> 00:00:13,893
therefore that these marginals necessarily
agree with each other. We have also seen

4
00:00:13,893 --> 00:00:18,406
that these marginals can be computed
using a single upward and downward pass

5
00:00:18,406 --> 00:00:22,979
over the clique tree. So fairly efficient
computation. But we also know that the

6
00:00:22,979 --> 00:00:27,375
problem of inference and the problem is
the graphical models is an NP hard

7
00:00:27,375 --> 00:00:31,889
problem, and so somewhere over there,
there must be a catch. That is there must

8
00:00:31,889 --> 00:00:36,252
be a computational cost that occurs, at least
in certain cases when we run the clique

9
00:00:36,252 --> 00:00:39,751
tree algorithm. And what we're going to
do now, is we're going to try and

10
00:00:39,751 --> 00:00:48,585
understand where that hidden cost might
lie. So while what we are going to do. So

11
00:00:48,585 --> 00:00:54,610
in order to analyze the computational
complexity of a clique tree, we are going

12
00:00:54,610 --> 00:01:00,559
to define a little bit of notation. So
let's consider an edge i,j, in the clique

13
00:01:00,559 --> 00:01:06,508
tree, T, and let's assign a little bit of
notation. We are going to divide the

14
00:01:06,508 --> 00:01:12,685
variables into three groups. There is this
group, so here what we have is a clique

15
00:01:12,685 --> 00:01:18,023
tree; here is Ci, and Cj. They are
adjacent cliques and they are connected to

16
00:01:18,023 --> 00:01:22,941
each other via sepset Sij. And then
there's this whole clique tree, whole

17
00:01:22,941 --> 00:01:28,352
bunch of cliques on the left side and
whole bunch of cliques on the right side.

18
00:01:28,352 --> 00:01:33,832
We are going to divide these variables
into these three groups. W, less, W that's

19
00:01:33,832 --> 00:01:39,938
on the i side of the i,j edge. Are the
variables that are just. In this group

20
00:01:39,938 --> 00:01:47,132
here not counting the sepset which is
going to appear in both types. W that's on

21
00:01:47,132 --> 00:01:54,236
the J side is over there. And Sij is the
stuff in the middle. So these are three

22
00:01:54,236 --> 00:02:01,790
mutually exclusive and exhaustive groups,
that partition all the variables in the

23
00:02:01,790 --> 00:02:09,377
tree. And now here is a, an interesting and
quite enlightening theorem, that says the

24
00:02:09,377 --> 00:02:15,720
clique tree T satisfies the running
intersection property, if and only if, for

25
00:02:15,720 --> 00:02:21,980
every sepset ij, we have that the
variables on the left side of the edge are

26
00:02:21,980 --> 00:02:28,824
independent of the variables on the right
side of the edge given the variables on

27
00:02:28,824 --> 00:02:36,408
the middle of the edge. That is, these
variables, the sepset, separate. The left

28
00:02:36,408 --> 00:02:43,533
side from the right side. Now remember
that the running intersection property was

29
00:02:43,533 --> 00:02:48,757
the critical property that we used to
prove correctness, of the clique tree

30
00:02:48,757 --> 00:02:54,405
algorithm. So this is a, coming up with
this condition that tells us exactly when

31
00:02:54,405 --> 00:03:00,123
running intersection holds is important
because this is the defining property for

32
00:03:00,123 --> 00:03:06,054
all of those nice behaviors that we talked
about earlier in terms of the clique tree

33
00:03:06,054 --> 00:03:11,267
algorithm. So let's try and convince
ourselves of this by looking at a concrete

34
00:03:11,267 --> 00:03:15,905
example first. Let's look at the
clique tree that we have over here and

35
00:03:15,905 --> 00:03:20,804
let's for example focus on this sepset
which has the variables G and S. And

36
00:03:20,804 --> 00:03:26,490
variables on the left side of that sepset
excluding variables G and S are I. D and C.

37
00:03:26,490 --> 00:03:32,466
On the other hand, the variables on the
right side of this sepset, again excluding

38
00:03:32,466 --> 00:03:37,705
G and S, are H, J, and L. So now let's
look at where these variables place

39
00:03:37,705 --> 00:03:42,943
themselves on the graph structure over
here, which is the induced graph

40
00:03:42,943 --> 00:03:48,698
corresponding to the Markov network which
we derived from the factors in this

41
00:03:48,698 --> 00:03:54,822
Bayesian network. So Bayesian network CPDs
produce factors. The factors give us this

42
00:03:54,822 --> 00:04:00,828
induced Markov network. So, where are the
sepset variables G and S? Those are over

43
00:04:00,828 --> 00:04:07,027
here. Where are the variables on the left
hand side? These are the blue variables C,

44
00:04:07,027 --> 00:04:12,545
I, D and they're sitting over there. And,
the green variables H, J and L, are

45
00:04:12,545 --> 00:04:17,987
sitting over here. And, a simple
inspection can show us that are no paths

46
00:04:17,987 --> 00:04:24,337
or trails, between the blue variables and
the green variables that do not go through

47
00:04:24,337 --> 00:04:30,940
the red variables. So that we conclude
from that, that the variables C, I, D

48
00:04:30,940 --> 00:04:43,166
are separated. From. H. L. And J given, G
and S. And from the connection between the

49
00:04:43,166 --> 00:04:52,080
graph structure and independence in Markov
networks, we can conclude from that, that

50
00:04:52,080 --> 00:05:01,248
this independence property. Holes that is
C, I and D are independent of H, J and L given G and S,

51
00:05:01,248 --> 00:05:09,544
Which is exactly what we wanted to show
that the sepset separates the variables on

52
00:05:09,544 --> 00:05:16,728
the left. The blue variables, from the
variables from on the right, green

53
00:05:16,728 --> 00:05:26,204
variables. Let's try and give a slightly
more, general argument for this, one that

54
00:05:26,204 --> 00:05:33,090
isn't just demonstrating it in the context
of a particular example. So let's ignore

55
00:05:33,090 --> 00:05:39,494
for a moment the concrete letters inside
this example and just think about what

56
00:05:39,494 --> 00:05:46,060
would, why this is going to be true. So
let's imagine that this is now a generic.

57
00:05:47,020 --> 00:05:55,705
sepset and this is it over here and we'd
like to prove that all the variables on

58
00:05:55,705 --> 00:06:04,979
the green side are independent of all the
variables on the blue side. So let's

59
00:06:04,979 --> 00:06:10,643
assume otherwise. This is going to be a
proof by contradiction. If this were not

60
00:06:10,643 --> 00:06:17,718
the case, then that means that in this
induced Markov network, there needs to be

61
00:06:17,718 --> 00:06:30,141
some. So there's needs to be, though assume
otherwise. Which means there needs to be a

62
00:06:30,141 --> 00:06:48,941
path. In the induced Markov network. Between.
The blue side and the green side, so

63
00:06:48,941 --> 00:07:02,252
between W less than IJ. And W less than
JI. But if there exists a path that goes

64
00:07:02,252 --> 00:07:06,578
from one side of this graph to the other
it means that there eventually has to be

65
00:07:06,578 --> 00:07:12,035
an edge where one node is on one side and
one node's on the other. So there, that

66
00:07:12,035 --> 00:07:18,591
means there needs to be some edge that
goes from the blue side to the green side.

67
00:07:18,591 --> 00:07:24,985
Now notice, as I forgot to say, this path
that exists in the induced Markov

68
00:07:24,985 --> 00:07:33,964
network doesn't. That doesn't go through.
The sepset. Because otherwise the sepset

69
00:07:33,964 --> 00:07:39,644
was separated, so doesn't go through S I
j. So there needs to be an edge, that goes

70
00:07:39,644 --> 00:07:44,973
for example, from here to there. Or, it
doesn't matter which node I pick, which

71
00:07:44,973 --> 00:07:50,653
pair of nodes I pick. There needs to be
some node on the green side and some node

72
00:07:50,653 --> 00:07:56,263
on the blue side. This is the green side,
and this is the blue side. And an edge that

73
00:07:56,263 --> 00:08:03,537
goes between though it doesn't go through
the sepset. But now that implies that

74
00:08:03,537 --> 00:08:12,180
there needs to be some factor,
phi, that involves those two

75
00:08:12,180 --> 00:08:24,172
variables, so in this case, C comma H. But
now because of family preservation, that

76
00:08:24,172 --> 00:08:31,625
factor must sit in some. One of the
cliques in this clique tree. And that

77
00:08:31,625 --> 00:08:37,270
clique is either on the green side or on
the blue side. It has to be somewhere. So

78
00:08:37,270 --> 00:08:41,940
let's assume that we put that clique
without loss of generality on.

79
00:08:42,700 --> 00:08:48,868
the green side, but now what happens? We have
an H that's sitting here, remember that H

80
00:08:48,868 --> 00:08:54,810
is a blue variable, and H is also sitting
here because it's in the blue side. And

81
00:08:54,810 --> 00:09:00,828
now we have an H in one clique and an H in
the other, and running the intersection

82
00:09:00,828 --> 00:09:06,620
property tells us that H needs to be
everywhere in between, and specifically.

83
00:09:07,260 --> 00:09:14,274
It needs to be in the sepset which is a
violation of the assumption either of the

84
00:09:14,274 --> 00:09:20,636
running intersection property or of the
assumption that the, the variable H is not

85
00:09:20,636 --> 00:09:26,121
in the sepset. And so that's sort of a
somewhat formal proof outline that can,

86
00:09:26,121 --> 00:09:30,899
with a little bit of extra effort and
notation, be made into a rigorous proof

87
00:09:30,899 --> 00:09:35,737
of why running intersection property
implies this independence assumption. And

88
00:09:35,737 --> 00:09:40,814
I didn't prove the other direction because
this is actually the direction that we

89
00:09:40,814 --> 00:09:45,526
care about more. So we start out this
whole discussion by saying th, these

90
00:09:45,526 --> 00:09:50,283
properties have computational implications
th, where are these computational

91
00:09:50,283 --> 00:09:55,417
implications? What can we conclude from
the fact that the sepset needs to separate

92
00:09:55,417 --> 00:10:00,237
the graph into conditionally independent pieces? Well,
it turns out that in many graphs that

93
00:10:00,237 --> 00:10:05,433
implies a certain minimal complexity that
can sometimes be quite large. So let's do

94
00:10:05,433 --> 00:10:10,629
this [inaudible], let's look at this in
the context of two quite simple but very

95
00:10:10,629 --> 00:10:15,637
commonly used examples. So here is an
example of a. It's what's called a, a

96
00:10:15,637 --> 00:10:23,881
complete bipartite graph. Where we have
two sets of variables. That have no edges

97
00:10:23,881 --> 00:10:29,857
between each of the sets separately but
where all of the cross edges are present.

98
00:10:29,857 --> 00:10:35,758
This is a structure that is, that we've
actually seen before. We saw it in the

99
00:10:35,758 --> 00:10:42,778
context of the, plate model for student.
For course difficulty. And students

100
00:10:42,778 --> 00:10:47,650
intelligence, where we had a bunch of
difficulty variables, a bunch of

101
00:10:47,650 --> 00:10:53,512
intelligence variables, and there were no
edges between the difficulties or between

102
00:10:53,512 --> 00:10:59,302
the intelligences. But for very difficulty
and intelligence pair there was an edge

103
00:10:59,302 --> 00:11:04,881
that wasn't used by the V structure
corresponding to an observed student grade

104
00:11:04,881 --> 00:11:09,895
between the course difficulty,
corresponding course difficulty and that

105
00:11:09,895 --> 00:11:14,909
student's intelligence. What is the
smallest sepset that we could possibly

106
00:11:14,909 --> 00:11:20,467
construct for this graph, can we for
example look at just say these two A's and

107
00:11:20,467 --> 00:11:25,416
separate out the graph into two
conditionally independent pieces? Well, no

108
00:11:25,416 --> 00:11:30,974
not really because for example if we now
look at these two B's we can see you can

109
00:11:30,974 --> 00:11:36,736
connect them via any one of the other A's
that I didn't include in the sepset and so

110
00:11:36,736 --> 00:11:41,887
this doesn't decouple the graph at all.
With a little bit of extra thought it's

111
00:11:41,887 --> 00:11:47,091
not difficult to convince oneself that the
smallest sepset that we could construct,

112
00:11:47,091 --> 00:11:51,793
that actually breaks up the graph into
meaningful pieces, is either all the

113
00:11:51,793 --> 00:11:56,996
variables on the one side or all of the
variable on the other which means that the

114
00:11:56,996 --> 00:12:06,980
smallest sepset. Where the small in any
kind of meaningful clique tree has size.

115
00:12:07,920 --> 00:12:13,410
Greater than or equal to min of k
comma m where k is the number of

116
00:12:13,410 --> 00:12:19,679
variables on the one side and m on the
other. A slightly less obvious example but

117
00:12:19,679 --> 00:12:25,083
one that is also imposes some very
significant lower boundaries in the

118
00:12:25,083 --> 00:12:30,411
context of the grid, such as we
encountered in the Izing model or when

119
00:12:30,411 --> 00:12:36,423
doing image analysis, where the variables
correspond to pixels. And now let's try

120
00:12:36,423 --> 00:12:42,283
and think about how we might break up this
graph into separate conditionally

121
00:12:42,283 --> 00:12:49,239
independent pieces. Now, we can construct
clique trees to have smaller sepsets, small

122
00:12:49,239 --> 00:12:55,121
sepset. For example, here's a sepset.
Breaks away A 1,1 from everything

123
00:12:55,121 --> 00:13:01,357
else. But notice that, that still leaves
me a very large everything else. But if we

124
00:13:01,357 --> 00:13:07,296
try, for example, to break up the graph so
that A 1,1 appears on the one side,

125
00:13:07,296 --> 00:13:13,236
and A 4,4 appears on the other, any
clique tree that you give me that will

126
00:13:13,236 --> 00:13:18,804
have this separation with A 1,1 on
the one side and A 4,4 on the

127
00:13:18,804 --> 00:13:31,960
other, any such clique tree has to have. A
sepset. Of size. Greater than or equal to

128
00:13:31,960 --> 00:13:37,196
N, where this is an N by N gri-, grid.
Which means that if you try and break up

129
00:13:37,196 --> 00:13:42,636
the N by N grid in a way that puts one
corner on one side and one corner on the

130
00:13:42,636 --> 00:13:48,280
other, then you're going to have a sepset
that's at least the dimension of the grid.

131
00:13:48,900 --> 00:13:55,056
And breaking it up in other ways doesn't
make it any better. So here are two cases

132
00:13:55,056 --> 00:14:01,227
where we can place a lower bound on the
size of the sepset that is required for

133
00:14:01,458 --> 00:14:08,014
running clique tree inference. And that is where we
pay the, exponential blowup. That is, in

134
00:14:08,014 --> 00:14:14,107
some sense, required by the fact that,
that the problem is intrinsically a

135
00:14:14,107 --> 00:14:19,032
NP hard problem. So, to summarize,
We've shown previously that the

136
00:14:19,032 --> 00:14:24,602
correctness of the clique tree inference
algorithms relies on having the running

137
00:14:24,602 --> 00:14:29,178
intersection property. And we have now
shown in turn that the running

138
00:14:29,178 --> 00:14:34,417
intersection property implies certain
separation properties on the original

139
00:14:34,417 --> 00:14:39,891
distribution. These separation properties
in turn can be used to analyze the

140
00:14:39,891 --> 00:14:45,674
complexity of inference in different
graphs and provide certain minimal bounds

141
00:14:45,674 --> 00:14:51,677
on the complexity that would have to be
incurred by the best possible clique tree

142
00:14:51,677 --> 00:14:57,606
on graphs. And we have already seen the
notion of minimal complexity which is the

143
00:14:57,606 --> 00:15:03,536
minimal induced width of the graph; this
notion is a little bit different because

144
00:15:03,536 --> 00:15:09,132
it talks about sepsets. Whereas being used
with really talks more about tweaks but

145
00:15:09,132 --> 00:15:14,636
these are both ways of analyzing the
complexity certain minimal complexity that

146
00:15:14,636 --> 00:15:20,008
has been incurred by exact inference which
again is related with again is related to

147
00:15:20,008 --> 00:15:21,600
the NP hardness of problem.