TD4: Constraint processing and Probabilistic reasoning from a Graphical Models Perspective
Tutorialists: Rina Dechter
Sunday, August 4th, afternoon
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 schemes (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.