What is the best, worst, and average running time complexity of SVM and ANN?
Why most of machine learning papers report only the classification accuracy, and ignore the running time?
The complexity of training a SVM is discussed succintly in Section 4.2 of [1]. In particular, time complexity depends on both R^3 (where R is the number of free support vectors) and nS (where n is the number of training samples and S is the number of support vectors). Space complexity depends on how many training samples are stored at each iteration by your solver.
For running a SVM, space and time complexity are linear with respect to the number of support vectors.
Clearly, this discussion is independent of the computation of the kernel values which are assumed as given, and in some cases this can be the main bottleneck.
[1] Bottou, Léon, and Chih-Jen Lin. "Support vector machine solvers." Large scale kernel machines (2007): 301-320.
The complexity of training a SVM is discussed succintly in Section 4.2 of [1]. In particular, time complexity depends on both R^3 (where R is the number of free support vectors) and nS (where n is the number of training samples and S is the number of support vectors). Space complexity depends on how many training samples are stored at each iteration by your solver.
For running a SVM, space and time complexity are linear with respect to the number of support vectors.
Clearly, this discussion is independent of the computation of the kernel values which are assumed as given, and in some cases this can be the main bottleneck.
[1] Bottou, Léon, and Chih-Jen Lin. "Support vector machine solvers." Large scale kernel machines (2007): 301-320.
Training a SVM is a quadratic programming problem, how can it be NP-complete? It would be nice to see any publication claiming this.
"Olivier Chapelle" talks extensively about complexity of SVM in this paper. and find an optimization. He made an arugument that as "Support Vector Machines
(SVMs) first state the primal optimization problem, and then go directly to the
dual formulation" and one should solve either the primal or the dual optimization problem depending on whether n is larger or smaller than d, resulting in an O(max(n, d) min(n, d)^2) complexity. where
Given a matrix(dataset) X ∈ R^( n×d) representing the coordinates of n points in d dimensions
For details may refer to the paper please : http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/neco_%5b0%5d.pdf
About ANN: I am sorry, I didnt have enough knowledge.
- Badges
- Science topic