[Colloquium] Talks at TTIC: Rina Dechter, Bren School of Computer and Information Sciences, UC Irvine

[Dawn Ellis]

When:     Thursday, May 22nd at 10am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Speaker:  Rina Dechter, Bren School of Computer and Information Sciences,
              UC Irvine

Title:      Modern Exact and Approximate MAP Algorithms for Graphical
models

Abstract:

In this talk I will present several principles behind state of the art
algorithms for solving combinatorial optimization tasks defined over
graphical models (Bayesian networks, Markov networks, and constraint
networks) and demonstrate their performance on some benchmarks.
Specifically I will present branch and bound search algorithms which
explore the AND/OR search space over graphical models and thus exploit
problem’s decomposition (using AND nodes), equivalence (by caching) and
pruning irrelevant subspaces via the power of bounding heuristics. In
particular I will show how the two ideas of  mini-bucket partitioning
 which relaxes the input problem using node duplication only, combined with
linear programming relaxations ideas which optimize
cost-shifting/re-parameterization schemes, can yield tight bounding
heuristic information within systematic, anytime, search.
Notably, a MAP solver embedding these principles has in 2011 won first
place in all time categories in the PASCAL2 approximate inference
challenge.  Recent work on parallel/distributed schemes and on m-best
anytime solutions may be mentioned, as time permits.


Host:  David McAllester,  mcallester at ttic.edu

-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140519/138b1cbf/attachment.htm