2

I've seen answers discussing the complexity of training SVMs and neural nets, but how about for predicting new responses once a model has been trained?

For context, I'm working on an app that should produce predictions in near real-time given incoming pixel data and I'm looking for a machine learning algorithm that can handle complex separating planes and predict as fast as possible.

user1956609
  • 565
  • 2
  • 5
  • 8

2 Answers2

7

In order of increasing on-line complexity:

  1. Linear SVM has prediction complexity $O(d)$ with $d$ the number of input dimensions since it is just a single inner product.
  2. NN complexity is related to the architecture, but will surely be above that of linear SVM.
  3. Prediction complexity of kernel SVM depends on the choice of kernel and is typically proportional to the number of support vectors. For most kernels, including polynomial and RBF, this is $O(n_{SV} d)$ where $n_{SV}$ is the number of support vectors. An approximation exists for SVMs with an RBF kernel that reduces the complexity to $O(d^2)$. For computer vision applications, additive kernels are often used because they yield very fast prediction speed (independent of the number of SVs).

Since you are doing a computer vision application, I recommend using either the RBF approximation or additive kernels as they are very fast in evaluation and among the state-of-the-art in terms of accuracy. Neural networks that can rival the performance of SVMs using these kernels in CV applications are typically quite large, and thus slower.

Marc Claesen
  • 17,399
  • 1
  • 49
  • 70
  • Thanks. Two questions: (1) I'm thinking NN complexity is directly related to the number of (inputs*nodes)? So if we're using 1 hidden layer, going from 64 inputs to 16 hidden nodes to 1 output, I'd assume it's just (64x16 mults) + (64x16 sums) + (16 sigmoids) + (16 mults) + (16 sums) or O(d*hiddenNodes). (2) Is it common that $n_{sv} > d$ for SVM? – user1956609 Apr 21 '14 at 20:26
  • @user1956609 (1) that is correct, but often you require fairly large (or several) hidden layers in computer vision applications and (2) this depends on the hyperparameters but in practice this is quite common, particularly for low dimensional problems. – Marc Claesen Apr 21 '14 at 20:29
  • Don't use SVM's for computer vision. See my new answer. – pir Dec 14 '16 at 22:59
3

For any computer vision task a convolutional neural network (even a simple one) will beat any kind of SVM. This already happened in 2012 when a ConvNet cut the error rate of previous state of the art in half (see papers.nips.cc/paper/4824-imagenet-classification-w).

Furthermore, there's many efficient implementations of ConvNets. Perhaps github.com/soumith/convnet-benchmarks can serve as an overview. There's also lots of implementations focused on efficient usage on mobile phones.

pir
  • 4,626
  • 10
  • 38
  • 73