Structured SVMs

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 $h$

$h:X\rightarrow Y$

where $x=\{(x_{1},y_{1}),...,(x_{n},y_{n})\}$ is a set of labeled training examples and $Y$ 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.

Training

While on training, for a set of samples and labels $(x_{n},y_{n})\in X\times Y,n=1,...,l$, the SSVM minimizes the risk function:

$\min _{w}||w||^{2}+C\sum _{n=1}^{l}\max _{y\in Y}(\Delta (y_{n},y)+w'\Psi (x_{n},y)-w'\Psi (x_{n},y_{n}))$

where $\Delta$ is an arbitrary function, which measures the distance between to labels and $\Psi$ is a function on samples and labels, which extracts feature vectors.

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

$\min _{w,\xi }||w||^{2}+C\sum _{n=1}^{l}\xi _{n}$

      $s.t.w'\Psi (x_{n},y_{n})-w'\Psi (x_{n},y)+\xi _{n}\geq \Delta (y_{n},y),n=1,...,l\forall y\in Y$

      $\xi _{n}\geq 0,n=1,...,l$

Testing

At test time, only a sample is known, and a prediction function maps it to a predicted label from the label space . For structured SVMs, given the vector obtained from training, the prediction function is the following.

Therefore, the maximizer over the label space is the predicted label. Solving for this maximizer is the so called inference problem and similar to making a maximum a-posteriori (MAP) prediction in probabilistic models. Depending on the structure of the function Ψ, solving for the maximizer can be a hard problem.

Related Papers

• I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support Vector Learning for Interdependent and Structured Output Spaces, ICML, 2004.
• Optimization Algorithms
  • Taskar 
et 
al.
(2003):

 SMO
 based 
on 
factored 
dual

  • Bartlet
 et 
al. 
(2004) 
and 
Collins 
et 
al. 
(2008):

 exponentiated 
gradient

  • Tsochantaridis 
et 
al. 
(2005): 

cutting 
planes 
(based 
on
 dual)

  • Taskar
 et 
al. 
(2005):

 dual 
extragradient

  • Ratliff
 et
 al.
 (2006):

 (stochastic) 
subgradient
 descent

  • Crammer
 et 
al. 
(2006):

 online
“passive‐aggressive”
 algorithms