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]

Temporal Models - DBNs

Probabilistic Graphical Models 1: Representation

与讲师见面