Rina Dechter

Bren School of Computer and Information Sciences, UC Irvine

 

Abstract
In this talk I will present several principles behind state of the art algorithms for solving combinatorial optimization tasks defined over graphical models (Bayesian networks, Markov networks, and constraint networks) and demonstrate their performance on some benchmarks.

Specifically I will present branch and bound search algorithms which explore the AND/OR search space over graphical models and thus exploit problem’s decomposition (using AND nodes), equivalence (by caching) and pruning irrelevant subspaces via the power of bounding heuristics. In particular I will show how the two ideas of mini-bucket partitioning which relaxes the input problem using node duplication only, combined with linear programming relaxations ideas which optimize cost-shifting/re-parameterization schemes, can yield tight bounding heuristic information within systematic, anytime, search.

Notably, a MAP solver embedding these principles has in 2011 won first place in all time categories in the PASCAL2 approximate inference challenge. Recent work on parallel/distributed schemes and on m-best anytime solutions may be mentioned, as time permits.

Bio:
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, an 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 150 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research and journal of Machine Learning (JLMR). She was awarded the Presidential Young investigator award in 1991, is a fellow of the American association of Artificial Intelligence since 1994, was a Radcliffe Fellowship 2005-2006 and received the 2007 Association of Constraint Programming (ACP) research excellence award. She has been Co-Editor-in-Chief of Artificial Intelligence, since 2011.