A Large-Margin Framework for Learning Structured Prediction Models

Опубликовано 6 сентября 2016, 5:40

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.