Probabilistic graphical models (PGMs) are a rich framework for encoding probability distributions over complex domains: joint (multivariate) distributions over large numbers of random variables that interact with each other. These representations sit at the intersection of statistics and computer science, relying on concepts from probability theory, graph algorithms, machine learning, and more. They are the basis for the state-of-the-art methods in a wide variety of applications, such as medical diagnosis, image understanding, speech recognition, natural language processing, and many, many more. They are also a foundational tool in formulating many machine learning problems. This course is the first in a sequence of three. It describes the two basic PGM representations: Bayesian Networks, which rely on a directed graph; and Markov networks, which use an undirected graph. The course discusses both the theoretical properties of these representations as well as their use in practice. The (highly recommended) honors track contains several hands-on assignments on how to represent some real-world problems. The course also presents some important extensions beyond the basic PGM representation, which allow more complex models to be encoded compactly.
Tree-Structured CPDs
Loading...
From the course by Stanford University
Probabilistic Graphical Models 1: Representation
795 ratings
From the lesson
Structured CPDs for Bayesian Networks
A table-based representation of a CPD in a Bayesian network has a size that grows exponentially in the number of parents. There are a variety of other form of CPD that exploit some type of structure in the dependency model to allow for a much more compact representation. Here we describe a number of the ones most commonly used in practice.
Meet the Instructors
Daphne KollerProfessor
School of Engineering
So we've argued that table CPDss are problematic, because of their exponential
growth in the number of parents. One of the classes of structured CPDs
that is most useful are classe, is the class of CPDs that encodes a dependence
of a child on a parent. But a dependence that is only happening
in certain contexts. One method for encoding that is using the
class of what's called tree-structured CPDs.
So, to understand what tree-structured CPDs are, let's look at this simple
example. Imagine that we have a.
are students. And the students is applying for a job.
and the. Job, the prospects of the students to get
the job depend on three variables. Depends on the quality of the
recommendation letter that they get from the faculty member, their SAT scores, and
whether the student chooses to apply for the job in the first place.
So let's think about one possible CPD for this, for this model.
so here we have, a tree structure that you can think of it as a set of, as a
branching process. Where, the distribution over job looks at
some variables and then decides what the distribution might look like.
So for example, initially the, The dependence is on whether the student
chooses to apply for the job or not. What happens if the student doesn't apply
for the job, well you might say in that case the student doesn't get the job, but
it turns out to be not the case, in the hay days of silicon valley, for example,
we have the different, internet bubbles students were getting job offers without
every applying for jobs and so it might actually might happen, but the students
propability of getting a job is, non zero, even in this case.
And notice that the student not having applied for the job didn't submit either
a commodation or the SAT scores, which means that the students job prospect
don't depend, in this scenario on either of these two variables.
And so in all possible configurations of the s and l variable, the proba, ugh, s
and l variables, the probability of the student getting a job is zero point two.
What if the student did choose to apply for the job.
Well, in this case we can imagine a recruiter whose primary interest in the
student's SAT scores. They don't really believe recommendation
letters all that much. And so the next, and so the recruiter
first looks at the student's SAT score. And if the student got a good score on
the SAT S1, then regardless of the recommendation letter that the recruiter
doesn't even choose to look at, the student's probability of getting a job is
0.9. Only in the case where the student's SAT
scores are not as strong, does the recruiter go back and look at the letter.
In which case there is a, a certain probability, say 60%, of getting a job if
the letter is strong. And ten% if the letter is weak.
So we can see that we have a CPD that in this case depends on three binary
variables. And so really we would need to represent
in principle eight different probability distributions over the J variable.
But we've only represented four because in certain context some of the variables
don't matter. So in fact this notion of a variable not
mattering, is, related to the notion of complex specific independence which we've
defined previously. So one can formalize this in fact as a
complex specific independence. So let's look at this tree, and think
about which complex specific independencies arise in the context of
this, tree structure CPD. So with looking at the first one does J
the variable that we care about depend on L?
In the context a1. S1.
Well, we can see that in the context a1s1, the recruiter never looks at the
letter, so in fact, j is independent of l in this context, so the answer to this
one is yes. Okay what about the next one.
J is independent of L given A1 alone. Well in this case we have we're going
down here and now there's two scenarios one in which S is equal to S1 but the
other S is equal to S0 and in this case the recruiter does look at at the letter
and so this one is in fact not true. What about the next one?
J is independent of L and S given A0. So let's look at the A0 case.
And sure enough, in the A0 case, there's no dependence on either L or S.
So this one is also true. The last one is a little bit interesting
because it's a mix of context-specific and noncontext-specific independence.
So we're asking if J is independent of L in the context of s1.
For both values of the variable A. And so now let's, and so, to answer this
question, we actually need to do a case analyses.
Because this reduces to two different independent statements.
J is independent of L, given S1 and A1. And J is independent of L, given S1 and
A0. So, let's evaluate each of these two
separately. J is independent of L, given S1A1, is
exactly this assertion. So this one's true.
J is independent of l given s one and a zero.
Is Represents this.
Which, in fact, is a special case of this scenario.
And so, both of these, in fact, are true independent statements.
And so, since both cases hold, we have another conditional independent statement
that holds here. Let's look at another example that turns
out to be representative of a large class of examples in this context.
So here the student when applying for the job, needs to submit a recommendation
letter, but has a choice between the two letters that they might that they might
elect to provide. One from one course and another from a
second course. So letter one and letter two.
Now, the student's job prospects depend on the quality of the letter that's
actually provided, because of course the recruiter does not have access to the
letter that was not provided. So if we look at this in the context of
the tree CPD, it would look like this. The first variable at the top corresponds
to the student choice. And it has two branches, C1 and C2.
And in the C1 case, there is dependence only on the quality of letter one.
And in the C2 case, there is dependence only on the quality of letter two.
So, this is an example of what a well. Related to something called a multiplexer
CPD because effectively, the choice variable determines the dependence on one
set of circumstances or another set of circumstances.
Now, it turns out that this example has some interesting ramifications, because
not only do we have context independent dependencies that, arise because of the
tree structure. It turns out that this also implies non
context independent dependance that we will see useful later in the course.
Specifically, we have that letter one is independent of letter two given J and C.
Now if you think about this from purely the, the prospective of the, the
deseparation structure is the flow of influence in this graph we can see that
the job actually activates. The v structure between letter one and
letter two, so you wouldn't actually expect letter one and letter two to be
conditionally independent, that is we have a flow of influence because of
intercausal reasoning. But now lets think about this in more
detail. And that's the location analysis just
like we did before. So we're now going to ask if letter one
is independent of letter two, given j and c1.
But what happens in the context c=c1? Well in this case, the, there's no longer
the dependence between job and letter two because the recruiters never given the
second letter. And so in the context C one, the graph
really looks like this where there's no edge from L to the J.
Conversely, looking at the other case analysis, where, c equals c2, in this
case, this other edge is going to disappear.
And once again, there's no v structure, and so there's no active trail between
these, two variables L1 and L2. So effectively, in both of these cases,
the active trail disappears, and so that implies the independent assumption.
I mention this example is related to a more general class of models called
Multiplexer CPD. the Multiplexer CPD in this case actually
has the following structure. We have a set of random variables Z1 up
to ZK all of which take up some value in some particular space.
and the variable Y is a copy of one of the [??].
The variable A over here, is the multiplexer, the selector variable.
And the selector variable takes on values in the space one decay and it selects
which of the ZIs the Y copies. And notice that the Y here is
deterministic, as we can see by the fact that we have these two these two lines
surrounding it which is our way of indicating deterministic dependencies.
And so what is the CPD of the variable Y given the selector A and the parent Z1 up
to ZK? We can think about this as remember we
need to specify probability distribution. So, this probability distribution is one
if, y is equal to z sub a. So what does that mean?
It means that, and, and zero otherwise. So what does that mean?
It means that if A stays equal to little A, then deterministically Y is equal to Z
sub little A with probability one and that is just a formal way of saying that.
So A tells us which, which of the variable Z Y needs to copy.
This turns out to be an extremely useful concept in a variety of applications.
So, for example, when we have perceptual, uncertainty, when you have noisy sensors,
where we observe, say, we have, say, a sensor observation of one
of several airplanes. But we don't know which airplane it is
that we're observing. And so the position of the observation is
the, represents the position of the airplane that we're observing.
But the variable A, here, is the one that tells us which airplane it is, which we
might also be uncertain about. And this gives rise to a whole set of
problems, known as registration or correspondence or data association
problems. Which are very common in many
applications. Different type of application for this,
type of structured CPD comes up in physical hardware configuration settings.
So this is an actual, example from a troubleshooter, for printers used at
Microsoft. And it turns out that all of the
troubleshooters that are part of the Microsoft operating system are,
Built on top of a Bayesian Network Technology.
So here the task is to try and figure out why a printer isn't printing.
So we have a variable here that tells us whether the printer is producing output,
and, that depends on a variety of factors, but one of the factors that it
depends on is where the printer input is coming from.
Is it coming from a local transport? Or a network transport.
And, depending on which of those it's coming from, there's a different set of
failures that might occur. So the variable here that serves the goal
of the selector variable is this variable print data out.
And that's the root of the tree that's used here.
And and depending on whether the print location is local or not.
then you depend either on properties of the local transport.
Or on properties of the network transport.
And it turns out that even in this very, very simple network, the use of tree
CPD's reduces the number of parameters from 145 to about 55, and makes the
elicitation process much easier. So to summarize tree CPDs provide us with
a compact representation that captures effectively this notion of dependence in
in a context specific way, and as we've mentioned is relevant in a broad range of
applications of which we're, we've only given some examples, hardware
configuration, medical settings, where depending on the kind of situation that
you're in you might depend on one set of predisposing factors, say, or another.
Dependence on an agents action, as we've seen for example in the student's
decision on whether to apply for a job or not, or which letter to submit.
And we've also discussed perceptual ambiguity, where the value of a
particular sensed observation depends on which real world that observation comes
from.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
