1
00:00:02,400 --> 00:00:07,472
We've argued that table CPDs are
problematic because of their exponential

2
00:00:07,472 --> 00:00:12,819
growth in the number of parents. One of
the classes of structured CPDs that is

3
00:00:12,819 --> 00:00:18,440
most useful are classes, is the class of
CPDs that encodes a dependence of a child

4
00:00:18,440 --> 00:00:23,787
on the parent. But a dependence that is
only happening in certain contexts. One

5
00:00:23,787 --> 00:00:29,065
method for encoding that is using the
class of what's called tree-structured

6
00:00:29,065 --> 00:00:33,589
CPDs. So to understand what
tree-structured CPDs are let's look at

7
00:00:33,589 --> 00:00:39,097
this simple example. Imagine that we have
a student, and the student is applying for

8
00:00:39,097 --> 00:00:44,429
a job. And the job, that the prospects of
the student to get the job depend on three

9
00:00:44,429 --> 00:00:49,696
variables. Depend on the quality of the
recommendation letter that they get from a

10
00:00:49,696 --> 00:00:54,835
faculty member, of their SAT scores, and
whether the student chooses to apply for

11
00:00:54,835 --> 00:01:01,359
the job in the first place. So let's think
about one possible CPD for this, for this

12
00:01:01,359 --> 00:01:08,286
model. So here we have a tree structure.
And you can think about it as a set of, as

13
00:01:08,286 --> 00:01:15,298
a branching process where the distribution
over a job looks at some variables and

14
00:01:15,298 --> 00:01:22,140
then decides what the distribution might
look like. So for example, initially the,

15
00:01:22,140 --> 00:01:27,315
The dependence is on whether the student
chooses to apply for the job or not. What

16
00:01:27,315 --> 00:01:31,618
happens if the student doesn't apply for
the job? Well, you might say in that case

17
00:01:31,618 --> 00:01:35,603
the student doesn't get the job, but it
turns out to be not the case. In the

18
00:01:35,603 --> 00:01:39,693
heydays of Silicon Valley, for example, we
have the different Internet bubbles.

19
00:01:39,693 --> 00:01:43,943
Students were getting job offers without
ever applying for jobs. And so it might

20
00:01:43,943 --> 00:01:47,981
actually happen that the student's
probability of getting a job is not zero

21
00:01:47,981 --> 00:01:52,071
even in this case. And notice that the
student not having applied for the job

22
00:01:52,071 --> 00:01:56,428
didn't submit either recommendation letter
or the SAT scores which means that the

23
00:01:56,428 --> 00:02:00,518
student's job prospects don't depend in
this scenario on either of these two

24
00:02:00,518 --> 00:02:05,545
variables. And so, in all possible
configurations of the s and l variable,

25
00:02:05,545 --> 00:02:11,377
the s and l variables, the probability of
the student getting a job is 0.2. What if

26
00:02:11,377 --> 00:02:15,993
the student did choose to apply for the
job? Well, in this case we can imagine a

27
00:02:15,993 --> 00:02:20,785
recruiter whose primary interest is in the
student's SAT scores. They don't really

28
00:02:20,785 --> 00:02:24,993
believe recommendation letters all that
much. And so the next, and so the

29
00:02:24,993 --> 00:02:29,960
recruiter first looks at the student's SAT
score. And if the student got a good score

30
00:02:29,960 --> 00:02:34,576
on the SAT, s1, then regardless of the
recommendation letter, which the recruiter

31
00:02:34,576 --> 00:02:39,076
doesn't even choose to look at, the
student's probability of getting a job is

32
00:02:39,076 --> 00:02:44,362
0.9. Only in the case where the student's
SAT scores are not as strong does the

33
00:02:44,362 --> 00:02:49,347
recruiter go back and look at the letter,
in which case there is a certain

34
00:02:49,347 --> 00:02:54,669
probability, say 60%, of getting a job if
the letter is strong. And ten percent if

35
00:02:54,669 --> 00:03:01,304
the letter is weak. So we can see that we
have a CPD that in this case depends on

36
00:03:01,304 --> 00:03:06,531
three binary variables and so really we
would need to represent in principle eight

37
00:03:06,531 --> 00:03:11,757
different probability distributions over
the j variable. But we've only represented

38
00:03:11,757 --> 00:03:17,598
four because in certain contexts some of
the variables don't matter. So in fact

39
00:03:17,598 --> 00:03:24,235
this notion of a variable not mattering is
related to the notion of context-specific

40
00:03:24,235 --> 00:03:29,934
independence, which we've defined
previously. So one can formalize this in

41
00:03:29,934 --> 00:03:36,414
fact as a context-specific independence.
So let's look at this tree and think about

42
00:03:36,414 --> 00:03:41,645
which context-specific independencies
arise in the context of this

43
00:03:41,645 --> 00:03:48,732
tree-structured CPD. So, let's Looking at
the first one, does j, the variable that

44
00:03:48,732 --> 00:04:00,212
we care about, depend on l? In the context
A1. S1 Well, we can see that in the

45
00:04:00,212 --> 00:04:06,325
context A1S1, the recruiter never looks at
the letter. So in fact, j is independent

46
00:04:06,325 --> 00:04:13,411
of l in this context. So the answer to
this one is yes. Okay, what about the next

47
00:04:13,411 --> 00:04:21,409
one. J is independent of l given A1 alone.
Well, in this case, we have, we're going

48
00:04:21,409 --> 00:04:29,407
down here and now there's two scenarios.
One in which S = S1 and the other, S = S0

49
00:04:29,407 --> 00:04:37,708
and in this case, the recruiter does look
at the letter and so this one in fact is

50
00:04:37,708 --> 00:04:46,187
not true. What about the next one? J is
independent of l and s given A0. So let's

51
00:04:46,187 --> 00:04:52,513
look at the A0 case. And sure enough, in
the A0 case there's no dependence on

52
00:04:52,513 --> 00:04:59,145
either l or s, so this one is also true.
The last one is a little bit interesting,

53
00:04:59,145 --> 00:05:04,464
because it's a mix of context-specific and
non-context-specific independence. So

54
00:05:04,464 --> 00:05:12,052
we're asking whether j is independent of l
in the context S1. For both values of the

55
00:05:12,052 --> 00:05:17,539
variable a. And so now let's, and so to
answer this question we actually need to

56
00:05:17,539 --> 00:05:23,280
do a case analysis because this reduces to
two different independent statements. J is

57
00:05:23,280 --> 00:05:32,195
independent of l given S1 and A1 and j is
independent of l given S1 and A0. So let's

58
00:05:32,195 --> 00:05:40,898
evaluate each of these two separately. J
is independent of l given S1A1 is exactly

59
00:05:40,898 --> 00:05:51,060
this assertion, so this one's true. J is
independent of l given S1 and A0 is

60
00:05:51,060 --> 00:06:03,841
represents this. Which, in fact, is a
special case of this scenario. And so both

61
00:06:03,841 --> 00:06:09,392
of these in fact are true independent
statements, and so since both cases hold

62
00:06:09,392 --> 00:06:14,945
we have another conditional independent
statement that holds here. Let's look at

63
00:06:14,945 --> 00:06:19,345
another example that turns out to be
representative of a large class of

64
00:06:19,345 --> 00:06:24,050
examples in this context. So here the
student, when applying for the job, needs

65
00:06:24,050 --> 00:06:29,245
to submit a recommendation letter but has
a choice between the two letters that they

66
00:06:29,245 --> 00:06:34,011
might, that they might elect to provide.
One from one course and another from a

67
00:06:34,011 --> 00:06:38,594
second course. So letter one and letter
two. Now the student's job prospects

68
00:06:38,594 --> 00:06:43,666
depend on the quality of the letter that's
actually provided because, of course, the

69
00:06:43,666 --> 00:06:48,267
recruiter doesn't have access to the
letter that was not provided. So if we

70
00:06:48,267 --> 00:06:52,867
look at this in the context of the
[inaudible], they don't even like this.

71
00:06:52,867 --> 00:06:58,223
The first variable at the top corresponds
the student choice and it has two branches

72
00:06:58,223 --> 00:07:03,201
c1 and c2, and in the c1 case, there is
dependence only on the quality of letter

73
00:07:03,201 --> 00:07:07,927
one and then the c2 case, there is
dependence only on the quality of letter

74
00:07:07,927 --> 00:07:17,484
two So this is an example of what
[inaudible] Related to something called a

75
00:07:17,484 --> 00:07:23,510
multiplexer CPD, because effectively the
choice variable determines the dependence

76
00:07:23,510 --> 00:07:29,580
on one set of circumstances or another set
of circumstances. Now it turns out that

77
00:07:29,580 --> 00:07:35,316
this example has some interesting
ramifications. Because not only do we have

78
00:07:35,316 --> 00:07:41,429
[inaudible] specific independence's that
arise because of this restructure, it

79
00:07:41,429 --> 00:07:47,542
turns out that this, also implies non
[inaudible] specific independence's that

80
00:07:47,542 --> 00:07:53,504
are quite useful as we'll see later on in
the course. Specifically we have that

81
00:07:53,504 --> 00:08:00,079
letter one is independent of letter two
given J and C Now, if you think about this

82
00:08:00,079 --> 00:08:07,399
from purely the proc-, the perspective of
the, the separation structure, the flow of

83
00:08:07,399 --> 00:08:14,428
influence in this graph, we can see that
the job actually activates the V

84
00:08:14,428 --> 00:08:20,113
structure, between letter one and letter
two. So you wouldn't actually expect

85
00:08:20,113 --> 00:08:25,275
letter one and letter two to be
conditionally independent. That is, we

86
00:08:25,275 --> 00:08:30,736
have a flow of influence because of
inter-causal reasoning. But now let's

87
00:08:30,736 --> 00:08:36,831
think about this in more detail. And let's
do a case analysis just like we did

88
00:08:36,831 --> 00:08:42,947
before. So we're now going to ask if
letter one is independent of letter two,

89
00:08:42,947 --> 00:08:49,144
given j and C1. But what happens in the
context C=C1? Well in this case, there's

90
00:08:49,144 --> 00:08:54,957
no longer a dependence between job and
letter two, because the recruiter is never

91
00:08:54,957 --> 00:09:00,483
given the second letter. And so, in the
context C1, the graph really looks like

92
00:09:00,483 --> 00:09:06,417
this, where there's no edge from l to the
j. Conversely, looking at the other case

93
00:09:06,417 --> 00:09:12,343
analysis where C=C2, in this case this
other edge is going to disappear and once

94
00:09:12,343 --> 00:09:18,346
again there's no V structure and so
there's no active trail between these two

95
00:09:18,346 --> 00:09:24,119
variables L1 and L2. So effectively, in
both of these cases, the active trail

96
00:09:24,119 --> 00:09:31,671
disappears and so that implies the
independence assumption. That I mention

97
00:09:31,671 --> 00:09:39,527
this example is related to more general
class of models called the multiplexer

98
00:09:39,527 --> 00:09:47,184
CPD. The multiplexer CPD in this case
actually has the following structure. We

99
00:09:47,184 --> 00:09:55,438
have a set of random variables, zero on up
to ZK all of which take on some value in

100
00:09:55,438 --> 00:10:06,075
some particular space. And the variable Y
is a copy of one of the ZIs. The variable

101
00:10:06,075 --> 00:10:12,873
A, over here, is the multiplexer, the
selector variable. And the selector

102
00:10:12,873 --> 00:10:19,641
variable takes on values in the space one
to K and it selects which of the ZIs the Y

103
00:10:19,641 --> 00:10:25,772
copies. And notice that the Y here is
deterministic, as we can see by the fact

104
00:10:25,772 --> 00:10:31,743
that we have these two lines surrounding
it, which is our way of indicating

105
00:10:31,743 --> 00:10:37,954
deterministic dependencies. And so what is
the CPD of the variable Y, given the

106
00:10:37,954 --> 00:10:46,484
selector A and the parent Z1 up to ZK? We
can think about this as, remember we need

107
00:10:46,484 --> 00:10:55,055
to specify a probability distribution so
this probability distribution is one, if Y

108
00:10:55,055 --> 00:11:02,904
is equal to Z sub A. So what does that
mean? It means that, and zero otherwise.

109
00:11:02,904 --> 00:11:09,923
So what does that mean? It means that if
A, say, is equal to little A, then

110
00:11:09,923 --> 00:11:17,046
deterministically Y is equal to sub little
A, with probability one. That's just a

111
00:11:17,046 --> 00:11:24,170
formal way of saying that. So A tells us
which of the variable Z Y needs to copy.

112
00:11:24,170 --> 00:11:30,762
This turns out to be an extremely useful
concept in a variety of applications. So

113
00:11:30,762 --> 00:11:37,192
for example when we have perceptual
uncertainty, when you have noisy sensors

114
00:11:37,436 --> 00:11:42,754
where we observe say What we have, say, a
sensor observation of one of several

115
00:11:42,754 --> 00:11:47,201
airplanes, but we don't know which
airplane it is that we're observing. And

116
00:11:47,201 --> 00:11:52,128
so the position of the observation is the,
represents the position of the airplane

117
00:11:52,128 --> 00:11:56,695
that we're observing but the variable A
here is the one that tells us which

118
00:11:56,695 --> 00:12:01,562
airplane it is, which we might also be
uncertain about. And this gives rise to a

119
00:12:01,562 --> 00:12:06,106
whole set of problems known as
registration, or correspondence, or data

120
00:12:06,106 --> 00:12:12,622
association problems which are very common
in many applications. Different type of

121
00:12:12,622 --> 00:12:17,937
application for this, type of structured
CPD, comes up in physical hardware

122
00:12:17,937 --> 00:12:23,598
configuration settings. So this is an
actual example from a trouble-shooter, for

123
00:12:23,598 --> 00:12:29,258
printers used at Microsoft. And it turns
out that all of the trouble-shooters that

124
00:12:29,258 --> 00:12:35,631
are part of the Microsoft operating system
are, built on top of [inaudible] network

125
00:12:35,631 --> 00:12:42,285
technology. So here the task is to try and
figure out why a printer isn't printing.

126
00:12:42,285 --> 00:12:49,020
So we have a variable here that tells us
whether a printer is producing output. And

127
00:12:49,020 --> 00:12:55,674
that depends on a variety of factors, but
one of the factors that it depends on is

128
00:12:55,674 --> 00:13:02,335
where the printer input is coming from. Is
it coming from a local transport? We're

129
00:13:02,335 --> 00:13:08,074
not [inaudible] And depending on which of
those it's coming from, there's a

130
00:13:08,074 --> 00:13:13,489
different set of failures that might
occur. So, the variable here that serves

131
00:13:13,489 --> 00:13:19,261
the goal of the selector variable, is this
variable Print Data Out. And that's the

132
00:13:19,261 --> 00:13:24,676
root of the tree that's used here. And,
and depending on whether the print

133
00:13:24,676 --> 00:13:30,234
location is local or not, then you depend
either on properties of the local

134
00:13:30,234 --> 00:13:36,773
transport or on properties of the network
transport. And it turns out that even in

135
00:13:36,773 --> 00:13:42,298
this very, very simple network the use of
tree CPDs reduces the number of parameters

136
00:13:42,298 --> 00:13:47,041
from 145 to about 55 and make the
elicitation process much easier. So to

137
00:13:47,041 --> 00:13:52,192
summarize [inaudible] provide us with a
compact representation that captures

138
00:13:52,192 --> 00:13:57,611
effectively this motion of dependence in a
[inaudible] specific way. And as we've

139
00:13:57,611 --> 00:14:03,030
mentioned as relevant in a broad range of
applications of which we're only given

140
00:14:03,030 --> 00:14:08,382
some examples, hardware configuration,
medical settings, we're depending on the

141
00:14:08,382 --> 00:14:14,135
kind of situation that your in you might
depend on one set of predisposing factors

142
00:14:14,135 --> 00:14:19,866
say or another Dependence on an agent
action, as we've seen for example in the

143
00:14:19,866 --> 00:14:25,759
student's decision on whether to apply for
a job or not or which letter to submit.

144
00:14:25,759 --> 00:14:30,717
And we've also discussed perceptual
ambiguity where the value of the

145
00:14:30,717 --> 00:14:36,609
particular sensed observation depends on
which real world object that observation

146
00:14:36,609 --> 00:14:37,400
comes from.