Support Vector Machines Template Library SVMTL

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:

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!
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).

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

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).
Cristianini, N.; Shawe-Taylor, J.; "Support Vector Machines and other kernel-based learning methods". Cambridge University Press. 2000.

Support Vector Machines Template Library SVMTL

Contents