Computer Science Colloquium

Tractable Learning of Structured Prediction Models

Ben Taskar

Friday, April 21, 2006 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Mehryar, (212) 998-3200


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.


Ben Taskar received his bachelor's degree with distinction in Computer Science from Stanford University. He later returned to Stanford for his master's and doctoral degrees in Computer Science. He is currently a postdoctoral fellow at the Electrical Engineering and Computer Science Department at the University of California at Berkeley. His research interests include machine learning, graphical models, large-scale and distributed convex optimization, applications in computational biology, natural language processing and computer vision. His work on structured prediction models has received best student paper award at the Neural Information Processing Systems (NIPS) conference and best paper award at the Empirical Methods in Natural Language Processing (EMNLP) conference, and his doctoral dissertation was selected runner-up for the Arthur Samuel Best Thesis Award.

top | contact