Aspects of Local Computation

Prof. Steffen Lauritzen (Department of Statistics, University of Oxford)

Info

Date	3rd March 2009 (week 7, Hilary Term 2009)
Time	16:30
Place	Lecture Theatre B

Abstract

A number of problems, for example associated with updating probabilities in large graphical models, involve a computation which in principle grows exponentially with the size of the problem.

However, exploiting sparsity in associated structures, essentially working with an appropriate acyclic hypergraph, fast algorithms related to dynamic programming can be developed. This lecture will describe the now basic local computation algorithm for probabilistic inference in some detail, as well as several of its closely related but different variants. Similarities and differences will be highlighted with the aim of understanding the algorithms in a unified way.