Spring 2006 UMASS Amherst
Operations Research / Management Science Seminar Series

Date: Friday, April 28, 2006

Time: 11:00 AM
Location: Isenberg School of Management, Room 112

Speaker: Professor Rina Dechter

Donald Bren School of Information and Computer Science
University of California, Irvine.

Biography: 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.

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, INFORMS, and the John F. Smith Memorial Fund. The Chapter wishes to thank Professor Anna Nagurney, its Faculty Advisor, for her help and  support of this series.

For questions, please contact the INFORMS Student Chapter Representative, Ms. Tina Wakolbinger, wakolbinger@som.umass.edu