1
00:00:00,000 --> 00:00:05,728
Very important insights about variable
elimination and how to best pick the

2
00:00:05,728 --> 00:00:11,682
elimination ordering is provided by
thinking about the operations the variable

3
00:00:11,682 --> 00:00:17,479
elimination executes as operations on a
graph. So let's see what that does. So

4
00:00:17,479 --> 00:00:23,639
let's consider the initial graph in our
example and let's first view this graph in

5
00:00:23,639 --> 00:00:29,798
terms of the factors that it involves. So
this is the set of factors that we have

6
00:00:29,798 --> 00:00:35,370
in, in our analysis, a viewed as
undirected, viewed as simply factors. So

7
00:00:35,370 --> 00:00:41,172
what is the structure of the graph that
corresponds to this set of factors? Well

8
00:00:41,172 --> 00:00:46,306
first we're going to make all the edges 
undirected, but that's not enough because we

9
00:00:46,306 --> 00:00:50,898
see, for example, that we have a factor
here which is a factor over G, I and D,

10
00:00:50,898 --> 00:00:55,791
and so what we need to do is we need to
add an edge between I and D to represent

11
00:00:55,791 --> 00:01:00,712
the fact that they're together in the
factor. Other examples, in that, other

12
00:01:00,712 --> 00:01:06,494
cases where we need to do this correspond
to the other V structures that we have in

13
00:01:06,494 --> 00:01:12,000
this graph. So here, for example, we have
a V structure involving J, so we're going

14
00:01:12,000 --> 00:01:17,828
to need to connect J's two parents and
similarly for H's two parents. This step

15
00:01:17,828 --> 00:01:26,080
by the way is called, not by me,
moralization. Because of the dubious moral

16
00:01:26,080 --> 00:01:33,230
value of marrying the parents of a child no
matter how many of them there are. Umm,

17
00:01:33,230 --> 00:01:39,851
and so I did not invent that name. So
having moralized the graph, we now have

18
00:01:39,851 --> 00:01:46,560
this version of it and this is what we
previously defined to be the induced

19
00:01:47,040 --> 00:01:54,686
Markov Network for the current set of
factors. So, now let's think about a

20
00:01:54,686 --> 00:02:00,789
variable elimination step and what it does
to this graph. So let's begin by

21
00:02:00,789 --> 00:02:06,973
eliminating C and if you remember that
involved this operation. And so first

22
00:02:06,973 --> 00:02:13,645
eliminating C is, changing the set of
factors. It removes these two factors over

23
00:02:13,645 --> 00:02:19,995
here from the set. And introduces a new
factor tau 1 of D. So, the

24
00:02:19,995 --> 00:02:26,472
induced graph is now going to look like
the following. We've taken C out. And this

25
00:02:26,472 --> 00:02:32,066
the remainder is the induced graph over the set of
factors. Okay? Now we are going to

26
00:02:32,066 --> 00:02:37,954
continue. We are going to eliminate D. So
once again we are going to take the two

27
00:02:37,954 --> 00:02:43,695
factors that we have now introduced. ...
Sorry ... These two factors that are

28
00:02:43,695 --> 00:02:49,731
involved here which is tau 1 of D and
phi G of G, I and D. Going to multiply them. And

29
00:02:49,731 --> 00:02:55,399
going to eliminate D. And so the
resulting, and then the resulting graph is

30
00:02:55,399 --> 00:03:01,289
now going to look like this. Where, again,
the, the nodes with the, with the dashed

31
00:03:01,289 --> 00:03:05,952
edges are not really there, they're just
there to remind us that they were there

32
00:03:05,952 --> 00:03:13,859
before. Continuing on, we're going to
eliminate I, and that involves multiplying

33
00:03:13,859 --> 00:03:21,850
in, this term, this term, and this term.
And now something interesting is going to

34
00:03:21,850 --> 00:03:29,391
happen. The factor that we introduced,
which is tau three of S and G Is a factor

35
00:03:29,391 --> 00:03:36,132
that doesn't have an edge in the current
graph. So if we're interested in having

36
00:03:36,132 --> 00:03:42,958
this graph represent our current set of
factors we're going to need to introduce

37
00:03:42,958 --> 00:03:49,700
this edge between G and S. Because that
edge, is necessary because S and G are

38
00:03:49,700 --> 00:04:07,929
together in the same factor. So that edge
is called a fill edge It's an edge that I

39
00:04:07,929 --> 00:04:12,849
had to introduce because of the
elimination ordering. So why don't we just

40
00:04:12,849 --> 00:04:17,560
think about this the way is using the
following example. Imagine every variable

41
00:04:17,560 --> 00:04:22,676
that's eliminated is going off on a trip
around the world And when it's doing that

42
00:04:22,676 --> 00:04:27,843
it is throwing a big goodbye bash and
inviting all of its friends to come and

43
00:04:27,843 --> 00:04:33,341
join it. And when it does that all of its
friends get to meet each other and say, oh

44
00:04:33,341 --> 00:04:38,641
you guys are nice I'm going to be your
friends too. And so all of the friends of

45
00:04:38,641 --> 00:04:43,345
the variable that's eliminated become
friends as a consequence of the

46
00:04:43,345 --> 00:04:52,347
elimination step, okay. So, let me write
that down, all variables connected to in

47
00:04:52,347 --> 00:04:59,980
this case, I, become connected after it's
eliminated, so become connected directly

48
00:05:02,160 --> 00:05:08,857
and that's a general, consequence of the
elimination step process. It's just that the

49
00:05:08,857 --> 00:05:14,825
previous ones didn't happen to introduce
fill edges. Okay, let's continue,

50
00:05:14,997 --> 00:05:19,747
[sound], so now we are going to eliminate
H, H also doesn't introduce any fill edges

51
00:05:19,747 --> 00:05:24,097
[sound], and so we are going to end up
with that, and basically the remaining

52
00:05:24,097 --> 00:05:28,734
steps are pretty mundane, we are going to
eliminate G [sound], L [sound] and S, and

53
00:05:28,734 --> 00:05:33,084
we are going to end up with the following
graph. So this particular variable

54
00:05:33,084 --> 00:05:37,148
elimination process only introduced one fill edge, which is a, a fairly

55
00:05:37,148 --> 00:05:41,956
conservative thing and shows that we, sort
of that we just selected a pretty good

56
00:05:41,956 --> 00:05:47,683
elimination ordering in this case [sound]
so we can now take and put all these edges

57
00:05:47,683 --> 00:05:53,788
that we ended up using together in a
single graph and that graph is called the

58
00:05:53,788 --> 00:06:00,500
induced graph and the induced graph,
which is denoted I, for induced,

59
00:06:00,500 --> 00:06:06,485
Phi comma alpha over a set of factors
Phi and induced by a particular

60
00:06:06,485 --> 00:06:12,021
ordering alpha, because you remember that
we were getting different complexities and

61
00:06:12,021 --> 00:06:17,755
we are going to have different fill edges,
depending on the order in which variables

62
00:06:17,755 --> 00:06:22,303
are eliminated. So this variable, this
induced graph, has the following,

63
00:06:22,501 --> 00:06:28,037
properties. It's an undirected graph where
we connect every pair of variables Xi and

64
00:06:28,037 --> 00:06:33,112
Xj, if they ever appeared in the same
factor when we ran variable elimination

65
00:06:33,112 --> 00:06:38,767
using alpha as the ordering. And so in this
case all of the original, all of the black

66
00:06:38,767 --> 00:06:44,181
edges, were there to begin with and we
ended up introducing just one of those

67
00:06:44,181 --> 00:06:54,943
additional, new or fill edges. So now,
lets... There is some interesting

68
00:06:54,943 --> 00:07:01,099
properties of the induced graphs that
are worth noting. First of all, there are

69
00:07:01,099 --> 00:07:07,342
some properties that relate factors
produced during variable elimination. And

70
00:07:07,342 --> 00:07:15,802
cliques in the induced graph. So first
let's define what a clique is. A clique is

71
00:07:15,802 --> 00:07:30,851
a maximal fully connected sub-graph So,
let's parse that too. So for example, DIG,

72
00:07:30,851 --> 00:07:36,374
here, is a fully connected sub graph,
because all of its three nodes are

73
00:07:36,374 --> 00:07:42,597
connected each other. And it's maximal,
because I can't add any other variable to

74
00:07:42,597 --> 00:07:49,054
this and still have that property hold. So
if I try and add S, for example, then S is

75
00:07:49,054 --> 00:07:55,433
not connected to D. If I try and add C, C
is not connected to I or G. So I can't add

76
00:07:55,433 --> 00:08:01,811
any other variable to this particular
clique, so it's a clique. Here is a clique

77
00:08:01,811 --> 00:08:11,340
that's not maximal So here is, so it's not
[inaudible], so G L J is it's a

78
00:08:11,340 --> 00:08:18,739
fully connected sub graph. But it's
not maximal because I can add S and still

79
00:08:18,739 --> 00:08:26,321
have that hold. Here's another clique in
this graph. You have GID being one clique

80
00:08:26,321 --> 00:08:34,177
and GSL and J being another clique. We're
going to have a third one which is GS and

81
00:08:34,177 --> 00:08:43,510
I another one which is CD. And let's see
if I have enough colors to do this. And a

82
00:08:43,510 --> 00:08:52,671
final one which is G, H and J. And if we
now look at the factors that we produced

83
00:08:52,671 --> 00:09:01,120
in the course of variable elimination, we
see that there is an exact correspondence

84
00:09:01,120 --> 00:09:09,569
between the factors and those cliques
so here for example, the yellow one is CD,

85
00:09:09,569 --> 00:09:17,712
which is this one over here. This one over
here which is GID is the red one, this

86
00:09:17,712 --> 00:09:28,780
one. So that's the red one. This one has S,
I, G, so that's the green one. This one

87
00:09:29,440 --> 00:09:40,601
This one is H, G, J which is the brown
one. Tau 5 induces the big factor, the

88
00:09:40,601 --> 00:09:46,228
one that involves four variables and
that's the blue factor over G, S, L, and

89
00:09:46,228 --> 00:09:52,381
J. And this one doesn't actually introduce
any new cliques which is why it doesn't

90
00:09:52,381 --> 00:09:58,383
have any, cliques associated with it. So
every factor produced during variable

91
00:09:58,383 --> 00:10:07,606
elimination is a clique in the induced
graph. [sound] We can equally well check,

92
00:10:07,606 --> 00:10:13,772
and we saw that in the previous
slide already that every maximal clique in

93
00:10:13,772 --> 00:10:19,213
the induced graph is a factor that's
produced during variable elimination.

94
00:10:19,213 --> 00:10:25,162
We've demonstrated this to ourselves by
inspection but let's actually get proof of

95
00:10:25,162 --> 00:10:31,184
this. So let's consider a maximal clique
in this induced graph. So let's consider for

96
00:10:31,184 --> 00:10:37,751
example GSLJ that's a maximal clique.
And now let's consider the run of variable

97
00:10:37,751 --> 00:10:44,822
elimination, and one of those variables
has to be One of those variables has to be

98
00:10:44,822 --> 00:11:01,462
the one to be eliminated first. So, some
variable in this clique. Some variable is

99
00:11:01,462 --> 00:11:12,656
first to be eliminated. Well, what happens
when a variable is eliminated? Once it's

100
00:11:12,656 --> 00:11:20,937
eliminated it, it doesn't, have any more
edges that get added to it. So once a

101
00:11:20,937 --> 00:11:42,831
variable is eliminated it has no more, no
new neighbors are added to it.

102
00:11:42,881 --> 00:11:57,631
Which means that at the time that it was eliminated

103
00:11:57,631 --> 00:12:07,495
It had all the neighbors that it had in the clique

104
00:12:07,495 --> 00:12:18,937
All the clique members as neighbors.

105
00:12:18,937 --> 00:12:28,063
But if that's the case, then it means that it had factors involving all those other guys.

106
00:12:28,278 --> 00:12:47,772
So it participated in factors with all these other guys.

107
00:12:47,772 --> 00:13:15,647
And that means that when I multiply them all together we're going to end up with a factor over all of them.

108
00:13:17,740 --> 00:13:23,936
And that is a proof that every maximal clique in the
induced graph must correspond to a factor

109
00:13:23,936 --> 00:13:31,866
produced during the variable elimination
algorithm. So now that we, umm, have

110
00:13:31,866 --> 00:13:37,629
constructed a graphical view of variable
elimination we can go ahead and construct

111
00:13:37,629 --> 00:13:43,045
a measure of a complexity variable
elimination and that is a measure known as

112
00:13:43,045 --> 00:13:48,600
the induced width. So first we are going
to define the width of an induced graph.

113
00:13:49,300 --> 00:13:55,796
Is the number of nodes in the largest
clique graph by convention minus one. Why

114
00:13:55,796 --> 00:14:02,780
minus one? No good reason but that's what
people, that's the of definition induced width

115
00:14:03,780 --> 00:14:10,388
The minimal induced width of the graph, is
the minimum over all possible elimination

116
00:14:10,388 --> 00:14:15,894
orderings alpha of the width of the
induced graph. So this is the best

117
00:14:15,894 --> 00:14:22,424
achievable complexity that one can aspire
to with any elimination ordering. You can

118
00:14:22,424 --> 00:14:28,953
think of the minimal induced width of the
graph as a lower bound on the best

119
00:14:28,953 --> 00:14:36,248
performance of variable elimination for
any model that factorizes over the graph.

120
00:14:36,940 --> 00:14:41,509
In summary, we've seen that the variable elimination algorithm can be viewed quite intuitively

121
00:14:41,662 --> 00:14:45,374
as taking a set of steps, each of which corresponds to a graph.

122
00:14:45,374 --> 00:14:52,235
Specifically, a variable elimination step for a variable X takes all of X's neighbours,

123
00:14:52,404 --> 00:14:56,831
that may or may not have been connected before, and connects them to each other.

124
00:14:57,062 --> 00:15:00,923
The result of all this is something
called the induced graph and we've seen

125
00:15:00,923 --> 00:15:06,376
that the induced graph is possibly quite
connected as a result of this variable

126
00:15:06,376 --> 00:15:11,303
elimination process and that the cliques
in this induced graph, that is, the

127
00:15:11,303 --> 00:15:16,296
maximally connected subsets, maximally
fully connected subsets correspond

128
00:15:16,296 --> 00:15:21,683
directly to the complexity of the variable
elimination algorithm. And as we'll see

129
00:15:21,683 --> 00:15:25,560
can therefore help us analyze its
computational properties.