Continuous Time Bayesian Network Approximate Inference and Social Network Applications (2009)

by Yu Fan

Abstract: 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 variables.

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-Hastings 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.

Download Information

Yu Fan (2009). Continuous Time Bayesian Network Approximate Inference and Social Network Applications. Doctoral dissertation, University of California at Riverside.

Bibtex citation

@phdthesis{Fan09,
   author = "Yu Fan",
   title = "Continuous Time {B}ayesian Network Approximate Inference and Social Network Applications",
   school = "University of California at Riverside",
   schoolabbr = "UC Riverside",
   year = 2009,
   month = Dec,
}

---

full list