Stochastic Systems Group  

Stochastic processes defined on graphs arise in a variety of fields, including coding theory, artificial intelligence, and statistical image processing. In part I of this tutorial overview, we presented the basics of graphical models, and recursive algorithms for performing exact calculations in singlyconnected graphs (i.e., trees). (Slides are available here).
Here we consider problems of estimation on graphs with cycles, including both exact and approximate methods. An important example of an exact method is the junction tree algorithm, which forms cluster nodes in order to convert a loopy graph to a tree. Standard propagation rules can then be applied to the resulting tree. In practice, junction tree is of limited use, since large clusters lead to slow algorithms. Other exact methods are stochastic in nature, and include Gibbs sampling and MCMC methods.
A simple approximate method is to apply the standard tree propagation rules to loopy graphs, where they are no longer guaranteed to compute the correct answer nor to converge. Nonetheless, they have been applied to some loopy graphs with remarkable success (e.g., turbo coding). More recently, some theoretical results have been obtained, which we summarize. Lastly, we discuss the class of variational methods (including mean field type approximations), which can be used to obtain both approximations, and error bounds.
Problems with this site should be emailed to jonesb@mit.edu