Tutorial: Constraint Processing and Probabilistic Reasoning from a Graphical Models Perspective

Abstract:
Constraint networks and Bayesian network can be viewed within the general framework of graphical models which includes also Markov random fields, cost networks and influence diagrams. Graphical models are knowledge representation schemes that capture independencies in the knowledge base and support efficient, graph-based algorithms for a variety of tasks, including scheduling, planning, diagnosis and situation assessment, design, and
hardware and software verification.

Algorithms for processing constraints and probabilistic models are of two primary types:inference-based and search-based and they support exact and approximate algorithms. Exact Inference (e.g., variable elimination, join-tree clustering) are time and space exponentially bounded
by the tree-width of the problem's graph. Exact Search-based algorithms (e.g., backtracking search) can be executed in linear space and often outperform their worst-case predictions. Constraint propagation schemes that approximate inference, can be applied with a bounded time and space. Likewise stochastic scheme (e.g, local search and sampling schemes) can be interpreted as approximate full search. The thrust of advanced schemes is in finding the right balance between search and inference within a hybrid scheme.

The tutorial will present the algorithmic principles behind the progress that has been made in the past decades in constraint processing and probabilistic reasoning for answering a variety of queries such as: determining consistency and finding one or all solutions, finding optimal solutions and answering likelihood and counting queries. Complexity analysis and empirical demonstration will be presented on variety of benchmarks. Example benchmarks include radio-frequency problems, linkage analysis, combinatorial auctions, and coding networks.

Bio:
Rina Dechter research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing, and probabilistic reasoning. She is a 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 over 150 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 in 2005, received the 2007 Association of Constraint Programming (ACP) Research Excellence Award, and she is a 2013 ACM Fellow. She is a UCI Chancellor Professor as of 2017. 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.