Structured SVM

Structured SVM

The structured support vector machine is a machine learning algorithm that generalizes the Support Vector Machine (SVM) classifier. Whereas the SVM classifier supports binary classification, multiclass classification and regression, the structured SVM allows training of a classifier for general structured output labels.

As an example, a sample instance might be a natural language sentence, and the output label is an annotated parse tree. Training a classifier consists of showing pairs of correct sample and output label pairs. After training, the structured SVM model allows one to predict for new sample instances the corresponding output label; that is, given a natural language sentence, the classifier can produce the most likely parse tree.

For a set of training instances, from a sample space and label space, the structured SVM minimizes the following regularized risk function.

The function is convex in because the maximum of a set of affine functions is convex. The function measures a distance in label space and is an arbitrary function (not necessarily a metric) satisfying and . The function is a feature function, extracting some feature vector from a given sample and label. The design of this function depends very much on the application.

Because the regularized risk function above is non-differentiable, it is often reformulated in terms of a quadratic program by introducing one slack variables for each sample, each representing the value of the maximum. The standard structured SVM primal formulation is given as follows.