Artificial Intelligence

Probabilistic Reasoning Meets Heuristic Search

Friday, April 13, 2018, 11:00am - 12:00pm PDTiCal
6th floor large conference room
This event is open to the public.
AI Seminar
Rina Dechter, UC Irvine

Graphical models, including constraint networks, Bayesian networks, Markov random fields and influence diagrams, have become a central paradigm for knowledge representation and reasoning in Artificial Intelligence, and provide powerful tools for solving problems in a variety of application domains, including coding and information theory, signal and image processing, data mining, learning, computational biology, and computer vision. Although past decades have seen considerable progress in algorithms in graphical models, many real-world problems are of such size and complexity that they remain out of reach. Advances in exact and approximate inference methods are thus crucial to address these important problems with potential impact across many computational disciplines. Exact inference is typically NP-hard, motivating the development of approximate and anytime techniques.

After summarizing the main principles behind the AND/OR search guided by heuristics based on variational inference (e.g., weighted mini-bucket and cost-shifting schemes) for solving graphical models queries, I will focus on recent work for solving the marginal map task, a query that combines, and generalizes optimization and summations queries and is far harder than both. These type of queries appears in sequential decision making and in particular in planning under uncertainty. The emerging solvers aim for anytime behavior that generates not only an approximation that improves with time, but also upper and lower bounds, which become tighter with more time.

Rina Dechter’s research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing, and probabilistic reasoning. She is a Chancellor's Professor of Computer Science at the University of California, Irvine. She holds a Ph.D. from UCLA, an M.S. degree in applied mathematics from the Weizmann Institute, and a B.S. in mathematics and statistics from the Hebrew University in Jerusalem. She is an author of Constraint Processing published by Morgan Kaufmann (2003), and Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms by Morgan and Claypool publishers, 2013, has co-authored close to 200 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research (JAIR), and Journal of Machine Learning Research (JMLR). She is a Fellow of the American Association of Artificial Intelligence 1994, was a Radcliffe Fellow 2005–2006, received the 2007 Association of Constraint Programming (ACP) Research Excellence Award, and she is a 2013 ACM Fellow. She has been Co-Editor-in-Chief of Artificial Intelligence since 2011. She is also co-editor with Hector Geffner and Joe Halpern of the book Heuristics, Probability and Causality: A Tribute to Judea Pearl, College Publications, 2010.

« Return to Events