AI Seminar 2004/2005

(please see the main page for schedule information)

Speaker: Ben Tasker

A Large-Margin Framework for Learning Structured Prediction Models

Abstract

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. We analyze the theoretical generalization properties of our approach and derive a novel margin-based bound for structured prediction. 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 briefly describe experimental applications to a diverse range of tasks, including handwriting recognition, 3D terrain classification, disulfide connectivity prediction, hypertext categorization, natural language parsing, email organization and image segmentation. These empirical evaluations show significant improvements over state-of-the-art methods and promise wide practical use for our framework.

Speaker Bio

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.


Maintainer is
Patrick Riley
Last modified: Sat Apr 9 20:22:40 EDT 2005