Stochastic Systems Group  

Stochastic processes defined on graphs arise in a variety of fields, including coding theory, artificial intelligence, and statistical image processing. This informal session provides a tutorial overview of graphical models, with particular emphasis on associated issues in estimation theory. We state the HammersleyClifford theorem, which describes how graphical structure constrains the probability distribution. We illustrate by considering some special cases, including hidden Markov models on chains, Markov random fields, and multiscale trees.
One important problem is to make inferences about hidden (state) variables on the basis of other observed variables. We present algorithms with local update rules for standard estimation tasks, including MAP estimation and computing conditional marginal distributions. For singlyconnected graphs (i.e., trees), these algorithms are guaranteed to converge to the correct answer in at most T iterations, where T is the graph diameter. Various wellknown algorithms for time series (e.g., Viterbi algorithm, KalmanRTS smoother) constitute special cases of these general update rules as applied to chain graphs. Other specific examples include highly efficient algorithms for linear multiscale estimation on trees.
This tutorial overview will lay the necessary foundation for addressing issues of current interest, including estimation on graphs with cycles, and other approximate methods for inference.
Problems with this site should be emailed to jonesb@mit.edu