CSAIL Event Calendar: Previous Series

Advanced Reasoning in Graphical Models

Speaker: Rina Dechter , Donald Bren School of Information and Computer Science, University of California at Irvine
Date: March 7 2006
Time: 4:00PM to 5:00PM
Location: 32-D463 (Stata Center - Star Conference Room)
Host: Brian C. Williams, MIT CSAIL

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 will be demonstrated empirically as time permits.

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 Mathematics 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 100 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.

See other events that are part of Robotics Seminar Series Spring 2006

See other events happening in March 2006