Structured Prediction Cascades

By David J. Weiss, B. Taskar. 2010

129 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Sergey Levine
2. Jitendra Malik
3. Mohit Bansal
4. Trevor Darrell
5. Jimmy J. Lin
6. Abhinav Kumar Gupta
7. Jianfeng Gao
8. Quoc V. Le

In Natural Language Processing

1. Jimmy J. Lin
2. Lidan Wang
3. Donald Metzler
4. Hinrich Schütze
5. Christoph H. Lampert
6. Benjamin Sapp
7. Sebastian Nowozin
8. Peter Gehler

Citations in the corpus

• Learning Parameterized Skills (2012, background): “The problem of predicting a vector of possibly correlated policy features can also be addressed via structured prediction techniques [84].”
• Human Pose Estimation with Iterative Error Feedback (2015, methodology): “Stacked inference methods [31, 44, 45, 41] are another related family of methods.”
• A cascade ranking model for efficient ranked retrieval (2011, methodology): “Similar approaches for using a mean-max threshold to control runtime scoring/prediction complexity have been used in the NLP task of structured prediction [29].”
• MODEC: Multimodal Decomposable Models for Human Pose Estimation (2013, methodology): “The use of structured prediction cascades has been a successful tool for drastically reducing state spaces in structured problems [15, 24].”
• Globally Normalized Reader (2017, background): “Our framework for conditional computation whereby the search space is pruned by a sequence of increasingly complex models is broadly reminiscent of the structured prediction cascades of (Weiss and Taskar, 2010).”
• Vine Pruning for Efficient Multi-Pass Dependency Parsing (2012, unknown): “6 ) to filter indices for subsequent rounds (similar to Weiss and Taskar (2010)).”
• Efficient Higher-Order CRFs for Morphological Tagging (2013, background): “Weiss and Taskar (2010) develop cascades of models of increasing complexity in a framework based on per-ceptron learning and an explicit trade-off between accuracy and efficiency.”
• Advanced Structured Prediction (2014, methodology): “Another group of methods consider solving the Argmin problem via cascading (Felzenszwalb and McAllester, 2007; Weiss and Taskar, 2010; Munoz et al., 2010), where inference is run in stages from a coarse to fine level of abstraction.”
• IDK Cascades: Fast Deep Learning by Learning not to Overthink (2017, background): “roughput and reduce mean latency without a loss in accuracy. Though prediction cascades are well established in the machine learning literature (Rowley, Baluja, and Kanade 1998; Viola and Jones 2004; Weiss and Taskar 2010; Angelova et al . 2015; Cai, Saberian, and Vasconcelos 2015), the classic appr”