Ben Taskar, University of Pennsylvania
Structured Prediction Cascades.
Structured prediction tasks are limited by a fundamental trade-off
between the need for model complexity to increase predictive power and
the limited computational resources for inference in
exponentially-sized output spaces such models require. We address this
trade-off by learning a cascade of increasingly complex models that
progressively filter the space of possible outputs. We represent an
exponentially large set of filtered outputs using max marginals and
propose a novel convex loss function that balance filtering error with
filtering efficiency. We develop generalization bounds for both
accuracy and efficiency and evaluate our approach on sequential
structured prediction tasks with large Markov order. We show very
large increases of efficiency compared to unfiltered baselines and
significantly outperform heuristic filtering baselines.