Speeding up MAP with Column Generation and Block Regularization
David B. Belanger, Alexandre Passos, Sebastian Riedel, Andrew McCallum · 2012
In this paper, we show how the connections between max-product message passing and linear programming relaxations for MAP al-low for a more efficient exact algorithm than standard dynamic programming. Our pro-posed 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 more than two 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 gener-ation depends on how quickly we can rule out entire sets of assignments to the edges of the chain, which is done by bounding the contri-bution 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. 1.