Linear SVM prediction time is scaling in an unexpected manner based on training data

Question

I'm using LIBSVM to do some training as it was recommended by Andrew Ng and is used under the hood in SciKit Learn. LIBSVM is doing something different than what I expect though:

My beliefs are as follows:

• LIBSVM when set to use a linear kernel is a reasonable implementation of a linear SVM
• A linear SVM model should just be a hyper plane and a margin.
• A n-1 dimensional hyper-plane can be represented by a single n dimensional vector and constant.
• A prediction performed against a single hyper-plane should be constant with respect to the number of training examples used to train the model.
• Linear kernel SVMs are roughly equivalent to logistic regression.

In practice, LIBSVM models trained with a linear kernel show different prediction times depending on how many data points the model was trained with. When I look in the model file, there are many vectors in the file instead of a single one.

Can anyone illuminate what I am missing?

Answer 1

Your problem is the following assumption:

LIBSVM when set to use a linear kernel is a reasonable implementation of a linear SVM

LIBSVM solves any SVM training problem in the exact same way, whether you are using linear SVM or kernel SVM. This general purpose solving strategy is not efficient for linear SVM. This is also why the linear SVM solution you get by LIBSVM contains support vectors $\mathbf{SV}$, weights $\alpha$ and a bias term $\rho$ rather than just the hyperplane of interest.

Prediction with any LIBSVM model is done using the following equation:

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

As per this equation, prediction complexity is linear in the number of support vectors for all LIBSVM models. For the linear kernel $\kappa(\mathbf{x}_i, \mathbf{z}) = \mathbf{x}_i^T\mathbf{z}$ the decision function can be rewritten as follows $f(\mathbf{z}) = \mathbf{w}^T\mathbf{z} + \rho$, where

$$\mathbf{w} = \alpha \times\mathbf{SV}^T.$$

This is not done in LIBSVM for linear models.

For linear models you should use LIBLINEAR, not LIBSVM. This software is designed by the same people, specifically to train linear models. It behaves exactly like you expect it to.

Answer 2

LibSVM is implemented for general case and doesn't make the optimization that you suggest of abstracting from support vectors to a single plane and margin. You should look at LibLinear.