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?


3 Answers 3


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.


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.

  • $\begingroup$ I would have thought that we forget about support vectors during predict no? Even if I trained with 1 bajillion samples, all we have in the end is a hyperplane and instructions for how to get from my input space to the space of that hyperplane. Am I missing something? $\endgroup$ Commented Nov 13, 2020 at 13:12
  • 3
    $\begingroup$ @AlexanderSoare the kernel space is implicitly given in terms of the cross-product with the support vectors (the RBF space is infinite dimensional). $\endgroup$
    – Firebug
    Commented Nov 13, 2020 at 14:13

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.

  • $\begingroup$ Thanks so much for this. I will find time to study it. One thing that might influence your answer though, is that I don't actually use 768x768 pixels to train the model (your first sentence says something about 5% --> 29K support vectors). My procedure is as follows: 1) show images, 2) ask users to click positive regions randomly about 100 times, 3) ask users to click negative regions randomly about 100 times, 4) train svm on that data. $\endgroup$ Commented Nov 15, 2020 at 11:23
  • $\begingroup$ Oh you are correct - the previous answer threw me off - in this case though you're right in terms of RBF evaluation time also influencing things. Let me add another answer for that $\endgroup$
    – MotiNK
    Commented Nov 15, 2020 at 11:43
  • $\begingroup$ Right, well that gives me another thing to look at. I think a moderator is asking you to put your answer in an edit. Once that's done I'll come back and accept. Thanks! $\endgroup$ Commented Nov 15, 2020 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.