-1
$\begingroup$

I would like to know what is the asymptotic time complexity analysis for general models of Back-propagation Neural Network, SVM and Maximum Entropy. Does it just depend on number of features included and training time complexity is the only stuff that really matters.

And does it real matter when applying on large chunk of text classification like twitter data or blog data

$\endgroup$
3
  • 2
    $\begingroup$ SVMs contain an underlying optimization step that is solved heuristically, so for any actual algorithm that purports to solve SVMs, the answer is undefined. A number like $O(n^3)$ is generally bandied around for implementations like libsvm, which means something like time/iteration * #iterations (where #iterations is assumed to be constant) $\endgroup$ Commented Aug 25, 2013 at 17:50
  • 1
    $\begingroup$ @SureshVenkat: That should be an answer, not a comment. $\endgroup$
    – Jeffε
    Commented Aug 31, 2013 at 18:14
  • $\begingroup$ @JɛffE it is done. $\endgroup$ Commented Sep 1, 2013 at 5:17

2 Answers 2

4
$\begingroup$

SVMs contain an underlying optimization step that is solved heuristically, so for any actual algorithm that purports to solve SVMs, the answer is undefined. A number like $O(n^3)$ is generally bandied around for implementations like libsvm, which means something like time/iteration * #iterations (where #iterations is assumed to be constant)

$\endgroup$
0
$\begingroup$

Relevance Vector Machines need a $O(n^3)$ time too, but the main overhead there is in the learning phase, it needs to repeatedly compute the inverse of a Hessian Matrix (that requires $O(n^3)$ computations.

Although tipping in his paper suggest a maximum of 5000 features vectors, I had a hard time to train a dataset of 2000 examples!

The k-nearest neighbor algorithm does not require any training time, and it can easily achieve near linear time complexity using approximation algorithms.

However, a preprocessing step is often useful and it also costs you $O(nd)$, specially if you want faster classification speeds. This is a good paper to read if you want to know more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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