Continuous Time Bayesian Network Approximate Inference and Social Network Applications
Yu Fan · 2009
Many real world systems evolve asynchronously in continuous time, for examplecomputer networks, sensor networks, mobile robots, and cellular metabolisms.Continuous time Bayesian Networks (CTBNs) model such stochastic systems incontinuous time using graphs to represent conditional independencies amongdiscrete-valued processes. Exact inference in a CTBN is often intractable as thestate space of the dynamic system grows exponentially with the number ofvariables.In this dissertation, we first focus on approximate inference in CTBNs. Wepresent an approximate inference algorithm based on importance sampling. Unlikeother approximate inference algorithms for CTBNs, our importance samplingalgorithm does not depend on complex computations, since our sampling procedureonly requires sampling from regular exponential distributions which can be donein constant time. We then extend it to continuous-time particle filtering andsmoothing algorithms. We also develop a Metropolis-Hasting algorithm for CTBNsusing importance sampling. These algorithms can estimate the expectation of anyfunction of a trajectory, conditioned on any evidence set containing the valuesof subsets of the variables over subsets of the time line.We then apply our approximate inference algorithms to learning social networkdynamics. Existing sociology models for social network dynamics require directobservation of the social networks. Furthermore, existing parameter estimationtechnique for these models uses forward sampling without considering the givenobservations, which affects the estimation accuracy. In this dissertation, wedemonstrate that these models can be viewed as CTBNs. Our sampling-basedapproximate inference method for CTBNs can be used as the basis of anexpectation-maximization procedure that achieves better accuracy in estimatingthe parameters of the model than the standard learning algorithm from thesociology literature. We extend the existing social network models to allow forindirect and asynchronous observations of the links. A Markov chain Monte Carlosampling algorithm for this new model permits estimation and inference.Experiments on both synthetic data and real social network data show that ourapproach achieves higher estimation accuracy, and can be applied to varioustypes of social data.