Putting permuted data into LibSVM precomputed kernel

Question

I'm doing quite simple SVM classification at the moment. I use a precomputed kernel in LibSVM with RBF and DTW.

When I compute the similarity (kernel-) matrix, everything seems to work very fine ... until I permute my data, before I compute the kernel matrix.

An SVM is of course invariant to permutations of input-data. In the below Matlab-code, the line marked with '<- !!!!!!!!!!' decides about the classification accuracy (not permuted: 100% -- permuted: 0% to 100%, dependant on the seed of rng). But why does permuting the file-string-array (named fileList) make any difference? What am I doing wrong? Have I misunderstood the concept of 'permutation invariance' or is it a problem with my Matlab-code?

My csv-files are formatted as: LABEL, val1, val2, ..., valN and all the csv-files are stored in the folder dirName. So the string array contains the entries '10_0.csv 10_1.csv .... 11_7.csv, 11_8.csv' (not permuted) or some other order when permuted.

I also tried to permute the vector of sample serial numbers, too, but that makes no difference.

function [SimilarityMatrixTrain, SimilarityMatrixTest, trainLabels, testLabels, PermSimilarityMatrixTrain, PermSimilarityMatrixTest, permTrainLabels, permTestLabels] = computeDistanceMatrix(dirName, verificationClass, trainFrac)
fileList = getAllFiles(dirName);
fileList = fileList(1:36);
trainLabels = [];
testLabels = [];
trainFiles = {};
testFiles = {};
permTrainLabels = [];
permTestLabels = [];
permTrainFiles = {};
permTestFiles = {};

n = 0;
sigma = 0.01;

trainFiles = fileList(1:2:end);
testFiles = fileList(2:2:end);

rng(3);
permTrain = randperm(length(trainFiles))
%rng(3); <- !!!!!!!!!!!
permTest = randperm(length(testFiles));

permTrainFiles = trainFiles(permTrain)
permTestFiles = testFiles(permTest);

noTrain = size(trainFiles);
noTest = size(testFiles);

SimilarityMatrixTrain = eye(noTrain);
PermSimilarityMatrixTrain = (noTrain);
SimilarityMatrixTest = eye(noTest);
PermSimilarityMatrixTest = eye(noTest);

% UNPERM
%Train
for i = 1 : noTrain
    x = csvread(trainFiles{i});   
    label = x(1);
    trainLabels = [trainLabels, label];
    for j = 1 : noTrain
        y = csvread(trainFiles{j});            
        dtwDistance = dtwWrapper(x(2:end), y(2:end));
        rbfValue = exp((dtwDistance.^2)./(-2*sigma));
        SimilarityMatrixTrain(i, j) = rbfValue;
        n=n+1
    end
end

SimilarityMatrixTrain = [(1:size(SimilarityMatrixTrain, 1))', SimilarityMatrixTrain];

%Test
for i = 1 : noTest
    x = csvread(testFiles{i});
    label = x(1);
    testLabels = [testLabels, label];
    for j = 1 : noTest
        y = csvread(testFiles{j});            
        dtwDistance = dtwWrapper(x(2:end), y(2:end));
        rbfValue = exp((dtwDistance.^2)./(-2*sigma));
        SimilarityMatrixTest(i, j) = rbfValue;
        n=n+1
    end
end

SimilarityMatrixTest = [(1:size(SimilarityMatrixTest, 1))', SimilarityMatrixTest];

% PERM
%Train
for i = 1 : noTrain
    x = csvread(permTrainFiles{i});        
    label = x(1);
    permTrainLabels = [permTrainLabels, label];
    for j = 1 : noTrain
        y = csvread(permTrainFiles{j});            
        dtwDistance = dtwWrapper(x(2:end), y(2:end));
        rbfValue = exp((dtwDistance.^2)./(-2*sigma));
        PermSimilarityMatrixTrain(i, j) = rbfValue;
        n=n+1
    end
end

PermSimilarityMatrixTrain = [(1:size(PermSimilarityMatrixTrain, 1))', PermSimilarityMatrixTrain];

%Test
for i = 1 : noTest
    x = csvread(permTestFiles{i});
    label = x(1);
    permTestLabels = [permTestLabels, label];
    for j = 1 : noTest
        y = csvread(permTestFiles{j});            
        dtwDistance = dtwWrapper(x(2:end), y(2:end));
        rbfValue = exp((dtwDistance.^2)./(-2*sigma));
        PermSimilarityMatrixTest(i, j) = rbfValue;
        n=n+1
    end
end

PermSimilarityMatrixTest = [(1:size(PermSimilarityMatrixTest, 1))', PermSimilarityMatrixTest];

mdlU = svmtrain(trainLabels', SimilarityMatrixTrain, '-t 4 -c 0.5');
mdlP = svmtrain(permTrainLabels', PermSimilarityMatrixTrain, '-t 4 -c 0.5');

[pclassU, xU, yU] = svmpredict(testLabels', SimilarityMatrixTest, mdlU);
[pclassP, xP, yP] = svmpredict(permTestLabels', PermSimilarityMatrixTest, mdlP);

xU    
xP

end

I'd be very thankful for any answer!

Regards Benjamin

Well, I do not know whether or not stackoverflow is the right place for my question, so I decided to post this on stats.stackexchange.com, too (http://stats.stackexchange.com/questions/96452/accuracy-changes-with-permutation-of-input-data-in-libsvm-with-precomputed-kerne). Feel free to answer my question here or there. Dear moderators: if this is not okay for you, feel free to delete my post. Thank you very much! — bhe, May 05 '14 at 11:49

score 0 · Answer 1 · edited May 23 '17 at 12:28

after cleaning up the code and letting a colleague of mine have a look on it, we/he finally found the bug. Of course, I have to compute the testing matrix from the training and testing samples (to let the SVM predict the testing data by using the sum over the product of alpha-values of the training vectors (they are zero for non support vectors)). Hope this clarifies the problem for any of you. To make it more clear, see my revised code below. But, as for example in using precomputed kernels with libsvm, there one with sharp eyes can also see the computation of the testing matrix with train and test vectors, too. Feel free to put comments or/and answers to this post if you have any further remarks/questions/tips!

function [tacc, testacc, mdl, SimilarityMatrixTrain, SimilarityMatrixTest, trainLabels, testLabels] = computeSimilarityMatrix(dirName)
fileList = getAllFiles(dirName);
fileList = fileList(1:72);
trainLabels = [];
testLabels = [];
trainFiles = {};
testFiles = {};   
n = 0;
sigma = 0.01;

trainFiles = fileList(1:2:end);
testFiles = fileList(2:5:end);

noTrain = size(trainFiles);
noTest = size(testFiles);

permTrain = randperm(noTrain(1));
permTest = randperm(noTest(1));

trainFiles = trainFiles(permTrain);
testFiles = testFiles(permTest);

%Train
for i = 1 : noTrain(1)
    x = csvread(trainFiles{i});
    label = x(1);
    trainlabel = label;
    trainLabels = [trainLabels, label];
    for j = 1 : noTrain(1)
        y = csvread(trainFiles{j});
        dtwDistance = dtwWrapper(x(2:end), y(2:end));
        rbfValue = exp((dtwDistance.^2)./(-2*sigma.^2));
        SimilarityMatrixTrain(i, j) = rbfValue;
    end
end

SimilarityMatrixTrain = [(1:size(SimilarityMatrixTrain, 1))', SimilarityMatrixTrain];

%Test
for i = 1 : noTest(1)
    x = csvread(testFiles{i});
    label = x(1);
    testlabel = label;
    testLabels = [testLabels, label];
    for j = 1 : noTrain(1)
        y = csvread(trainFiles{j});     
        dtwDistance = dtwWrapper(x(2:end), y(2:end));
        rbfValue = exp((dtwDistance.^2)./(-2*sigma.^2));
        SimilarityMatrixTest(i, j) = rbfValue;

    end
end

SimilarityMatrixTest = [(1:size(SimilarityMatrixTest, 1))', SimilarityMatrixTest];

mdlU = svmtrain(trainLabels', SimilarityMatrixTrain, '-t 4 -c 1000 -q');
fprintf('TEST: '); [pclassU, xU, yU] = svmpredict(testLabels', SimilarityMatrixTest, mdlU);
fprintf('TRAIN: ');[pclassT, xT, yT] = svmpredict(trainLabels', SimilarityMatrixTrain, mdlU);

tacc = xT(1);
testacc = xU(1);
mdl = mdlU;

end

Regards Benjamin

Putting permuted data into LibSVM precomputed kernel

1 Answers1