UAI 2004 Tutorials

(July 8)

Eliciting, Modeling, and Reasoning about Preference using CP-nets

Download Slides


Ronen Brafman

Department of Computer Science

Ben-Gurion University

Home Page:

In the past 20 years, most of the attention of researchers in the area of knowledge representation, including the UAI community, was devoted to representing and reasoning with partial and uncertain information about the state of the world. Tremendous progress has been made on this topic, but for Bayesians, it should be quite clear that this progress must go hand in hand with progress in the area of eliciting, modeling, and reasoning with preferences. Until recently, this has not been the case, and this area has been largely overlooked.Yet, in the past few years, we have witnessed more and more work on preference elicitation and reasoning techniques. In this tutorial, I will describe one of the more extensively studied models in this area: CP-networks (short for conditional preference, or ceteris paribus networks). The development of CP-networks was largely motivated by the desire to emulate the use of structure and independence in Bayes-nets within a model of preferences. CP-networks are a graphical model based on directed graphs. Like Bayes-nets, nodes correspond to variables and edges denote the direct dependence of one's preferences over the value of one variable on the value of another variable. I will discuss the motivation behind CP-nets, their semantics, some of the algorithms used to answer queries with them, and some of their extensions.

Constraint processing: a graphical models perspective

Download Slides


Rina Dechter

Department of Information and Computer Science

University of California at Irvine

Home Page:


The tutorial will present the principles and tools that underlie reasoning with constraints, emphasizing graph-based considerations. Formulating world knowledge in terms of constraints has proven useful in the areas of vision, language comprehension, default reasoning, diagnosis, scheduling, and temporal and spatial reasoning. By placing constraints within the graphical models framework, I will be able to compare constraint processing with probabilistic reasoning along the two main reasoning paradigms: search-based and inference-based. In constraints processing, search-based algorithms are characterized by backtracking, while inference-based algorithms by variable-elimination and constraint propagation methods (also known as consistency enforcing methods.) The probabilistic parallels of these methods, (e.g., belief propagation, tree-clustering, and cutest conditioning schemes), will be discussed.

Graphical Models in Computational Molecular Biology

Download Slides Part I

Download Slides Part II

Download Slides Part III



Nir Friedman

School of Computer Science and Engineering

Hebrew University

Home Page:

Research in molecular biology is undergoing a revolution. The availability of complete genome sequences facilitates the development of high-throughput assays that can probe cells at a genome-wide scale. Such assays measure molecular networks and their components at multiple levels. These rich data illuminate the working of cellular processes from different perspectives and offer much promise for novel insights about these processes. The challenge for computational biology is to provide methodologies for transforming high-throughput heterogeneous data sets into biological insights about the underlying mechanisms. In this tutorial, I will give a short introduction to the relevant concepts in biology, survey applications of graphical models to address data analysis and discovery from the high-throughput data, and will outline some of the technical and biological challenges.

Graphical models, exponential families, and variational inference

Download Slides


Martin Wainwright

Department of Electrical Engineering and Computer Science

University of California at Berkeley

Home Page:

Graphical models are used and studied in various fields, including artificial intelligence, computational biology, image processing, and error-control coding. At the core of applying a graphical model lies a common set of challenging problems, including the computation of marginals, modes and log likelihoods, and learning parameters from data. Exact solutions are computationally prohibitive for general graphical models, which motivates the development of approximate methods.

The focus of this tutorial is the class of variational methods, which (in contrast to sampling-based approaches) provide deterministic approximations. Working within the framework of exponential families, we describe how the computation of marginals, modes, and log likelihoods can be formulated in a \emph{variational manner}: namely, as the solution of low-dimensional convex optimization problems. The tractability of exactly solving these convex programs is closely tied to the underlying graphical structure. For intractable models, we discuss how a variety of known algorithms --- including mean field, belief propagation (sum-product), max-product, and cluster variational methods --- can all be understood as solving particular non-convex approximations to the true variational principle. We also touch on new methods based on convex relaxations, and describe various open research directions that are suggested by this perspective.