SVM classification step on embedded system with RBF kernel

Question

I am about to implement the classification step of a trained SVM model. I would like to ask, how the actual classification step is carried out (assuming I would like to port that step to some low-level language)?

From my trained Matlab SVM model I have:

Support vectors (n * #features)
the bias (1x1)
alpha (n * 1)
shift (1 x n)
scaleFactor (1 x n)
sigma for rbf (1x1)

Given a new sample (1 x #features) I would carry out the classification step as follows:

1. Scale and shift each feature in sample:

   sample = scaleFactor * (sample + shift)

2. Calculate the kernel mapping with an RBF with

   kernel = exp(-1/(2*sigma^2) * ||x-y_i||^2)

where x is my new sample and y every single support vector (?)

Now I am puzzled:

• Is every distance between x and y_i multiplied by the appropriate alpha?
• Are all these values summed and then the bias added followed by a simple sign()?

So:

sign(sum(exp(-1/(2*sigma^2) * ||x-y_i||^2) * alpha_i) + bias)

Would that be correct? If so, to save memory on runtime - is there a way to divide the kernel computation in a way that not all support vectors have to be stored in memory?

Answer 1

Assuming X is the matrix of new data points (size m x n where each row is an example), you can tackle the problem by considering several kernel.

1. if your kernel is linear (i.e. dot product)
   The predicted labels can be easily evaluated by
   p = X * model.w + model.b;
   where model.w is an array containing the free parameters of the hyperplane and model.b is the bias.
2. if your kernel is RBF (i.e. Gaussian)

% square and sum new data points by rows  
X1 = sum(X.^2, 2);  
% square and sum SVs  
X2 = sum(model.SV.^2, 2)';  
% evaluate exponential for RBF formula  
K = bsxfun(@plus, X1, bsxfun(@plus, X2, - 2 * X * model.SV'));  
% evaluate kernel  
K = model.kernelFunction(1, 0) .^ K;  
% multiply Gram matrix by SV labels  
K = bsxfun(@times, model.SVL', K);  
% multiply again by alphas  
K = bsxfun(@times, model.alphas', K);  
% gather final predictions
p = sum(K, 2);

where model.alphas is the Lagrange Multiplier vectors, model.kernelFunction() is the kernel function, model.SV are the Support Vectors and model.SVL are the Support Vectors Labels

3. or an arbitrary kernel, apply the standard rule:

for i = 1:m  
    prediction = 0;  
    for j = 1:size(model.SV, 1)  
        prediction = prediction + model.alphas(j) * model.SVL(j) * model.kernelFunction(X(i,:)', model.SV(j,:)');  
    end  
    p(i) = prediction + model.b;  
end

After all that you might want to shrink the predicted labels vector p in a friendly binary format:

predictedLabels(p >= 0) =  1;
predictedLabels(p <  0) =  0;

and predictedLabels is now your final output.