André Martins (IST, CMU, Priberam)

Structured Prediction, MAP Inference, and Dual Decomposition with Augmented Lagrangians

Abstract:

In the first half of the talk, I will give an overview on structured prediction, a general framework which encompasses many learning formalisms, such as those underlying hidden Markov models, conditional random fields, and structured support vector machines. Applications abound in natural language processing, computer vision, and computational biology. In the second half, I will focus on approximate MAP inference in discrete graphical models. I will describe a new consensus-based algorithm that solves an LP relaxation of the original problem, while exploiting the structure of the graphical model. It combines an augmented Lagrangian method (the "alternating directions method of multipliers," or ADMM) with the dual decomposition method, hence we call it DD-ADMM. Our algorithm is provably convergent, parallelizable, and suitable for fine decompositions of the graph. We show how it can efficiently handle problems with (possibly global) structural constraints via simple sort operations. Experiments on synthetic and real-world data show that our approach compares favorably with the state-of-the-art.

This is joint work with Mario Figueiredo, Pedro Aguiar, Noah Smith and Eric Xing.

--

Bio: André Martins is a PhD student in Language Technologies, at Instituto Superior Técnico and Carnegie Mellon University. His main research interests are machine learning, natural language processing, and optimization.