On Amortizing Inference Cost for Structured Prediction

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1114–1124, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics On Amortizing Inference Cost for Structured Prediction Vivek Srikumar∗ and Gourab Kundu∗ and Dan Roth University of Illinois, Urbana-Champaign Urbana, IL. 61801 {vsrikum2, kundu2, danr}@illinois.edu Abstract This paper deals with the problem of predict- ing structures in the context of NLP. Typically, in structured prediction, an inference proce- dure is applied to each example independently of the others. In this paper, we seek to op- timize the time complexity of inference over entire datasets, rather than individual exam- ples. By considering the general inference representation provided by integer linear pro- grams, we propose three exact inference the- orems which allow us to re-use earlier solu- tions for certain instances, thereby completely avoiding possibly expensive calls to the infer- ence procedure. We also identify several ap- proximation schemes which can provide fur- ther speedup. We instantiate these ideas to the structured prediction task of semantic role la- beling and show that we can achieve a speedup of over 2.5 using our approach while retain- ing the guarantees of exactness and a further speedup of over 3 using approximations that do not degrade performance. 1 Introduction Typically, in structured prediction applications, ev- ery example is treated independently and an infer- ence algorithm is applied to each one of them. For example, consider a dependency parser that uses the maximum spanning tree algorithm (McDonald et al., 2005) or its integer linear program variants (Riedel and Clarke, 2006; Martins et al., 2009) to make pre- dictions. Given a trained model, the parser addresses * These authors contributed equally to this work. each sentence separately and runs the inference al- gorithm to predict the parse tree. Thus, the time complexity of inference over the test set is linear in the size of the corpus. In this paper, we ask the following question: For a given task, since the inference procedure predicts structures from the same family of structures (depen- dency trees, semantic role structures, etc.), can the fact that we are running inference for a large num- ber of examples help us improve the time complexity of inference? In the dependency parsing example, this question translates to asking whether, having parsed many sentences, we can decrease the parsing time for the next sentence. Since any combinatorial optimization problem can be phrased as an integer linear program (ILP), we frame inference problems as ILPs for the purpose of analysis. By analyzing the objective functions of integer linear programs, we identify conditions when two ILPs have the same solution. This allows us to reuse solutions of previously solved problems and theoretically guarantee the optimality of the so- lution. Furthermore, in some cases, even when the conditions are not satisfied, we can reuse previous solutions with high probability of being correct. Given the extensive use of integer linear programs for structured prediction in Natural Language Pro- cessing …

Content truncated to 500 words