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

SSG Seminar Abstract

Probabilistic calculations on graphs with cycles:
Perturbations and bounds

Martin Wainwright
SSG Doctoral student

Graphical models are a powerful framework for representing and manipulating probability distributions; accordingly, they are studied in a variety of fields (e.g., coding, medical diagnosis, image processing). Probabilistic calculations like state and parameter estimation can be performed efficiently for graphs without cycles (i.e., trees). However, these same problems for graphs with cycles are typically intractable, which motivates the development of approximate methods.

This talk focuses on estimation in discrete-valued processes, and in particular on the problem of approximating the expectation of a function under some target distribution on an arbitrary graph. Many estimation tasks (e.g., computing posterior marginals, or conditional means) can be formulated in this way. In this talk, I will discuss two related approaches to this problem. The first approach is to develop perturbation expansions for the expectation in terms of a tractable distribution (typically a tree). Such an expansion provides valuable information about sensitivity to changes in model parameters. It also gives rise to a series of increasingly accurate approximations; however, like other methods for discrete problems, the cost of computing higher order corrections increases exponentially. Like many other approximate techniques (e.g., belief propagation), a weakness is the lack of error bounds. Accordingly, the goal of the second part is to use probabilistic quantities, again obtained from tractable distributions, to derive lower and upper bounds on the actual expectations. The results are illustrated by application to the problem of computing posterior marginal distributions for discrete processes on graphs with cycles.

Problems with this site should be emailed to