What's the speed bottleneck in sklearn.svm.SVC.predict?

Question

I'm working with some high resolution images of specimens in test tubes and I found that using an SVC to classify each pixel by HSV value helps me to a great job at segmenting out just the specimen from the rest of the image.

The problem is that it's non-trivially slow to make a prediction (other questions on the forum ask about training - this is not that). A 768x768 image takes on the order of a second.

I know enough about SVMs to understand that for each pixel the algorithm has to apply the kernel function, in my case rbf, then compute a dot product (or something like that). My best guess is that the rbf kernel is the bottleneck, but I'm still not sure why is should take so long.

Any thoughts on that? And any ideas how I can speed things up?

Answer 1

To add a separate dimension to my previous answer - there are two aspects which can impact the evaluation speed for prediction.

1. The number of support vectors - this gives the number of kernel evaluations you need to do.
2. The cost of evaluating the kernel function - which in this case is directly tied to the dimensionality of the problem, and the performance of the operations.

My previous answer focused on how to reduce the number of kernel evaluations. The other part that you can try to improve upon is to reduce the cost. There are numerous approaches to speed the evaluation of the RBF. This paper evaluates Taylor and Random Fourier approximation methods - the latter was also used in a highly scalable approach in terms of number of samples. One can also look to leverage dimensionality reduction - there are well known results in this space for e.g. using Random projection which could be relevant - in particular if the Euclidean distances are well approximated after the projection, then the RBF would also be well approximated. Note that this would generally be a pre-processing step, before training.

Answer 2

You are performing classification by pixel, so a 768x768 is in fact 589824 samples.

The number of support vectors might as well be a bottleneck, if you have many of them, because you must build a $n_\text{sv}\times n$ kernel matrix, which is huge.

Answer 3

The issue here is very likely to be the number of support vectors - if the fraction of points misclassified is just 5% then in your case you will have at least 29K support vectors.

There are several different techniques you can use to achieve a sparser solution - see for example here or here (amongst many others).

A simple alternative technique you can use (which is inspired by this paper which uses compression bounds whereby we look at the number of bits it takes to encode a solution which correctly classifies all the training points), is to create a new sparse solution from the support vectors. The idea relies on the facts that:

1. A decision plane that classifies all the points on the margins as +1/-1 will be very sparse and classify the vast majority of points correctly (in particular those beyond the margin).
2. Misclassified points can be a large fraction, but - being wrong - they don't actually do a good job supporting the separation between the classes, in particular if they have large loss. Further more, any modification to the solution can't make it perform worse from a 0-1 loss perspective for these points.
3. Points that are close to the decision boundary, but still correctly classified are more sensitive to being misclassified than points that are far from the boundary. These points are also more important in defining the "local" shape of the decision boundary.

Based on the above, we define the following approach. Let $\delta \in [0,1)$ be a cut-off for points in the third group - for example $\delta = 0.1$ would mean that we would consider all points with loss in the range $[1-\delta, 1)$ to be in that group. Let the first group be $M$ (for SVs on the margin, these are unbound SVs having $0 \leq \alpha_i < C$, and the third group be $P_\delta$. Then we solve the following linear program to create a new solution defined as $w = \sum_i \beta_i y_i x_i$ by solving:

$$ \min_{i \in M \bigcup P_\delta} \sum |\beta_i| \\ \textrm{s.t.}\\ \forall j \in M: \sum \beta_i y_i y_j k(x_i,x_j) = 1 \\ \forall j \in P_\delta: \sum \beta_i y_i y_j k(x_i,x_j) > 0 $$ The number of additional misclassified points based on this approach will be quite small (and indeed may be negative as some previously misclassified points may now be correctly classified), while the solution will be significantly sparser.