So there are many classes of models that,
that allow us to represent in a single
concise representation, a template over,
rich models that incorporate multiple
copies of the same variable. And also
allows to represent multiple models
within, as a byproduct of the single
representation. But, one of the most
commonly used among those, is for
reasoning about temporal models, where we
have a system that evolves over time. So.
So let's look at what we have, [inaudible]
represent a distribution over temporal
trajectories. So the first thing we wanna
do when representing a distribution over
continuous time, is, in most cases, not
always, is to try and forget that time's
actually continuous. Because continuous
quantities are harder to deal with. So
we're going to discretize time. And
specifically. Eyes closed. And
specifically, we're going to do that by
picking a particular time granularity
delta. Which is the time granularity; it's
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, when 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 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 P. And X of P denotes the value of a
particular variable X. A variable X being
a template variable. X of P being a
particular instantiation of that variable
at time point P 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 [inaudible]
introduce it. Where X of T denotes the
variable X at time T. Xt: T prime denotes
the set. [inaudible] between P and P
prime. So a discrete in this case because
we've discredited 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, a concise
representation that allows us to represent
this probability distribution over the
traject, 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. Well how
do we represent what is, a, first of all,
an infinite family of probability
distributions because you could look at
trajectories of, of duration two, five,
ten, a million, select an infinite family
of distributions. And each of these is a
distribution over of 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's 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. It's
the same building block that we use to
[inaudible] 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. Sorry the set of variable
expanding the time from zero all the way
to capital T so I haven't made any
assumptions yet in the statement so I am
just writing this down, we expressing it
in term of the chain rule for probability,
there's no chain rule for daisy and
network yet here, 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 points, t + one, given.
So, this is the state at t + one. Given
the state. At all previous claim 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 P+1, that is the state of time P+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
states. You don't care anymore about your
past. [sound] 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 up to zero, from time
zero to time T. Now everything up to T-1
is conditionally independent. Given, so
all this is conditionally independent of
P+1, given X of T. Which means that I've
allowed myself to move X of P here as the
only thing that I'm conditioned on,
conditioning on, in order to determine the
probability of distribution of X, P+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
pos. Of a robot, or an object that's
moving. Is it the case that the location
of the robot at T+1, so L of T+1+1, is
independent of, say, L of P-1, just to
simplify our lives, given L of P. 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
fix it? The one, one way to fix it is to
enrich the state description. So estimate
the mark-up assumption to better
approximation. Just like any independent
estimation the mark-up assumption is
always going to be an approximation. But
the question is, how good of an
approximation? And if we add for example
ZUT. Which is the velocity at time t and
maybe the [inaudible] at 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 proving the
Markov assumption true. An alternative
strategy which we are not going to talk
about right now is to move away from the
Markov assumption by adding dependencies.
They go further back in time. Back in
time. And that's called a semi mark up
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 intended
to deal with the question of, well fine,
so we've reduced the model to encoding A
probability of X of P+1, given X of P. But
it's still an unbounded number of
conditional probabilities. Now at least
each of them is compact, but there is
still a probabilistic models 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 of X prime, given
X. X prime denotes the next time point,
and X denotes the current time point. And
we're going to see that, that model is
replicated. For every single time point.
That is, when you're moving from time zero
to time one, you use the small one. You
move from time one to time two, you also
use the small. 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. Do 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. And on whether there is a
big football match and all sorts of thing
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
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
[inaudible] is composed of a set of random
variables. And so we're [inaudible], so 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 the sensor, whose 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 prime, and
O prime, Given, the previous state. So
given W V L 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 kinda hanging down here, if we
included it. But since 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 additional
distribution. The condition distribution
of the C plus one, gives them C. But, wa,
but. In order to represent that we still
use the same tools that we had in the
context of vary, 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 the schedule over here. The
probability of the prime, the velocity, so
this says that the weather, the first one
says that the weather [inaudible] depends
on the weather time T. The second one that
the velocity of time T plus one depends on
the weather time T and the velocity of
time T which indicates a certain
persistence in the velocity as well as the
fact that if it's raining you might slip
sideways so the velocity might change.
Also if you're careful you might
[inaudible] down if it's raining and so
again there might be an effect of the
weather and the velocity. The probability
of the location at time t plus one given
the location at time t and the velocity at
time t. The probability of the sensor
failure time t plus one give them a
failure and the previous time and the
weather. Which indicates that once the
sensor is failed it?s probably more likely
to stay failed but if many rain can make
the sensor behave badly. And then finally,
the probability of the observation of time
t plus one gives them the location of time
t plus one and the failure time t plus
one. So there are several important things
to note about this diagram that are worth
highlighting. First of all, we have a
dependencies both within and across time.
So here we have a dependency that goes
from T to T+1. And here we have a
dependency that is within T plus one
alone. What, what induces us to make a d-,
a modeling choice like this go one way
versus the other, the assumption here is
that this is a fairly [inaudible]. The
[inaudible] 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
them names. These are called intra time
slice. Edges. That means they're called,
inter, or between times five. And the
model can include a combination of both of
these. Another kind of, anoth-, 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? So we can
see that we have CPDs for the
variables of the right hand side, the
prime variables. But there is 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 CPDs 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
the entire system we also need to provide
a distribution over the initial state and
this is just the standard generic Bayesian
network which represents the probability
over the state at time 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 time zero bayesian network.
Which represents 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 if we continue copying
this indefinitely, and each copy gives us
the probability distributions of the next
time slice given the one that we just had.
And so we can construct arbitrary long
bayesian networks. So to make this definition
slightly more formal we define the notion
of a two time slide Bayesian network also
known as a 2TBN. And the 2TBN over a
set of template variables X1 up to XN, is
specifying 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 variables X1 prime up to XN prime
prime up to XN prime, and some subset of
X1 up to XN, which are the variables, the
time T variables. That affect directly.
The state at T plus one. Okay. And,
because we want this to represent a
conditional probability distribution. Only
the time T plus one 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. Using something that
looks exactly like the chain rule. So the
probability of x prime given x is the
product of each variable in time t plus
one so only the prime variables given its
parents. Which may or be, which may be in
time t plus one or time t or a combination
of both. A dynamic Bayesian network is now
basically defined by a two TBN. Which we
just defined and a Basian network over time 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, dependency
model for time zero is copied from the
base net for time zero, and this is the
transition is copied. From the bayes net that denotes
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 X dot
and Y dot are the velocities. As well as
various more semantic notions of location
like whether you?re in the lane.
[inaudible] 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. There is [inaudible] of
the state from time t to time t plus one.
As well as a variety of this intermediate
variables over here, that allow us to
represent the probability distribution in
even more compact way by incorporating
variables that do not persist to at least
a simple five model that not persist. And
finally. We see that there are a large
number of sensor observations, such as
turn signal. Whether it be cars clear on
the right and on the left, or appears to
be clear on the right and the left, 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 provide us with
a language for encoding structure
distributions over time. And by making the
assumptions of a Markovian evolution, as
well as time and variants, we can use a
single compact network to allow us to
encode arbitrarily long transitions, over
arbitrarily long time sequences. [sound].
But these assumptions that we made, the
Markovian assumption, and the time
invariance assumption, are not
immediately, correct, and might require
that we redesign the model, so as to,
enforce, so as to make these assumptions a
better approximation to, the true
underlying distribution. By, for example,
adding variables as we showed. [sound]