A Large-Margin Framework for Learning Structured Prediction Models

  • Ben Taskar | University of California at Berkeley

We present a novel statistical estimation framework for structured models based on the large margin principle underlying support vector machines. We consider standard probabilistic models, such as Markov networks (undirected graphical models) and context free grammars as well as less conventional, combinatorial models such as weighted graph-cuts and matchings. Our framework results in several efficient learning formulations for complex prediction tasks. Fundamentally, we rely on the expressive power of convex optimization problems to compactly capture inference or solution optimality in structured models. Directly embedding this structure within the learning formulation produces compact convex problems for efficient estimation of very complex and diverse models. For some of these models, alternative estimation methods are intractable. In order to scale up to very large training datasets, we develop problem-specific optimization algorithms that exploit efficient dynamic programming and combinatorial optimization subroutines. We have applied this framework to a diverse range of tasks, including handwriting recognition, 3D terrain classification, disulfide connectivity prediction, hypertext categorization, natural language parsing and bilingual word alignment.

Speaker Details

Ben Taskar received his Ph.D. in Computer Science from Stanford University working with Daphne Koller. He is currently a postdoctoral fellow with Michael Jordan at the Computer Science Division, University of California at Berkeley. One of his interests is structured model estimation in machine learning, especially in computational linguistics, computer vision and computational biology. Last year, he co-organized a NIPS workshop on this emerging topic. His work on structured prediction has received best paper awards at NIPS and EMNLP conferences.

Watch Next