| 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 |