acl acl2013 acl2013-237 acl2013-237-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Gourab Kundu ; Vivek Srikumar ; Dan Roth
Abstract: Given that structured output prediction is typically performed over entire datasets, one natural question is whether it is possible 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 previous solutions are provably optimal. Second, we introduce decomposed amortized inference, which is designed to address very large inference problems, where earlier amortization methods become less ef- fective. This approach works by decomposing the output structure and applying amortization piece-wise, thus increasing the chance that we can re-use previous solutions for parts of the output structure. These parts are then combined to a global coherent solution using Lagrangian relaxation. In our experiments, using the NLP tasks of semantic role labeling and entityrelation 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 reduction in the number of inference calls.
Y-W. Chang and M. Collins. 2011. Exact decoding of phrase-based translation models through Lagrangian relaxation. EMNLP. J. Cselnarteknece an cdom Mpr.es Lsaiopant:a. An2 in0t0e6g.er pCroognrsatmraminitn-bga asepdproach. In ACL. D. Gildea and D. Jurafsky. 2002. Automatic labeling of semantic roles. Computational Linguistics. R. Kate and R. Mooney. 2010. Joint entity and relation extraction using card-pyramid parsing. In Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 203–212. Asso- V. Srikumar, G. Kundu, and D. Roth. 2012. On amortizing inference cost for structured prediction. In EMNLP. p K. Toutanova, A. Haghighi, and C. D. Manning. 2008. CAom glpoubta ltio joninalt L minogdueilst fiocsr, s 3e4m:1a6n1t–i1c9 r1o.le labeling. ciation for Computational Linguistics. T. Koo, A. M. Rush, M. Collins, T. Jaakkola, and D. Sontag. 2010. Dual decomposition for parsing with non-projective head automata. In EMNLP. C. Lemar ´echal. 2001. Lagrangian Relaxation. In Computational Combinatorial Optimization, pages 112–156. M. Palmer, D. Gildea, and N. Xue. 2010. Semantic Role Labeling, volume 3. Morgan & Claypool Publishers. V. Punyakanok, D. Roth, and W. Yih. 2008. The importance of syntactic parsing and inference in semantic role labeling. Computational Linguistics. R. Reichart and R. Barzilay. 2012. Multi event extraction guided by global constraints. In NAACL, pages 70–79. S. Riedel and J. Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In EMNLP. S. Riedel. 2009. Cutting plane MAP inference for Markov logic. Machine Learning. D. Roth and W. Yih. 2004. A linear programming formulation for global inference in natural language tasks. In Hwee Tou Ng and Ellen Riloff, editors, CoNLL. D. Roth and W. Yih. 2007. Global inference for entity and relation identification via a linear programming formulation. In Lise Getoor and Ben Taskar, editors, Introduction to Statistical Relational Learning. A.M. Rush and M. Collins. 2011. Exact decoding of syntactic translation models through Lagrangian relaxation. In ACL, pages 72–82, Portland, Oregon, USA, June. A. M. Rush, D. Sontag, M. Collins, and T. Jaakkola. 2010. On dual decomposition and linear programming relaxations for natural language processing. In EMNLP. 913