Learning to Speed Up Structured Output Prediction

Xingyuan Pan, Vivek Srikumar
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3996-4005, 2018.

Abstract

Predicting structured outputs can be computationally onerous due to the combinatorially large output spaces. In this paper, we focus on reducing the prediction time of a trained black-box structured classifier without losing accuracy. To do so, we train a speedup classifier that learns to mimic a black-box classifier under the learning-to-search approach. As the structured classifier predicts more examples, the speedup classifier will operate as a learned heuristic to guide search to favorable regions of the output space. We present a mistake bound for the speedup classifier and identify inference situations where it can independently make correct judgments without input features. We evaluate our method on the task of entity and relation extraction and show that the speedup classifier outperforms even greedy search in terms of speed without loss of accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-pan18b, title = {Learning to Speed Up Structured Output Prediction}, author = {Pan, Xingyuan and Srikumar, Vivek}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3996--4005}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/pan18b/pan18b.pdf}, url = {https://proceedings.mlr.press/v80/pan18b.html}, abstract = {Predicting structured outputs can be computationally onerous due to the combinatorially large output spaces. In this paper, we focus on reducing the prediction time of a trained black-box structured classifier without losing accuracy. To do so, we train a speedup classifier that learns to mimic a black-box classifier under the learning-to-search approach. As the structured classifier predicts more examples, the speedup classifier will operate as a learned heuristic to guide search to favorable regions of the output space. We present a mistake bound for the speedup classifier and identify inference situations where it can independently make correct judgments without input features. We evaluate our method on the task of entity and relation extraction and show that the speedup classifier outperforms even greedy search in terms of speed without loss of accuracy.} }
Endnote
%0 Conference Paper %T Learning to Speed Up Structured Output Prediction %A Xingyuan Pan %A Vivek Srikumar %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-pan18b %I PMLR %P 3996--4005 %U https://proceedings.mlr.press/v80/pan18b.html %V 80 %X Predicting structured outputs can be computationally onerous due to the combinatorially large output spaces. In this paper, we focus on reducing the prediction time of a trained black-box structured classifier without losing accuracy. To do so, we train a speedup classifier that learns to mimic a black-box classifier under the learning-to-search approach. As the structured classifier predicts more examples, the speedup classifier will operate as a learned heuristic to guide search to favorable regions of the output space. We present a mistake bound for the speedup classifier and identify inference situations where it can independently make correct judgments without input features. We evaluate our method on the task of entity and relation extraction and show that the speedup classifier outperforms even greedy search in terms of speed without loss of accuracy.
APA
Pan, X. & Srikumar, V.. (2018). Learning to Speed Up Structured Output Prediction. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3996-4005 Available from https://proceedings.mlr.press/v80/pan18b.html.

Related Material