UC Riverside

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