"Support Vector Machines for Structured Output Prediction"

Abstract

Over the last decades, much of the research on discriminative learning has focused on problems like classification and regression, where the prediction is a single univariate variable. But what if we need to predict complex objects like trees, orderings, or alignments?  Such problems arise, for example, when a natural language parser needs to predict the correct parse tree for a given sentence, when one needs to optimize a multivariate performance measure like the F1-score, or when predicting the alignment between two proteins.

This talk discusses a support vector approach and algorithm for predicting such complex objects. It generalizes conventional classification SVMs to a large range of structured outputs and multivariate loss functions. While the resulting training problems have exponential size, there is a simple algorithm that allows training in polynomial time. The algorithm is implemented in the SVM-Struct software and empirical results will be given for several examples.

Bio

Thorsten Joachims is an Associate Professor in the Department of Computer Science at Cornell University.  In 2001, he finished his dissertation with the title "The Maximum-Margin Approach to Learning Text Classifiers: Methods, Theory, and Algorithms", advised by Prof. Katharina Morik at the University of Dortmund.  From there he also received his Diplom in Computer Science in 1997 with a thesis on WebWatcher, a browsing assistant for the Web.  From 1994 to 1996 he was a visiting scientist at Carnegie Mellon University with Prof. Tom Mitchell. His research interests center on a synthesis of theory and system building in the field of machine learning, with a focus on Support Vector Machines and machine learning with text.  He authored the SVM-Light algorithm and software for support vector learning.