4
$\begingroup$

What is the impact of data dimensionality on computation complexity of SVM? I found on the literature that the complexity of SVM is $O(N^3)$, where $N$ is the number of training examples. If the number of dimension (e.g., $D$) does not impact the training time why it s better to reduce the dimensionality for training high-dimension dataset? Is it just to avoid overfitting?

BTW, I m using SVDD (support vector data description) from RRTools.

$\endgroup$
9
$\begingroup$

The O($N^3$) training complexity involves $n^2$ dot products and $n^3$ inverse of kernel matrix (A.Bordes et al Fast Kernel Classifiers with Online and Active Learning). However, it is also shown that the runtime of linear SVM optimization may decrease as the training size $N$ increases (Shai Shalev-Shwartz et al. SVM Optimization: Inverse Dependence on Training Set Size).

Mostly people view the training complexity independent of feature number, yet in SVM with RBF kernel, the training complexity is regarded as $O(dN^2)$ or $O(dN^3)$ ,where $d$ is the feature number (dimensionality)(Sreekanth Vempati et al.Generalized RBF feature maps for Efficient Detection).

While reducing the feature number might help in reducing the training complexity, the aim of feature selection is mainly to remove the additional features that may not help separate the classes in the feature space (sometimes may even at the risk of learning the noise in the data) (J. Weston et al Feature Selection for SVMs).

$\endgroup$
3
  • $\begingroup$ Thanks for your answer. So is that correct to say that RBF is the only kernel that its complexity is effected by the number of features (d)? $\endgroup$ Mar 6 '14 at 2:09
  • $\begingroup$ To my knowledge it may be the only kernel that is d dependent $\endgroup$
    – lennon310
    Mar 6 '14 at 2:19
  • $\begingroup$ @lennon310 Almost all kernels evaluations are dependent on $d$ since they typically involve an inner product. This is true for all common kernels (linear, polynomial, sigmoid, RBF). $\endgroup$ Apr 21 '14 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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