•   When: Friday, February 15, 2019 from 11:00 AM to 12:00 PM
•   Speakers: Rina Dechter, Donald Bren School of Information and Computer Sciences, UC Irvine
•   Location: JC Gold Room
•   Export to iCal

Abstract:

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 numerous application areas. Reasoning over probabilistic graphical models typically involves answering inference queries, such as computing the most likely configuration (maximum a posteriori or MAP) or evaluating the marginals or the normalizing constant of a distribution (the partition function). A task called marginal MAP generalizes these two by maximizing over a subset of variables while marginalizing over the rest, which is similar to sequential decision making for maximizing expected utility.

Exact computation of such queries is known to be intractable in general, leading to the development of many approximate schemes, the major categories of which are variational methods, search algorithms, and Monte Carlo sampling. The key is to leverage ideas and techniques from the three inference paradigms, and integrating them to provide hybrid solutions that inherit their respective strengths. In the past decade, my research group at UCI has developed state-of-the art algorithms based on such integration, winning a few solver competitions. In this talk I will review the main principles behind the AND/OR search for graphical models and show how it can be guided by heuristics based on variational inference (e.g., decomposition bounds such as weighted mini-bucket and cost-shifting schemes) for solving probabilistic and deterministic graphical models queries. The emerging solvers allow flexible trading off memory for time and time for accuracy and aim for anytime behavior that generates not only an approximation that improves with time, but also confidence bounds which become tighter with more time.

Short Bio:

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 was a Co-Editor-in-Chief of Artificial Intelligence 2011-2018 and she was elected as the conference chair of IJCAI-2022.