Take the 2-minute tour ×

I've created an SVM in R using the kernlab package, however it's running incredibly slow (20,000 predictions takes ~45 seconds on win64 R distribution). CPU is running at 25% and RAM utilization is a mere 17% ... it's not a hardware bottleneck. Similar calculations using data mining algorithms in SQL Server analysis services run about 40x faster.

Through trial and error, we discovered that the laplacedot kernel gives us the best results by a wide margin. Rbfdot is about 15% less accurate, but twice as fast (but still too slow). The best performance is vanilladot. It runs more or less instantly but the accuracy is way too low to use.

We'd ideally like to use the laplacedot kernel but to do so we need a massive speedup. Does anyone have any ideas on how to do this?

Here is some profiling information I generated using rprof. It looks like most of the time is spent in low level math calls (the rest of the profile consists of similar data as rows 16-40). This should run very quickly but it looks like the code is just not optimized (and I don't know where to start).


Edit: Sample code to reproduce:

dummy.length = 20000;
source.data = as.matrix(cbind(sample(1:dummy.length)/1300, sample(1:dummy.length)/1900))
colnames(source.data) <- c("column1", "column2")
y.value = as.matrix((sample(1:dummy.length) + 9) / 923)

model <- ksvm(source.data[,], y.value, type="eps-svr", kernel="laplacedot",C=1, kpar=list(sigma=3));

The source data has 7 numeric columns (floating point) and 20,000 rows. This takes about 2-3 minutes to train. The next call generates the predictions and consistently takes 40 seconds to run:

predictions <- predict(model, source.data)

Edit 2: The Laplacedot kernel calculates the dot product of two vectors using the following formula. This corresponds rather closely with the profr output. Strangely, it appears that the negative symbol (just before the round function) consumes about 50% of the runtime.

return(exp(-sigma * sqrt(-(round(2 * crossprod(x, y) - crossprod(x,x) - crossprod(y,y), 9)))))

Edit 3: Added sample code to reproduce - this gives me about the same runtimes as my actual data.

share|improve this question
Note that if you have a 4-core machine, then 25% CPU would mean R is maxing out one core. It's single-threaded, so that's all it's designed to use. –  Hong Ooi Dec 8 '11 at 3:51
That's actually not what's happening. There is substantial activity on three cores on my local and 7 cores on our server. Not sure why the fourth core isn't doing much. I'm using Revolution R distro, btw. –  user1024824 Dec 8 '11 at 4:00
It would help if you provide a reproducible example that people can run on their own machines. –  Paul Hiemstra Dec 8 '11 at 9:53
Unfortunately, that would require me to give you top secret clearance to our database. Not going to happen ;-) But that's why I included the rprof results. –  user1024824 Dec 8 '11 at 13:46
My guess is that you haven't vectorized your code. The only way we can help is if you make a reproducible example. And no, that doesn't require access to your top secret database. Make up some sample data. –  Andrie Dec 8 '11 at 14:45
show 3 more comments

1 Answer

SVM itself is a very slow algorithm. The time complexity of SVM is O(n*n).

SMO (Sequence Minimum Optimization http://en.wikipedia.org/wiki/Sequential_minimal_optimization) is an algorithm for efficiently solving the optimization problem which arises during the training of support vector machines.

libsvm ( http://www.csie.ntu.edu.tw/~cjlin/libsvm/) and liblinear are two open source implementation.

share|improve this answer
add comment

Your Answer


