Continuous Time Bayesian Network Approximate Inference and Social Network Applications
- Author(s): Fan, Yu
- Advisor(s): Shelton, Christian R
- et al.
Many real world systems evolve asynchronously in continuous time, for example
computer networks, sensor networks, mobile robots, and cellular metabolisms.
Continuous time Bayesian Networks (CTBNs) model such stochastic systems in
continuous time using graphs to represent conditional independencies among
discrete-valued processes. Exact inference in a CTBN is often intractable as the
state space of the dynamic system grows exponentially with the number of
In this dissertation, we first focus on approximate inference in CTBNs. We
present an approximate inference algorithm based on importance sampling. Unlike
other approximate inference algorithms for CTBNs, our importance sampling
algorithm does not depend on complex computations, since our sampling procedure
only requires sampling from regular exponential distributions which can be done
in constant time. We then extend it to continuous-time particle filtering and
smoothing algorithms. We also develop a Metropolis-Hasting algorithm for CTBNs
using importance sampling. These algorithms can estimate the expectation of any
function of a trajectory, conditioned on any evidence set containing the values
of subsets of the variables over subsets of the time line.
We then apply our approximate inference algorithms to learning social network
dynamics. Existing sociology models for social network dynamics require direct
observation of the social networks. Furthermore, existing parameter estimation
technique for these models uses forward sampling without considering the given
observations, which affects the estimation accuracy. In this dissertation, we
demonstrate that these models can be viewed as CTBNs. Our sampling-based
approximate inference method for CTBNs can be used as the basis of an
expectation-maximization procedure that achieves better accuracy in estimating
the parameters of the model than the standard learning algorithm from the
sociology literature. We extend the existing social network models to allow for
indirect and asynchronous observations of the links. A Markov chain Monte Carlo
sampling algorithm for this new model permits estimation and inference.
Experiments on both synthetic data and real social network data show that our
approach achieves higher estimation accuracy, and can be applied to various
types of social data.