1
$\begingroup$

Training an SVM with an RBF kernel model with c = 5.5 and gamma = 1.06, for a 5-class classification problem on the NSL-KDD train data-set with 122 features using one vs rest strategy takes $2162$ seconds. Also, considering binary classification (c = 10, gamma = 4), it takes $520.56$ seconds.

After dimensionality reduction, from 122 to 30, using a sparse auto-encoder, the training time falls dramatically, from $2162$ to $240$ and $520$ to $170$, while using the same hyperparameters for the RBF-kernel.

What is the reason for that? Is it not true that using kernel neutralized the effect of high dimensions?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

SVM complexity is $O(\max(n,d)\min(n,d)^2)$ according to Chapelle, Olivier. "Training a support vector machine in the primal." Neural Computation 19.5 (2007): 1155-1178.

$n$ is the number of instances and $d$ is the number of dimensions. I'm assuming that you have more instances than dimensions giving a complexity of $O(nd^2)$. Hopefully this explains fully why reducing the number of dimensions will reduce the training time.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ thank you for your answer. but; is this true after using RBF kernel? because its map data form original feature space to an other space. The SVM used this space for training, which means its don't matter the dimension of original space. $\endgroup$
    – alighorbani
    Commented Oct 17, 2020 at 13:36
  • $\begingroup$ I do know that the RBF kernel does not scale well with training samples or input feature dimensions, so I would assume unfavourable complexity would still hold in terms of input dimensions. But that's about the extent of my knowledge sorry! $\endgroup$
    – Cameron Chandler
    Commented Oct 18, 2020 at 0:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .