Speedmachines: Anytime structured prediction

Structured prediction plays a central role in machine learning appli-cations from computational biology to computer vision. These models require significantly more computation than unstructured models, and, in many applications, algorithms may need to make predictions within a computational budget or in an anytime fashion. In this work we pro-pose an anytime technique for learning structured prediction that, at training time, incorporates both structural elements and feature compu-tation trade-offs that affect test-time inference. We apply our technique to the challenging problem of scene understanding in computer vision and demonstrate efficient and anytime predictions that gradually improve towards state-of-the-art classification performance as the allotted time in-creases.