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.
Temporal Models - DBNs
Loading...
From the course by Stanford University
Probabilistic Graphical Models 1: Representation
860 ratings
From the lesson
Template Models for Bayesian Networks
In many cases, we need to model distributions that have a recurring structure. In this module, we describe representations for two such situations. One is temporal scenarios, where we want to model a probabilistic structure that holds constant over time; here, we use Hidden Markov Models, or, more generally, Dynamic Bayesian Networks. The other is aimed at scenarios that involve multiple similar entities, each of whose properties is governed by a similar model; here, we use Plate Models.
Meet the Instructors
Daphne KollerProfessor
School of Engineering
There are many classes of models that that allow us to represent in a single
concise representation, a template over riched models that incorporate multiple
copies of the same variable and also allow us to represent multiple models
within as a byproduct of a single representation.
But one of the most commonly used among those is for reasoning about template
models where we have a system that evolves over time.
So so, let's look at what we have, we represent a distribution over template
trajectories. So the first thing we want to do when
representing a distribution over continuous time is, in most cases, not
always, is to try and forget the time is actually continuous.
Because continuous quantities are harder to deal with.
So, we're going to discretize time. And specifically,
i is claimed. And specifically, we're going to do that
by picking a particular time granularity delta,
which is the time granularity at which we're going to measure time.
Now, in many cases, this is something that we already is given to us by the
granularity of our sensor. So, in many cases, for example, we have a
video or a robot there is a certain time granularity at which we obtain
measurements and so that's usually the granularity that we'll pick.
But in other cases, we might want to have have a different a different granularity
so there is a choice here. So, here's our time granularity, for
example. And now, we have a set of template random
variables, X of t. And X of t denotes the value of a
particular variable x, variable x being a template variablem x to the t being a
particular instantiation of that variable at the time point t delta so that we have
multiple copies, one for each time point. Now, here's some notation that we're
going to end up using later on. So, let's introduce it.
where X of t denotes the variable t at time t x(t:t) prime denotes the set of
between t and t prime. So, a discrete, in this case, because
we've discretized time. So, a finite set of random variables that
spans these two time points, inclusive. Now, our goal is that we would like to be
able to have a concise representation that allows us to represent this
probability distribution over the trajectory,
over a trajectory of the system of any duration.
So, we want to start at a particular time point.
Usually, this is going to be zero. And then, how what is the probability
distribution over trajectories of arbitrary length?
So, how do we represent what is a, first of all, an infinite family of probability
distributions because you could look at trajectories of duration 2, 5, 10, a
million. So, that's an infinite family of
distributions. And each of these is a distribution over
an unbounded number of random variables. Because if you have a distribution over a
trajectory length a million, you have to represent a million dimensional
distribution. So, how do we compactify that, how do we
make that a much more concise representation?
So, there is different pieces to this. The first of those is what's typically
called the Markov assumption. And the Markov assumption goes, is
effectively a type of conditional independence assumption.
So, it's the same building block that we use to compactify general purpose
graphical models, we're going to use here in the context of time course data.
So here, we're saying that the probability of the variable, X,
I'm sorry, the set of variables expanding the time
from zero all the way to capital T. so, I haven't made any assumptions yet in
this statement so I'm just writing this down.
I'm re-expressing it in terms of the chain rule for probabilities.
There is no chain rule for Bayesian networks yet here.
And this is just a chain rule for probabilities.
And the chain rule for probabilities in this context basically says that, that
probability is equal to the probability of X at time zero times the probability
of each consecutive time point, t + 1, given, so this is the state at t + 1,
given the state at all previous time points, zero up to t.
So, this is not in any way an assumption. This is just a way of re-expressing this
probability distribution in the way that time flows forward.
But it's not an assumption. You can represent any probability
distribution over these random variables in this way.
But now, we're going to add this assumption.
And this is an assumption. This is an independence assumption.
And this independence assumption tells me that X of t plus one,
that is the state of time t + 1, the next step.
So, this is the next step, is independent of the past,
given the present. So, this is a forgetting assumption.
Once you know the current state, you don't care anymore about your past,
okay? If you do that, we can now go back to
this chain rule over here and simplify it, because whereas before, we
conditioned on x upto zero, some times zero to time t,
now everything upto t - 1 is conditionally independent, given.
So, all of this is conditionally independent of t plus one given X of t,
which means that I've allowed myself to move X of t here as the only thing that
I'm conditioned on, conditioning on, in order to determine the probability of
distribution of X = 1. So, to what extent is this assumption
warranted? So, is this true?
And let's take as an example, X equals the location or pose of a robot or an
object that's moving. Is it the case that the location of the
robot at t plus one. So, L of t plus one plus one is
independent, of say, L of t minus one, to simplify our
lives, given L of t.
Is this a reasonable assumption? Well, in most cases, probably not.
And the reason is that it completely ignores the issue of velocity, which
direction are you moving and how fast? And so, this is a classical example of
where the Markov assumption for this particular model is probably too strong
of an assumption. So, what do we do to fix it?
The one, one way to fix it is to enrich the stay description.
So, estimate the Markov assumption a better approximation.
Just like any independent assumption, the Markov assumption is always going to be
an approximation but the question is how good of that approximation and if we add,
for example, V of t, which is the velocity times t, maybe the
exploration of time t, maybe the robot's intent, where its goal is.
I mean, all sorts of additional stuff into the state.
Then, at that point, the Markov assumption becomes much more
warranted, okay?
And so that's one way of making the Markhov assumption true.
An alternative strategy which we're not going to talk about right now is to move
away from the Markov assumption by adding dependencies that go further back in
time, back in time.
And that's called a semi-Markov model. And we're not going to talk about that
right now. The second big assumption that we are
going to have to make in order to simplify the model is in order to deal
with the question of, well, fine, so we've reduced the model to encoding
a probability of X of t + 1, given X of t, but it's still an unbounded number of
conditional probabilities. Now, at least each of them is compact,
but there's still a probabilistic model for every P.
And this is where we're going to end up with a with a template based model.
We're going to stipulate that there is a probabilistic model, P p of x prime given
x. X prime denotes the, next time point and
X denotes the current time point. And we're going to assume that that model
is replicated for every single time point.
That is, when you're moving from time zero to time one, you use this model.
When you're moving time one to time two, you also use this model.
And and that assumption, for obvious reasons, is called time invariance.
Because it assumes that the dynamics of the system, not the actual position of
the robot, but rather the dynamics that move it from
state to state, or the dynamics of the system, don't depend on the current time
point t. And once again, this is an assumption,
and it's an assumption that's warranted in certain cases and not in others.
So, let's imagine that this represents now the traffic on some road.
Well does that traffic, does the, does the dynamics of that traffic depend on
on, say, the current time point of the system?
On most roads, the answer is probably yes.
It might depend on the time of day, on the day of the week,
on whether there is a big football match, on all sorts of things that might affect
the dynamics of traffic. The point being that just like in the
previous example, we can correct inaccuracies in our assumption by
enriching the model. So, once again, we can enrich the model
by including these variables in it. And once we have that, then the, again,
the model becomes a much better reflection of reality.
So now, how do we represent this probabilistic model in in the context of
a graphical model like we had before? So, let's now assume that our stayed
description is composed of a set of random variables.
And so, we're interested, we have we have a little baby traffic system where we
have the weather at the current time point, the location of, say, a vehicle,
the velocity of the vehicle. We also have a sensor, who's observation
we get at each of those time points. And the sensor may or may not be failing
at the current time point. And what we've done here is we've encoded
the the probabilistic model of this next state.
So, W prime, V prime, L prime, F f prime, and O prime, given the previous states.
So, given W, V, L, and F. Why is O not here on the right-hand side?
It's not here on the right-hand side because it doesn't affect any of the next
state variables. So, it would be kind of hanging down here
if we included it. But that doesn't, it doesn't affect
anything, we don't choose to to represent it.
So, this model represents a conditional distribution.
Now, we have a little network fragment. So, this is a network fragment.
And it doesn't represent a joint distribution,
it represents a conditional distribution. The conditional distribution of the t + 1
given t. But what, but in order to represent that,
we still use the same tools that we have in the context of variance, of graphical
models. And so, we can write that as the same
kind of chain rule that we used before. So, this would be the probability of W
prime, given W, based on this edge over here,
times the probability of V prime, the velocity.
So, this, this says that the weather, the first one says, that the weather at time
t plus one depends on the weather at time t.
The second one that the velocity of time t plus one depends on the weather at time
t and the velocity at time t which indicates a certain persistence in the
velocity as well as the fact that, you know, if there, if it's raining you might
slip sideways so the velocity might change.
Also if you're careful, you might slow down if it's raining.
And so again, there might be an effect of the weather on the velocity.
The probability of the location at time t + one, given the location at time t and
the velocity time t. The probability of a sensor failure at
time t1. + 1, given the failure, and at, at the
previous time and the weather. Which indicates that, once the sensor has
failed, it's probably more likely to stay failed.
But maybe rain can make the sensor behave badly.
And then, finally, the probability of the observation of time t + 1 given the
location of time t1. + 1, and the failure of time t1.
+ 1. So, there's several important things to
note about this diagram that are worth highlighting.
First of all, we have dependencies both within and across time.
So here, we have a dependency that goes from t to t plus one.
And here, we have a dependency that is within t T plus one alone.
What's, what induces us to make a modeling chose like this go one way
versus the other? The assumption here that this is a fairly
wide [UNKNOWN] dependency so that a, the observation is relatively instantaneous
compared to our time granularity. And so, we, we don't want that to go
across time but rather we want it to be within a time slice because it's a better
reflection for which variable is it that actually influences the observation.
Is it the current location or the previous location?
So these kinds of edges, let's just give the names.
These are called intra-time slice edges and these are called inter or between
time slice. And the model can include a combination
of both of these. Another kind of
anothwe, a particular type of inter-time slice edge that's worth highlighting
specifically are edges that go from a variable at one time point to the value
of that variable at the next time point. These are often called persistence edges
because they indicate the the tendency of a variable to persist in
state from one time point to another. Finally, let's just go back and look at
the parameterization that we have in this model. So, what CPDs did we actually need
to include in this model? And we can see that we have CPDs for the
variables on the right-hand side, the prime variables.
But there's no CPDs for the variables that are unprimed,
the variables on the left. And this is because the model doesn't
actually try and represent the distribution, O over W, V, L, and F.
It doesn't try and do that. It tries to represent the probability of
the next time slice, given the previous one.
So, as we can see, this graphical model only has CPD's for a subset of the
variables in it. The ones that represent the next time
point. So, that represents the transition
dynamics. If we want to represent the probability
distribution over an entire system, we also need to provide a distribution over
the initial state. And this is just the standard generic
Bayesian network which represent the probability over the state at times zero
using some appropriate chain rule. So, nothing very fancy here.
With those two pieces, we can now represent probability distributions over
arbitrarily long trajectories. So, we represent this by taking for time
slice zero and copying the times zero Bayesian network, which represent the
probability distribution over the time zero variables. And now, we have a bunch
of copies that represent the probability distribution at time one, given time
zero. And here, we have another copy of exactly
the same set of parameters that represents time two given time one.
And we can continue copying this indefinitely and each copy gives us the
probability distribution of the next time slice given the one that we just had and
so we can construct arbitrarily along Bayesian network.
So, to make this definition slightly more formal, we define the notion of a
two-time slice Bayesian network, also known as a 2TBN.
And the 2TBN over a set of template variables X1 up to Xn, is specified as a
Bayesian network fragment along exactly the same lines that we used in the
example. The nodes have two copies.
the next time state variable X prime up to Xn prime.
And some subset of X1 up to Xn, which are variables, the time t
variables, that affect directly the state of three
plus one, okay?
And because we want this to represent a conditional probability distribution,
only the time t + 1 nodes have parents and a CPD.
Because we don't really want to model the distribution over the variables of time
t. And the 2TBN defines a conditional
distribution using the chain rule. You can tell me it looks exactly like the
chain rule. So, the probability of X prime, given X
is the product of each variable and time t plus one, so only the prime variables
can have parents. Which may or be, may be in time P plus
one, time P, or a combination of both. A dynamic Bayesian network is now
basically defined by a 2TBN, which we just defined, and a Bayesian
network over times zero. So, this is the dynamics and this is the
initial state. And we can use that to define arbitrary
probability distributions for sorry,
probability distributions over arbitrarily long trajectories using
what's called the unrolled network or also called the ground network.
And this is exactly in the, as in the example that I showed,
the dependency model for time zero is copied from the Bayes net for time zero.
And this is, the transition is copied from the Base N under the nodes, the
conditional probability for transitions. So, before we conclude this lecture,
let's look at an example of a dynamic Bayesian network that is a more realistic
one than the simple examples that we've shown before.
This is a network that was actually designed for tracking vehicles in a
traffic situation. And so, we can see that there are
multiple variables here that represent both the position and velocity of the
vehicle both in an absolute sense. For example, this is Xdot and Ydot are
the velocities as well as various more semantic notions of location, like
whether you're in the lane. There are contextual variables such as
left clear and right clear. the engine status, for example as well as
what the driver is currently doing, for example the forward action and the
lateral action. We can see that there are persistence
edges that denote the persistence of various forms of the state from time t to
time t plus one, as well as a variety of these
intermediate variables over here that allow us to represent the probability
distribution in a more compact way by incorporating variables that do not
persist, or at least in this simplified model,, do not persist.
And finally, we see that there are a large number of
sensor observations, such as turn signal, whether the car is clear on the right and
on the left or appears to be clear on the right and left, and so, and so on.
So, this is a much more realistic model of how traffic evolves than the
simplified one that we saw before. To summarize, dynamic Bayesian networks
provides us with a language for encoding structured distributions over time.
And by making the assumptions of the Markovian evolution as well as time
invariance, you can use a single compact network to allow us to code arbitrarily
long transitions over arbitrarily long time sequences.
But these assumptions that we made, the Markovian assumption and the time
invariance assumption are not really correct and might require that we
redesign the model so as to enforce, so as to make these assumptions a better
approximation to the two underlying distribution, by, for example, adding
variables as we showed. [SOUND]
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.
