/libsvm

Experimental extension of LIBSVM, supporting arbitrary kernels via dynamically loaded library

Primary LanguageC++BSD 3-Clause "New" or "Revised" LicenseBSD-3-Clause

Multi-core support and Arbitrary kernel in LIBSVM

This is a fork of LIBSVM which adds support for arbitrary kernels, implemented as an external dynamically loaded library. It also incorporates the patch that enables OpenMP multi-core support and extend the support to other portions of the code. This fork was tested only on OpenSUSE and CentOS.

New options

svm-train recognizes a new value of 5 for option -t, which selects the external kernel. It also recognizes two new options, -l to specify the file name of the library implementing the kernel and -x to specify the parameters for the kernel (e.g. $\gamma$ for the Gaussian Radial Basis Function). The new options are reflected in the model generated by svm-train and are recognized by svm-predict.

svm-train also recognizes a -V option for outputting to console the git tag (version).

Dynamic library implementing the kernel

The dynamic library implementing the kernel must expose two functions:

  • void init(const char *)
  • double kernel(const struct svm_node *, const struct svm_node *)

init() is used to acquire the kernel parameters if any. The string it receives as argument is the one specified via option -x.

kernel() takes two objects and is supposed to return the value of the kernel for those two objects.

You can refer to tanimotoRbf_kernel.c for a complete example. It implements a kernel which is the composition of Gaussian RBF (with its bandwidth parameter $\gamma$) and the Tanimoto coefficient: $ T(A,B) = \frac{\sum_{i=1}^d \min(a_i,b_i)}{\sum_{i=1}^d (a_i + b_i) - \sum_{i=1}^d \min(a_i,b_i)} $

To obtain a library from tanimotoRbf_kernel.c, one can use the following commands: gcc -fPIC -c -Wall tanimotoRbf_kernel.c gcc -shared tanimotoRbf_kernel.o -Wl,-soname,tanimotoRbf_kernel.1 -o tanimotoRbf_kernel.so.1.0.1 -lc

Source code is provided for Tanimoto kernel, Tanimoto+RBF, and InfiniteKnot-Spline of degree 1 (deg-1 INK-Spline) kernel.

OpenMP support

In this fork, parallelization on multi-core via OpenMP is supported when:

  • Computing kernel values
  • Selecting the new working set
  • Swapping entries in the cache (cache::swap_index())
  • a few other places

The patch suggested in LIBSVM FAQ only addresses the first item. This is enough in many cases, because generally the majority of CPU time is spent calculating the kernel values.

However, this last statement is not always true.

With parallelization applied only to kernel computations, one would observe that, especially for larger problems (say, 150k training examples) and for large cache sizes (option -m set to, say, 80000, i.e. 80GB) the processor occupancy on a system with many cores drops often to 100% (from the max of N*100% in a system with N cores) indicating "no parallelism" and eventually stays most of the time at that level. This happens when the cache manages to serve many hits and therefore there is no need to recalculate the kernel.

One would not notice this behaviour unless the cache is big enough for the hit rate to be large.

Also, investigations indicated that the majority of CPU time when the "no parallelism" issue occurs is spent in Cache::swap_index(). Its cost in fact increases linearly with the size of the cache. This is one more reason for the "no parallelism" condition to arise for large sizes of the kernel cache.