UAI 2004 Tutorials
(July 8)
Eliciting, Modeling, and Reasoning about Preference using CP-nets
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
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
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
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.