[Colloquium] Sumer/Dissertation Defense/Jun 3, 2011

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Ozgur Sumer

Date:  Friday, June 3, 2011

Time:  1:00 PM

Place:  Ryerson 251

Title: Adaptive methods for exact and approximate inference

Abstract:
Many algorithms and applications involve repeatedly solving variations
of the same inference problem; for example, to introduce new evidence
to the model or to change conditional dependencies as used in
dual-decomposition methods. As the model is updated, the goal of
adaptive inference is to take advantage of previously computed
quantities to perform inference more rapidly than from scratch. This
task is especially critical for dual-decomposition methods as they
decompose a complex model into a collection of simpler subproblems
(such as trees) and iteratively solve them by changing the model
parameters at each iteration.

In this thesis, we first present algorithms for adaptive exact
inference on general graphs that can be used to efficiently compute
marginals and update MAP configurations under arbitrary changes to the
input factor graph and its associated elimination tree. We then apply
this methodology to dual-decomposition approximate inference. The key
to our approach is a linear time preprocessing step which builds a
data structure called cluster tree that can efficiently be maintained
when the underlying model is slightly modified. We demonstrate how
cluster tree can be used to compute any marginal in time that is
logarithmic in the size of the input model. Moreover, in contrast to
max-product our approach can also be used to update MAP configurations
in time that is roughly proportional to the number of updated entries,
rather than the size of the input model. This fact enables us to use
our framework to speed up the convergence of the dual-decomposition
methods particularly when combined with the high degree of parallelism
which cluster tree is easily amenable to.

To evaluate the practical effectiveness of our algorithms, we
implement and test them using synthetic data as well as for three
real-world applications: protein secondary structure prediction,
minimum-energy conformation of a protein and stereo matching. Our
experiments show that adaptive exact inference can achieve substantial
speedups over performing complete inference as the model undergoes
small changes over time. In the case of dual-decomposition methods,
this translates to achieving significant improvement in convergence
time.



Ozgur's advisors are Prof. Laszlo Babai and Prof. Umut A. Acar,  Ramgopal R. Mettu

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#osumer

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=