Professor Rina Dechter University of California, Irvine Photo albums: Class Lecture Dinner with Class Ice Cream Social with Class Colloq Talk Visiting Modern Arts Midwest Dinner w/ ConSystLab members

Talk title: Principles for Reasoning with Mixed Probabilistic and Deterministic 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. They support efficient, graph-based algorithms for a variety of reasoning tasks, including scheduling, planning and decision making, diagnosis, situation assessment, design, hardware and software verification and bio informatics tasks such as linkage analysis. It is known that all these tasks are computationally hard, and while substantial progress has been made in the last 2-3 decades pushing the computational boundaries far ahead, numerous real-life problems are still out of reach for current technologies. Advance in exact or approximate methods is crucial, with potential impact across many computational disciplines. In this talk I will describe progress made in the past 5 years on developing algorithms that can adapt to the problem's structure by recognizing and exploiting problem decomposability, equivalence and irrelevance, and through which we can 1) Efficiently and flexibly trade space for time, 2) Efficiently and flexibly trade time for accuracy, gradually transitioning into approximations, 3) Exploit deterministic relationships and 4) Trade online for offline computation. Specifically, I will focus on exact algorithms with a focus on AND/OR search spaces, and as time permit will discuss compilation schemes that exploit conditional problem decomposition, and approximation schemes that use sampling and bounded inference.

Biographical information:

Professor Rina Dechter 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 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, she was a Radcliffe fellow 2005-06 and recently awarded the ~Association of Constraint Programming award (ACP 2007) for research excellence.