On the Empirical Complexity of Text Classification Problems

In order to train a classifier that generalizes well, different learning problems, in particu-lar high-dimensional ones such as text classification, can require widely different amounts of training, as measured in terms of the number of training instances required to reach adequate accuracy or the number of features effectively utilized in the classifier. We define several mea-sures of learning difficulty and explore their utility in approximately capturing the inherent complexity of text classification problems. These measures can be efficiently computed for real-world problems for which linear classifiers are effective. We observe an intimate relation-ship (a high positive correlation) between feature complexity and instance complexity when using the measures. Such measures of difficulty are useful for comparing learning problems and corpora, and gaining insight into the variable success of methods such as active learning. In particular, we quantify the difficulty of 358 text classification problems and 9 corpora using the proposed measures, including those popularly used for benchmarking the performance of text classifica-tion algorithms, such as the Reuters and 20 Newsgroups corpora. We demonstrate the spectrum of problems that exist in text classification in addition to quantifying results that have only been qualitatively discussed in the text classification literature. We observe that many problems in the commonly used data sets are of low to medium complexity, that is, only roughly tens of well-selected features are required to gain most of the maximum attained performance on such concepts, when using linear classifiers. We find that learning for such types of problems espe-cially stands to benefit from incorporating feature feedback (prior knowledge on features) into active learning techniques. 1