Morphochem

Support Vector Machines Template Library SVMTL

Contents

Description
Motivation
Design
Template Parameters
Header Files
Kernels
Container Selectors
Examples
References

Description

The SVMTL is a generic library that provides functionalities for the calculation and manipulation of support vector machines (SVM). The sole and only algorithm SVMTL provides is the Platt algorithm [Platt, 1999], however is very easy to write algorithms using SVMTL interface.
Support Vector Machines are learning systems that use a hypothesis space of linear functions in a high dimensional feature space, trained with a learning algorithm from optimization theory that implements a learning bias derived from statistical learning theory [Cristianini and Shawe-Taylor, 2000].
Platt algorithm was designed to speed up the quadratic programming problem required to calculate SVMs. A quadratic programming problem is characterized by the minimization (or maximization) of a quadratic function bounded to linear constraints.
A detailed descriscription of SVM is outside the scope of this documentation. We refer you to Burge's tutorial for a complete introduction to SVM.

Motivation

As the time of writing this documentation (August 2003) SVM are useful classification methods. The idea was to use them to classify biologically active molecules.
Facing the requirement of a fast training algorithm for SVM, the author (me) developed the library with the two most common objectives of OOP in mind: extensibility and reusability. I used generic programming to achieve those objectives: the svm class is highly orthogonalized.

Design

Following is a diagram of class dependencies on the SVMTL:

  training class  -----------------
      ^                             \   ------------|
      |                              >  |           |
      |   objective function   ----->   | svm class |
      |     ^                        >  |           |
      |     |                       /   ------------|
    kernel functor  ---------------


Being the svm class the main object to be instantiated by the user, giving the desired selectors.

Template Parameters


  svm<KernelT,PointsBigContainer,WeightsContainerT,b_Type,AlphasContainerT,
  TargetsContainer,ErrorContainerT,ToleranceT,CType,SigmaT>

Table 1:Template parameters for the svm class
Parameter Description Default Models
KernelT Type of kernel selector: linear_kernelS, gaussian_kernelS,polynomial_kernelS, or hyper_tangentS linear_kernelS complete type
PointsBigContainer Type of the sequence of sequences that contain the training points std::vector<std::vector<double> > sequence of sequences
WeightsContainerT Selector for the type of sequence that contain the weights morpho_svm::vecS complete type
b_Type Type for the bias value double floating point type
AlphasContainerT Selector for the type of sequence that contain the alphas morpho_svm::vecS complete type
TargetsContainer Type of the sequence that contain the target points std::vector<double> sequence
ErrorContainerT Selector for the type of sequence that contain the errors morpho_svm::vecS complete type
ToleranceT Type for the tolerance double floating point
CType Type for the C value double floating point
SigmaT Type for the Sigma value double floating point

Header Files

#include <morpho/svm/Svmtl.hpp>

Kernels

Different types of kernel functions are provided with the library. As you select the kernel with the specific selector given to the template parameters to the svm class, you will need to call a distinctive constructor for the svm class, specialized for that particular kernel. Table 2 shows the constructor arities for the 4 kernel types:

Table 2:svm class constructors
Kernel Type Description svm class Constructor prototype
linear_kernelS Linear kenel: K(x,y) = (x dot y)
svm(ToleranceT tol, CType e_C, examples_container_t& points,
    targets_container_t& targets)
gaussian_kernelS Gaussian kenel: K(x,y) = (exp (- |x - y|^2 / (2 * sigma^2) ) )
svm(const SigmaT e_sigma, const ToleranceT tol, const CType e_C,
    examples_container_t& points, targets_container_t& targets)
polynomial_kernelS Polynomial kernel: K(x,y) = (((x dot y) + bias) ^ degree)
svm(const SigmaT e_degree, const SigmaT e_kernel_bias,
    ToleranceT tol, CType e_C, examples_container_t& points,
    targets_container_t& targets)
hyper_tangentS Hyperbolic kernel: K(x,y) = tanh(sigma*(x dot y) - shift)
svm(const SigmaT e_sigma, const SigmaT e_shift,
    ToleranceT tol, CType e_C, examples_container_t& points,
    targets_container_t& targets,  const SigmaT dummy)

Container Selectors

Selectors are complete types (usually empty structs) that allows template specialization.
The selection of the container types control the complexity of the internal mechanisms of the library.

Table 3:container selectors
Selector Description
vecS selects std::vector<> for the container
listS selects std::list<> for the container

Examples

Following is an example on how to use the class in client code:
  1. Declare the object:
      morpho_svm::svm<>  svm_class(tol, C, training, target);  // linear kernell
    
    notes:
    The target container contains the class each set belongs to. The classes are represented with values of -1 and 1 !!! Heuristics: C value: more than 1.0, tol: very small (less than 1.10E-4). Is recomended that the training array has been normalized!

  2. Calculate the sv. For now, just structural minimal optimization is available
      svm_class.smo_me(svm_class);
    
    At this point, we have calculated the support vectors. What's left is to calculate the separation from the hyperplane these support vectors creates, of the points we want to classify (vectors to be predicted).

  3. Calculate the output for the points to be predicted:
    	//.- For linear kernels: X^T * W - b . X being the points to predict.
    
      mult.resize(test.size());
     //Multiply:
      lata::matrix_vector(test.begin(), test.end(),svm_class.weights.begin(),mult.begin(),
        nin::multiply<double, double>(),nin::assign<double>());
     //Substract b:
      nin::permanent_substract<double, double>  subs(svm_class.b);
      std::for_each(mult.begin(), mult.end(), subs);
    
    
    	//.- For non-linear kernels: Sum[1..n.points] (alpha[i] * target[i] * kernel(X[i],point) ) - b
    
     for (int j=0; j<test.size(); ++j) {
      double result(0.0);
      for (int i=0; i<svm_class.errors.size(); ++i) {
        result+= svm_class.alphas[i] * target[i] * svm_class.kernel(training.sets[i].begin(),training.sets[i].end(),test.sets[j].begin());
      }
      result-= svm_class.b;
      all_results.push_back(result);
     }
    
    

References

  1. Platt, J.; "Fast Training of Support Vector Machines using Sequential Minimal Optimization"; Advances in Kernel Methods - Support Vector Learning, B. Schölkopf, C. Burges, and A. Smola, eds., MIT Press, (1999).
  2. Cristianini, N.; Shawe-Taylor, J.; "Support Vector Machines and other kernel-based learning methods". Cambridge University Press. 2000.

Copyright (c) Vladimir Josef Sykora and Morphochem AG 2003