Tractable Learning of Structured Prediction Models

Structured prediction is a fundamental machine learning task involving classification or regression in which the output variables are mutually dependent or constrained. Such dependencies and constraints reflect sequential, spatial or combinatorial structure in the problem domain, and capturing these interactions is often as important for the purposes of prediction as capturing input-output dependencies.

Probabilistic graphical models and combinatorial graph-based models are used to represent problem structure across many fields, including computational biology, vision and linguistics. Typical structured models may involve hundreds of thousands of interacting variables and parameters. In general, the standard (likelihood-based) learning of such models is intractable because of the exponential explosion of the number of possible joint outcomes.

I will present a large-margin learning framework for structured prediction that enables tractable learning for several important classes of models via convex optimization. By exploiting the underlying combinatorial problem structure, I will derive a simple, efficient and scalable learning algorithm. I will demonstrate practical applications of the approach for problems in object recognition, protein folding and machine translation.