Structured SVMs

From Cohen Courses
Jump to navigationJump to search

Being edited by Rui Correia

The Method and When to Use it

Structured (or Structural) Support Vector Machines (SSVM), as the name states, is a machine learning model that generalizes the Support Vector Machine (SVM) classifier, allowing training a classifier for structured output.

In general, SSVMs perform supervised learning by approximating a mapping

where is a set of labeled training examples and is a complex structured object, like trees, sequences, or sets, instead of simple univariate predictions (as in the SVM case).

Thus, training a SSVM classifier consists of showing pairs of correct sample and output label pairs, that are used for training, allowing to predict for new sample instances the corresponding output label

In NLP one can fing a great variety of problems that rely on complex outputs, such as parsing and Markov Models for part-of-speech tagging.

The Algorithm

For a set of training instances , the SSVM minimizes the risk function:


where and Since 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.

Slightly
 different 
version 
of 
the
 loss 
function:


      

Related Papers