[Colloquium] TTIC Talk: David Sontag, MIT

[Julia MacGlashan]

*REMINDER*

When:             *Wednesday, Apr 14 @ 11:00am
*

Where:           * TTIC Conference Room #526*, 6045 S Kenwood Ave, 5th Floor


Who:              * **David Sontag*, MIT


Title:          *      **Approximate Inference in Graphical Models using LP
Relaxations*****



 Graphical models such as Markov random fields have been successfully
applied to a wide variety of fields, from computer vision and natural
language processing, to computational biology. Exact probabilistic inference
is generally intractable in complex models having many dependencies between
the variables.

In this talk, I will discuss recent work on using linear programming
relaxations to perform approximate inference. By solving the LP relaxations
in the dual, we obtain efficient message-passing algorithms that, when the
relaxations are tight, can provably find the most likely (MAP)
configuration.

Our algorithms succeed at finding the MAP configuration in protein
side-chain placement, protein design, and stereo vision problems. More
broadly, this talk will highlight emerging connections between machine
learning, polyhedral combinatorics, and combinatorial optimization.

Host:              Nati Srebro, nati at ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100413/e984bfba/attachment.htm