SVM-Light Add-ons :: Route Kernels


The Route Kernel is a tree kernel which focuses on relative positioning of substructures in the original structure. For a detailed description of the kernel see my publication list. It is implemented as a module of Alessandro Moschitti's SVM-lighT-TK 1.2 software, which, in turn, is based on SVM-Light 5.01 by Thorsten Joachims. The version implemented here is the one with local kernel defined on node labels.

 

A Brief Description

The Route Kernel is defined for labeled rooted positional trees of arbitrary but finited out-degree. It considers as features the label of a node together with the route to one of its ancestors. The route is defined as the series of indices of the edges in the shortest path connecting the two nodes. The following figure gives an example of a simple tree (left) and the set of its features (right) according to the Route Kernel.

 

Usage

The following options has been modified or added to the svm_learn command:

  • -D [0,1,2] -> 0, SubTree kernel or 1, SubSet Tree kernels or 2, Route Kernel (default 1).
    Type -D 2 to select the Route kernel (The version implemented here is the one with local kernel defined on node labels).
  • -L float -> decay factor in tree kernel (default 0.4).
    The lambda parameter of the Route and tree kernels.
  • -O int -> maximum path depth taken into account by path kernel.
    -O n let the kernel look for matching routes no longer than n.
  • -d int -> parameter d in polynomial (route) kernel
    -s float -> parameter s in sigmoid/poly (route) kernel
    -r float -> parameter c in sigmoid/poly (route) kernel.
    The polynomial version of the Route Kernel is enabled by the same options of the polynomial kernel for vectors.
The following are examples of usage:

./svm_learn -t 5 -c 1 -D 2 -C T -L 0.1 trainingset modelfile

./svm_learn -t 5 -c 1 -D 2 -C T -L 0.1 -d 2 trainingset modelfile

The first example of execution trains an SVM with the Route Kernel (lambda=0.1) to trainingset and saves the resulting model to file modelfile. The second example is identical except for the fact that it applies the polynomial version of the Route Kernel with exponent equals to 2.
  For the format of the input, please refers to this page.

 

Download

The software can be downloaded here (use tar -xzvf svm-light-ROUTE-KERNEL.tgz to uncompress the file).

 

References

If using the Route Kernel software, please refer to it as

Aiolli, F., Da San Martino, G., Sperduti, A. "Route Kernels for Trees". Appearing in Proceedings of the 26th International Conference on Machine Learning, Montreal, Canada, 2009.