libsvm on MATLAB with rbf kernel: Compute distance from hyperplane

Question

I have a One-Versus-All classification task with 80 different labels. In order to parallelize the problem to take advantage of multiple nodes on a computer cluster, I first trained 80 binary SVM classifiers in parallel with MATLAB's frontend of libSVM. All of them use the default RBF kernel. The models are cross-validated and all get dumped to disk, so I can load them at any time later on and run predictions on testing data. The idea is to run every model on the testing data and assign every testing point the label of the classifier that provides me with the most confident response, in classic OVA fashion.

Unfortunately, for binary classification tasks, the function svm_predict does not output confidences of any form, for instance distance from the margin or probabilities. I quote the following from the general-purpose (top-level) README of libSVM:

`svm-predict' Usage

Usage: svm-predict [options] test_file model_file output_file

options:

-b probability_estimates: whether to predict probability estimates, 0 or 1 (default 0); for one-class SVM only 0 is supported

This tells us that we cannot use probability estimates for binary SVMs, which would be fine if we had some other estimate of the classifier's confidence for every test point. For multi-class SVMs, svm_predict outputs such a confidence value, as this quote from the MATLAB readme (libsvm-root/matlab/README) of libsvm suggests:

Result of Prediction

The function 'svmpredict' has three outputs. The first one, predictd_label, is a vector of predicted labels. The second output, accuracy, is a vector including accuracy (for classification), mean squared error, and squared correlation coefficient (for regression). The third is a matrix containing decision values or probability estimates (if '-b 1' is specified). If k is the number of classes in training data, for decision values, each row includes results of predicting k(k-1)/2 binary-class SVMs. For classification, k = 1 is a special case. Decision value +1 is returned for each testing instance, instead of an empty vector. For probabilities, each row contains k values indicating the probability that the testing instance is in each class. Note that the order of classes here is the same as 'Label' field in the model structure.

So, not only does this give me some decision values based on an All-Versus-All fashion (since each row contains $k \choose 2$ values), instead of my desired One-Versus-All fashion, for k=1 this row is not even well-defined, giving me a decision value of +1. Now, if I used a linear kernel instead, computing the distance from the hyperplane for a test point x would be very easy, I would just have to do $w \dot x + b$. This post from Stats shows that this is possible:

How to find the distance from data point to the hyperplane with MATLAB SVM?

And the question-answer pair "How could I generate the primal variable w of linear SVM" from the libsvm FAQ:

http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f415

shows how one can retrieve the primal variable $\vec{w}$ from the dual $\vec{\alpha}$ by using variables stored in the trained model. In the case of the RBF kernel, however, I am not sure at all how I can find such a decision value. Is there any way I can calculate this without having to repeat all my experiments again with a linear kernel instead?

Answer 1

The decision value (distance to $\mathbf{w}$) for a test instance $\mathbf{z}$ is:

$$f(\mathbf{z}) = \sum_{i\in SV} \alpha_i y_i \kappa(\mathbf{x}_i, \mathbf{z}) - \rho$$

In LIBSVM models, svm_coef contains $\alpha \cdot y$, the RBF kernel function is defined as $\kappa(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i-\mathbf{x}_j\|^2)$. The support vectors are stored in SV.

So what you need to do is compute the decision values yourself based on the content of the model object. Retraining is not necessary, everything you need is available.

You'll need to take care in the structure of the support vectors and coefficients, which is poorly documented. I don't remember the details myself anymore so I can't provide the full code, but it's not that difficult.