NystromCoRe

Less is More: Nyström Computational Regularization

LIM2

The NyströmCoRe Matlab Package

Less is More: Nyström Computational Regularization

LIM1

Copyright (C) 2015, Laboratory for Computational and Statistical Learning (IIT@MIT). All rights reserved.

By Raffaello Camoriano, Alessandro Rudi and Lorenzo Rosasco

Contact: raffaello.camoriano@iit.it

Please check the attached license file.

Introduction

This Matlab package provides an implementation of the Nyström Computational Regularization algorithm presented in the following work:

Alessandro Rudi, Raffaello Camoriano, Lorenzo Rosasco, Less is More: Nyström Computational Regularization, 16 Jul 2015, http://arxiv.org/abs/1507.04717

We study Nyström type subsampling approaches to large scale kernel methods, and prove learning bounds in the statistical learning setting, where random sampling and high probability estimates are considered. In particular, we prove that these approaches can achieve optimal learning bounds, provided the subsampling level is suitably chosen. These results suggest a simple incremental variant of Nyström Kernel Regularized Least Squares, where the subsampling level implements a form of computational regularization, in the sense that it controls at the same time regularization and computations. Extensive experimental analysis shows that the considered approach achieves state of the art performances on benchmark large scale datasets.

This software package provides a simple and extendible interface to Nyström Computational Regularization. It has been tested on MATLAB r2014b, but should work on newer and older versions too. If it does not, please contact us and/or open an issue. Examples are available in the "examples" folder.

Examples

Automatic training with default options

load breastcancer

% Perform default cross validation
[ training_output ] = nystromCoRe_train( Xtr , Ytr );

% Perform predictions on the test set and evaluate results
[ prediction_output ] = nystromCoRe_test( Xte , Yte , training_output);

Specifying a custom kernel parameter


load breastcancer

% Customize configuration
config = config_set('kernel.kernelParameter' , 0.9 , ...           % Change gaussian kernel parameter (sigma)
                    'kernel.kernelFunction' , @gaussianKernel);     % Change kernel function

% Perform default cross validation
[ training_output ] = nystromCoRe_train( Xtr , Ytr , config);

% Perform predictions on the test set and evaluate results
[ prediction_output ] = nystromCoRe_test( Xte , Yte , training_output);

Specifying a custom subsampling level range

load breastcancer

% Customize configuration
config = config_set('kernel.minM' , 10 , ...         % Minimum subsampling level
                    'kernel.maxM' , 200 , ...        % Maximum subsampling level
                    'kernel.numStepsM' , 191 , ...   % Set m steps (in this version, it must be set to maxM - minM + 1)
                    'kernel.kernelParameter' , 0.9 , ...           % Change gaussian kernel parameter (sigma)
                    'kernel.kernelFunction' , @gaussianKernel);     % Change kernel function

% Perform default cross validation
[ training_output ] = nystromCoRe_train( Xtr , Ytr , config);

% Perform predictions on the test set and evaluate results
[ prediction_output ] = nystromCoRe_test( Xte , Yte , training_output);

Some more customizations

load breastcancer

% Customize configuration
config = config_set('crossValidation.recompute' , 1 , ...           % Recompute the solution after cross validation
                    'crossValidation.codingFunction' , @zeroOneBin , ...   % Change coding function
                    'crossValidation.errorFunction' , @classificationError , ...   % Change error function
                    'kernel.kernelParameter' , 0.9 , ...           % Change gaussian kernel parameter (sigma)
                    'kernel.kernelFunction' , @gaussianKernel);     % Change kernel function

% Perform default cross validation
[ training_output ] = nystromCoRe_train( Xtr , Ytr , config);

% Perform predictions on the test set and evaluate results
[ prediction_output ] = nystromCoRe_test( Xte , Yte , training_output);

For a complete list of customizable configuration options, see the next section.

Configuration Parameters

All the configurable parameters of the algorithm can be set by means of the provided config_set function, which returns a custom configuration structure that can be passed to the nystromCoRe_train function. If no configuration structure is passed, nystromCoRe_train uses the default configuration parameters listed below. nystromCoRe_train performs the training by running the NYTRO algorithm. It returns a structure with the trained model, which can then be passed to nystromCoRe_test for performing predictions and test error assessment.

This is an example of how the configuration parameters can be customized by means of the config_set function. See the code in "examples/customCrossValidation.m" for more details.

% Customize configuration
config = config_set('crossValidation.recompute' , 1 , ...           % Recompute the solution after cross validation
                    'crossValidation.codingFunction' , @zeroOneBin , ...   % Change coding function
                    'crossValidation.errorFunction' , @classificationError , ...   % Change error function
                    'kernel.kernelParameter' , 0.9 , ...           % Change kernel parameter (sigma)
                    'kernel.kernelFunction' , @gaussianKernel);     % Change kernel function

The default configuration parametrs are reported below:

Output structures

nystromCoRe_train

nystromCoRe_test