Random Forest vs Support Vector Machine. Which is faster?

Question

I am comparing the performance of Support Vector Machine with a radial basin function and Random Forests with 250 trees. I am using e1071 (SVM) and randomForest (RF) packages.

My dataset contains about 500,000 training samples. Although both methods obtain similar OA, the training time is very different for both.

In RF the training time is small, however in SVM the training time grows exponentially as the number of samples increases.

Is this a habitual behavior? Is it a characteristic of the SVM and RF algorithms or is it the e1071 implementation which is too slow? Is this relationship true in other implementations such as scikit-learn?

Answer 1

Recall how SVM works, it applies the kernel to each pair of the inputs, and this scales badly. SVM has time complexity of $O(dn^2)$ or $O(dn^3)$ for libsvm used by e1071.

Random forest uses independent decision trees. Fitting each tree is computationally cheap (that's one of the reasons we ensemble trees), it would be slower with larger number of trees, but they can be fitted in parallel. The time complexity is $O(n\log(n)dk)$.

SVM would scale worse than random forest and is generally not recommended for larger datasets.