Lecture: Advanced Reasoning in Graphical Models
Professor Rina Dechter from the University of California at Irvine will deliver the seventh lecture in the Spring 2006 Operations Research / Management Science Seminar series.
Title: Advanced Reasoning in Graphical models
Abstract: Graphical models, including constraint networks, belief networks, Markov random fields 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, including scheduling, planning, diagnosis and situation assessment, design, and hardware and software verification. Algorithms for processing graphical models are of two primary types: inference-based and search-based. Inference-based algorithms (e.g., variable-elimination, join-tree clustering) are time and space exponentially bounded by the tree-width of the problem's graph. Search-based algorithms can be executed in linear space and often outperform their worst-case predictions. The thrust of advanced schemes is in combining inference and search yielding a spectrum of memory-sensitive algorithms universally applicable across graphical models.
Following an overview of principles of reasoning with graphical models developed in the last decade in constraints and probabilistic reasoning, I will introduce a new AND/OR search perspective for graphical models and the parameters that govern their space-time tradeoffs. In particular, I will prove exponential saving for linear-memory search as compared to the traditional (OR) search-space and show that in the presence of full caching, the AND/OR space is exponential in the tree-width while the OR space is exponential in the path-width. The computational power of this concept across all graphical models will be demonstrated empirically on Linkage analysis benchmarks.
This series is organized by the UMass Amherst INFORMS Student Chapter. Support for this series is provided by the Isenberg School of Management, the Department of Finance and Operations Management, and the John F. Smith Memorial Fund.
Check here for more details about this speaker series.
