Sunday, Jan 29, 2006, 11:15-12:15
Room 309
--------------------------------------------------------------------------------
Yair Weiss
Title:
Solving NP-hard problems in practice – lessons from
computer vision and computational biology
Abstract:
It is often useful to formulate problems in vision
and in computational biology as
energy minimization problems.
For many of these problems, finding the global optimum is NP
hard and researchers have focused
on approximation methods.
From an application standpoint, using approximations is
problematic
because when things fail we don't
know whom to blame - the energy function
or the approximate minimization.
In this talk I will describe our recent successes in finding
the
GLOBAL optimum for energy functions in stereo vision, side
chain prediction and protein design.
Our approach is based
on a classical technique - linear
programming (LP) relaxations, but
with a novel twist - we use a
variant of belief propagation
to solve the LP relaxation. By
using belief propagation,
we can find the global optimum for
large, real-world
problems in a few minutes.
Joint work with Talya Meltzer and Chen Yanover