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.
Speaker Biography
David Sontag is a Ph.D. candidate in Computer Science at MIT. He received his Bachelor’s degree in Computer Science from the University of California, Berkeley in 2005. His research focuses on theory and practical algorithms for learning and probabilistic inference in large statistical models. His work has been awarded with an outstanding student paper award at NIPS in 2007 and a best paper award at UAI in 2008. He currently has the Google Fellowship in Machine Learning.