TechTalks from event: ICML 2011

Structured Output

  • An Augmented Lagrangian Approach to Constrained MAP Inference Authors: Andre Martins; Mario Figueiredo; Pedro Aguiar; Noah Smith; Eric Xing
    We propose a new fast algorithm for approximate MAP inference on factor graphs, which combines augmented Lagrangian optimization with the dual decomposition method. Each slave subproblem is given a quadratic penalty, which pushes toward faster consensus than in previous subgradient approaches. 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.
  • Max-margin Learning for Lower Linear Envelope Potentials in Binary Markov Random Fields Authors: Stephen Gould
    The standard approach to max-margin parameter learning for Markov random fields (MRFs) involves incrementally adding the most violated constraints during each iteration of the algorithm. This requires exact MAP inference, which is intractable for many classes of MRF. In this paper, we propose an exact MAP inference algorithm for binary MRFs containing a class of higher-order models, known as lower linear envelope potentials. Our algorithm is polynomial in the number of variables and number of linear envelope functions. With tractable inference in hand, we show how the parameters and corresponding feature vectors can be represented in a max-margin framework for efficiently learning lower linear envelope potentials.
  • Inference of Inversion Transduction Grammars Authors: Alexander Clark
    We present the first polynomial algorithm for learning a class of inversion transduction grammars (ITGs) that implement context free transducers -- functions from strings to strings. The class of transductions that we can learn properly includes all subsequential transductions. These algorithms are based on a generalisation of distributional learning; we prove correctness of our algorithm under an identification in the limit model.
  • Minimal Loss Hashing for Compact Binary Codes Authors: Mohammad Norouzi; David Fleet
    We propose a method for learning similarity-preserving hash functions that map high-dimensional data onto binary codes. The formulation is based on structured prediction with latent variables and a hinge-like loss function. It is efficient to train for large datasets, scales well to large code lengths, and outperforms state-of-the-art methods.