Paper: On Amortizing Inference Cost for Structured Prediction

ACL ID D12-1102
Title On Amortizing Inference Cost for Structured Prediction
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2012

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 t...