Fast Intersection Kernel SVMs

Below is a C++ implementation of the fast Intersection Kernel SVM classifier described in the paper:

Classification Using Intersection Kernel Support Vector Machines is efficient.
Subhransu Maji and Alexander C. Berg and Jitendra Malik.
In Proceedings, CVPR 2008 (to appear).
pdf
The source code is available as a tar.gz file libsvm-mat-2.8.1-fast.tar.gz(updated on 05/19/08).

For intallation untar the file and read the instructions in README and READMEFAST.
Run test.m in MATLAB after compiling the code. It runs a toy benchmark problem.

%training data%
numtr = 1000;
numte = 50000;
dim = 100;
trd = rand(numtr,dim);
trl = (rand(numtr,1) > 0.5)+1;
%test data%
ted = rand(numte,dim);
tel = (rand(numte,1) > 0.5)+1;

model = svmtrain(trl,trd,'-s 0 -t 4');
tic;
[p,acc,dec] = svmpredict(tel,ted,model);
svmtime=toc;

nbins = [10 20 30 40 50 80 100 150 200 250 300]; %number of divisions
for i = 1:length(nbins)
  teststring = sprintf('-v 0 -n %d',nbins(i));
  [fe,fpwc,fpwl,ft(i,:)] = fastpredict(tel,ted,model,teststring); 
  err_e(i)   = mean(abs(dec-fe));
  err_pwc(i) = mean(abs(dec-fpwc));
  err_pwl(i) = mean(abs(dec-fpwl));
end

%%
numtrs = [100 200 500 1000 1500];
numte = 50000;
dim = 100;
%test data%
ted = rand(numte,dim);
tel = (rand(numte,1) > 0.5)+1;
nbins = 100;
clear err_e; clear err_pwc; clear err_pwl; clear ft;clear nsv;svmtime;
for i = 1:length(numtrs)
    %training data%
    numtr = numtrs(i);
    trd = rand(numtr,dim);
    trl = (rand(numtr,1) > 0.5)+1;

    model = svmtrain(trl,trd,'-s 0 -t 4');
    tic;[p,acc,dec] = svmpredict(tel,ted,model);svmtime(i)=toc;
    nsv(i) = model.totalSV;
    teststring = sprintf('-v 0 -n %d',nbins);
    [fe,fpwc,fpwl,ft(i,:)] = fastpredict(tel,ted,model,teststring); 
    err_e(i)   = mean(abs(dec-fe));
    err_pwc(i) = mean(abs(dec-fpwc));
    err_pwl(i) = mean(abs(dec-fpwl));
end

Output Graphs:

Caltech 101

Using 15 training and test examples per category, we get about 52% accuracy rate on average.
The graphs below show the error rate and speed of classification as a function of number of bins on a random run(gets 51.22% accuracy).
Total Classification Times : libSVM 130.63s, piecwise linear 3.52s and piecewise constant 2.86s, with 40 bins.(45x speedup).

Matlab source files to run these experiments are available as a tar.gz file fiksvm_caltech101.tar.gz (You will also need libsvm-mat-2.8.1-fast.tar.gz)
You will need the Caltech 101 dataset to compute the features from scratch. We also provide a precomputed feature set for this dataset.

Plots in the Paper:

We tested both accuracy and classification speeds on INRIA pedestrian dataset, DC pedestrian Dataset and Caltech 101.
(Note that the run times for caltech 101 are suitably scaled to refect times for 10,000 examples and averaged among categories.)

back