  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.
