Advances in Search and Inference for Graphical Models

Tuesday morning, 17th August, 2010, Room 6.1.36

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 (e.g., branch and bound) 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 applicable to numerous optimization tasks across variety of graph-based knowledge bases such as constraint optimization, Bayesian networks and Markov decision processes.

The goal of this talk is to present the algorithmic principles behind the progress that has been made in the past decade in this area in the graphical models communities such as Constraint networks and Probabilistic networks, focusing on optimization queries and likelihood and counting queries. It will focus on: (1) how bounded-inference (e.g., mini-bucket and mini-clustering schemes) can be used to generate lower-bound and upper bound approximations and on their use as heuristics for search; (2) how these heuristics are contrasted and compare with those based on linear programming and on soft arc-consistency; (3) the role of caching goods during search; (4) how problem decomposition can be incorporated into search using AND/OR search spaces; (5) how problem structure can be exploited to yield more efficient compilation schemes for probabilistic inference and post-optimality analysis. All these enhancements yield a new generation of search algorithms (e.g., branch and bound or best-first search) that can trade-off time and space using a few controlling parameters.

Complexity analysis and empirical demonstration of all algorithms will be presented on variety of benchmarks for Max-CSP, for the Most Probable Explanation (MPE) task for probabilistic reasoning, for Integer Programming and for general constraint optimization tasks.  Example benchmarks include radio-frequency problems, linkage analysis, combinatorial auctions, and coding networks.

Short bios

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 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 since 1994, was a Radcliffe Fellowship 2005-2006 and received the 2007 Association of Constraint Programming (ACP) research excellence award.

Robert Mateescu is a postdoc researcher at Microsoft Research Cambridge UK. He received his PhD and MS degrees in Information and Computer Science (in 2007 and 2003) from the University of California Irvine, advised by Professor Rina Dechter. Between 2007-2009 he was a postdoc at Caltech, hosted by Professor Jehoshua Bruck. His current research is focused on efficiently solving very large scale optimization problems, and in particular SAT solving. Some of the topics of the past work include AND/OR search for graphical models, message-passing algorithms, compilation schemes for graphical models, data representation and coding for flash memory.

Radu Marinescu is a postdoctoral scholar at the Cork Constraint Computation Centre (4C), University College Cork, Ireland working with Professor Eugene Freuder. He received his PhD and MS degrees in Computer Science from the University of California Irvine (in 2004 and 2008, respectively) working with Professor Rina Dechter. His research focuses on automated reasoning with emphasis on high performance methods exploiting AND/OR search spaces for solving optimization tasks in probabilistic and deterministic graphical models. His recent interests are centered on decision analysis and multi-objective optimization. He co-authored papers appearing in the AIJ, JAIR, AAAI, IJCAI, UAI, CP and CPAIOR.