Structured SVMs

From Cohen Courses
Jump to navigationJump to search

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.


While on training, for a set of samples and labels , the SSVM minimizes the risk function:

where is an arbitrary function, which measures the distance between to labels and is a function on samples and labels, which extracts feature vectors. These two function are to be defined according to the problem at hand

Since the equation above is non-differentiable, one can reformulate it introducing slack variables, , representing the value of the maximum. Using this approach the SSVM comes as:



Given a sample, and a mapping one can obtain the correspondent lable. The mapping is defined as

where is the vector during the training phase.

The inference problem of solving for this maximizer over the label space is dependent on the structure of the function that varies according to the problem.

Related Papers