Support Vector Machines for Structured Outputs

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

Over the last decade, 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, vectors, or orderings? 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 a search engine needs to predict which ranking is best for a given query. This talk will discuss a support vector approach to predicting complex objects. It generalizes the idea of margins to complex prediction problems and a large range of loss functions. While the resulting training problems have exponential size, there is a simple algorithm that allows training in polynomial time. Empirical results will be given for several examples.