Structured Prediction Cascades
Structured prediction tasks pose a fundamental trade-o between the need for model complexity to increase predictive power and the limited computational resources for inference in the exponentially-sized output spaces such models require. We formulate and develop structured prediction cascades: a sequence of increasingly complex models that progressively lter the space of possible outputs. We represent an exponentially large set of ltered outputs using max marginals and propose a novel convex loss function that balances ltering error with ltering eciency. We provide generalization bounds for these loss functions and evaluate our approach on handwriting recognition and part-of-speech tagging. We nd that the learned cascades are capable of reducing the complexity of inference by up to ve orders of magnitude, enabling the use of models which incorporate higher order features and yield higher accuracy.