-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$
  • 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$ – Suresh Venkat Aug 25 '13 at 17:50
  • 1
    $\begingroup$ @SureshVenkat: That should be an answer, not a comment. $\endgroup$ – Jeffε Aug 31 '13 at 18:14
  • $\begingroup$ @JɛffE it is done. $\endgroup$ – Suresh Venkat Sep 1 '13 at 5:17
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)

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

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.