Margin-based Decomposed Amortized Inference

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 905–913, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Margin-based Decomposed Amortized Inference Gourab Kundu∗ and Vivek Srikumar∗ and Dan Roth University of Illinois, Urbana-Champaign Urbana, IL. 61801 {kundu2, vsrikum2, danr}@illinois.edu Abstract Given that structured output prediction is typically performed over entire datasets, one natural question is whether it is pos- sible to re-use computation from earlier inference instances to speed up inference for future instances. Amortized inference has been proposed as a way to accomplish this. In this paper, first, we introduce a new amortized inference algorithm called the Margin-based Amortized Inference, which uses the notion of structured margin to identify inference problems for which pre- vious solutions are provably optimal. Sec- ond, we introduce decomposed amortized inference, which is designed to address very large inference problems, where ear- lier amortization methods become less ef- fective. This approach works by decom- posing the output structure and applying amortization piece-wise, thus increasing the chance that we can re-use previous so- lutions for parts of the output structure. These parts are then combined to a global coherent solution using Lagrangian relax- ation. In our experiments, using the NLP tasks of semantic role labeling and entity- relation extraction, we demonstrate that with the margin-based algorithm, we need to call the inference engine only for a third of the test examples. Further, we show that the decomposed variant of margin-based amortized inference achieves a greater re- duction in the number of inference calls. 1 Introduction A wide variety of NLP problems can be natu- rally cast as structured prediction problems. For * These authors contributed equally to this work. some structures like sequences or parse trees, spe- cialized and tractable dynamic programming algo- rithms have proven to be very effective. However, as the structures under consideration become in- creasingly complex, the computational problem of predicting structures can become very expensive, and in the worst case, intractable. In this paper, we focus on an inference tech- nique called amortized inference (Srikumar et al., 2012), where previous solutions to inference prob- lems are used to speed up new instances. The main observation that leads to amortized inference is that, very often, for different examples of the same size, the structures that maximize the score are identical. If we can efficiently identify that two inference problems have the same solution, then we can re-use previously computed structures for newer examples, thus giving us a speedup. This paper has two contributions. First, we de- scribe a novel algorithm for amortized inference called margin-based amortization. This algorithm is on an examination of the structured margin of a prediction. For a new inference problem, if this margin is larger than the sum of the decrease in the score of the previous prediction and any increase in the score of the second best one, then the previ- ous solution will be the highest scoring one for the new problem. We formalize this intuition to derive …

Content truncated to 500 words