FaLKM-lib
a Library for Fast Local Kernel Machines

Author: Nicola Segata <segata@disi.unitn.it>
Dipartimento di Ingegneria e Scienza dell'Informazione, University of Trento

Current version: 1.01
Date: 25.06.2009
Overview

FaLKM-lib is a C++ software library for learning with local kernel machines which is scalable for very large datasets. The library contains modules for kNN, local SVM (LSVM) classification and for local maximal margin based noise reduction. The local SVM approach showed to be statistically more accurate than SVM and, using some implemented strategies, faster than SVM and thus scalable for very large datasets (some million of samples for non high-dimensional data). The FaLKM-lib library and its algorithms are concisely introduced and formally described in the document [Segata, 2009] available here.

If you have any general comments, suggestions or problems using the code, please write to segata@disi.unitn.it.
Brief Description

Local Support Vector Machines (LSVM) have been introduced by [Blanzieri, Melgani, 2006, 2008] and proved to be statisticlaly more accurate than SVM as shown in [Segata, Blanzieri 2009a]. LSVM learning can be made scalable and dramatically faster than SVM using some approximation strategies of LSVM as shown in [Segata, Blanzieri 2009b] and some other modifications (not published yet). The LSVM approach showed to be very effective also for noise reduction (which is an important preprocessing step for other analysis and for instance-based learning) both with the original LSVM setting [Segata, Blanzieri, Delany, Cunningham, 2008] and with its scalable version [Segata, Blanzieri, Cunningham, 2009]. FaLKM-lib implements the Cover Tree data-structure [Beygelzimer, Kakade, Langford, 2006] for fast retrieval of neighborhoods in the feature space, and integrates LibSVM [Chang, Lin 2001] version 2.88 for SVM training and prediction.

FaLKM-lib consists in the following five modules:

    * FkNN is a fast implementation (using Cover Tree) of (kernel) k-nearest neighbors.
    * FkNNSVM is a fast implementation (using Cover Tree) of the accurate (i.e. non-approximated) Local SVM descried and tested in [Blanzieri, Melgani, 2006, 2008], [Segata, Blanzieri 2009b]. Very briefly it is a classifier representative of the clas of local learnin algorithms [Bottou, Vapnik 1992], and it builds, for each testing sample, a SVM model on its local neighborhood in the feature space of the training set, and uses the local SVM model to predict the label. It can give as out ut the label or a probability estimate.
    * FaLK-SVM (Fast Local Kernel Support Vector Machines) is a very fast and scalable version of FkNNSVM. The approximation is based on building a set of local SVM models covering the entire training set (with redundancy) and on predicting the label of a testing point with its nearest feature-space SVM model and other optimization as described in [Segata, Blanzieri 2009b]. In the current version we adopt Cover Tree obtaining training and testing time mush lower than SVM maintaining however a higher classification rate. FaLK-SVM consists in a training module called FaLK-SVM-train and a testing module called FaLK-SVM-predict.
    * FkNNSVM-nr is a version of FkNNSVM adapted for the use as a noise reduction method as described in [Segata, Blanzieri, Delany, Cunningham, 2008]. It is based on the probabilistic version of FkNNSVM and buils a local model in the neighbourhood of each training sample removing the sample if the probability associated with the correct classification is below a threshold. It has been shown that FkNNSVM-nr is more accurate than state-of-the-art noise reduction techniques (which are based on the majority rule) on real and artificial datasets and it is very effective for datasets perturbed by Gaussian noise and in presence of uneven class densities. A preliminari verison of FkNNSVM-nr is available here.
    * FaLKNR is a very fast and scalable version of FkNNSVM-nr based on the approximations introduced for FaLK-SVM an dit is presented in [Segata, Blanzieri, Cunningham, 2009] where it is shown to perform better than other noise-reduction techniques both in terms of competence enhancement of the training set and of computational performances.

In addition to the traditional cross-validation model selection, the modules contains primitives for performing local model selection as described for FaLKNR in [Segata, Blanzieri, Cunningham, 2009]. Moreover the library can handle multi-class data and gives as output the Accuracy, the PrecisIon, the Recall and the F-Measure.

The matematical formulations on which the modules of FaLKM-lib are based are available here, the explantions about how to use FaLKM-lin can be found in the README file in library package and at the end of this page.
Source Code and Binaries

The current realise of FaLKM-lib is the 1.0 (May 2009) and it is freely available for research and educational purposes (please read the COPYRIGHT before downloading FaLKM-lib) and can be obtained downloading the package as zip archive or tar.gz archive.

The archives contain the sources, the makefile for building the executables in Unix-based systems, the windows executables, the Makefile.win for building the executables in Windows systems using Visual Studio compiler, the README file with detailed explantations for the usage, and the COPYRIGHT file. FaLKM-lib has been tested mainly under Linux, so the more stable and safe version is the Unix-based one.
Previous versions
Current version is 1.01. Starting from verision 1.0 the modifications are:

    * 1.01: Some minor bugs corrected, addition of silent mode (-S option)
    * 1.00: First Version 

Please write to segata@disi.unitn.it if you need versions different from the current one.
How to cite FaLKM-lib
If you use FaLKM-lib please cite the library as:

Nicola Segata, FaLKM-lib: a Library for Fast Local Kernel Machines, 2009. Software available at http://disi.unitn.it/~segata/FaLKM-lib
The bibtex entry is:

@TECHREPORT{Segata2009,
  AUTHOR =       {Nicola Segata},
  TITLE =        {{FaLKM-lib v1.0: a Library for Fast Local Kernel Machines}},
  INSTITUTION =  {DISI, University of Trento, Italy},
  YEAR =         {2009},
  note = 	 {Software available at \url{http://disi.unitn.it/~segata/FaLKM-lib}}
  number =       {DISI-09-025},
}

Please cite also the paper relative to the FaLKM-lib you use; for FkNNSVM cite [Blanzieri, Melgani, 2008], for FaLKM-SVM cite [Segata, Blanzieri 2009b], for FkNNSVM-nr cite [Segata, Blanzieri, Delany, Cunningham, 2008], for FaLKNR cite [Segata, Blanzieri, Cunningham, 2009].
Benchmarks

    * Benchmarks of FkNNSVM on non-large datasets can be found in [Segata, Blanzieri 2009a]
    * Benchmarks of FkNNSVM-nr on non-large datasets can be found in [Segata, Blanzieri, Delany, Cunningham, 2008]
    * Benchmarks of FaLK-SVM vs. LibSVM (and FkNN) on 8 large datasets are available here
    * Benchmarks of FaLKNR vs. ENN, RENN, AkNN and AkNNc (implemented using Cover Trees) on 9 large datasets are available here and in [Segata, Blanzieri, Cunningham, 2008]

Aknowledgements
The author of FaLKM-lib would like to thank Enrico Blanzieri for the fruitful discussions related to local approaches for learning with kernels and his crucial support in the implementation work, and P?draig Cunningham for his suggestions about the implemented noise reduction algorithms.
References

[Segata, 2009]
	

N. Segata, FaLKM-lib v1.0: a Library for Fast Local Kernel Machines. Technical Report DISI-09-025. Department of Information Engineering and Computer Science, University of Trento, Italy, 2009. Software available at http://disi.unitn.it/~segata/FaLKM-lib

[Blanzieri, Melgani, 2006]
	

E. Blanzieri, F. Melgani, An Adaptive SVM Nearest Neighbor Classifier for Remotely Sensed Imagery. IEEE International Conference on Geoscience and Remote Sensing Symposium, 2006. pp. 3931-3934.

[Blanzieri, Melgani, 2008]
	

E. Blanzieri, F. Melgani, Nearest Neighbor Classification of Remote Sensing Images With the Maximal Margin Principle. IEEE Transactions on Geoscience and Remote Sensing. June 2008 Volume: 46, Issue: 6 On page(s): 1804-1811

[Segata, Blanzieri, 2009a]
	

N. Segata, E. Blanzieri, Empirical Assessment of Classification Accuracy of Local SVM. DISI Technical Report. Accepted for pubblication at Benelearn 09.

[Segata, Blanzieri, 2009b]
	

N. Segata, E. Blanzieri, Fast Local Support Vector Machines for Large Datasets. Proceedings of International Conference on Machine Learning and Data Mining 2009. To Appear.

[Segata, Blanzieri, Cunningham, 2009]
	

N. Segata, E. Blanzieri, P. Cunningham, A Scalable Noise Reduction Technique for Large Case-Based Systems. Proceedings of the International Conference on Case-Based Reasoning 2009. To Appear.

[Segata, Blanzieri, Delany, Cunningham, 2008]
	

N. Segata, E. Blanzieri, S.J. Delany, P. Cunningham, Noise Reduction for Instance-Based Learning with a Local Maximal Margin Approach. Technical Report.

[Beygelzimer, Kakade, Langford, 2006]
	

A. Beygelzimer, A. Kakade, J. Langford, Cover trees for nearest neighbor. Proceedings of the 23rd international conference on Machine learning, 2006.

[Bottou, Vapnik 1992]
	

L. Bottou, V. Vapnik, Local learning algorithms. Neural computation 4:(6), 1992.

[Chang, Lin 2001]
	

C.C. Chang, C.J. Lin, LIBSVM : a library for support vector machines. 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
How to use

All modules accept inputs and generate output accordingly to the LibSVM and SVM-light file format which is defined as:

<line> .=. <target> <feature>:<value> <feature>:<value> ... <feature>:<value> # <info>
<target> .=. +1 | -1 | 0 | <float> 
<feature> .=. <integer> | "qid"
<value> .=. <float>
<info> .=. <string>
The usage of each module is described below.
FkNN
FkNN takes the training set and the testing set (unless the cross-validation option is enables) and writes to the prediction output file (unless the cross-validation option is enables) the predictions corresponding to the testing examples and prints to the standard output the accuracy (and FMeasure, Precision and Recall) results. FkNN is called in the following way:

Usage: FkNN [options] training_dataset_file [testing_dataset_file output_label_file]

and the available options are:

-K neighborhood size k
-C conservative variant for the majority rule , 0 or 1 (default 0)
-R relaxation parameter for cover trees (default 1)
-t kernel_type : set type of kernel function (default 2)
        0 -- linear: u'*v
        1 -- polynomial: (gamma*u'*v + coef0)^degree
        2 -- radial basis function: exp(-gamma*|u-v|^2) [EQUIVALENT TO LINEAR KERNEL!]
-d degree : set degree in kernel function (default 3)
-r coef0 : set coef0 in kernel function (defaul 1)
-s knn strategy : (defaul 0 = majority rule)
-g gamma : set gamma in kernel function, negative values for estimation based on histogram of distances (default = -0.5 for RBF, default = 1 for polynomial kernels)
-v n: n-fold cross validation mode
-S silent mode (default 0)
 

Examples
The nearest neighbor results reported in [Segata, Blanzieri, Cunningham, 2009] are obtained in the following way:

./FkNN -t 0 -K 1 -R 3 training_set.tr testing_set.te output_file.out > accuracy_results.nn

the 10 fold cross validation for a neighborhood size of 10 using an inhomogeneous polynomial kernel of degree 3 can be obtained as follows

./FkNN -t 1 -g 1 -d 3 -r 1 -K 5 -v 10 training_set.tr 

FkNNSVM
FkNNSVM takes the training set and the testing set (unless the cross-validation option is enables) and writes to the prediction output file (unless the cross-validation option is enables) the predictions corresponding to the testing examples and prints to the standard output the accuracy (and FMeasure, Precision and Recall) results. FkNNSVM is called in the following way:

Usage: FkNNSVM [options] training_dataset_file [testing_dataset_file output_label_file]

and the available options are:

-R relaxation parameter for cover trees (default 1)
-K neighborhood size k
-t kernel_type : set type of kernel function (default 2)
        0 -- linear: u'*v
        1 -- polynomial: (gamma*u'*v + coef0)^degree
        2 -- radial basis function: exp(-gamma*|u-v|^2)
-c cost : set the parameter C of C-SVC, epsilon-SVR, and nu-SVR (default 1)
-d degree : set degree in kernel function (default 3)
-g gamma : set gamma (locally) in kernel function, negative values for estimation based on histogram of distances (default = -0.5 for RBF, default = 1 for polynomial kernels)
-r coef0 : set coef0 in kernel function
-S silent mode (default 0)

Examples
The following setting is for apply a local SVM with neighborhood size of 200, regularization parameter C equals to 10, with the RBF kernel function whose width is computed on every local model as the median of the histogram of distances in the local neighborhood:

./FkNNSVM -t 2 -c 10 -g -0.5 -K 200 training_set.tr testing_set.te output_file.out

FaLK-SVM
FaLK-SVM is divided in a training module called FaLK-SVM-train which produced the model, and in a testing module FaLK-SVM-predict that use the trained module for predicting the label of testing examples.

FaLK-SVM-train is called in the following way:

Usage: FaLK-SVM-train [options] input_dataset_file model_file

-t kernel_type : set type of kernel function (default 2)
        0 -- linear: u'*v
        1 -- polynomial: (gamma*u'*v + coef0)^degree
        2 -- radial basis function: exp(-gamma*|u-v|^2)
-L local model selection (default 0)
        0 -- no local model selecion
        1 -- local model selection on C K and kernel parameters on -M local models (the ranges are specified with -C -G -N)
-R relaxation parameter for cover trees (default 1)
-K neighborhood size k
-P assignement neighborhood size as fraction of K such that: K'=K*P (default 0.5)
-d degree : set degree in kernel function (default 3)
-g gamma : set gamma (locally) in kernel function, negative values for estimation based on histogram of distances (default = -0.5 for RBF, default = 1 for polynomial kernels)
-r coef0 : set coef0 in kernel function (default 0)
-c cost : set the parameter C of C-SVC, epsilon-SVR, and nu-SVR (default 1)
-C c values for local grid model selection separated by ':'
-G G values for local grid model selection separated by ':'
-N K values for local grid model selection separated by ':'
-M number of local models used for local model selection
-wi weight: set the parameter C of class i to weight*C, for C-SVC (default 1)
-b probability_estimates : whether to train local models for probability estimates, 0 or 1 (default 0)
-v n: n-fold cross validation mode
-S silent mode (default 0)

And the FaLK-SVM-predict:

Usage: FaLKM-predict [options] test_file model_file output_label_file

-T local model retrieval strategy (default 0)
        0 -- nn with all points
        1 -- nn with centers only
        2 -- knn with centers only
-b probability_estimates: whether to predict probability estimates, 0 or 1 (default 0);-K k for knn with centers only (default 3)
-M performance measure
-S silent mode (default 0)

Examples
The following example show hot to train a model and predict the testing labels using FaLKM-SVM with neighorhood size of 1000, assignement neighborhood size 500 (0.5*neighborhood size), regularization parameter C equals to 10, with the RBF kernel function whose width is computed on every local model as the 10 percentile of the histogram of distances in the local neighborhood:

./FaLK-SVM-train -t 2 -c 10 -g -0.1 -K 1000 -P 0.5 training_set.tr model_file.m
./FaLK-SVM-predict testing_file.te model_file.m predictions.p

For estimating the emprirical error with model selection with the settings of the last example the command line is

./FaLK-SVM-train -t 2 -c 10 -g -0.1 -K 1000 -P 0.5 -v 10 training_set.tr 

It is possible to use the local model selection and directly train the model. Based on the previous example, if we want to perform local model selection (using 10 local models) choosing C among 1,10,100,1000, g among -0.1, -0.5, -0.9 and the neighborhood size among 250, 500, 1000, 2000 the proper comamnd line is:

./FaLK-SVM-train -t 2 -L 1 -C 1.0:10.0:100.0:1000.0 -G -0.1:-0.5:-0.9 -N 250:500:1000:2000 -P 0.5 -M 10 training_set.tr model_file.m
./FaLK-SVM-predict testing_file.te model_file.m predictions.p

The same model can be evaluated faster (but probably with less accuracy) using only the centers of the models to retrieve the loacl SVM:

./FaLK-SVM-predict -T 1 testing_file.te model_file.m predictions.p

FaLKNR
FaLKNR takes the training set and the edited set on which the training set without noisy examples is written. It is called in the following way:

Usage: sFastLKM [options] input_dataset_file edited_dataset_file

-K neighborhood size k
-P assignement neighborhood size as fraction of K such that: K'=K*P (default 0.5)
-t kernel_type : set type of kernel function (default 2)
        0 -- linear: u'*v
        1 -- polynomial: (gamma*u'*v + coef0)^degree
        2 -- radial basis function: exp(-gamma*|u-v|^2)
-L local model selection (default 0)
        0 -- no local model selecion
        1 -- local model selection on C K and kernel parameters on -M local models (the ranges are specified with -C -G -N)
-R relaxation parameter for cover trees (default 3)
-d degree : set degree in kernel function (default 3)
-g gamma : set gamma (locally) in kernel function, negative values for estimation based on histogram of distances (default = -0.5 for RBF, default = 1 for polynomial kernels)
-r coef0 : set coef0 in kernel function (default 0)
-c cost : set the parameter C of C-SVC, epsilon-SVR, and nu-SVR (default 1)
-C c values for local grid model selection separated by ':'
-G G values for local grid model selection separated by ':'
-N K values for local grid model selection separated by ':'
-M number of local models used for local model selection
-wi weight: set the parameter C of class i to weight*C, for C-SVC (default 1)
-S silent mode (default 0)

The results detailed in [Segata, Blanzieri, Cunningham, 2009] are obtained performing local model selection on C, estimating the g parameter as the median of the histogram of distances in the local neighborhood, the neighborhood size fixed to 1000 and the assignement neighborhood size to 250 (0.25*neighborhood size). The command for this setting is:

./FaLKNR -t 2 -L 1 -R 3 -K 1000 -P 0.25 -C 1.0:10.0:100.0 -g -0.5 -M 10 training_set.tr edited_training_set.tr
