Suitable number of classes for SVM in text categorization

Question

I'm doing text categorization with R and SVM in the package e1071. I have around 30000 text files for training, and 10000 for test. The goal is to hierarchically categorize these files. For example, I have 13 categories in level 1, such as sports, literature, politics, etc, and in the second level, there are more than 300 categories. For instance, below sports category, there are sub-categories, like football, basketball, rugby, etc.

There are two strategies to reach the categorization in level 2. First is to classify the files in first level (13 categories), and then recursively, classify the files among its own subcategories. Second strategy is more direct, i.e. we assign different labels to all categories (more than 300) in level 2, then we train the model with SVM.

For the second strategy, although I have used SVD to doc-term matrix, reducing its dimension to 30,000 * 10. The svm function in package e1071 still breaks down, giving the error cannot allocate vector of size 12.4 Gb.

So I'd like to ask you gurus, whether the large number of categories is a real problem for SVM? Specifically, in my case, which strategy will produce better results and is more feasible in practical ?

Answer 1

Following answer is based on my own personal insights of doing text analysis.

Of course, an increase in the number of categories will increase the time significantly since you have bigger matrix dimensions and so on. But it's not necessary a bad approach. Moreover first strategy looks somehow strange to me since the result of guessing subgroup maybe interfered with bad result of guessing the group (some subcategories can be significally different from other categories or subcategories, but the whole can not). So I would probably go with the second strategy.

In second approach you will need quite much computational power. The error you're getting is that your RAM memory is full (also swap if you have one). There are couple basic suggestions concerning this problem.

1. Try to reduce your doc-term matrixes. That includes removing stopwords, punctuation, removing words that have no meaning whatsoever. This is very common procedure but sometime one can consider creating his own bigger filter.
2. Don't use whole amount of articles, instead use only the sample. Well, sampling is one of the most simplest procedures to reduce the amount of computing.
3. The most lazy solution, either get a pc with more operative memory or increase your swap memory and let computer do the rest.

These are more common approaches in your second case. I might would skip through the package called RTextTools that makes all of this work easier. Another insight would be using another approach rather than SVM. I'm not sure, but I think there are already implemented classification algorithms that implies that some of your categories have subcategories.

And as always don't forget to protect your progress when R crashes by saving workspace, .Rdata and then loading it. Also try to use R's garbage collector gc().

Answer 2

You might want to consider using LibLINEAR instead of (Lib)SVM. It is said to run faster than SVM for cases like document classification, though I'm not sure how it effects memory usage (see section 'When to use LIBLINEAR but not LIBSVM'). Here is the package for R.

Answer 3

I work as a project manager & software engineer at a small, research oriented software company. We have recently completed a text categorization project and made many experiments on the way.

We work with a Lineer SVM implementation I coded in C# based on Platt's "Sequential Minimal Optimization" Algorithm and later improvements for the linear case. The items are product definitions being sold on the internet. Our categories is a two level tree with about 15 first level nodes and 200 leaves. Here is a two sentence summary of what I have learned:

Success depends on the quality of the training set much more than the exact methodology. Although it is true that SVM performs somewhat better than Decision Trees, Nearest Neighboors and any other "simple" approach, selecting the kernel, optimizing the system parameters make little difference in terms of success rate.

Our experiments included the comparison of the two approaches you wrote about. Although my common sense still tells me that first approach should perform better, there was no statistically significant difference in terms of success rate in our experiments: very likely, when a product is classified, either both approaches classify it correctly, of neither.

For the RAM usage, I don't know about R to make concrete suggestions. However I can give some general advice, in case you have not already implemented these steps:

• Remove stop words
• Remove uncommon words (i.e. words that occur in less than say 10 documents)
• Format and Stem all the words so that COME, come, came, coming, etc. are mapped to the same term. (There are free libraries for this)

SVM needs much memory during training. Still, 24 Gb seems more than enough to me. (Again, I don't know anything about the R implementation) However here is an experiment you may perform, which if succeeds will make training much faster, and will consume much less resources:

If you have 300 categories, construct 300 different training sets and Support Vector Machines. For each category let your training set consist of 100 positive samples and say 400 randomly selected negative samples (find the optimum number by experimentation). You will have 300 different term-document matrices but each will be of much less size. When a document is to be classified, ask each SVM and return the category with the maximum value.