DISTINGUISHED LECTURE: 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 focusing on “mixed networks”, a recently proposed graphical model that permits expressing both probabilistic information and constraints, explicitly.

Rina Dechter is a professor of Computer Science at the University of California, Irvine. She received her PhD in Computer Science at UCLA in 1985, a MS degree in Applied Mathematic from the Weizmann Institute and a B.S in Mathematics and Statistics from the Hebrew University, Jerusalem. Her research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing and probabilistic reasoning. Professor Dechter is an author of “Constraint Processing” published by Morgan Kaufmann, 2003, has authored over 50 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research and Logical Method in Computer Science (LMCS). She was awarded the Presidential Young investigator award in 1991, is a fellow of the American association of Artificial Intelligence and is a Radcliffe fellow 2005-06.