Course:CPSC522/Dynamic Bayesian Networks

Dynamic Bayesian Networks

A Dynamic Bayesian Network is a Bayesian Network over time sequences with arcs connecting adjacent time sequences

Principal Author: Bronson Bouchard
Collaborators:

Abstract

This page describes properties of Dynamic Bayesian Networks, how they are different from Hidden Markov Models, and briefly describes inference.

Builds on

A Dynamic Bayesian Network is a Bayesian Networks that is extended to include a temporal probability model.

Related Pages

Hidden Markov Models are a basic case of a Dynamic Bayesian Network where the state is represented by one random variable.

Content

Overview

A Dynamic Bayesian Network (DBN) is a belief network that models a set of variables and their dependencies at a given time but includes dependencies between steps through time. This can be modeled by a pair of Bayesian Networks made of an initial Bayesian Network which contains the prior probability distribution and a Bayesian network that models the transition from one time step to another, usually called a "Two-Timeslice Bayesian Network (2TBN)." In a first-order model the parent of any node in a time slice can be within the time slice or in the previous time slice, higher order models allow a parent to be in a further time step from the current but complicates the model. The benefit of the temporal component is the belief in a variable can be changed depending on the observations in the previous time steps.

The Dynamic part of a DBN is only with regard to the belief that can be made by making temporal observations, the network structure must remain static. While stepping through time no variables can be added or removed and the conditional probability distributions cannot be changed. Additionally there cannot be a dependency from a future time step to a previous time step

The main difference between a DBN and a Hidden Markov Model is that a DBN represents the hidden state as a set of random variables where the Hidden Markov Model only uses a single variable. DBNs provide more freedom in model and conditional probability distribution (CPD) structure.

One of the applications of DBNs is detecting sensor failure. If several sensor can be modeled to have some conditional dependence on the states in previous time steps then when a sensor detects something abnormal it can use the observations made in previous time steps and infer whether it is a true reading.

Definition

With the assumption of a first-order transition model a DBN can be defined formally as follows.
Given a collection of random variables $X_{t}^{i}=(X_{t}^{1},X_{t}^{2}...X_{t}^{N})$ at any time slice $t$ which are either hidden or observable and prior distribution $P(X_{1})$.
The 2TBN can be defined as
$P(X_{t}|X_{t-1})=\prod _{i=1}^{N}P(X_{t}^{i}|Pa(X_{t}^{i})$
where $Pa(X_{t}^{i})$ denotes the parent of $X_{t}^{i}$.
Each variable $X_{t}^{i}=(X_{t}^{1},X_{t}^{2}...X_{t}^{N})$ has a conditional probability distribution that defines $P(X_{t}^{i}|Pa(X_{t}^{i})$ where $Pa(X_{t}^{i})$ can either be in the current time step or the previous.
Unrolling the DBN for T time slices results in the joint distribution of
$P(X_{1:T})=\prod _{t=1}^{T}\prod _{i=1}^{N}P(X_{t}^{i}|Pa(X_{t}^{i})$

Inference

Performing inference on a Dynamic Bayesian Network is done in the same way as with a Bayesian Network. The limitation being, unless the number of time steps t since the start is small, the inference will be computationally impossible to compute exactly. This is because the Bayesian Network at time step t has to be unrolled to the initial state, which can be nearly infinite time steps. The inference can instead be done approximately, one way is by Particle Filtering, which works to reduce the number of samples required for the inference. There are also a few tasks which are specific to the temporal domain, mainly Filtering, Smoothing, Prediction, and Decoding. Filtering is the process of updating the current belief state by recursive estimations using the previous states. Smoothing, or hindsight, is the task of estimating the state by using all the observations made up to the current time step. Prediction is done by using the belief of the current state, after t time steps, to predict the state at some number of time steps in the future. Decoding, or most probable explanation, is the process computing the most likely hidden variables given all observations made that could have caused some observations in the current state.

Learning

Learning in DBNs is done in a similar way to traditional BNs. When the structure is fully known and the values for parameters need to be learned, the EM Algorithm can be applied as in normal Bayes Nets with the addition that parameters must span time steps and must not change for a given variable. When the structure is unknown it can be learned in the same fashion as in a BN because the structure will not change between time steps, the only difference being that the parent of a variable can be in the current time step or the previous time step.

Example

In this example a very simple model of an engine in a car is used to demonstrate some of the concepts of a DBN.

Figure 1. The example initial Bayesian Network

Figure 2. The example Two-Timeslice Bayesian Network

Figure 3. The example DBN unrolled for three time steps

The set of variables is $X_{t}={CoolantLeak,CoolantLevel,FaultyHeadGasket,BrokenThermostat,CoolingFanSpeed,EngineOverheating}$
$X^{1}=CoolantLeak$, $X^{2}=CoolantLevel$ ... , $X^{5}=EngineOverheating$.
$X^{2},X^{4},$ and $X^{5}$ are observable, and $X^{1},X^{3},$ and $X^{4}$ are hidden variables corresponding to some problems that can occur.
We can define our initial BN as in figure 1, the only initial dependency is that the initial coolant level depends on the coolant leak. We can also define a 2TBN as in figure 2 where all variables in $X$ are persistent across time slices, or $X_{t+1}^{i}$ is dependent on $X_{t}^{i}$. Unrolling the 2TBN in figure 2 with the initial BN from figure 1 for three time steps results in the Bayes Net in figure 3. Assuming the parameters are known we can perform inference tasks on the model. If we are at time step 3 and we are unsure of our observation of $X^{5}=EngineOverheating$ we can perform filtering with our previous two time steps and update our current belief of the model. Additionally, if we observe our engine is overheating at time step 3 and we want an explanation we can step go through the previous two time steps and find the highest probability hidden variables along the trip through time and make a guess as to what caused the over heating. We can also predict whether our engine will overheat in the future given our current belief in the state of the model from our observations made.

Applications

DBNs can be used in a variety of different applications that have temporal data and can benefit from the more complex models. DBNs are used in robotics for such things as understanding human interaction, collision avoidance tasks, and action choice. DBNs are also applied in speech recognition, computer vision, and bioinformatics.

To Add

Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.