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

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.

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.

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

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

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 |

#include <morpho/svm/Svmtl.hpp>

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

The selection of the container types control the complexity of the internal mechanisms of the library.

Selector | Description |
---|---|

vecS |
selects std::vector<> for the container |

listS |
selects std::list<> for the container |

- 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); }

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

Copyright (c) Vladimir Josef Sykora and Morphochem AG 2003