Skip to main content
Unpublished Paper
Learning to Speed Up MAP Decoding with Column Generation
  • D. Belanger
  • A. Passos
  • S. Riedel
  • Andrew McCallum, University of Massachusetts - Amherst
In this paper, we show how the connections between max-product message passing for max-product and linear programming relaxations allow for a more efficient exact algorithm for the MAP problem. Our proposed algorithm uses column generation to pass messages only on a small subset of the possible assignments to each variable, while guaranteeing to find the exact solution. This algorithm is three times faster than Viterbi decoding for part-of-speech tagging on WSJ data and equivalently fast as beam search with a beam of size two while being exact. The empirical performance of column generation depends on how quickly we can rule out entire sets of assignments to the edges of the chain, which is done by bounding the contribution of the pairwise factors to the score of the solution. This provides an opportunity at the intersection of inference and learning: at training time, we can regularize the model in a way that makes inference faster without changing its structure.
Publication Date
This is the pre-published version harvested from CIIR.
Citation Information
D. Belanger, A. Passos, S. Riedel and Andrew McCallum. "Learning to Speed Up MAP Decoding with Column Generation" (2012)
Available at: