What is the impact of number of training documents on classification time?

Question

Is there any impact of number of training documents on classification time ?? I know for K-nn that all of computations in K-nn is carried out in classification while no or minimum work is done in training. Is same is the case with SVM, Naive Bayes, Decision Trees etc ?

Answer 1

Only lazy classifiers have such a characteristics, one of which is KNN.

• SVM - classification time depends on the number of support vectors, which may, but not have to be - dependent on the number of training documents (they are the upper bound of the number of SVs)
• Naive Bayes - there is no impact, unless these new documents carry many new words, as the NB classification time is O( number of features ), so if you do not enlarge the vocablurary (in case of BOW model) you are safe to use many training data
• Decision Tree - the same as for NB, it depends only on the number of features (and the complexity of the problem, which do not change with number of instances)
• Neural Network - here classification time only depends on the number of neurons