Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Informal Group Discussion:
Tutorial Overview Of Graphical Models And Estimation Issues

Erik Sudderth, Dewey Tucker, and Martin Wainwright
SSG Doctoral Students

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 Hammersley-Clifford 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 singly-connected 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 well-known algorithms for time series (e.g., Viterbi algorithm, Kalman-RTS 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