LP relaxations for MAP inference

Add to your list(s) Download to your calendar using vCal

• Adrian Weller (University of Cambridge)
• Thursday 22 October 2015, 14:30-16:00
• Engineering Department, CBL Room 438.

If you have a question about this talk, please contact Yingzhen Li.

For discrete graphical models, we consider the combinatorial optimization challenge of finding a mode configuration of variables, that is a setting of all variables that has highest probability, also known as maximum a posteriori (MAP) inference. We shall provide a brief introduction to a popular method that frames the problem as an integer linear program then relaxes this to a linear program (LP) over continuous variables. For computational efficiency, the space over which this LP is performed is typically relaxed to an outer bound called the local polytope which enforces only pairwise consistency. We shall also discuss tighter relaxations that have recently been explored with some success, and touch on message passing methods that may be used to try to solve the problem efficiently.

readings:

Wainwright and Jordan 2008 Graphical models, exponential families and variational inference Section 8

David Sontag’s phd thesis chapter 2

This talk is part of the Machine Learning Reading Group @ CUED series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge University Engineering Department Talks
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Engineering Department, CBL Room 438
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Journal Clubs
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• ML
• Machine Learning Reading Group
• Machine Learning Reading Group @ CUED
• Machine Learning Summary
• Quantum Matter Journal Club
• Required lists for MLG
• School of Technology
• Simon Baker's List
• TQS Journal Clubs
• Trust & Technology Initiative - interesting events
• bld31
• custom
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list

Note that ex-directory lists are not shown.