NIPS 2008 Workshop
Approximate inference - How far have we come?
Basic information
Date: Saturday, Dec. 13, 2008
Length: One day
Location: Whistler, British Columbia, Canada
Organizers:
Amir Globerson,
David Sontag
and Tommi Jaakkola
Description
Graphical models have become a key tool in representing multi-variate
distributions in many machine learning applications. They have been
successfully used in diverse fields such as machine-vision,
bioinformatics, natural language processing, reinforcement learning
and many others.
Approximate inference in such models has attracted a great deal of
interest in the learning community, and many algorithms have been
introduced in recent years, with a specific emphasis on inference in
discrete variable models. These new methods explore new and exciting
links between inference, combinatorial optimization, and convex
duality. They provide new avenues for designing and understanding
message passing algorithms, and can give theoretical guarantees when
used for learning graphical models.
The goal of this workshop is to assess the current state of the field
and explore new directions. We shall specifically be interested in
understanding the following issues:
- State of the field: What are the existing methods, and how do they
relate to each other? Which problems can be solved using existing
algorithms, and which cannot?
- Quality of approximations: What are the theoretical guarantees
regarding the output of the approximate inference algorithms (e.g.,
upper or lower bounds on MAP or marginals, optimality within a given
factor, certificates of optimality etc.). How do these depend on the
complexity of the inference algorithms (i.e., what is the tradeoff
between running time and accuracy)?
- Efficiency issues: What type of convergence guarantees do different
message passing algorithms have, and what can be proven about their
running time? Do certain methods dominate others in terms of these
guarantees? When are message passing algorithms better than other
"out-of-the-box" convex optimization tools?
- Scalability and applicability to real problems: How well do current
methods scale to large-scale problems (e.g. in machine-vision and
bioinformatics)? How hard is inference in typical real-world
problems? Although inference is generally NP hard, this does not imply
that a specific real problem cannot be solved exactly. The relative
success of approximate inference methods on some real-world problems
suggests that we are working in a regime of problems that are amenable
to approximation. Can we characterize it?
- Connections across fields: Approximate inference is closely linked
to problems in combinatorial optimization (e.g., maximization of
functions over graphs, or counting problems), and in convex
optimization (e.g., dual ascent methods). What techniques can we
"import" from these fields, and what from our advances in approximate
inference can we "export" back?
-
Inference and learning: Learning the parameters of a graphical
model often requires inference as a subroutine. How should approximate
inference be embedded into learning? Once a model is learned, what
inference method should be used, and how should it relate to the one
used during learning? What efficient algorithms exist for joint
learning and inference?
-
Continuous models: Many new approximate inference approaches have
been developed in the context of discrete variable models. How can
these be applied to continuous valued or hybrid models?
The workshop will bring together researchers from diverse communities:
machine learning researchers working on approximate inference,
practitioners of graphical models from applied communities such as
machine-vision and bioinformatics, and researchers from the
optimization community who are working on similar problems but in the
optimization context.
Schedule
Morning session 7:30am-10:45am
7:35am Introduction, review and themes, Organizers
8:00am Approximate inference in graphical models: Some progress and
open questions, Martin Wainwright
8:40am Convergent Message-Passing algorithms for LP-relaxations and Convex Free Energy minimization using Fenchel Duality, Tamir Hazan
9:10am Break
9:20am MAP Estimation: Setting the State of the Art with Duality Theory and Linear Programming, Nikos Komodakis
9:50am Approximate inference methods for stochastic optimal control theory, Bert Kappen
Afternoon session 3:30pm-4:10pm
3:30pm Andrew Eats Crow: Why Reinforcement Learning Might be Useful After All; Massive-Scale, Relational MAP Inference by MCMC with Delayed Reward, Andrew McCallum
4:10pm Inference in Large Scale Nonparametric Bayesian Models, Max Welling
4:50pm Break
5:00pm Learning Deep Boltzmann Machines, Ruslan Salakhutdinov
5:30pm Approximate inference as exact inference on approximate models: theoretical results and practical implications, Adnan Darwiche
6:10pm Discussion and Conclusions, Organizers