May 9, Wednesday 14:15, Room 303, Jacobs Building

Title: Principles of Reasoning with Graphical Models

Lecturer: Rina Dechter

Lecturer homepage : http://www.ics.uci.edu/~dechter/

Affiliation : University of California, Irvine

Graphical models, e.g., Bayesian networks, Markov random fields, constraint networks and influence diagrams, are knowledge representation schemes that capture independencies in the knowledge base and support efficient, graph-based algorithms for a variety of reasoning tasks. Their applications include scheduling, planning, diagnosis and situation assessment, design, and hardware and software verification. Algorithms for reasoning in graphical models are of two primary types: inference-based (e.g., variable-elimination, join-tree clustering) and search- based. Exact inference-based algorithms are exponentially bounded (both time and space) by the tree-width of the graph. Search algorithms that explore an AND/OR search space can accommodate a more flexible time and memory tradeoff but their performance can also be bounded exponentially by the tree-width. My talk will focus on overviewing the two primary types of reasoning algorithms , presenting and contrasting their properties , and considering their hybrids. If time permits, I will comment on approximations of inference (e.g., mini-bucket and belief propagation) and search (e.g., SampleSearch, AND/OR sampling and cutset sampling).