Abstract

Constraint networks and Bayesian networks 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.

Speaker 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 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. She has been Co-Editor-in-Chief of Artificial Intelligence, since 2011.

Slides

Please send any questions, concerns or comments to Rina Dechter.