Structured prediction is a framework for solving problems of classification or regression in which the output variables are mutually dependent or constrained. These dependencies and constraints reflect sequential, spatial or combinatorial structure in the problem domain, and capturing such interactions is often as important as capturing input-output dependencies. Many such problems, including natural language parsing, machine translation, object segmentation, gene prediction, protein alignment and numerous other tasks in computational linguistics, speech, vision, biology, are not new. However, recent advances have brought about a unified view, efficient methodology and more importantly, significant accuracy improvements for both classical and novel problems. This tutorial will explain the fundamental computational and statistical challenges arising from the high dimensionality of the inputs and the exponential explosion of the number of possible joint outcomes.

I will describe the confluence of developments in several areas in resolving these challenges for broad classes of problems: large margin and online methods for prediction, variational methods for graphical model inference, and large scale combinatorial and convex optimization. I will also outline several open issues of particular difficulty in structured prediction, including asymptotic consistency, the effects of approximate inference, semisupervised and weakly supervised learning.