What is the minimum training set size required for a given number of features for document classification?

Question

For document classification problems, is there a rule of thumb for the number of training instances required for the number of terms in the vocabulary?

I am using a logistic regression classifier with TF-IDF weighted features. After stop-word filtering, stemming, and filtering by minimum and maximum document frequencies, I have a vocabulary of ~13,000 terms for a training set with ~20,000 documents. I have attempted using LDA for dimensionality reduction by adding topic probabilities as features, but this did not significantly affect performance. The performance of a classifier trained only on LDA topic probability features was inferior to the performance of the classifiers trained on TF-IDF features and TF-IDF+LDA topic probability features.

Answer 1

If you want to use something like plain (i.e., unregularized) logistic regression, then the argument cited by Jose stands: you need the ratio #features/#examples to be small.

However, you can do much better by using regularization. Popular forms of regularization include L1 (lasso) and L2 (ridge) regularization. If you regularize your features properly, you can get away with having many more features than training examples. In this paper, for example, using "dropout regularization" allowed us to train an efficient logistic regression model with 25k training examples and 5 million features.

Finally, if you have even fewer training examples (say, a few hundred examples and a million features), you may need to go even further and use generative models models like naive Bayes. As explained here, you may get away with having a number of training examples that grows logarithmically with the number of features.

Answer 2

Unfortunately, I do not know of such a rule of thumb. There is an interesting discussion on the topic in David D. Thesis (1992), in section 2.3.3. I cannot copy it here because the original thesis is in PS format and I cannot copy from the PDF I link, but here you got an screenshoot:

If you follow Fuhr, and given that your limit is the number of documents (20k - I guess 20 newsgroups or Reuters-21578 dataset), you should have an upper limit of 200-400 atributes.

I suggest an alternative way, that is making use of feature selection. You can either select a maximum number of attributes from those top scoring using a usual Information Theory quality metric like Information Gain or X-square. For instance, you can rank the words according to their Information Gain score and keep top 400 (or testing with different vocabulary sizes).

Alternatively, you can just keep those attributes (words) with an Information Gain score over 0.0 (meaning that they provide at least some predictive quality). You can use upper thresholds (0.1, etc.) to decrease the number of attributes.

In both cases, the optimal number of attributes can only be known through experimentation.